PoTD Solutions - 6th June
------
### 1. Systems - Easy
unordered_map works on hashing. Due to collisions, the worst case access time becomes O(n), otherwise, the amortized time is O(1).

### 2. Puzzles - Medium

#### **You Should Never Go First**

N-Nim usually refers to a game of Nim with 2 piles of $N$ sticks each.
Recall that in Nim the person who cannot pick a stick loses.
We will prove this by induction.

Assertion: If the state of game is $(i, i)$, the person to move loses.

If the state is $(0,0)$, it is obvious.

Now suppose this holds for all $i < N$.

Clearly, if the state of game is $(N, N)$, the person to move can change state to $(p, N)$, where $0 \le p < N$. The other player can simply remove $N-p$ sticks from the larger pile to get to $(p, p)$. As $p < N$, the first player now loses.

> ### Bonus
> Prove that if there are $k$-piles of $N$ sticks each, iff $k$ is odd it is beneficial to go first.
> **Solution:** Use XOR

### 3. CP - Hard
https://usaco.org/current/data/sol_262144_platinum_open16.html