AlimA's blog

TLE in "Numbers"
By AlimA, 12 years ago, In English

Hi all

My code for the problem Numbers has got TLE. I think my code should be fast enough but... . Can anyone find my mistake or give some hints to me? I don't wanna look at the tutorial. :)

Thx all :)

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

It's because your program is slow. It seems that your program makes all possible numbers and count it, but this is too slow to solve this problem.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    So can you give me some hints?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +7 Vote: I do not like it

      use DP. I will describe you not the most effective way, but it runs in polynomial time. lets iterate over all possible final lengths for (finalLen = a[0] + ... + a[9]; finalLen <= n; ++finalLen). inside the loop we have to solve more simple problem, because we know final length. to solve this subproblem we can use dp d[digitsUsed][i] — in how many ways we can place digits (0, 1, ..., i) using totally exactly digitsUsed digits. The rest (finalLen — digitsUsed) digits would be digits (i + 1, i + 2, ..., 9).

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      You can visit editorial to see solution

      → Reply