I was attempting some afternoon funsies for most of today, which I basically totally bricked.

Here is a hopefully not too scuffed breakdown. (would say it has spoilers, but I barely solved any of the actually interesting problems so nah)

0:00 - 0:30

Read through questions and concluded that p1 was the only I had a chance at full solving..

The initial reduction was pretty easy to see - each trigger essentially had to sequentially output a sequence t_{1..m} upon activations 1..m. As long as no switches are shared between triggers, they behave completely independently, so this held.

This turned the problem instead into constructing some binary tree that could output a specific sequence while also satisfying all the necessary properties of the switches.

I wrote up some initial solution to target first few test cases, where each trigger only occured at most four times. Spent too long figuring out how the submission format worked oops

Anyway this got a whole.. 15 points!!!

0:30 - 1:30

Creating the binary tree was complicated because essentially each switch had to be activated an even number of times. I thought I could try some full-binary-tree stuff to get around this: the trigger outputted into the root node of the tree, and its outputs were on the leaves. Due to the nature of the switches, each one would be activated an even number of times.

Of course, not all leaves would have outputs, because output count wasn't guaranteed to be a power of two. I decided to use the most basic possible fix to this, and have non-endpoint leaves redirect straight to the root of the tree.

This was still kinda hard to implement, because the order of leaves activated in the tree wouldn't be as simple as just left -> right. After drawing stuff out and thinking for probably too long, I saw this cool pattern:

Consider the behavior of the root node. It essentially moves all even-number activations down the left path, and odd-number ones down the right one. (when zero-indexing; it made the further observation easier.) What about level-two nodes? They did something similar, switching paths based on whether the twos bit of the query number was set. Similar with level-three nodes, like so:

+
/ \
/     \
/         \
/             \
+               +
/ \             / \
/     \         /     \
+       +       +       +
/ \     / \     / \     / \
000 100 010 110 001 101 011 111

This made the pattern pretty clear: the i'th query, when zero indexed, ended up at the leaf with index rev(i). This made a lot of sense: the the root node's effect was basically to set the most significant bit of the leaf, and then the level2 nodes set the second most significant, and so on.

I implemented this approach, and got acceptable on the cases that failed before. This solution wasn't very good, because it could potentially use way more switches than necessary.

1:30 - 2:00

Continued bricking on p1

2:00 - 2:45

Remembered that other problems existed and went back to them. p2 was kind of scary, but p3 looked like I could cheese a couple partials. I wrote up a really stupid n^2 logn solution targeting the first two subtasks, which performed the obvious divide-and-conquer approach of selecting the tallest mountain in the range, and checking which side of it would be optimal to for the meeting.

This got 19 points.

This is also where I pulled another no eyes extreme stupidity moment: I assumed that constraints in the test cases formed a monotonically increasing sequence. Clearly, this wasn't true, because subcase 3 guaranteed h_i <= 2. (bruh)

2:45 - 4:00

I basically filled up the nearest available college mail scrap paper with random configurations of binary trees, and tried to find one that would be less wasteful. I considered some heap-order configurations, but none of the ones I came up with were easily modifiable to satisfy the switch rules or just seemed like a massive pain to implement. Around 3:30 I decided to use some scuffed solution that "pushed" all the actual trigger -> trigger paths to a contiguous region on the right side of the tree, so that some redundant switches could be removed. (Any switch whose paths all mapped back to the root could be removed and replaced with just a jump to root.)

This was kinda really annoying to implement because a) I am dumb and b) the paths still had to be unscrambled and such.

I ended up with a submission that got full on all except the last subtask: 85 points.

4:00 - 5:00

Around this time richard reminded me that p3 was farmable. (I still hadn't realized the relaxed constraints on subtask 3.)

So I spent basically the rest of the time trying to debug a segtree bash. I didn't end up getting any more points, because I suck at implementation :dead:

boing

I realized after contest that there might be a somewhat easy way to make my p1 approach more efficient. Instead of completely isolating each trigger and its outputs from one another, I think it might be possible to perform one final pass through the switches that got activated an odd number of times, instead of trying to resolve each cluster individually.

Also, richard pointed out that one of the subtasks for p2 guaranteed that the graph was a tree, which would make it not impossible - something else I failed to see in contest... I'll write these up soon (tm)

Anyway, I'll be doing ioi18d1 tomorrow; it is apparently not entirely impossible..

tags: programming ioi contest-logs