Color The Fence codeforces - TLE I am trying to solve this problem:


  Igor has fallen in love with Tanya. Now Igor wants to show his
  feelings and write a number on the fence opposite to Tanya's house.
  Igor thinks that the larger the number is, the more chance to win
  Tanya's heart he has.
  
  Unfortunately, Igor could only get v liters of paint. He did the math
  and concluded that digit d requires \$a_d\$ liters of paint. Besides, Igor
  heard that Tanya doesn't like zeroes. That's why Igor won't use them
  in his number.
  
  Help Igor find the maximum number he can write on the fence.
  
  Input The first line contains a positive integer v (0 ≤ v ≤ \$10^6\$). The
  second line contains nine positive integers \$a_1\$, \$a_2\$, ..., \$a_9\$
  (1 ≤ \$a_i\$ ≤ \$10^5\$).
  
  Output Print the maximum number Igor can write on the fence. If he has
  too little paint for any digit (so, he cannot write anything), print
  -1.


https://codeforces.com/problemset/problem/349/B

My solution that works correctly, but times out:

from collections import defaultdict

v = int(input())
a = [int(i) for i in input().split()]
cache = {}


def dfs(v):
    if v in cache:
        return cache[v]
    res = 0
    for i, num in enumerate(a):
        if num == v:
            res = max(res, i+1)
        if num &lt; v:
            x = dfs(v-num)
            if x &gt; 0:
                s = str(i+1) + str(x)
            else:
                s = str(i+1)
            sorted_nums = sorted([str(i) for i in s], reverse=True)
            l = int("".join(sorted_nums))
            res = max(res, l)
    cache[v] = res
    return res


ans = dfs(v)
if ans == 0:
    print(-1)
else:
    print(ans)



How do I optimize it in terms of time complexity?
There is no need to comment your code. It is totally broken. Very first thing you need to do is to calculate your complexity. ACM is not about code quality, it is not about language. It is about algorithms. You can write the ugliest code ever but can it be executed? Not a problem if you have satisfying algorithm complexity.

You can not just write different code without thinking about the algorithm and how your changes influence complexity. Moreover, you have to write code that will follow your algorithm.

General strategies for optimizing code for programming challenges? What? If there where such strategies no one would be challenging anymore. That is why it is so difficult and those competitions exist even now.

There are classes of problems that can be solved effectively with specific algorithm\approach. Competition task itself never describes what class or problems it is and what algorithm to use, you have to find it out by yourself. Determine the class of the problem you are trying to solve and then choose an algorithm that will satisfy the problem's memory/time requirements.

First of all. The problem you are trying to solve can be recognized as "implementation" when it didn't relate to any specific class directly. You have to do what it says. Implementation class requires you to be flexible minded, especially in this case because you have time requirements that brute-force didn't meet. 

Algorithm

We have a set of digits with their costs. How to construct the largest possible number from it? We have to research the relation between numbers order and digits they have.

$$ 
A &gt; B =
\begin{cases}
  true  &amp; \text{if } dc(A) &gt; dc(B) &amp; \text{(1)}
  \\
  true  &amp; \text{if } dc(A) = dc(B) \text{ and } \\
        &amp; \text{if } h(A) &gt; h(B) \text{ or } h(A) = h(B) \text{ and } t(A) &gt; t(B) &amp; \text{(2)}
  \\
  false &amp; \text{else}
\end{cases}
$$

, where 
\$ X = \left( x_1, x_2, \dots, x_n \right) \$ - number or vector of \$ n \$ digits  
\$ dc(X) = |X| = n \$ - is number of digits in number (digits count) 
\$ h(X) = x_1 \$ - returns digit of the highest order (head), e.g. \$ h(123) = 1 \$ 
\$ t(X) = X' = \left( x_2, \dots, x_n \right) \$ - returns number without the highest order digit (tail), e.g. \$ t(123) = 23 \$

Let's look at those rules and figure out rules that will give us the biggest possible number using the given set of digits.

\$ \text{(1)} \$ consequence: more digits you have - better.  That means we have to be greedy and take as much as possible digits with the lowest price.

\$ \text{(2)} \$ consequence: is it obvious that some times we will have enough amount of paint to replace digit with the bigger one but not enough to add another one. Now we know that we have to replace digits starting from the number's head.

Now let's take a look at how much digits we will have in the worst case. It is around \$ 10^6 \$. 

With such a number of characters to output, we can not output by a single character at a time because input\output operations took too much time. I hope there is no need to prove that IO takes a long time.

Let's consider using python's big numbers. We will not look at their implementation, just pretend that we have \$ 10^6 \$ digits to write and we know exactly what is it.

start = time.time()
num = 1;
for _ in range(10**5):
    num = num * 10 + 1
finish = time.time()
print (finish - start)


Takes 4 seconds to complete and it is still \$ 10^5 \$. No, we can not use python's big integers.

We can not build a string because it is an immutable object and we will copy it every time on change, same as with big integers.

More or less acceptable will be to make a list with the required amount of digits in it and then use str.join(). Let's stick with this approach for a while and continue research.

So, first, we will find the highest digit with the lowest price \$ d \$, determine the length of the resulting number \$ n = \lfloor \frac{v}{\text{lowest cost}} \rfloor \$ and make a resulting list of \$ d \$ repeated \$ n \$ times.

Now, while we have some paint to spare, we will loop through digits from the highest to lowest and try to replace as many head digits as possible.

But yeah, now when we spell it, you can see that you do not actually need that list at all. You need to know how much digits to write and who it will be starting from the head of the result.

One can say: "hey, this is greedy problem class, not implementation" - yeah we are all smart now.

Implementation

Here is my implementation of described algorithm:

from copy import deepcopy


class Digit(object):
    def __init__(self, _cost, _value):
        self.cost = _cost
        self.value = _value


def main():
    v = int(input())
    a = list(map(int, input().split()))
    a = tuple(Digit(cost, digit+1) for digit, cost in enumerate(a))
    low_digit = deepcopy(min(a, key=lambda digit: digit.cost*10 - digit.value))

    if low_digit.cost &gt; v:
        print(-1)
        return

    digits = v // low_digit.cost
    v -= digits * low_digit.cost
    for i in range(9):
        a[i].cost -= low_digit.cost
    low_digit.cost = 0

    for better in reversed(a):
        if better.cost &gt; 0 and better.value &gt; low_digit.value:
            count = v // better.cost
            v -= count * better.cost
            digits -= count
            print(str(better.value) * count, end='')
    print(str(low_digit.value) * digits)


if __name__ == "__main__":
    main()