It is somehow difficult to count the number of such subsequences in an arbitrary string. Can you think of strings where it is trivial?
The number of such subsequences can be $$$0$$$.
Key observation: A bitstring where all $$$\mathtt{1}$$$ bits come before all $$$\mathtt{0}$$$ bits is perfect as it has no $$$\mathtt{101}$$$ or $$$\mathtt{010}$$$ subsequences.
You can fix the number of $$$\mathtt{1}$$$ bits to be $$$k$$$ and then put $$$n-k$$$ $$$\mathtt{0}$$$ bits after them. This achieves a perfect bitstring with the number of $$$\mathtt{1}$$$ bits being $$$k$$$.
The answer matrix will have permutations in every row and column. Can you think of such a matrix?
Let our final matrix have all cyclic shifts of the identity permutation in each row. Can you perform a cyclic shift using $$$3$$$ operations?
One of the operations performed on each row becomes redundant.
Key observation: You can cyclic shift an array using $$$3$$$ operations.
The operations to achieve this are "$$$1$$$ $$$n$$$", "$$$1$$$ $$$i$$$", "$$$i+1$$$ $$$n$$$". Perform these with a different $$$i$$$ for each row, you will obtain all cyclic shifts of the identity permutation. To optimize it to $$$2n$$$ operations observe that performing "$$$1$$$ $$$n$$$" on each row does nothing.
Think in binary.
Let $$$x$$$ be an integer. What is the smallest number $$$y \gt x$$$ that is more beautiful than $$$x$$$?
$$$y$$$ always equals $$$x$$$ with the smallest valued $$$0$$$ bit set to $$$1$$$.
Key observation: To increase the beauty of a number, it is always optimal to set the least valued $$$0$$$ bit to $$$1$$$.
Let our number be $$$x$$$ and call the least valued $$$0$$$ bit special. Let $$$y$$$ be $$$x$$$ with the special bit set to $$$1$$$. To increase the beauty, we must increase $$$x$$$ by at least $$$1$$$. This will set the special bit to $$$1$$$, and all bits with a smaller value to $$$0$$$. Until we reach $$$y$$$, there will always be at least one $$$0$$$ bit with a smaller value than the special bit while the bits with a higher value stay the same. This means that no number is more beautiful between $$$x$$$ and $$$y$$$, showing that the observation is correct.
From this, we can construct a solution. Let us count the number of $$$0$$$ bits at each position. Iterate from the least valued bit to the highest. Greedily set one such bit to $$$1$$$ until we run out of $$$0$$$ bits or the remaining $$$k$$$ is less than the value of the bit.
This solution has a time complexity $$$O(N\log{10^{18}})$$$.
2118D2 - Red Light, Green Light (Hard version)
Divide the problem into some subproblems:
- Find the next traffic light efficiently.
- Detect cycles efficiently.
For D1 it is enough to do the first subproblem in $$$O(N)$$$, the second subproblem with $$$O(N)$$$ calls of the first subproblem. For D2 we need to do better.
Try to simulate the problem by hand.
Iterate over all traffic lights and check if we would collide with it if we don't turn. Then we can select the next traffic light in the correct direction. This is $$$O(N)$$$.
If we collide with the same traffic light from the same direction twice than the answer is no. For detecting cycles we can store visited traffic lights that we collided together with direction. Notice that we can only collide with a specific traffic light in a unique time modulo $$$k$$$.
This solution has a time complexity $$$O(Q*N^2)$$$.
First, let's quickly find the next traffic light in the positive direction. Imagine movement by moving along diagonals, refer to the images in the statement for a visual representation. Group the traffic lights by $$$(d_i-p_i)\bmod k$$$, when at position $$$x$$$ at time $$$t$$$ you will collide with the group of $$$(t-x)\bmod k$$$. We can binary search the next position on this. To do the same for the anti-diagonals you can group by $$$(d_i+p_i)\bmod k$$$ and search by $$$(t+x)\bmod k$$$.
We can still simulate each query, but after finding out the answer you can store for each state the result. In later queries, you can refer to the already checked states. In total, you will only check each state at most once.
Alternatively, you can notice that after colliding with a traffic light in a specific direction, the next traffic light will always be the same. From this you can build a graph and detect cycles before reading queries.
Both solutions have a time complexity of $$$O(N\log{N})$$$.
Why is it important that both $$$N$$$ and $$$M$$$ are odd?
Try generalizing the trivial case when $$$N=1$$$.
Try extending the solution from a smaller case... in a literal sense.
Key observation: Having $$$N \ge M$$$ and N, M both odd, an $$$(N - 2) \times M$$$ grid can easily be extended into a $$$N \times M$$$ grid
To achieve this first color a cell in the middle of both of the $$$M$$$ long sides. By this we ensure that the rectangle will be so wide that its side will be at maximum chessboard distance from each other. This means that any cells colored next to one of its sides can only increase the penalty of cells of the opposite side. By coloring cells alternating up and down on each side (similarly to the solution to the case $$$N=1$$$) we can ensure that every cell gets at most $$$2$$$ penalty.
This only leaves the corners as corner cases (as they can be increased from two sides), but they can also be solved by choosing the order of vertical and horizontal extensions correctly.
Some interesting observations:
- It can be observed that order that ordering the points from the center (and always deciding the ties in the right manner) can also yield a solution.
- There actually exists a solution which works for even sized boards
- As an extra challenge it can be interesting to find a solution where no cell has more than 2 penalties.
The order of two elements only matters if the absolute value of their difference is at most 1. Try to store the positions of elements with value $$$v$$$ relative to elements with value $$$v+1$$$. (The next hint will be about what to do with these.)
We want to somehow hash the relative positions. (The next hint will be about a thing you might not have known you can hash.)
It is possible to hash rooted trees, see Vladosiya's blog post. Note: the structure you hopefully came up with using hint 2 will certainly not be a single rooted tree, use this algorithm more as a guide. (The next hint will be about how you can check if two strings are rotations of each other.)
We'll consider the arrays cyclic: $$$a_1$$$ and $$$a_n$$$ are also adjacent.
For each array, let's build rooted trees where the children of each vertex are ordered. Each vertex corresponds to an value in an array. For each index $$$i$$$, let its children be the occurrences of the value $$$a_i - 1$$$ in order between the $$$i$$$-th element and the next occurrence of the value $$$a_i$$$. The roots of the trees will be nodes with value $$$m$$$ in an array. We hash each tree, then compare if the sequences of hashes are rotations of each other (for example using KMP).
For hashing a tree, see Vladosiya's blog post.
This solution has a time complexity $$$O(N\log{N})$$$ if you use a map for deterministic hashing.
