Upsolve Contest Tracker, Apr – Jun, 2020.

April 25, 2020 (1st Div1 Contest Done!)
Codeforces Round #635 (Div. 1): C, D, E, F (Done)
E: linear algebra, FWT
This problem is about relating bitwise-xor FWT operation $B[x]=\sum_y (-1)^{\langle x,y\rangle}A[y]$ with linear orthorgnal complement when $A$ is a linear subspace. It turns out that when the the rank of $A$ is large, the rank of the linear orthorgaal complement will be small, and the number of non-zero entries in $B = FWT(A)$ will be small.

April 29, 2020 (2nd Div1 Contest Done!)
Codeforces Round #637 (Div. 1) – Thanks, Ivan Belonogov!: D, F (Done)
F: bracket sequence, segment tree, hash
Consider a segment tree to merge bracket information. We can know that a bracket in a node should be of form “…}]){{({…”, we can merge two nodes if they can match the adjacent parts (we can check by hash).
The key property of this merging action is that the prefix of the left node (i.e. the “…}])” part) and the suffix of the right node (i.e. the ” {{({… ” part) will never get shorter when merged. Then we have storing in each node the longest valid prefix and suffix even if the sequence in it is not valid. By doing this, we can do the query in the same way as update since we can query the prefix and suffix of certain length as in update.
Code: 78524960

April 30, 2020
Educational Codeforces Round 86 (Rated for Div. 2): E, F (Done)
F: bitmask, brute force
DP usually had its value as another hidden dimension, so when our DP is too large, always think about putting one dimension to the value.

Jun 3, 2020
Codeforces Round #646 (Div. 2) : F (Done)

Leave a Reply

Your email address will not be published. Required fields are marked *