2
\$\begingroup\$

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 < v:
            x = dfs(v-num)
            if x > 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?

\$\endgroup\$
  • \$\begingroup\$ Use maximum possible number of digits first (lowest price) then improve it as much as possible starting from highest order. It is O(n) no recursion, no DP. \$\endgroup\$ – outoftime Oct 19 at 22:03
  • \$\begingroup\$ Largest time I have for my solution is 62ms. \$\endgroup\$ – outoftime Oct 19 at 23:57
2
\$\begingroup\$

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 > B = \begin{cases} true & \text{if } dc(A) > dc(B) & \text{(1)} \\ true & \text{if } dc(A) = dc(B) \text{ and } \\ & \text{if } h(A) > h(B) \text{ or } h(A) = h(B) \text{ and } t(A) > t(B) & \text{(2)} \\ false & \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 > 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 > 0 and better.value > 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()
\$\endgroup\$
1
\$\begingroup\$

General strategy for optimizations on programming challenges

To optimize your code, you need to be able to perform some measure on different inputs and you want to make sure your optimization does not break anything.

You usually want both things to be performed easily - automatically and instantly if possible. This is usually possible with simple tests. For programming challenges, this is even simpler because they usually correspond to task with a well defined input and a well defined output and on top of that, examples may be provided.

Thus, this leads to the general rule of thumb about desirable properties of your code:

  • you want your code to be testable then

  • you want your code to be tested (with potentially failing tests) then

  • you want your code to be correct (all tests pass)

  • you want your code to be fast

Applying this to your code:

  • define dfs as a function taking both inputs a and v as parameters
  • write a function to test dfs using input/output like you did but also a function with automated tests based on the provided example
  • rename dfs for something conveying the name of the problem solved without giving the implementation details
  • see that having a cache breaks leads to wrong behavior when we want to call dfs with different inputs -> we can remove it for the time being
  • we can see that the import is useless

At this point, we have:

def max_nb_painted(v, a):
    """Return the the maximum number Igor can write on the fence (or -1 if he has too little paint for any digit)"""
    res = 0
    for i, num in enumerate(a):
        if num == v:
            res = max(res, i+1)
        if num < v:
            x = max_nb_painted(v-num, a)
            if x > 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)
    return -1 if res == 0 else res

def test_max_nb_painted_io():
    """Test based on std input/ouput."""
    v = int(input())
    a = [int(i) for i in input().split()]
    print(max_nb_painted(v, a))

def test_max_nb_painted_auto():
    """Automated tests."""
    # Note: you could use a proper unit-tests framework for this
    print(max_nb_painted(5, [5, 4, 3, 2, 1, 2, 3, 4, 5]) == 55555)
    print(max_nb_painted(2, [9, 11, 1, 12, 5, 8, 9, 10, 6]) == 33)
    print(max_nb_painted(0, [1, 1, 1, 1, 1, 1, 1, 1, 1]) == -1)

test_max_nb_painted_auto()

More tests

The provided tests only cover the case where the painted number contain a unique digit. Let's try to add other tests:

    assert max_nb_painted(1, [1, 1, 1, 1, 1, 1, 1, 1, 1]) == 9
    assert max_nb_painted(1, [1, 1, 1, 1, 1, 1, 1, 1, 1]) == 9
    assert max_nb_painted(5, [2, 2, 2, 2, 2, 2, 2, 2, 3]) == 98
    assert max_nb_painted(50, [9, 10, 11, 12, 13, 14, 15, 16, 17]) == 61111
    assert max_nb_painted(70, [19, 20, 21, 22, 23, 24, 25, 26, 27]) == 961

Also, we can add tests with returned value as big as we want which can be useful for benchmark purposes:

    n = 6  # Length of expected return value
    c = 1  # Cost per digit
    assert max_nb_painted(n * c, [c] * 9) == int(str(9) * n)

A different algorithm

Instead of using dfs blingly, we can try to solve the issue manually and see how we'd do it.

We can easily compute the length of the returned value based on the minimal cost in a.

Also, if we want to improve the corresponding value, we'd do it from the left hand side.

def max_nb_painted(v, a):
    # Evaluate maximum length based on digit with minimal cost
    min_cost = min(a)
    max_len = v // min_cost
    if max_len == 0:
        return -1
    # The base would be to use only that digit
    # But we try to use bigger digits (from the left)
    min_dig = a.index(min_cost) + 1
    rem_v = v - max_len * min_cost
    n = 0
    for i in range(max_len):
        n = 10 * n + min_dig
        for digit, cost in reversed(list(enumerate(a, start=1))):
            if digit >= min_dig:
                if cost - min_cost <= rem_v:
                    n += digit - min_dig
                    rem_v += min_cost - cost
                    break
    return n

This can be significatively improved. For instance, we could precompute the digits that may be useful in order not to iterate over the whole list:

    relevant_digits = list(reversed([(digit, cost) for digit, cost in enumerate(a, start=1) if digit > min_dig and cost - min_cost <= rem_v]))
    for i in range(max_len):
        n = 10 * n + min_dig
        for digit, cost in relevant_digits:
            if cost - min_cost <= rem_v:
                n += digit - min_dig
                rem_v += min_cost - cost
                break
    return n

Conclusion

Despite multiple attempts, I did not reach anything better than "Time limit exceeded on test 25".

I do not have any ideas left except maybe trying to be starter when picking min_dig (by starting from the right) or pruning the list of relevant digits when we update rem_v.

My best try is:

def max_nb_painted(v, a):
    # Evaluate maximum length based on digit with minimal cost
    min_cost = min(a)
    max_len = v // min_cost
    if max_len == 0:
        return -1
    # The base would be to use only that digit
    # But we try to use bigger digits (from the left)
    v -= max_len * min_cost
    relevant_digits = []
    for digit, cost in reversed(list(enumerate(a, start=1))):
        delta_cost = cost - min_cost
        if delta_cost <= v:
            if delta_cost == 0:
                min_dig = digit
                break
            relevant_digits.append((digit, delta_cost))
    n = 0
    for i in range(max_len):
        n *= 10
        for digit, delta_cost in relevant_digits:
            if delta_cost <= v:
                n += digit
                v -= delta_cost
                relevant_digits = [(digit, delta_cost) for digit, delta_cost in relevant_digits if delta_cost <= v]
                break
        else:
            n += min_dig 
    return n

but it is not good enough :(

\$\endgroup\$
  • \$\begingroup\$ Have you even tried you solution on codeforces? Do you imagine how long dealing with big numers will take? Have you any idea what complexity you have? \$\endgroup\$ – outoftime Oct 20 at 6:14
  • \$\begingroup\$ @outoftime Thanks for the suggestion. Initially I did want to bother registering to codeforces but I should have. \$\endgroup\$ – SylvainD Oct 20 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.