Just virtual’d chinese NOI 2024 day 1, did ok (202 total).
my live log of what happened:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
05:00 read A
04:33 mindsolve 12pts on A, then +4, then i think AC with 2p
04:33 read B
04:11 wtf???
03:45 bruh misread
03:50 +~50 for B
03:45 read C
03:30 impl A start
02:56 still debugging samples
02:51 submit A
02:52 80 points got constant factored :skull:
02:25 still getting constant factored kms
sometime in the middle i realize i submitted the wrong file every time
02:06 ac but bruhhhhhhhhhhh
02:06 implement B
02:20 submit st1
01:18 get 71 on B
01:06 decide marginal time is best spent on opt and get 82 on B
up until 00:43 went for a walk "rq":tm:
gonna code the trivial stuff
00:30 still impl
00:28 get 12 on C
00:20 get 20 on C
00:00 sadge couldn't get the last 8 points i planned to
A was not bad, I got the critical observation that you can hash the set of indices containing an element fairly early. The main bottleneck was debugging, and then I got constant factored (during which I created a new version of my file, and then surprise! submitted the old version nooo, costing me 40 mins)…
B was funny, I first thought it was impossible cuz you can’t sort in less than $O(n \log n)$ with comparisons… until i remembered that it wasn’t about sorting. Then it took a few minutes to think of dnq, then naturally extended it to brute-forcing the top and then d-ary dnq. Got 82 points, turns out if you microoptimize the dnq structure with remainders you get fullsolve (la ji fullsolve basically)
I had no idea in C, just subtask grabbed. In retrospect, I got the crucial observation (it’s always possible when paths have >=2 unfixed edges) and the approach (whenever you have some edge that must be fixed, fix it, otherwise set the first edge to 0), and didn’t think of adding the two together…..
Hope I do better on day 2!
