I submitted a Python solution for Codeforces Round #627 (Div. 3) F. I got Runtime Error on test 36. I thought the problem was stack overflow due to recursion limit. So I increased the limit. But that still gives me the same error.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 21:12:49 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
The following is a slight update to your code that was accepted, but it is written in C++. 73182681
Hope this helps you in fixing your Python solution.
Sorry, but I cannot find out what you have changed.
How about catching the exception and printing to console?
How? I put everything in a try block and tried to print the Exception, but it didnt print it.
https://codeforces.net/contest/1324/submission/73183628
The best I could do was to make the RTE become WA. But the WA output looks strange though. I think the next best thing would be to generate large random test to stress test your solution.
His code gets AC if you just get around Python's horrible built in recursion 73202667.
Shall I use this decorator whenever I want to do recursion with python?
You could, but it is kinda slow. Better (if you want to continue using Python) is probably to learn how to write recursion iteratively. Or just switch to C++.
Can you send some good link on how to write recursion iteratively?
Messing around with deep recursion in Python means opening a can of worms. The underlying issue is that recursion in Python by design uses a huge amount of memory.
In PyPy depending on what you set the recursion limit to PyPy tries to estimate how much memory it needs to allocate for its internal stack. Problem this time is that its estimate was too low, which is why you got RTE. You could in theory fix this by setting the recursionlimit higher but for this problem setting the limit higher causes MLE.
So how do you do deep recursion in Python without using a ton of memory? One way is to write everything iteratively using your own stack (which is what I usually do). Another way you could do it is to use this decorator I wrote a while back. The decorator abuses coroutines in Python to do recursion without actually doing recursion, see 73202667 (AC).