582924A - Card Constructions

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

582924B - Frog Jumps

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

582924C - Dungeon

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

582924D - Worms

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

582924E - Recursive Queries

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