2024.06.16 APCS Taiwan Examination
What a wobbly week filled with enthusiasm and timorousness. I guess this is how you feel when you are still waiting for the result after finishing an exam. Am I cooked? Or am I cooking? It's the 2024/06/16 Taiwan APCS examination. Let’s just dive right into the conclusion first, I got 320/400 on the practical problem examination. Below are my thoughts on the problems.
First up we got problem 1. Well, there’s really nothing much to say about it since problem 1 is typically an easy implementation problem, and the writer didn’t make the constraints too large in a way that your code will get TLE if it contains a few nested loops.
Second of all, problem 2 is relatively easier this time compared to some of the others that were tested before. The first thing that came to my mind was brute force from the given point in each update with a lot of loops and if/else statements. But the funny thing is, the problem statement tells exactly what you should do (it says only render cells that have distance less than or equal to t). This way it becomes way simpler. The entire examination was two and a half hours, I finished the first two problems within the first 20 - 30 minutes (I was smiling before reading problem 3 & 4).
Next up is problem 3. When I first saw this problem I was like “Oh no no no, yet another problem dealing with strings.” After I finished reading it, I jumped right to reading problem 4. Let’s come back and talk about it later.
While reading problem 4, I knew this has to be something to do with the prefix sum. But the statement “the number of odd and even integers should be the same” just knocks me over my head. I noticed that this problem stated that “the difference between the number of odd and even integers at any time is ≤ 2000.” This is actually an implicit hint that the solution should be something dealing with the difference. After I vaguely figured out the solution idea, it was time to code! Okay, the process of debugging took me a long time, but I still did it anyway because I knew my solution was “potentially” correct. There was only around 30 minutes left after I got the sample and some other hand-written test cases correct. Now, it’s time to move back to problem 3.
For problem 3, since K and L are really small in values, this must be a brute force problem plus some optimization (constraints also stated that K^L ≤ 10^5). Now I just need to figure out how to know if the string formed is a substring of S within logN or smaller. Due to the time limit (there was around 15 minutes left), I knew that some points are better than no point, therefore I just coded out a O(K^L * N) solution, which eventually resulted in a partial credit of 20/100 points. It turns out that the searching algorithm / optimization was binary search (perhaps my brain was not “braining” after doing problem 4).
Overall, I really enjoyed this examination and it’s a nice experience, meeting a bunch of top coders in Taiwan and realizing that I still need a fair amount of practices to get to the next level. Never stop learning!
Definitely check out the practical problem editorial I wrote!
