another approach for B is that we can round DOWN the value at each index to the closest power of 2. Then just print the array. Although it was a tougher contest than usual, as far as i know.

Let x[i] = log2(a[i])

then b[i] = 2^x[i]. It can be prove that sum of all 2*|a[i] — b[i]| always <= S

This problem can be extend to k*|a[i] — b[i]| <= S. It will be so funny XD

Maybe you can have a look at my code. It is easy to understand I think.

Yes. For example, we can print 2^k, where k = floor(log2(Ai)) for each i.

My submission: https://codeforces.com/contest/1463/submission/101614243

Proof: At first, if each b[i] is a power of 2 the first condition will be done. Let's prove the second condition will be done too. It means that b[i] >= ceil(a[i] / 2) for each i. If b[i] is equal to 2^k, where k = floor(log2(a[i])) the second condition will be done as well. Let's say x = a[i] = 5. It's 101 in binary representation. y = b[i] = 4. It's 100 in binary representation. Then, x / 2 = 5 / 2 = 101 >> 1 = 010 = 2. After the operation the highest bit in x / 2 will be equal to 0, but at the same time it's equal to 1 in y. Hence, y > x / 2. We have proved it.

Here's a different solution which I think is a little more simple, (my code 101560737)

You can alternate between taking the number in A and taking 1. So your array B The intuition is that will look like this: B = [ a, 1, a, 1, a ... ]

The differences will be, A — B = [0, a-1, 0, a-1, 0 ....]

although it may happen that the difference is bigger if you take the zeros when a_i is a big number.

However we can prove that by taking zeros on either the even indices or the negative indices, we get a sum of at most S/2 (S being the sum of all elements in A)

[0, a-1, 0, a-1, 0, a-1 ... ] + [a-1, 0, a-1, 0, a-1, 0 ... ] = [a-1, a-1, a-1, a-1, a-1, a-1 ...]

The sum of all the differences will be: S-n (where n is the number of elements in A)

This means that on average, if we use this method we will get a sum of differences of (S-n)/2. To guarantee a correct answer we can use this method with even indices and odd indices, calculate our score, and choose the one which is lower.

very nice video editorials !!

Now I want you to answer a question which is probably the most asked question in history of codeforces.

How to become an orange coder ? What exact path or strategy we can follow ?

Although many coders have answered such questions but it is always beneficial to listen 1 more time.

Suggestion: It would be good to find the find the links of the problem and solution in the you tube description area.

tidy solution! Can someone explain this approach?

Consider the prerequisite edges marked as 0 and special pairs as edges marked as 1.

if a single vertex has more than one edges marked as 1 outgoing or incoming than it's not possible to find an ordering. Moreover, the graph should not contain any cycle.

After checking this we can first group all the edges marked as 1 they will form a simple path, compress all the vertices to a single vertex and assign it as a parent of all vertices. Also keep the ordering of vertices for that component.

Now add the edges marked as 0 in the new graph between parent of vertices, if both have different parent add the edge else we can ignore that cause we already checked for cycle. After this topsort the graph, if it is not possible than answer is zero else find the topsorted list will give a valid ordering. Print them by iterating through every vertex list that we found in the compression stage. my code

d should be sum/9 and also you have to use '&&' instead of '&'

It turns out that, given the lemma from the editorial (there exists an optimal string with period $$$x+y$$$), this problem can be solved in $$$O(x+y)$$$ time.

First, if $$$g = \gcd(x,y) \ne 1$$$, we can split the problem up by mod $$$g$$$, because all edges connect two things that are separated by $$$x$$$ or $$$y$$$, which are multiples of $$$g$$$. Thus, we can assume $$$\gcd(x,y) = 1$$$.

The key thing to observe is that all edges span $$$\pm x$$$ modulo $$$x+y$$$. Because of the lemma, we can merge all nodes with the same residue mod $$$x+y$$$ to get $$$x+y$$$ super-nodes. Furthermore, because the edges are exactly the changes by $$$\pm x$$$ mod $$$x+y$$$, and we assumed $$$\gcd(x,y) = 1$$$, these supernodes form exactly 1 complete cycle. Then, instead of doing the DP in $$$1 \ldots x+y$$$ order, we can use the order of this cycle ($$$x, 2x, 3x, \ldots \pmod{x+y}$$$). This means our DP only needs to track whether we took the first element and whether we took the latest, so there are only $$$4(x+y)$$$ states.

Disappointedly not a decent explanation. Where understanding is so tough, there solving is just a fun

Consider the following test case: Your first command on $$$t = 1$$$ is to go to $$$x = 10^9-1$$$. It will arrive on $$$t = 10^9$$$. Then the second and last command is on $$$t = 10^9$$$ (which the robot won't ignore as it's not moving anymore), to go to $$$x = -10^9$$$. You can see it will take $$$\left|(10^9-1)-(-10^9)\right| = 2\cdot10^9-1$$$ units of time to get there. Therefore, it will arrive at $$$t = 3\cdot10^9-1$$$.

Both commands are successful, while your code will only tell the first one is successful, as your variable mmm which you add at the end of the list of commands in what it seems to be a "dummy" element, is only equal to $$$10^9+5$$$, restricting your time range and therefore calculating incorrectly the range of positions where the robot would pass, and by so not counting the last command as successful. Increasing that value to $$$3\cdot10^9$$$ should fix the issue, but of course by doing that you may have to be careful and work with long long variable types.

Can you tell me how do you understand it? I've reread the last paragraph of the legend a hundred times and still have no idea how can you interpret it other than the intended way...

We were getting questions about it during the contest, I was answering "The robot should visit $$$x_i$$$ at some moment between $$$t_i$$$ and $$$t_{i+1}$$$" and the people seemed to be getting it and not returning with more questions, but I literally see no difference between the statement and that...

It's true. I think it's not necessary to find the order of the vertices inside each component by sorting, as you can just have for each lecture, the previous and next lecture in each of the components of special pairs, and reconstruct in linear time from each component after the topsort. Then you would just check if no lecture which should be a prerequisite is given after the one you're checking in the ordering, and thereby determine if no answer exists or that it does and you have to print the solution.

At least with that I could also pass the tests with an almost $$$\mathcal{O}\left(n\right)$$$ solution (just used a set for counting components, but can easily be replaced with something that also works in linear time... 101592299).

The statement clarifies: " i. e. after some enhanced shot, the health points of each of the monsters should become equal to $$$0$$$ for the first time ".

In your test case and the way you've shown of killing the monsters, you can see that the second monster gets killed (health points drops to $$$0$$$) after the 7th movement while the others haven't yet. You can prove that there's no way of fulfilling this condition in that test case.