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.

Islands can be created while running. For example

2 4 4 3 5

Let's say you start by removing 1 from all :

1 3 3 2 4

remove min from all and add to answer

0 2 2 1 3

ans = 1

Your answer would then be to add 3 to this (return ans = 4) But if you run the algorithm, after a pass you're going to end up with :

0 1 1 0 2

ans = 2

Problem here is you created a new island that you didn't account for, so the answer would be 5, not 4 !

You had to take care of the case when you start descending (4 -> 3 in original array) and then you start ascending (3 -> 5 in original array)

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

The same to me

Without a single hope for something good, I solved problem C on the 18th attempt

https://codeforces.net/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.

Just always choose min value.

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 ?

In problem E,what is the highest node in the tree?And what do we return as the answer?

In problem D, you are under-estimating the actual amount of damage monsters will take. How are you sure that would yield a correct answer?

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$$$.

Did this, but was getting some TLE so added some ugly heuristics to try and make it work. I'm really bad at C++ apparently ahhhhh. Welp thanks for confirming at least that my idea was sound !

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

I just tested with some cases by choosing min and it seems to be correct, plus there was just about only less than a minute left (and I couldn't make it in time as in my comment).

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

Wow, good job;

For me, it was D > B > C > A. C came intuitively to me and I found D much harder.

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.

can you explain your answer?

" 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

For first move, you will need a[1]-1 moves always

you can always move to A[i] from A[i-1] if A[i]<=A[i-1] without Teleporting

But if A[i]>A[i-1] you need to Teleport A[i]-A[i-1] times

Ans can be

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.