# Coin stacks
Intuitively, the only way we can lose is we end up with a single stack that's very large. So why don't we always pick the two largest stacks? This turns out to be optimal. So we can simply simulate this, and print the output if it's valid, otherwise print no.

A very evil edge case is that the input can have coin stacks with no coins in them, which we must simply discard.

[Implementation](https://gist.github.com/Matistjati/d1da4fb17ee3f3b4a60fd695463415a3)

# Cash transport
The main insight in this problem is that transports get more valuable over time, so we want to rob the $K$ most valuable of them. The only problem is then To choose the $K$ most valuable without double counting. The way i implemented it is that each bank stores a list of all transactions that has gone into it. Once a cash van transports money from bank a to bank b, bank a's transactions is emptied, and converted into a single transaction for bank b. At the end, we just take the $K$ most valuable of these.
We also need to be careful so we don't accidentally rob banks (money that has never been moved)

[Implementation](https://gist.github.com/Matistjati/1bf762c8c93711ccd967d36f7f955310)

# Find the graph
Hasty editorial
First, for every node $u$, query the following sets: $\{u\}$ and the rest of the graph. This gives us the degree of every node. If we query $\{v,u\}$ and the rest of the graph, the answer will be equal to $deg[u]+deg[v]$ if there is no edge between them. If it is not equal to that, there is an edge. So in one query, we can find whether some edge exists. As we can make many queries, we can simply query every pair of vertices.

# Sharing candies
Hasty editorial
Let $p[i]=c_0+c_1+\dots+c_{i-1}$ (mod n). Compute all $p[i]$. If any $p[i]=0$, we are done. Otherwise, it turns out that there is always a contiguous interval with sum divisble by $n$. Consider some $i$. All intervals ending with $i$ can be expressed as $p[i]-p[j]$ for some $j<i$. So we want to check if there is some $j$ s.t. $p[i]-p[j]=0 \Rightarrow p[i]=p[j]$. So we can simply keep track of possible $p[j]$, and if any $p[i]$ is possible, we are done. In fact, by the pidgeonhole principle plus the fact that if any $p[i]$ is 0 we are done, this must always create a valid sum.

# Red/blue spanning tree
Hasty editorial
https://codeforces.com/blog/entry/94709

# Football
If you are very clever, there's a quite ingenious bitset solution. However, there is a simpler one. The main insight is that "every boy faces every other boy atleast once" is equivalent to "there is no pair of boys that are on the same side every time". From this, we simply need a nice encoding describing the sides that each boy has been on, and then check if there are any duplicates. One natural such encoding is that for the i:th match, the i:th bit is on if they are on the left, and 0 if not. We can then just throw all of these into a set and check if there any duplicates. Voila!

Implementation note: to set the i'th bit, we do

x |= 1LL << i;

Note the 1LL. If we just do 1, that's an int, and will overflow for i>31.

[Implementation](https://gist.github.com/Matistjati/a70114d7f946f8b4cb69187e21a27945)

# RúnaHeimur
First off, note that we have *a lot* of moves at our disposal. In the worst case, the board is $10 \times 10=100$. If we move each block across the whole board, it would move 100 spaces. So in this worst case, we make $100^2=10000$ moves. So as long as we use a reasonable strategy, the number of moves is not a concern.

The first insight is that we can solve the top layer, and then completely ignore it, reducing the puzzle by 1 row. This can always be done "easily" as long as we have at least 4 rows left. By symmetry, the same can be done for the columns. In the end, we're left with a 3x3 sliding puzzle, which can be solved by a simple BFS.

## Checking possibility
It is a well-known result that a sliding puzzle is solvable IFF the parity of the number of inversions is even. https://datawookie.dev/blog/2019/04/sliding-puzzle-solvable/
So we start by checking this.

## Row/column reduction
Just play the game a couple of times to build some intuition https://icherya.github.io/Fifteen-Puzzle/.

We can pretty easily move things into place as long as we don't move already fixed blocks. However, there is one very annoying case:

The way I solved it was simply to hardcode a solution once they were moved into place. It looked something like "DLUURDDLURDLUURDLURDLRDLU" (although I don't remember where they were supposed to be relative to each other to work).

The way I implemented the problem was to create a primitive "move block x to position p". This was then implemented by creating a function that moves the empty block to a certain position in the fewest number of steps using a BFS, and repeatedly calling that to move our block to the correct spot. Implementing this bug-free is the hard part of the problem.

## BFS
You can debug your implementation here https://po.kattis.com/problems/attaspelet.

[Here](https://gist.github.com/Matistjati/0f6e83d2bdb2127791f86710e833a322) is my implementation. It's very long, as any solution to this problem is going to be. You can dm me about details if you're wondering about anything.