Completed the second half of IOI18. Performance was kinda eh, but wasn't expecting much :clown:

0:00 - 1:30

Solved Combo. Essentially the construction I found was to guess the next 2 bits in the sequence over the course of two queries: there were 3^2 = 9 possible arrangements of next bits, and each query had three possible return values, which worked out to a basically perfect 1:1 mapping between query and bit found.

1:30 - 2:00

Looked around at the other problems - I thought of some bounding box stuff for p2 but couldn't think of a good approach. Considered a little bit of range query on range query, but it was scuffed. I did notice that subtask 5 seemed doable, because it restricted the shape of the board to a line, but I moved on because I didn't have a solution to this either.

p3 seemed like I could farm some points on its subtasks (guaranteed line graph) so I tried it.

2:00 - 3:00

Essentially the problem reduced to finding the range of cities accessible from the start while in human form, and finding the range of cities accessible from the end while in wolf form. If these overlapped, the answer would be yes, otherwise, no.

For this I just used some segtrees. First I flattened the line graph into an array, and then built an RMQ that kept track of both min and max. Answering each query was then just binary searching to the left and right of endpoint, using segtree. (I firstly didn't feel like writing a segtree walk, and secondly didn't really trust that I would implement it correctly. Binary search I was much more confident in.)

(this got 34 points)

3:00 - 3:30

Messed around with the line case of p2, trying to find a reduction that I could make. I thought I saw some hull stuff, which I could implement with a segment combination sort of algorithm. This ended up being fundamentally flawed, but I would only realize this at the very end of contest.

3:30 - 4:30

I wrote up some sqrt decomp to compute the segment combination and then tried to submit it. There was some sort of issue on the OJ side, because I kept getting RTE. I tried submitting some code that just returned 0 for every case, and still got RTE. Richard told me to use DMOJ instead. My solution didn't RTE there, but got WA. I realized about here that my solution was fundamentally flawed.

4:30 - 5:00

Tried drawing out more configurations, but couldn't really think of one that would work. I did end up realizing that I could adapt my segment joining sqrt decomp algorithm to solve some cses problem that I have been stuck on for a while, so we don't fully lose, I guess!

Final score

I ended with 134 + 104, missing silver by 21 points. Overall though I think it was alright, and I had lots of oppurtunities yesterday to get more points, like the various subtasks on p2 and p3, as well as a better p1.

I'll try to get through most of my upsolve queue in the next few days - one final burst before school starts!

tags: programming ioi contest-logs