Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

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

Have you encountered this before ?
Автор rmz, история, 8 месяцев назад, По-английски

In this problem I made a dp solution that gets MLE.

Then i added this piece of code.

    for (int i = 1 ; i < n ; i++){
        depee(i,0);
    }

Surprisingly, it worked and i got AC.

can you explain what happened?

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
The Nice lines of the code
→ Ответить
»
8 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

I think your recursion calls itself too much if you do it all in one go -depee(10000000) would call depee(9999999) which calls depee(9999998) ... depee(0), and the program consumes alot of memory to keep track of all this recursion. Your second submission avoids this issue. When depee(n) is called, it calls depee(n-1) which was previously solved, and thus fewer recursive calls need to be kept track of at a time.

→ Ответить