I believe it was because there was a codechef starters at the same time. I also remember the cc admin saying "we are discussing the clashing of the dates with codeforces".

problems*

So, this was said sarcastically?

You got downvotes for your previous comments

Problem D is actually even easier, you don't need any range data structures.

If you have $$$k$$$ open APs which together add a sum $$$s$$$ to some position $$$i$$$, when moving to $$$i - 1$$$, it will add a sum $$$s - (k - start_{i})$$$ where $$$start_{i}$$$ is the number of APs which start at $$$i$$$.

So by just storing the number of APs starting from a point (which can be trivially set when we add a new A), we have all the information we need to just simply solve it with a single iteration.

Submission — 153184495

How can you solve D with this technique from Polynomial Queries? I have an AC on CSES and honestly, I don't know how to use it here

Why ??

Don't forget A — cringe ;)

and cringe E (indeed)

I thought it was a segment tree problem, but my implementation was too buggy to finish it in contest time :(.

It can be done with a segment tree. For a range you should store the number of components in it and the connectivity information among its six vertical border cells. These are enough to merge two adjacent ranges.

What's the solution? i tried using binary search initially to find minimum required days

You can do the operations greedily from right to left.

Create a from the end.

collecting smaller elements in one array, and bigger elements in another array, because |ai — aj| must be minimum

Yeah i saw my friend doing it that way !

Just a bfs problem using reverse edges

Hints :

• 32768 is 2^15

• Max Probable Operation : 15

We can put the number of operations needed to make each number $$$i$$$, $$$1\text{ to }32768$$$ by using the second operation, $$$(2\times i)\text{ mod }32768$$$, in an array, $$$ans[\text{ }]$$$ . Then calculate if there is any number $$$j$$$ such that $$$j-i$$$ $$$+ans[j] $$$ $$$<$$$ $$$ans[i]$$$.If there is then print $$$\text{MIN}(j-i + ans[j],\text{ 32768}-i)$$$ otherwise $$$\text{MIN}(ans[i],\text{ 32768}-i)$$$.

Try to make the height of all trees be 3

Water the tree with height 2 on day 1 so you can do something on the even days.

On day 1 , water the tree of height 2 , so new array becomes => [ 1 , 1 , 1 , 1 , 1 , 1 , 3] ,On day 2 , water the tree of height 1 , so new array becomes => [ 3 , 1 , 1 , 1 , 1 , 1 , 3] ,On day 3 , water the tree of height 1 , so new array becomes => [ 3 , 2 , 1 , 1 , 1 , 1 , 3] ,On day 4 , water the tree of height 1 , so new array becomes => [ 3 , 2 , 3 , 1 , 1 , 1 , 3] ,On day 5 , water the tree of height 2 , so new array becomes => [ 3 , 3 , 3 , 1 , 1 , 1 , 3] ,On day 6 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 1 , 1 , 3] ,On day 7 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 2 , 1 , 3] ,On day 8 , water the tree of height 1 , so new array becomes => [ 3 , 3 , 3 , 3 , 2 , 3 , 3] ,On day 9 , water the tree of height 2 , so new array becomes => [ 3 , 3 , 3 , 3 , 3 , 3 , 3]

Someone please say how to solve 3rd case in 1st test case in 16 days as well.

Thank you for your replies Bungmint, robostac, helios_

They didn't say we always have to make everything equal to max element of array. Just extra check for max_element + 1 would have passed all testcase . I got this intution by this example which i created during contest Hope it help you.

Testcase Example — 1 1 1 1 1 1 1 1 1 2 (Instead making everything 2 make everything 3) Making everything 2 will cost 17 days while making 3 will cost 13 days . I was so happy when i found it during contest and got Ac.

memset is o(n) and you do it t times

It is easier than it

I did not find a counterexample for my submission. My submission id 153253105 ticket 4346

I have linear solution

great solution :3

Just that will suffice. The rest is figuring out the best way to water the plants (how to properly distribute the 1's and 2's)

I upsolved it in the following way. There will be a max of 15 operations because applying the second operation 15 times will make the given number a multiple of 2 ^ 15. Also, all the manageable addition operations should be done initially. The second operation will shift the bitmask of the given number and doing the first operation on the shifted bitmask will take more cost than it is taking while doing those operations initially. Brute force over the initial addition operations up to 15 and then brute force over the second type of operations 15 times and then add whatever is needed to reach the end i.e 2 ^ 15.

Nice!

max(h) + 2 isn't a possible candidate because if all the trees could reach that height, they would have been able to reach max(h) in less time. The mathematical proof is prolly a more general version of this idea.

If value of a1 is equal to 0 your while loop will enter into an infinite loop.

It was translated from another language, I'm sorry if something is unclear. note that we do not necessarily want to make everyone equal to the current maximum, sometimes it is a maximum of + 1. For example, 2 1 1 1 1 1 1 1 1 is faster to lead to the form 3 3 3 3 3 3 3 3 3, than to 2 2 2 2 2 2 2 2 2 also note that > max + 1 is obviously bad (instead of increasing each by 2+ from the current maximum, we could just not do it) then we will separately solve the problem for max and for max + 1 and take a smaller value as we solve: alternately, we look at the current growth of the tree and if it needs to be grown to an odd height, we add 1 to CNT 1 — the minimum of operations + 1 that we will have to perform, otherwise it will not be possible to grow the tree to an odd height

for now, we will assume that we will do all the rest of the height +2, we will write the number of such operations in cnt2

that is, the height of the tree 3 that we want to grow to 10 will add 1 to CNT 1 and 3 to cnt2 (1 + 3*2 = 7)

now if cnt1 = cnt2 — the answer is 2 * cnt1 (we do 1 2 1 2 1 2 1 2 1 2, no day is missed, so it can't be more effective)

if cnt1 > cnt2, then the answer is 2 * cnt1 — 1 In short, it will not work, cnt1 tc (we do 1 2 1 2 1 2 1 _ 1 _ 1) — cnt1 is the minimum of operations that we have to do

if cnt2 > cnt1, then the intuitive solution looks like this 1 2 1 2 _ 2 _ 2 _ 2. And we can improve this by replacing some 2 with 1 1

let the sum = cnt1 + 2 * cnt2 — how much height we have to add to the trees.

Then if the sum is divided by 3 — obviously the most effective scheme 1 2 1 2 1 2 1 2 1 2 answer = sum // 3 * 2

If the remainder of the division = 1, then 1 2 1 2 1 is the sum // 3 * 2 + 1

if the remainder of the division is 2, then 1 2 1 2 1 2 _ 2 In the latter case, it will definitely not be shorter, since without the last two we will not reach the sum of the answer sum // 3 * 2 + 2

You don't need a segment tree. Your idea will be $$$O(n^2)$$$ if you apply your additions to all $$$k$$$ values at once. Don't do this, this can be done more efficient! Remember how often you applied the addition at positions $$$i+1$$$, $$$i+2$$$, ... $$$i+k-1$$$. Let this be $$$m$$$ additions and their total sum at the moment for position $$$i$$$ is $$$S$$$. When you go from $$$i$$$ to $$$i-1$$$, $$$S$$$ will decrease by $$$m$$$.

I guess this can be quite confusing, compare 153239645 the values q, element and sum and only consider the case i >= k - 1 at first.

It returned early: if(now==0) return dist[now]; So to hack it we should find the last number that is reachable.

4037 is the best to hack, but still fail. Because of early return, the most iteration cnts will be 4146

check diagnostics