Easier contest (by nature of its age) but still pretty fun. Due to schedule I started around 3 pm and therefore ended at 8, on both days, so didn't have much time to writeup each day separately.

1. Reduced to some sort of quasi-functional graph, and it looked like it could be broken into almost-cycles, but I couldn't find a smart way to do this. Instead just bruteforced for 49 points.


2. I couldn't find any approaches much better than tree DP storing the smallest-node path of length 0..k and iterating for each node. This got subtasks 1 and 2, theoretically should have gotten subtask 3, but I got implementation wrong. (21 pts)


3. Essentially another bruteforce. It turns out that there will always be an optimal position situated exactly at one field, and I pretty much iterated over all positions. This got 68 points, for a day 1 total of 138.



4. Fun question. Tree case was, after a little bit of observation, a leaf-contraction sort of thing, and then for graph I decided that surely this could be modeled as relaxing nodes in an undirected graph, and so use spfa. I didn't entirely prove the complexity of this, but it sort of made sense. (repeated relaxation of a node would probably imply closely connected graph.) Either way, it got AC.


5. Bruteforce with decently good constant factors was enough to get 50 points. Tried working out some segtree/sqrt to speed up, but couldn't get anything in time.


6. Pretty fun question! My first approach was to dedicate some x of each packet's 8 bits to store data, and the other 8-x to store packet # for reconstruction. To transmit n bits of data using this protocol, n/x packets would need to be sent, and this would need to be within the limit of 2^(8-x).
   
   While this was sufficient for subtasks 1..3, it failed on 4 and above even with x = 1. I realized that the limiting factor here was numbering each packet individually.
   
   My new approach was to break up the input data into sections of 3 bits. Each section would correspond to a specific bit position on a set of 7 packets: Counting the number of set bits across all 7 packets, a 3-bit number which corresponded to the original 3 bits. Since these 8 packets didn't need to be ordered, I was able to (for subtask 4) get away with using 5 bits of addressing space and the remaining 3 bits for this overlay encoding. For subtask 5, where n could be 64, I had to use 6 bits of address space and 2 bits for encoding, and instead store 4 virtual bits in each encoding. This meant that each input number corresponded to exactly 15 packets of transfer, which was worth exactly 1 point, for a problem total of 82 points, a day 2 total of 232, and an overall total of 370.

Funnily, the 1 point on p6 task 5 was actually significant, because silver cutoff in 2011 was exactly 370. So this is I guess the second silver like I've hit, although still too close (and too old of a contest) to really count as a modern-day IOI silver performance.

tags: programming ioi contest-logs