I wish too.

When Codeforces is top priority

Me too :). Good luck to everyone hoping to change color!

B > C > D

I agree

B>D>C

Bro, I'm your fan

E<A

me who builded a segment tree on D for no appearant reason

There are 2 equivalent worst-case lightning strikes.

Here is the test case: 2 1 5 6 4 3

First example:

• 8 damage onto 6
• 7 damage onto 5
• 6 damage onto 1
• 5 damage onto 2
• 4 damage onto 4
• 3 damage onto 3

Notice the damage toward the end is exact so you can't do better than 8. The other worst case is:

• 8 damage onto 6
• 7 damage onto 4
• 6 damage onto 3
• 5 damage onto 5
• 4 damage onto 1
• 3 damage onto 2

Again, we have exact damage at one point, so we can't do better.

EDIT: Fixed bad formatting.

yeah I was also getting 7 as the output. as we can move from 6->5->4->3->1->2. Here 7 looks like optimal ans

Suppose you start by hitting the 6 HP monster, and the following happens:

• hit 6 HP monster with 7 dmg

• hit 5 HP monster with 6 dmg

• hit 1 HP monster with 5 dmg

• hit 2 HP monster with 4 dmg

• hit 4 HP monster with 3 dmg

• hit 3 HP monster with 2 dmg

The last monster lives.

If you pick any monster further left as the starting point, the 3 HP monster lives in some scenario. If you pick any monster further right as the starting point, the 2 HP lives in some scenario.

Because...a power of $$$7$$$ isn't enough to kill all monsters? Why do you think it is enough? Remember that you can only choose the starting monster, you can't affect the order they're killed in after that.

I was trying to solve D with BS, Is there a BS solution for D?

The same to me

https://codeforces.me/contest/1901/submission/234100259

Fix some position of $$$k$$$, then find the lowest possible damage a monster at each position could receive.

For $$$k=1$$$, the first monster receives at least $$$x$$$ damage, the second at least $$$x-1$$$, the third at least $$$x-2$$$, and so on.

For $$$k=2$$$, the first monster receives at least $$$x-n+1$$$ damage (when only the last lightning strike hits it), the second receives at least $$$x$$$ damage, the third receives at least $$$x-2$$$ (in the worst case, the second lightning strike hits the first monster, and the third strike hits the third monster), and so on.

Now you'll find a pattern:

• For $$$i<k$$$, the minimum damage dealt is $$$x - n + i$$$ (zero indexed)

• For $$$i=k$$$, $$$x$$$ damage is dealt

• For $$$i>k$$$, the minimum damage dealt is $$$x+1-i$$$

So for any $$$k$$$, the minimum $$$x$$$ required is $$$\max(\max_{i<k}(a_i+n-i), a_k, \max_{i>k}(a_i - 1 + i))$$$. You can use prefix and suffix maximums to compute this for all values of $$$k$$$ and return the minimum answer.

An edge is incident to a node if that node is one of the edge's endpoints.

These terms should be defined in the statement imo. Also, authors can use more familiar terms, like "degree", which should also be defined

D maybe, but not C

B:

When a teleportation happens, there is a source and destination. My approach was to count how many source teleportations are required and how many destination teleportations are required.

For each $$$i$$$ in which $$$c_i > c_{i - 1}$$$, there must have been $$$(c_i - c_{i - 1})$$$ teleportations with destination $$$c_i$$$. Add that to the destination count.

For each $$$i$$$ in which $$$c_i < c_{i - 1}$$$, there must have been $$$(c_{i - 1} - c_i)$$$ teleportations with source $$$c_{i - 1}$$$. Add that to the source count.

Furthermore, add $$$c_1 - 1$$$ to the destination count, and also add $$$c_n - 1$$$ to the source count. Return the maximum between source and destination counts.

C:

