Training Section 3.1 Stamps

Problems and Contests
#1

Here is my python 3 code for the USACO Training Section 3.1 problem stamps:

"""
ID:
LANG: PYTHON3
TASK: stamps
"""
with open('stamps.in') as f:
    K, _ = map(int, f.readline().strip().split())
    stamps = [int(num) for st in f.readlines() for num in st.strip().split()]
    dp = [0]
    num = 1

while True:
    mi = float('Inf')
    
    for stamp in stamps:
        if num >= stamp:
            mi = min(mi, dp[num - stamp] + 1)

    if mi > K:
        break
    
    dp.append(mi)
    num += 1

with open('stamps.out', 'w') as f:
    f.write(f'{num - 1}\n')

However, it TLEs on the test cases. How can I make this code run faster?

#3

his solution is dp

#4

The time complexity of your solution seems correct. Try optimizing some constant factors? Maybe it’s just python being slow?

#5

sorry lol im dumb

#6

Yeah, I remember trying this problem myself and Python TLEing on some test cases.

#7

Hmm… I checked the LickIt GitHub and they also had tle’d on this problem with python 3. So, they had written their solution in c++. I copy pasted the solution and it ran like a breeze. Can someone confirm that my method is the same as their c++ solution?

/*
ID: solasky1
LANG: C++
TASK: stamps
*/
#include <iostream>
#include <fstream>
using namespace std;
#define MAXM 10000000

int main()
{
    ifstream fin("stamps.in");
    ofstream fout("stamps.out");

    int K, N;
    fin >> K >> N;

    int *stamps = new int[N];
    for (int i = 0; i < N; i++)
        fin >> stamps[i];

    unsigned char *s = new unsigned char[MAXM];
    s[0] = 0;
    int m = 0, min;

    while (s[m++] <= K)
    {
        min = MAXM;
        for (int i = 0; i < N; i++)
            if (m >= stamps[i] && s[m - stamps[i]] < min)
                min = s[m - stamps[i]];

        s[m] = min + 1;
    }

    fout << (m - 2) << "\n";
    return 0;
}

On a side note, should I quit Python by now? I’ve heard that practically nobody uses Python 3 seriously for gold, which chapter 3 is (advanced silver / gold). I’m not sure if I’ll aim for gold yet (I was in elementary school last year). If I learn another language, I’ll likely use Java since that’s what my school is using for all the classes.

#8

If you want to consistently get AC, I suggest that you switch to a compiled language, yes. Python should still work for most Bronze/Silver problems, though.