MusselPie's blog

By MusselPie, history, 6 years ago, In English

Hello Codeforces!

Today I participated in CodeCraft-21 and Codeforces Round 711 (Div. 2). I solved the first few problems relatively quickly and then got the idea for the subject of this blog, Problem D (1498D - Бананы в микроволновке), a fairly simple solution based on BFS.

After coding my solution I submitted it, but I was unfortunately greeted by an unfavorable verdict: Time limit exceeded on pretest 8. No problem, I thought, and got to work on speeding up some parts of my solution. Time limit exceeded on pretest 8 again. At this point, I was desperate and started trying all sorts of stuff to speed my program up, to no avail. The wrong submissions piled up and pretest 8 still stood strong.

I don't remember what I tried next, but it somehow worked, and I excitedly saw my submission make it past pretest 8... only to get Time Limit Exceeded again, on pretest 15. Ugh. In my desperation, and seeing how the contest was almost over, I decided to submit my solution again, but with the incredible optimization of ignoring all subsequent steps after I computed all the answers. Miraculously this worked, and I passed protests with a time insanely close to the time limit. I was scared of system tests, but I couldn't come up with anything else, so I prayed. Luckily this actually worked, and I passed with only 5ms to spare! (Shoutouts to PyRival and its authors, since I definitely wouldn't have passed without their very useful Python templates)

However, I wasn't quite satisfied, since this solution is incredibly close to the time limit and it can probably be made to fail with adversarial test data. So after the contest, I looked at the Python solution given in the editorial and tried to take some tricks from it. This had some effect and I managed to make my runtime a bit faster, but it was still quite tight. After a bunch of fiddling, I tried submitting the editorial solution to have something to benchmark against, and to my surprise, it was also really close to the time limit! (111408363, passes with 2870/3000ms)

So that takes us to this blog, where I'm out of ideas and asking for help. Here is my AC submission in-contest (111402095). Can someone familiar with python point out what is particularly slow about it? Is Python just cursed to be slow always? I'd greatly appreciate any inputs.

  • Vote: I like it
  • 0
  • Vote: I do not like it