Codeforces markup like [contest:<contest_ID>] is behaving differently for me in group and personal blogs.

In a personal blog, it ends up as a hyperlink to https://codeforces.net/contest/<contest_ID>. This is desired behavior.

In a group blog, it ends up as a hyperlink to https://codeforces.net/group/<group_ID>/contest/<contest_ID>. This is not desired. In fact, the link is invalid.

The same happens for [problem:problem_ID] and [submission:submission_ID].

This is leading to problems. First, I wrote personal blogs and linked to them in the group. But this clutters the public blogs. Now, I am explicitly hyperlinking in group blogs, e.g., [Codeforces Round 966 (Div. 3)](https://codeforces.net/contest/2000). This is inconvenient.

Is there any way that I can get the desired behavior directly in a group blog?

[problem:582924a]

Let $$$T(h)$$$ be the number of cards used for height, $$$h$$$. We then have that, $$$T(1) = 2, T(h) = T(h-1) + 2h + h - 1$$$. Use this to pre-compute the array $$$a$$$ where $$$a_i=T(i)$$$ for all $$$i$$$ such that $$$T(i)\le 10^9$$$. The highest value of $$$i$$$ comes to $$$25,820$$$, i.e. T($$$25,820$$$)= 1,000,021,510$. This is easily computed within the given time. Note that $$$a$$$ is increasing.

No pyramid can be made with 1 or fewer cards. For higher values of $$$n$$$, we find the smallest number $$$i$$$ such that $$$a_i\ge n$$$. If $$$n=a_i$$$, then a pyramid of height $$$i$$$ can be built and no cards remain. Otherwise, a pyramid of height $$$i-1$$$ can be built and we repeat for $$$n-a_{i-1}$$$ cards. $$$i$$$ can be found using binary search.

The complexity of this solution is determined by - pre-computation of $$$a$$$: $$$\Theta(25802)$$$ - a few binary searches over $$$a$$$ for each $$$n$$$: $$$O(t\cdot 25820\log 25820)$$$.

Original problem: 1345B - Card Constructions, leads to official tutorial and all solutions including WS solution: 302657703

[problem:582924b]

Clever Solution

Credit: hassan343

The longest run of Ls is the largest length that the frog has to jump over.

The complexity of this solution is $$$\Theta(n)$$$.

Solution: 302779860

Boring Solution

Only the cells with an R are relevant to the frog.

We can start with an initial estimate of $$$d$$$ and update it as we trace the frog backward from cell, $$$n+1$$$, to cell $$$0$$$, visiting only cells with R. Initially, we set the frog's position, $$$p$$$ and $$$d$$$ as follows: $$$p=n+1$$$ and $$$d$$$ is the distance between $$$n+1$$$ and the rightmost R. $$$p$$$ is then updated to the position of the found R. The frog keeps jumping left to cells with R until $$$p$$$ becomes $$$0$$$ as follows.

If the frog finds one or more cells with R between the cells $$$p$$$ and $$$p-d$$$, it jumps to the leftmost among them. Otherwise, it jumps to the closest R to its left and we update $$$d$$$ to this new distance. $$$p$$$ is updated to the new position.

The new position each time can be found through a binary search on the positions of R.

The complexity of this solution is determined for each test case by - noting the positions of R: $$$\Theta(n)$$$ - finding updated positions as we trace the frog backward from cell $$$n+'$$$ to cell $$$0$$$: $$$O(n\log n)$$$.

Original problem: 1324C - Frog Jumps, leads to official tutorial and all solutions including WS solution: 302664793

[problem:582924c]

Bonus: no need for binary search

Consider rounds of shots, where each round comprises 6 shots followed by 1 enhanced shot.

For the three monsters to die at the end of the $$$i$$$-th round, $$$a, b, c$$$ must each be equal to $$$1$$$ just before the enhanced shot in the round. Each of $$$a, b, c$$$ must also start the $$$i$$$-th round with a value of at least $$$1$$$. In order to survive the first $$$6$$$ shots of the $$$i$$$-th round, $$$a+b+c$$$ must be at least $$$6$$$ at the start of the $$$i$$$-th round. Specifically, $$$a+b+c$$$ must be equal to $$$9$$$ at the start of the round.

Similarly, at the start of the $$$(i-1)$$$-th round, $$$a,b,c$$$ must total $$$18$$$ with all values at least equal to $$$2$$$.

To die at the end of the $$$i$$$-th round, the sum of $$$a,b,c$$$ must be $$$9i$$$ and each of $$$a, b, c$$$ must be at least $$$i$$$.

The complexity of this solution is $$$\Theta(1)$$$.

Original problem: 1463A - Dungeon, leads to official tutorial and all solutions including WS solution: 302660332

[problem:582924d]

Consider $$$b$$$, the prefix sum array of $$$a$$$. $$$b_i$$$ indicates the largest label present in pile $$$i$$$. Also, $$$b$$$ is increasing.

Given $$$q_i$$$, we can find the smallest $$$j$$$ such that $$$q_i\le b_j$$$. Then, $$$j$$$ is the pile containing the label $$$q_i$$$.

The complexity of this solution is $$$\Theta(n)$$$.

Original problem: 474B - Worms, leads to official tutorial and all solutions including WS solution: 252317151

[problem:582924e]

The arguments to $$$g$$$ are in the range $$$[1, 10^6]$$$. Pre-compute the 2D array, $$$d$$$, such that $$$d_i$$$ contains all the numbers $$$j$$$ such that $$$g(j)=i$$$ where $$$1\le j \le 10^6, 1 \le i \le 9$$$.

For a given $$$l, r, k$$$, the answer is then found in the array, $$$d_k$$$ as follows. Let $$$y$$$ denote the count of the numbers, $$$j$$$ in $$$d_k$$$ such that $$$j\le r$$$. Let $$$x$$$ denote the count of the numbers, $$$j$$$ in $$$d_k$$$ such that $$$j< l$$$. Then the answer is $$$y-x$$$.

Once $$$d$$$ is computed, each query takes $$$O(\log n)$$$ time assuming that $$$d_k$$$ is sorted and $$$x$$$ and $$$y$$$ are found using binary search.

Original problem: 932B - Recursive Queries, leads to official tutorial and all solutions including WS solution: 302675125

Editorial for [contest:582923]

[problem:582923a]

To minimize the number of candies, Timur will favor candies with higher sugar content. We can sort $$$a$$$ in reverse and compute its prefix sum array, $$$b$$$. Note that $$$b$$$ is increasing. $$$b_i$$$ represents the maximum amount of sugar that Timur can get after eating $$$i$$$ candies, and $$$b_n$$$ represents the total amount of sugar that Timur can get from eating all the candies.

If $$$x_j> b_n$$$, then the answer is $$$-1$$$. Otherwise, the answer is the smallest $$$i$$$ such that $$$b_i \ge x_j$$$. This can be found easily through a binary search on $$$b$$$.

The main steps and their complexity are:

• $$$O(n\log n)$$$ to sort $$$a$$$ in reverse
• $$$\Theta(n)$$$ to compute $$$b$$$, the prefix sum array of $$$a$$$
• $$$O(q\log n)$$$ for $$$q$$$ binary searches over $$$b$$$

The overall complexity is therefore $$$O(\max(n\log n, q\log n))$$$.

Original problem: 1676E - Eating Queries, leads to official tutorial and all solutions including WS solution: 302470603

[problem:582923b]

We note that only the positions of the teachers that immediately surround David are relevant. These can be found easily by sorting $$$b$$$ and performing a binary search in $$$b$$$ for a given $$$a_i$$$.

If there is no teacher on one side of David, then David can move as far as possible in that direction and make no further moves when he reaches the end. Depending on the side, the number of moves to be made by the teacher is $$$b_1-1$$$ or $$$n-b_m$$$.

When there are teachers on both sides, let $$$l$$$ and $$$r$$$ be the number of empty cells between David and the teachers on each side, and let $$$l$$$ be the smaller distance. One optimal strategy is for David to stay still for $$$l$$$ moves and then start moving. By this time one teacher is just adjacent to David and the other is $$$r-l$$$ cells away. David runs from the teacher just next to him, and thus moves closer to the other teacher, who ends up catching David in an additional $$$(r-l)//2$$$ moves. The answer is $$$l + (r - l)//2$$$.

The main steps and their complexity are:

• $$$O(n\log n)$$$ to sort $$$a$$$
• $$$O(q\log n)$$$ for $$$q$$$ binary searches over $$$b$$$

The overall complexity is therefore $$$O(\max(n\log n, q\log n))$$$.

Original problem: 2005B2 - The Strict Teacher (Hard Version), leads to official tutorial and all solutions including WS solution: 302489261

Editorial for [contest:582534].

[problem:582534a]

For a given $$$h$$$, we can compute $$$w$$$ as $$$w(h)=\sum_{i=1}^n \max(h-a_i, 0)$$$. For the following, assume that $$$a$$$ is sorted.

For any $$$h<a_1$$$, $$$w(h)=0$$$. With the given bounds, $$$1\le n\le 2\cdot 10^5, 1\le x\le 10^9, 1\le a_i\le 10^9$$$, the maximum $$$h$$$ is $$$2\cdot 10^9$$$.

Now that we have the lower and upper bounds for $$$h$$$, and noticing that $$$w(h)$$$ is non-decreasing, we can do a binary search over the range of values of $$$h$$$ to find the value at which $$$w(h)$$$ just exceeds $$$x$$$. The answer is then one less than that value.

If $$$H$$$ is the size of the range of possible values of $$$h$$$, then the complexity of this solution is $$$O(\log H)$$$, determined by the binary search.

Original problem: 1873E - Building an Aquarium, leads to official tutorial and all solutions including WS solution: 276080524

[problem:582534b]

After climbing the $$$i$$$-th step, the height that is reached is $$$h_i = a_1+a+2+\ldots+a_i$$$. In order to climb the $$$i$$$-th step, the shortest required leg length is $$$m_i = \max(a_1,a+2,\ldots,a_i)$$$.

Given the array, $$$a$$$, we can compute the arrays $$$h$$$ and $$$m$$$ as above, each in $$$O(n)$$$ time. Note that $$$h$$$ and $$$m$$$ are non-decreasing. Given a leg length, $$$k$$$, we find the maximum leg length in $$$m$$$ that is equal to or less than $$$k$$$. That is, $$$i=\max_j m_j\le k$$$. This can be found in $$$O(\log n)$$$ time using binary search. If no such $$$i$$$ exists, i.e. $$$k < m_1$$$, then the answer is 0, otherwise the reached height is $$$h_i$$$.

The complexity of this solution is $$$O(n + q\log n)$$$ determined by the computation of $$$h$$$ and $$$m$$$, and by the binary search for each of the $$$q$$$ queries.

Original problem: 1742E - Scuza, leads to official tutorial and all solutions including WS solution: 269560517

[problem:582534c]

Let's sort $$$a$$$ and let $$$s$$$ be its sum. Then we have that $$$ x \le s - a_i - a_j \le y$$$ and $$$s-y \le a_i + a_j \le s-x$$$. Note that $$$i$$$ and $$$j$$$ are distinct. For any $$$i$$$, we have to find all values of $$$j$$$ such that $$$s-y-a_i \le a_j \le s-x-a_i$$$. As $$$a$$$ is sorted, this can be done with 2 binary searches.

In order to avoid double counting, the search should only be performed on $$$a_{i+1}, a_{i+2},\ldots,a_n$$$.

The complexity of this solution is determined by

• the sorting of $$$a$$$ which takes $$$O(n\log n)$$$ time, and
• the binary searches for each $$$a_i$$$, which totals to $$$O(n\log n)$$$.

Altogether, the complexity is $$$O(n\log n)$$$.

Original problem: 2051D - Counting Pairs, leads to official tutorial and all solutions including WS solution: 302196583

Editorial for [contest:581634]

[problem:581634a]

Output the element in the matrix which occurs only twice.

Original problem: 1915B - Not Quite Latin Square, leads to official tutorial and all solutions including WS solution: 277700626

[problem:581634b]

Raze wins if the last unmarked digit is odd. So Raze's optimal strategy is to mark all even digits before marking odd digits. Breach wins if the last unmarked digit is even. So Breach's optimal strategy is to mark all odd digits before marking any even digits.

If $$$n$$$ is odd, then the last unmarked number will be in an odd position, i.e. in a position that only Raze can access. Raze can win if there is at least a single odd digit among the odd positions. Raze can take care to leave this number unmarked till the end. If there is no odd digit among the odd positions, i.e. all the digits in the odd positions are even, then the last unmarked digit is even and Breach wins. So, if $$$n$$$ is odd, Raze wins if there is at least one odd digit among the odd positions, otherwise Breach wins.

Similarly, if $$$n$$$ is even, then Breach wins if there is at least one even digit among the even positions, otherwise Raze wins.

Original problem: 1419A - Digit Game, leads to official tutorial and all solutions including WS solution: 300911809

[problem:581634c]

We can imagine the position of the queen defining 4 quadrants: each comprising of positions above-left, above-right, below-right, and below-left of the queen. Some quadrants may be empty if the queen is at an edge or corner. The king can reach the destination only if its position and the destination position are in the same quadrant. Otherwise, it will have to change quadrants which it cannot do without going into check.

Original problem: 1033A - King Escape, leads to official tutorial and all solutions including WS solution: 300913056

[problem:581634d]

The string, $$$a$$$, comprises three letters, A, B, and C. For $$$a$$$ to be balanced, the first letter and last letter in $$$a$$$ must correspond to ( and ) respectively. If these letters are the same, the string is not balanced.

Further, for $$$a$$$ to be balanced, the count of the third letter, i.e. the letter that is not the first or last in $$$a$$$, must be equal to the absolute difference of the counts of the first and last letters. If this is not the case, the string is not balanced.

One way to find the third letter is as follows. In $$$a$$$, replace A with 0, B with 1, and C with 2. Then if the integer values of the first and last letters are $$$F$$$ and $$$L$$$, then the integer value of the third letter is $$$3-F-L$$$.

Further, for $$$a$$$ to be balanced, the third letter corresponds to ( if the count of the first letter in $$$a$$$ is less than the count of the last letter. Otherwise, the third letter corresponds to ).

Now that we know the brackets corresponding to all three letters, we determine whether $$$a$$$ represents a balanced bracket sequence, e.g., using a stack.

Original problem: 1494A - ABC String, leads to official tutorial and all solutions including WS solution: 301131398

[problem:581634e]

The number of layers is $$$\min(m,n)/2$$$.

We can use index calculations to determine the corners of each layer. It helps that layers are symmetric horizontally and vertically. We unravel a layer into a string $$$s$$$ as follows. Starting from any position in the layer and traversing the layer in clockwise order, assemble all the encountered digits into a single string, $$$s$$$. We then count the number of occurrence of the string 1543 in $$$s$$$.

We need to take care to also check if unraveling a layer has split an occurrence of the string 1543 into different ends of $$$s$$$.

Original problem: 2036D - I Love 1543, leads to official tutorial and all solutions including WS solution: 289530642

Editorial for [contest:581467]

[problem:581467a]

We traverse the cells in the grid from left to right and top to bottom. A lake can be identified through a dfs on all cells with non0zero value. Take care to convert each visited cell to 0, so that it does not get revisited once it has been counted.. Output the maximum sum over all the lakes.

Original problem: 1829E - The Lakes, leads to official tutorial and all solutions including WS solution: 275432569

581463A — Mr. Perfectly Fine

Each $$$s_i$$$ can only be 00, 01, 10, or 11, corresponding to the decimal values, $$$0, 1, 2,$$$ and $$$3$$$. We can treat these as indexes in an array $$$a$$$ of size $$$4$$$. Index $$$1$$$ corresponds to learning skill 1, index $$$2$$$ to skill $$$2$$$, and index $$$3$$$ to both skills. Each index is initialized to $$$\infty$$$, meaning the skill is not learned yet, and is minimized with $$$m_i$$$ whenever the corresponding $$$s_i$$$ is read. Index $$$0$$$ can be ignored. Once all inputs are read, we check $$$a_3$$$ and $$$a_1+a_2$$$. If both are infinity, then no skill has been learned and we output -1. Otherwise, we output the minimum of $$$a_3$$$ and $$$a_1+a_2$$$.

Original problem: 1829C — Mr. Perfectly Fine, leads to official tutorial and all solutions including WS solution: 276753145

580448A - Robin Helps

We have to count the number of $$$0$$$s in $$$a$$$ that Robin encounters while he has gold. Robin's gold starts at 0, decrements for every $$$0$$$ encountered, but doe snot become negative, and increases by $$$a_i$$$ whenever $$$a_i\ge k$$$.

Original problem: 2014A - Robin Helps, leads to official tutorial and all solutions including WS solution: 282393143

580448B - Card Game

There are always 4 different ways in which the game can proceed. These can be brute-forced.

Original problem: 1999B - Card Game, leads to official tutorial and all solutions including WS solution: 274876674

580448C - Challenging Valleys

We record $$$l$$$, the starting index of the last valley, and $$$r$$$, the ending index of the first valley. If there is only one valley, then $$$a_l=a_{l+1}=a_{l+2}=\ldots=a_r$$$.

Note that every $$$a$$$ has at least 1 valley, so we will always find one $$$l$$$ and one $$$r$$$.

Original problem: 1760D - Challenging Valleys, leads to official tutorial and all solutions including WS solution: 269613934

580448D - Email from Polycarp

We can look at consecutive runs of letters in $$$s$$$ and in $$$t$$$. For positive output, the number of runs in each must be the same, and for each run, the letters in $$$s$$$ and $$$t$$$ must match, the length of the run in $$$t$$$ must be no less than that in $$$s$$$.

Original problem: 1185B - Email from Polycarp, leads to official tutorial and all solutions including WS solution: 247606625

580448E - Permutation Transformation

We can approach this problem recursively. This is feasible because $$$n$$$ is small, $$$1\le n\le 100$$$, so the recursion limit will not be encountered.

We maintain a separate array, $$$b$$$, of size $$$n$$$. Given indexes $$$i, j$$$ and depth, $$$d$$$, we find the index, $$$k$$$, of the maximum element in $$$a[i:j]$$$ (python slice indexing), set $$$b[k]=d$$$, and recurse for the subarrays to the left and right of index $$$k$$$. Recursion stops when the subarray contains a single element. For the first call, $$$(i, j, d) = (0, n, 0)$$$.

Original problem: 1490D - Permutation Transformation, leads to official tutorial and all solutions including WS solution: 258828754

[problem:580948a]

We only need to check $$$a_i, b_i, c_i$$$ for each $$$1\le i\le n$$$. We guess $$$t_i$$$ based on $$$a_i$$$ and $$$b_i$$$. If, for any $$$i$$$, there is a mismatch between $$$c_i$$$ and $$$t_i$$$, the output is YES, otherwise, it is NO.

There are 2 cases, each with its subcases.

• $$$a_i \ne b_i$$$
  • $$$t_i$$$ must be $$$X$$$ where $$$x \ne a_i$$$ and $$$x \ne b_i$$$. To mismatch, $$$c_i$$$ must be $$$x$$$, i.e. $$$c_i !\ne a_i$$$ and $$$c_i \ne b_i$$$
• $$$a_i = b_i$$$
  • $$$t_i$$$ may be $$$X$$$ where $$$x \ne a_i$$$ and $$$x \ne b_i$$$. To mismatch, $$$c_i$$$ must be $$$x$$$, i.e. $$$c_i !\ne a_i$$$ and $$$c_i \ne b_i$$$
  • $$$t_i$$$ may be uppercase $$$A_i$$$ (note, $$$a_i=b_i$$$ in this case). To mismatch, $$$c_i$$$ must be different from lowercase $$$a_i$$$, i.e. $$$c_i !\ne a_i$$$ and $$$c_i \ne b_i$$$.

In all cases, for $$$c_i$$$ to mismatch, it must be that $$$c_i !\ne a_i$$$ and $$$c_i \ne b_i$$$.

Original problem: 1922A - Tricky Template, leads to official tutorial and all solutions including WS solution: 300910838

581466A - Preparing for the Exam

We identify 3 cases for $$$k$$$.

• $$$k=n$$$. Monocarp passes the exam for all question lists.
• $$$k < n-1$$$. Monocarp does not pass the exam for any question list.
• $$$k == n-1$$$. There is one question, $$$q$$$, for which Monocarp does not know the answer. He will pass the exam for list $$$i$$$ only if $$$a_i=q$$$.

Original problem: 2051C - Preparing for the Exam, leads to official tutorial and all solutions including WS solution: 301141282

I learn a lot by looking at other people's solutions. It will be great if I can show my appreciation of some solution, e.g., by starring it. We can already upvote comments and blog entries, and star users. Something like that will be nice for solutions. It will also serve as encouragement to users who write good solutions.