Educational Codeforces Round 78 Reflection

December 20, 2019

A: Shuffle Hashing

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

There is a O(N)O(N) solution, where NN 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 hh with the same length as pp using multiset<char>. Then we have a solution of complexity O(TS2logS)O(TS^2 \log S), where SS 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;
        b += i;

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

Also, we need to increment NN until the parity of N(N+1)2\frac{N(N + 1)}{2} and ba|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 ithi^\text{th} jar of jam to the left of the ladder LiL_i, and the ithi^\text{th} jar of jam to the right of the ladder RiR_i. Then we can define two arrays SLSL and SRSR, where

SL0=SR0=0SL_0 = SR_0 = 0 SLi=SLi1+(if Li=1 then 1 else 1)SL_i = SL_{i-1} + (\text{if } L_i = 1 \text{ then } -1 \text{ else } 1) SRi=SRi1+(if Ri=1 then 1 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)(l, r), where we eat ll jars of jam from the left and rr jars of jam from the right, we must have SLl+SRr=count2count1SL_l + SR_r = count_2 - count_1. We can simply simply store the smallest rr for each SRr=kSR_r = k with a map, then simply query the index where SRr=count2count1SLlSR_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

i=0n(1m)i(m1m)ni(ni)ik\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.