Sep 2012
1 / 5
Sep 2012
Oct 2015
erixonar
Sep '12

Trying to solve piggy_bank and similar DP problems using Python3 and keep getting TLE.
Checked google for best algorithm and it seems the same as mine.

Note: got TLE even when read entire input with sys.stdin.read()

import sys
infinity = 9999999
def generate1(w):
    return [0]+[infinity]*w
count = int(sys.stdin.readline())
for rnd in range(count):
    e1,e2 = sys.stdin.readline().split(" ")
    total_w = int(e2)-int(e1)
    list1 = generate1(total_w)
    rang = int(sys.stdin.readline())
    s2 = [[int(i) for i in sys.stdin.readline().split(" ")] for rnd1 in range(rang)]
    s2.sort(key=lambda x: x[1])
    for j in range(0,total_w):
    if list1[j]==infinity:
        continue
    for v,w in s2:
        if w+j > total_w:
            break
        else:
            list1[j+w]=min(list1[j+w],list1[j]+v)
if list1[-1]==infinity:
    print("This is impossible.")
else:
    print("The minimum amount of money in the piggy-bank is %d." % list1[-1])

  • created

    Sep '12

  • last reply

    Oct '15
  • 4

    replies

  • 882

    views

  • 3

    users

numerix
Sep '12

What do you think is the reason that there is not a single Python 3 solution among the more than 2700 AC solutions?
If you look at the mem usage, you will detect that all those (few) Python AC submissions use psyco.
So the answer to your question is simple: Python 3 is too slow.

erixonar
Sep '12

Ty for help Numerix.
That problem really got me frustrated..

So, overall, DP problems should't be tackled in python3 i guess.

3 years later
carofe82
Oct '15
1

Same here. I think the time limit of that problem needs to be adjusted. My solution for the limit case runs in 0.8s:

start_time = time()
print(get_worst_case(9999,[(randrange(1,50000),randrange(1,10000)) for _ in range(500)]))
print(time()-start_time)

My Solution

def get_worst_case(weight, avail_coins):
    '''
    get worst case scenario for the pigbank
    :param weight: total weight to match
    :param avail_coins: list of tuple [(coin value, coin weight)]
    :return: worst case value
    '''

    max_value = max(map(lambda c: c[0], avail_coins))
    impossible = 1+max_value*weight

    partial = [0 for _ in range(weight+1)]
    for p_w in range(1,len(partial)):
        min_value = impossible
        for c_v,c_w in avail_coins:
            if p_w - c_w >= 0:
                p_v_with_c = partial[p_w - c_w] + c_v
                if p_v_with_c < min_value:
                    min_value = p_v_with_c
        partial[p_w] = min_value
    return partial[-1] if partial[-1] != impossible else None


cases = int(input())

for c in range(cases):
    ef = input().split(" ")
    e = int(ef[0])
    f = int(ef[1])
    weight = f-e
    num_coins = int(input())
    avail_coins = []
    for coin in range(num_coins):
        pw = input().split(" ")
        avail_coins.append((int(pw[0]),int(pw[1])))
    worst_value = get_worst_case(weight,avail_coins)
    if worst_value == None:
        print("This is impossible.")
    else:
        print("The minimum amount of money in the piggy-bank is "+str(worst_value)+"."
carofe82
Oct '15

I was able to get it AC with PyPy (after changing input() with raw_input())