Блог пользователя AlimA

TLE in "Numbers"
Автор AlimA, 12 лет назад, По-английски

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 :)

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    So can you give me some hints?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

      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).

      → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      You can visit editorial to see solution

      → Ответить