9:27 AM
Virtualed IOI14d1 yesterday. Due to time (18:30 - 23:30) I didn't feel like writing up last night, so I'm just doing this while bored at school :p
0:00 - 0:15
Mostly just looked through the problems, considered approaches. p1 + p3 both interactive, pretty scary. p2 looked like a somewhat doable range query - ironically seemed easier than p1? idk. Wrote some observations for p1 then started implementing p2.
My p2 approach was some sort of range combination thing where I kept track of min and max values for towers in each range, and did some overlay with priority thing to combine. overcomplicated probably idk
0:15 - 1:30
impl speed severely lacking
I was pretty sketched out by my approach so I decided to write with sqrt decomp initially. (easier to debug, also didn't have to deal with multiple levels of lazy prop) Even so it took me about an hour to write the whole thing..
First submission at 1:15, got WA. Made a couple of edge cases, found an issue with my range combiner thing.
Fixed up and resubmitted at 1:28, got 61 pts w/ RTE on last subtask. (array + bucket size tuned for small subtasks, so overflowed on big) Because my approach was O(k logn) for k = 5e5, n = 2e6, I thought that my sqrt wouldn't pass, but decided to try just for the heck of it. bucket is usually pretty good constant-factor wise.
Turned out that something on the order of 1024 * 2e6 operations passed, in around 2.5 seconds, with my not even entirely optimized decomp. (redundant push operations, bucket rebuilds, etc.) Though this might be an artifact of the OJ, and might have TLE in contest. idk.
1:30 - 2:00
Thought more about approach for p1 and also read p3. Came up with somewhat of an idea for p1.
This targeted subtask 3 and below, because it relied on knowing every pairwise distance.
Initially: determine the closest station to station 0. With a little bit of observation we can see that this station must 1) be a type D station, and 2) be the closest such station to the right of station 0.
Then once we find this station, iteratively perform the following:
Let l, r be the leftmost and rightmost found stations. Find the closest unfound station to l, and call it x. Using the distances between x and l, r, we can determine by casework the position and type of x:
- x < l
We can prove here that x must be type C. If it were type D, to travel from x to l, the train would have to move left from x, then turn around at some C block, and then go to l. In this case, the C block would be closer than x. And because l represents the leftmost found station, this C block cannot have previously been found.
We can check for this case pretty easily. Consider the following example:
( ( ) ( ) ) x l m r
m denotes the closest station to l; it is guaranteed to be of type D.
To get from x to l, the shortest route is to go left to m, then turn around and go to l. The distance to r is just the direct difference in position.
Therefore, we can check for this condition by solving for the position of x using both of the measured distances, and checking if they match up.
With some work we can prove that no other configuration satisfies this, I think. - x > r
Similar to last case. - l < x < r, x
Here we only need to check if x is of type C or D, which we can do by calculating positions based on distances for both cases and checking which one matches up.
2:00 - 3:45
implementation...
First submit at 3:00, got 8 pts due to some issue with determining case. Fixed that up for a 30 pt submission at 3:15, then spent the next half hour or so trying to get subtask 3 to work. No luck.
3:45 - 4:30
Decided that fighting with p1 was probably not a good use of my remaining time and so decided to try farming p3.
I decided that it was maybe optimal to only return 'edge exist' if all other edges connecting u, v had been previously asked. In theory this wasn't very complicated, but seeing that I don't know LCT or other form of dynamic connectivity, my approach used an n^2 dfs to determine reachability, (n^2 because complete graph is quadratic in the # of edges), and was too slow for subtask 4.
Took until 4:10 to get implementation correct, giving 42 pts, then spent a while trying to optimize approach for task 4. No luck.
4:30 - 5:00
fought with p1 some more, no improvement
ya so.. my interactives definitely need work, as well as general implementation speed / debugging / not having bugs in the first place etc. Ended with 172 points, which sits at 71st place tie, I think?
Gonna do d2 today at around the same time, hopefully won't throw as much !!
tags: programming ioi contest-logs