Bits and Bytes

Today, I’d like to share another really cool programming problem. This problem is Editor from the 2015 Baltic Olympiad in Informatics.

Here’s a quick summary of the problem: You’ve invented a text editor where there are 2 operations: edit and undo. Each operation has a level. An edit changes the editor state (initially 0) to some new state. An undo of level $L$ undoes the most recent operation with level strictly less than $L$. Note that an undo can undo a previous undo. Each edit has level 0 and the user determines the level of each undo. You’re now given a sequence of $N \leq 10^5$ operations. For each operation, you want to know the editor state directly after you apply it.

Today, I’d like to share a really cool problem I solved from the Japanese Olympiad in Informatics. This problem is Synchronisation from the 2013 Open Contest.

Here’s a quick summary of the problem: You have $N \leq 10^5$ computers and $N - 1$ connections that form a tree. Initially, all connections are inactive and all computers hold a single unique piece of information. Each time the connection between computers $A$ and $B$ is activated, the computers connected to $A$ and $B$ (including $A$ and $B$) sync up and share information. The states of the connections are changed $M \leq 10^5$ times and you would like to know how many unique pieces of information are stored on each computer at the end.

There are many ways to solve this problem (I know of 4 distinct ways), but I’ll share what I think is the most elegant solution, which relies on more observations and has relatively light implementation.

Let’s solve this problem subtask by subtask, just as we would in an actual competition!