Unfortunately, due to certain circumstances, this will be the last blog of this year.
Basically I decided that I should actually be productive during the christmas break. I also virtualed a USACO plat contest, paken 2023 day 1, paken 2023 day 3, and JOI 2023 but I’m kinda too lazy to write so many blogs.
Day 1
Virtual
spoiler
After reading all the problems, pA felt kind of dp-ish, pB’s probably some weird geometry stuff which I’m really bad at, and pC was probably also some kind of dp + perhaps BIT, but I could only think of the O(N^2) sol atp.
Estimated difficulty: C < A << B, so I tried to solve C first.
In problem C I kept aiming for some O(NlogN) solution but then after a few minutes I finally figured out the O(NsqrtN) solution.
0:35 C 58
Passing all subtasks except for the O(N^2) one was very absurd, so I wondered whether it was a modulo issue
0:37 C 100
That was nice.
Before dumping a potential 4 hours into problem A, I thought I shouldn’t make the same mistake as TOI 2024 (only aiming for full scores instead of subtasks, which only gave me a score of 200/500 in the end)
Therefore, I looked at subtask 1 in pB and guessed that the answer was the rectangle area minus 1
0:49 B 0
whoops, maybe that guess was wrong then
I then drew a few cases by hand and found out that I overthought and the answer was actually -1
0:53 B 1
At least I passed the subtask, although 1 point isn’t really any better than 0
Then after drawing a few more cases I made an “educated guess” (without proof because I’m bad at geo / linear alg / whatever) that the answer for subtask 3 is (gcd of differences in x) times (gcd of differnces in y).
1:04 B 10
Oh wait there isn’t 自動聯集 ??? (automated subtask union or whatever that’s called in english, honestly i don’t know)
1:05 B 11
Well, I tried my best, at least I probably wouldn’t regret not spending more time on this problem afterwards, so I started thinking about pA.
I mindsolved subtask 1, and subtasks 2 and 3 could be done with some priority_queue. I decided to implement subtasks 2 and 3 first.
2:14 A 0
Just some kind of out-of-bounds error
2:21 A 29
I then went back to implement subtask 1
2:25 B 40
Currently my score is 40 / 11 / 100
Despite how I said “I spent enough time on pB”, I still felt that 11 points was way too low, so I threw pA aside temporarily (which turned out to be a very good decision)
After drawing out a few more cases, I guessed again that the answer for subtask 2 was (the triangle area formed by the three points) * 2
2:49 B 11
I forgot that when the triangle area is 0 I’m supposed to output -1
2:55 B 21
I then went on guessing that by combining subtasks 2 and 3, the answer is 2 * (gcd of all triangle areas). I tried proving it, but failed miserably
3:01 B 50
How were almost all my guesses correct? I then decided to use some randomization to pass subtask 5 (because I forgot that I could actually fix one point in the triangle)
3:07 B 65
This gave me some hope and I tried using some better (?) randomizations, trying to obtain the full score and failed (I thought the official solution would involve randomization smh)
65 was probably decent enough anyway, so I decided to spend the rest of the time on pA. I came up with the solution for subtask 4 but there was like 998244353 bugs in my code.
4:34 A 69
And I spent the remainder of the time doing essentially nothing.
Reflection
spoiler
Final score: 69 / 65 / 100
Total: 234
Day 1 rank 5
This is much higher than what I should’ve gotten, at least my score would’ve been 170 without guessing
Also less people solved pA than I originally thought, and scores generally aren’t that high on pB. I guess I should improve my math though, otherwise my score would probably have been pretty low.
Also I should be better at implementation 💀 I wasted a lot of time on debugging, especially pA (I didn’t include all my submission scores since then the blog would be even longer)
Day 2
After Day 1 I actually gained a bit of confidence in my poor OI ability, maybe perhaps too much
Virtual
spoiler
The entire problemset just felt harder than day 1 for some reason (although it turned out that a great amount of people performed better on day 2 than day 1) The only thing I could think of was the O(N^2) solution for pA (40 pts). The implementation for pB seemed cancerous, and I didn’t have any idea for pC.
I made a few WA submissions
0:50 A 40
Then it turned out that subtask 4 wasn’t that hard
0:53 A 53
I was really afraid that I would end up with a sub-100 score, so I still decided to move on and try pB. Subtask 1 (4 pts) was just a rectangle, but I read the problem incorrectly and originally thought the problem was asking for the number of squares one can put in the rectangle.
1:14 B 4
Subtask 2 seemed like a lot of casework but I decided to try it anyway. Wasted like an hour and got 0 points so I moved on.
For pC, subtask 1 was just enumeration, and later came up with the solution for subtask 5
2:29 C 20
Then I went back to problem B subtask 2 since I thought nothing could’ve gone wrong. I couldn’t figure out anything until at the three hour mark when I found that I actually MISREAD THE PROBLEM 😭
3:05 B 13
My current score is 53 + 13 + 20 = 86. I might actually get a sub-100 score if things continue like this. At the same time (3 hours), my day 1 score was above 200, which is very depressing
At least I was sure I finally understood the problem correctly, and found out that subtask 3 was actually quite similar to subtask 2.
3:20 B 24
I then spent some more time on a solution for subtask 5 which turned out to be wrong, leaving me with less than 1.5 hours left. I found out that I probably spent less than 30 minutes on pC so I went back and came up with the solution for subtasks 1-3.
4:13 C 56
This problem is the only one (in day 2) where my submissions don’t repeat their scores. My score is finally higher than 100 (133), but is still pretty low imo. The solution for subtask 4 (14 pts) is also very similar but perhaps a bit harder to implement. Soon, I also figured out how I could obtain the remaining 47 points for pA.
Now I have like 40 minutes left, and I can probably decide to do pA (perhaps more risky?) or pC. Upon contemplation, I made the worst choice possible: try to solve pB.
Why? Maybe I’m inexperienced in OI. Maybe I’m greedy and think that 40 minutes is still plenty of time left. Maybe I just thought I could get lucky like day 1 and get a lot of points by guessing. Anyway, I wasted more time to get 0 points on pB until I found it was probably too late to implement (and finish debugging from past experience) the full solution for pA.
4:44 A Compilation Error
This was so weird (and maybe funny). My code in xcode ran perfectly, and I don’t know what I was thinking but didn’t look at the error message and instead stared at my code for errors.
4:51 A 53
Then I couldn’t find the bug until the end of the contest.
5:02 A 74
Turned out I forgot to add 1 somewhere. Well, too bad, the contest ended already. An extra 21 points wouldn’t have made me gold anyway.
Reflection
spoiler
Final score: 53 / 24 / 56
Total: 133
Day 2 rank 17
This was actually so bad. I also didn’t expect so many people to perform better in day 2 compared to day 1. My maximum score in day 2 across all problems is lower than the minimum in day 1 💀
I think the main problem was that I spent most of the time trying pB without even getting a lot of points. Perhaps I should’ve given up earlier and worked on pA and pC instead.
My luck on day 1 might’ve actually destroyed my day 2 performance, since it was because of how my guess obtained so many points that made me willing to spend time and guess wrong solutions on day 2 as well.
Also I made a lot more submissions than listed in the blog, and by a lot I mean
There’s no penalty, so it doesn’t matter … right?
I totally regret the decision I made when there was 40 minutes left, I don’t know where the confidence came from that made me think I could get all 64 points in like 20 minutes.
Perhaps I’m not good at CP after all.
Final Results
spoiler
Total: 367
Overall rank: 9 (high silver?)
Wasn’t any close to gold anyway, would’ve needed all 67 points. My score on pB was really kind of low despite I tried for more than 3 hours probably.
I never learn the lesson. I shouldn’t get stuck on one single problem. Hopefully I can at least be happy with my performance in the next USACO in January.
Doing OI virtuals is somewhat fun though ngl, but unfortunately I’m very bad at these. Perhaps doing more virtual contests would help me come up with some kind of optimal contest strategy? Or maybe what I should do at each weird scenarios? idk actually, and idt I have that much time after semester 1 ends (4 less study blocks 😭)