Consider when there are two distinct values $$$a$$$ and $$$b$$$. No matter which value of $$$x$$$ you pick, the difference between $$$a$$$ and $$$b$$$ reduces to either $$$\left\lfloor\frac{b - a}{2}\right\rfloor$$$ or $$$\left\lfloor\frac{b - a}{2}\right\rfloor + 1$$$. The former is optimal and can be achieved by simply choosing either $$$a$$$ or $$$b$$$ as your $$$x$$$.

If you have more than two distinct elements, all you need to do is ensure that the smallest and biggest values coincide, and this guarantees that all other values will coincide too. Simply find the difference between the largest and smallest elements, and then return the number of bits in the binary representation for this difference.

my solution was if the max element in the array is even and the min element in the array is odd we choose 1

else we choose 0

we keep doing this until the array become equal

If the parity of the max element and the min element is same it doesn't matter what you choose, the difference will be halved anyways, as the difference would be even too.

Otherwise, the difference is odd and so it is better to choose 1 if min element is odd and choose 0 if its even. You can infer the same wrt max element in this case.

Assuming that you're talking about this submission: 234119469

Notice how you printed an extra $$$5$$$ for the first test case even though the number of operations was $$$0$$$. The contest system thought that this $$$5$$$ was your number of operations for the second case (it was the next token in the output file) and $$$5 > 2$$$ so the verdict is WA.

what do you think the rating for problem E is ?

Are you talking about problem C? If yes, you probably missed the part where it said rounding $$$y$$$ down to the nearest integer. We're rounding down and the nearest integer below $$$1.5$$$ is $$$1$$$, not $$$2$$$.

What is the logic behind choosing x = min? I always chose x = 0 or x = 1.

Wow, good job

WOW but it seems your code is semi-complicated while the solution is each time x = max_number + 1

because, (x+x+1)/2 = x while (x+x+2)/2 = x+1 so what ever happened all numbers will not exceed max_number and make the min_number be equal to max_number you can check my submission 234086134

That's why I use

#define int long long

I know it's bad practice but I've made that mistake way too many times.

" very balanced round in recent months "

Problem D: 1987

Problem E: 255

Its decreasing by 10. Ideally it should decrease by 2 on each step to be balanced.

When x=0 and y=1 you get infinite loop which allocates large amount of memory

for test n = 7 a = {5, 5, 5, 4, 4, 4, 4} your solution return 11 but right answer is 10

That greedy solution you are talking about? Probem B is: we have array $$$a_1,a_2,\ldots,a_n$$$. Find minimum number of following operations we have to do to make array all zeroes. Operation is take a subsegment $$$[l,r]$$$ and decrease all values by $$$1$$$.

It's easy to proof that if we use our operation on segment $$$[l,r]$$$ and can use it on segment $$$[l', r'] (l' < l, r < r')$$$ we should use it on segment $$$[l', r']$$$.

Take a look at Ticket 17155 from CF Stress for a counter example.

What if there are multiple monsters with highest health?

Also try this case

7
3 1 4 2 2 2 2

If you start with 3, the minimum power is 8 If you start with 4, the minimum power is 9

Check out this test:

8
1 11 1 1 12 1 1 1

Here, if we choose the monster with 12 health we need x = 17, but if we choose to start from the monster with health 11 we only need x = 16.

We can't choose the monster with 12 and have x = 16 because we kill that monster and all monster to the right and our power decreases to 12, we kill the monster to the left of it with 12 and we get to 11, we kill the left monster again and we are down to 10, this is less than what we need to kill the monster with 11 health.

If you start at index 4 with power 7 you than kill the index 5 with power 6 and the index 6 with power 5, now you don't have enough power left to kill the monster at index 4. Remember, since the monster killed is chosen randomly between the 2 options possible (or 1 if there are no 2 possible options), you have to account for the worst case scenario. Sure, power 7 would've worked if you killed index 3 first, then the indexes >4 and than the indexes <3, but that's only one case, we have to account for all possible cases.

just wait for a few days and it will change.

When will we get the editorials and ratings change BledDest/awoo? Thank you.

I hope so. I should become green (Im trusting carrot).

Take a look at Ticket 17158 from CF Stress for a counter example.

Can anyone provide information? Pls