Favorite Problems From CF 2020
2020 was an eventful year for competitive programming for me, especially on CodeForces.
In terms of rating, I have accumulated a maximum rating of 2499 and have reached the title Grandmaster and International Master during the 2nd half of the year and was a stable Master for the 1st half of the year. Compared to 2019, where I initially dropped from Candidate Master to Expert and later stayed at Master, I am very satisfied with my rating progress in 2020.
As for submissions, I have made 2220 submissions and among them, I solved 655 problems. Also, I participated in 24 contest officially on Codeforces.
The primary reason that I wanted to write this blog is to share some of my favorite problems that I solved on Codeforces in 2020. When thinking about what were my favorite problems of the year I accounted for the impact it had on me and the elegance of the solution. There were simply too many problems that I enjoyed solving this year, but I managed to compile a list of 37 problems and cut it down to the 10 best problems. First I’ll list in the order I solved them in for the honorable mention problems that made it to the 37 problem cut and then I will show and explain the best 11.
Honorable Mention
 NN County
 The Untended Antiquity
 Recursive Queries
 Too Much Money
 Water Balance
 TShirt
 Magical Permutation
 Selling Souvenirs
 You Are Given A Tree
 Exam Cheating
 Ski Accidents
 The Hidden Pair
 Sky Full Of Stars
 Pointer Ordering
 Rearrange
 Treeland And Viruses
 Tree Modification
 World Of Darkraft  2
 New Year And Cleaning
 U2
 Winding Polynomial Line
 The Hardwork Of The Paparazzi
 Allowed Letters
 Nullify The Matrix
 Sum
 Errich Tac Toe
Top 11

Subset With Zero Sum
Problem Link, Difficulty: 2700
Solution
$$in \le a_i \le i1$$ $$n \le a_ii \le 1$$ $$n \ge ia_i \ge 1$$ This means that $ia_i = j$ where $1 \le j \le n$ is another index. Now consider the graph where edges are drawn between $i$ and $i  a_i$. Note that this is a functional graph, meaning that there exists an oriented cycle. Now consider all the nodes in an oriented cycle $\{i_1, i_2, i_3, \ldots, i_k, i_1\}$. Summing each distinct node in the sequence, we get $$\sum_{i = 1}^k i_k = \sum_{i = 1}^k i_k  a_{i_k}$$ Subtracting $i_k$ on both side, yields $$0 = \sum_{i = 1}^k a_{i_k} \implies 0 = a_1 + \ldots + a_k$$ Thus, we reduced the problem to finding an oriented cycle in a functional graph, which can be solved using DFS or Floyd's Cycle Detection Algorithm. 
Awesome Substring
Problem Link, Difficulty: 2600
Solution
Think about the string as an array of integers instead ('0' turns into value 0 and similar for '1'). Compute the prefix sum and call it $pre$ where $pre[i]$ represents the sum of the first $i$ elements. Now we can state the condition as count the number of subarrays $(l, r)$ such that $$pre[r]  pre[l  1]  r  l + 1$$ In other words, we can count the number of unordered pairs $(l, r)$ such that there exists some $k \in \mathbb{Z}$ such that $$k * (pre[r]  pre[l  1]) = r  l + 1$$ Since $r  l + 1$ is bounded by $N$, then either $k$ or $pre[r]  pre[l  1]$ is less than or equal to $\sqrt{N}$.
If $k$ is less than or equal to $\sqrt{N}$, then rearranging can get that $$k * pre[r]  r = k * pre[l  1]  k * (l  1)$$ So, for each $k$ we can maintain a frequency array of $k * pre[i]  i$ for every $i$ and then we can use $(fre[v] * fre[v  1]) / 2$ for every nonzero $v$;
If $pre[r]  pre[l  1] \le \sqrt{N}$, then for every $r$ group each $l$ into group of $1 \le g \le \sqrt{N}$ such that $pre[r]  pre[l1] = g$. Notice that each group is contiguous and let it be $[a_g, b_g]$. Fixing $g$ allows us to calculate how many $g  r  l + 1$ where $l \in [a_g, b_g]$. This is the same to count the number of $l$ such that $r$ is congruent to $l1$ in modulo $g$.
Note that when implementing be careful to not overcount subarrays where it satisfies both conditions. One method to avoid that is to subtract those subarrays by using PIE, but I find that to be slow in practice. Another method is to count those that satisfy the first condition and then count subarrays who satisfy the second but not the first condition or vice versa.
Since, each pass is $\mathcal(O)(N\sqrt{N})$, then it should pass within the time limits. However, I find that the time limit is tight. One optimization is to use a 100 million sized int array for the frequency array.

Varying Kbits
Problem Link, Difficulty: 2700

Secure Password
Problem Link, Difficulty: 2800

Crossword Expert
Problem Link, Difficulty: 2400

Souvenirs
Problem Link, Difficulty: 3100

Almost All
Problem Link, Difficulty: 2700

Change Free
Problem Link, Difficulty: 2400

Double Knapsack
Problem Link, Difficulty: 3000

Reality Show
Problem Link, Difficulty: 2800

Roads And Ramen
Problem Link, Difficulty: 2800