Codeforces Round 966 Discussion stream (with hints)

Split the string such that A is integer formed using first 2 char. Split the string such that B is integer formed using remaining.

A should be equal to 10, $2 \le B$, and 3rd char must not be 0. One can use built in string to int functions. stoll

Maintain set of seats occupied so far. Then x is valid, if set is empty, or x-1 or x+1 is present in set.

If length of s is not equal to n, the answer is NO.

Maintain pairing charToInt and intToChar.

First check is there exists an integer assigned to current char, and print NO if its not equal to current integer. Then check is there exists a char assigned to current integer, and print NO if its not equal to current char.

Now, create pairing if required.

Prefix Sum

Two pointers

We can first find the optimal matching and then do operations. Greedy works. We should try to match first L with last R. We should try to match second L with second last R. so on….

You prefix sums for finding range sum in $O(1)$.

For each cells we can find how many squares it can be a part of.

Greedy. Put maximum no to the cell that is part of maximum no of rectangles.

For a rectangle $L \times W$ if we paint $x$ rows and $y$ columns, minimum no of operations we need is $x \cdot W + y \cdot L - x \cdot y$ operations. We can first calculate minimum no of operations required if we want to earn $i$ points using this rectangle, where $0 \le i \le L+W$.

Dynamic Programming

$dp_{i,j}$ denotes minimum no of operations required to earn $j$ points using first $i$ cells.

Binary search FTW

Lets say we have a blackbox function $f(t)$ which returns true if we can reach node $N$ if we start at time $t$.

If maximum leave time is $T$, then notice that -

• $f(t)$ is true for $ t \le T$, and
• $f(t)$ is false for $ t \gt T$

Dijkstra Algorithm

To check if we can reach node $N$ if we start at time $t$, we can use dijkstra algorithm with some modifications.

Notice that the answer will be one among $x+1$ for all the elements $x$ currently present in the set.

So for all of these nos $d$ we should maintain maximum $k$ such that $d, d + 1, \ldots, d + (k - 1)$ are not present in set.

We can ignore rest of the nos by assigning k=0 for remaining nos.

Maintain the set of no currently present.

When we want to add or remove some element $x$ from set - We can use lower_bound, and then we can do it++ or it–, to find element just more than $x$ and just less than $x$ (say $y$) still present in the set.

Notice that maximum $k$ changes only for $x+1$ and $y+1$

To find the first element $\ge K$ for third query. We can either do a binary search again or Walk on a Segment Tree to remove one $logN$ factor.