A: Shuffle Hashing

At the beginning, I didn't read the constraint clearly and thought that it is annoying.

There is a $O(N)$ solution, where $N$ is the total string length. You can use sliding window and a frequency array to check whether the frequency of all characters are the same as the password.

For the constraints of this problem, it can be solved using brute force. Simply compare each substring of $h$ with the same length as $p$ using multiset<char>. Then we have a solution of complexity $O(TS^2 \log S)$, where $S$ is the length of one string.

B: A and B

This is the third problem I attempted. When I first read the problem, I didn't know how to approach it. I tried writing a greedy solution, but that didn't pass even the first test case. The greedy solution was something like this:

ll a, b, i;
for (i = 1; a != b; i++)
    if (a < b)
        a += i;
    else
        b += i;

I noticed that you can select a subset of $\{1, 2, 3, \dots, N\}$ such that the sum is in $[1, \frac{N(N + 1)}{2}]$. This means that we simply need to ensure that $\frac{N(N + 1)}{2} > |b - a|$. We can binary search on $N$ to find the minimum $N$.

Also, we need to increment $N$ until the parity of $\frac{N(N + 1)}{2}$ and $|b - a|$ are the same.

C: Berry Jam

I attempted this problem after finishing A, because I had no idea how to do B yet.

This problem is an interesting one. We can exhaust each left position, and find the right position closest to the middle such that removing the left part and the right part results in equal jars of strawberry and blueberry jam.

We can consider the parts to the left and to the right of the ladder separately. Lets call the $i^\text{th}$ jar of jam to the left of the ladder $L_i$, and the $i^\text{th}$ jar of jam to the right of the ladder $R_i$. Then we can define two arrays $SL$ and $SR$, where

$SL_0 = SR_0 = 0$ $SL_i = SL_{i-1} + (\text{if } L_i = 1 \text{ then } -1 \text{ else } 1)$ $SR_i = SR_{i-1} + (\text{if } R_i = 1 \text{ then } -1 \text{ else } 1)$

Then we know for a valid arrangement $(l, r)$, where we eat $l$ jars of jam from the left and $r$ jars of jam from the right, we must have $SL_l + SR_r = count_2 - count_1$. We can simply simply store the smallest $r$ for each $SR_r = k$ with a map, then simply query the index where $SR_r = count_2 - count_1 - SL_l$.

D: Segment Tree

I could not solve this problem during the contest. I misread the question and didn't notice that one interval must not be completely in another, and wrote a greedy solution that, even if fixed, cannot run within the time limit.

E: Tests for problem D

I solved this problem within contest time. I drew the tree on a paper and wrote down the suggested solution, and tried to write a DFS applying the same strategy. It worked.

Edit: the solution was a TLE. Don't use endl when avoidable.

F: Cards

I tried to derive the formula. The formula is

$\sum_{i=0}^n (\frac{1}{m})^i \cdot (\frac{m-1}{m})^{n-i} \cdot \binom{n}{i} \cdot i^k$

I could not simplify the formula so it can be computed within the time limit.