Training Section 3.1 Stamps

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

TASK: stamps
with open('') 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:
    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?

his solution is dp

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

sorry lol im dumb

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

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
TASK: stamps
#include <iostream>
#include <fstream>
using namespace std;
#define MAXM 10000000

int main()
    ifstream fin("");
    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.

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.