Here for a nice explanation by iica

Search about diofantic equations.

Goal : check if there is at least k red cells in between two consecutive blue cells

Extended Euclidean Algorithm : a*x + b*y = gcd(a,b)

so , in our case we can write : r*x - b*y = g (say, g = gcd(r,b) )

that is , r*x = b*y + g

which implies , for any pos = b*y colored blue , we have (pos + g) colored red

(here , two consecutive blue cells pos and pos+b)

generally , we have to use color red for these (m+1) cells :

pos+g ,pos+g+r , pos+g+2r , pos+g+3r , ....... (pos+g+m*r)

where , m>=0 and (pos+g+m*r)<(pos+b) ==> (g+m*r)<b

if (g+m*r)<b && m == k-1 , then we have at least k red cells in between (pos,pos+b)

so rebel, if (g+(k-1)*r)<b ; else obey

why are we diving r and b with GCD(r,b) somebody please explain in turorial its written very shortly someone plzz explain

You know, if b is very large, the answer is REBEL, because there are too many planks between plank pos and plank pos+b. And if b is small enough, you have to paint only few planks between pos and pos+b, then the answer is OBEY.

As editorial says, what we are concerned about is whether it will happen or not that there are too many planks between pos and pos+b. Here "too many" means "if you paint pos+1 in red, your k'th red plank comes before next blue plank pos+b".

This is like, if a=3 and k=5, red planks are [pos+1, pos+4, pos+7, pos+10, pos+13]. Thus you must worry if pos+13 < pos+b or not. This "13" comes from (5-1)*3+1 (see this figure below).

1  2  3  4  5
#..#..#..#..#

In general, if (k-1)*r+1 < b, it means in the worst case (like above) you will have k (or more) red planks between blue planks, then the answer is REBEL. If not, it means in any cases next blue plank comes before your k'th red plank, then the answer is OBEY.

Because, at every step we select some random integer x. Then either we subtract x from a and 2x from b or vice versa. So at every step we are subtracting (x + 2x) or 3x from a + b. So, at some step to get both values of a and b to be zero we have to have sum of initial value of a and b a multiple of 3 otherwise it won't happen. Thats why (a + b) mod 3 must be 0.

My solution. Denote x as the number of time to subtract 2 from a and subtract 1 from b, y as the number of time to subtract 2 from b and subtract 1 from a, then:

It's easy to make it simple:

Because $$$x\geq 0$$$ and $$$y\geq 0$$$, so we should have $$$2a-b\geq 0$$$ and $$$2b-a\geq 0$$$

if 2*a >= b is false, then b is more than twice as big as a, even if you always remove 2x from b until it is zero then you must subtract half of b from a, which would make a negative (b>2*a => b/2>a). In the editorial the author swaps a and b so that b is always the biggest number, this way he just has to check for 2*a > b, and not 2*b > a as well.

Let $$$x_1, x_2, ..., x_k$$$ be the numbers you use so $$$a := a - x$$$ and $$$b := b - 2x$$$ was done some time in the "process" of turning $$$a$$$ to $$$0$$$ and $$$b$$$ to $$$0$$$. Also, let $$$y_1, y_2, ..., y_m$$$ be the numbers you use so $$$a := a - 2y$$$ and $$$b := b - y$$$ was done some time in the "process" of turning $$$a$$$ to $$$0$$$ and $$$b$$$ to $$$0$$$.

Notice that at the end we get:

Or...

Let $X = x_1 + x_2 + ... + x_k$ and $$$Y = y_1 + y_2 + ... + y_m$$$. Interesting observation: this means that you only need to do at most one operation of the first or second type, with the number used being the sum of all the other numbers. Then:

Substituting $X = a - 2Y$ from the first into the second equation and simplifying, we get:

Since $Y \geq 0$, $$$2a - b \geq 0$$$, so $$$2a \geq b$$$. Also, from here, you can get $$$X$$$. You only need to check that $$$X \geq 0$$$ and $$$Y \geq 0$$$.

and me being an absolute non java coder — which are the two lines to read ?

Wow,can you please explain your solution?

Can you please explain the reasoning behind this approach ? How does this greedy work ?

Anyone explain A

Think of the problem this way. You have some numbers $$$a_1, a_2, \ldots, a_c$$$, where $$$a_i \geq 0$$$, and $$$a_1 + a_2 + \ldots + a_c = sum$$$. You need to minimize $$$a_1^2 + a_2^2 + \ldots + a_c^2$$$.

If $$$c \geq sum$$$ then you can just use $$$sum$$$ ones, and the rest are zeros. The cost would be $$$1^2 + \ldots + 1^2 + 0^2 + \ldots + 0^2 = sum \cdot 1^2 + (c-sum) \cdot 0^2 = sum$$$.

Now, let's consider the case when $$$c \lt sum$$$. It can be proven that it's optimal for all the numbers to be as close as possible (this is done in the editorial).

So, how to make them as close as possible? If $$$sum$$$ is divisible by $$$c$$$, we can do $$$a_i = sum/c$$$. But most of the time it won't be, and we can't have decimal numbers, only integers.

To get the intuition for how to make them as close as possible, let's see an example. $$$sum = 17, c = 4$$$. So we need to split $$$17$$$ into $$$4$$$ parts that sum back to $$$17$$$, and the parts are as close as possible. We can do $$$4, 4, 4, 5$$$. If we had $$$sum = 18, c = 4$$$, we'd get $$$4, 4, 5, 5$$$. If we had $$$sum = 19, c = 4$$$, we'd get $$$4, 5, 5, 5$$$. If we had $$$sum = 20, c = 4$$$, we'd get $$$5, 5, 5, 5$$$. If we had $$$sum = 21, c = 4$$$, we'd get $$$5, 5, 5, 6$$$. And so on. How do we do this generally?

Set $$$a_i = \lfloor sum/c \rfloor$$$. But now the total sum is too small, because we are rounding down the numbers. So, to make it big enough, we will add $$$1$$$ to some of the numbers. From number theory we know: $$$sum = \lfloor sum/c \rfloor \cdot c + (sum \ mod \ c)$$$, and also $$$(sum \ mod \ c) \lt c$$$, so we can just add $$$1$$$ to exactly $$$sum \ mod \ c$$$ of the numbers.

In the end, we have $$$sum \ mod \ c$$$ numbers with value $$$\lfloor sum/c \rfloor + 1$$$, and the rest, exactly $$$c - (sum \ mod \ c)$$$, are $$$\lfloor sum/c \rfloor$$$. The total cost will be:

$$$\lfloor x \rfloor$$$ is the floor function. $$$a \ mod \ b$$$ is the modulo operation. You should understand these before trying to solve this problem, probably.

Let's see an example. $$$sum = 6, c = 4$$$. We have $$$4$$$ numbers, we need their sum to be $$$6$$$, and we need to minimize the sum of their squares. $$$\lfloor sum/c \rfloor = \lfloor 6/4 \rfloor = 1$$$, So initially we have $$$1, 1, 1, 1$$$. $$$sum \ mod \ c = 6 \ mod \ 4 = 2$$$, so we need to add $$$1$$$ to exactly $$$2$$$ of the numbers. So we get $$$1, 1, 2, 2$$$, which is indeed optimal.

Another example. $$$sum = 11, c = 4$$$. $$$\lfloor sum/c \rfloor = 2$$$, so initially we have $$$2, 2, 2, 2$$$. $$$sum \ mod \ c = 3$$$, so we need to add $$$1$$$ to $$$3$$$ of the numbers. So we get $$$2, 3, 3, 3$$$, which is optimal.

Heavy-Light Decomposition

Suppose that a is the minimum of both So obviously we have to decrease b, minimum value of x we can choose is 1 ,keep doing this until a becomes 0 ,b=b-2*a,so if b>2*a not possible

I explained it here.

My first approach was same as the one you described.

I am also still unable to figure out why this is incorrect.

What will your algo output here? (ans is 23)

16

1 2 3 4 5 -1 9 10 11 12 7 8 13 14 15 16

same doubt as we just need to find the max r value in those selected segments and that should give the req_time but that's now what is being done here..don't understand why

If a trap (s.x,s.y) is after lastr, fully, then the part from lastr to s.x is not traversed thrice, and thus isn't needed to be included into req_time.

Consider points 10,11,12,13,14,15,16

You are standing at point 10 with your squad and there is a trap at point 11 with its defuse at point 14. Assume this is a new segment so we cannot enter 11, and we need to defuse 14 first. hence effective distance we need to travel for this new segment [li,ri] will be 14-10=14-11+1. If there was another trap at point 13 with its defuse at 15, then we could directly visit 15 from 14 since we already move past 13, i.e. effective distance for this pair of [li,ri]= 15-14=1.
We only consider the distance going forward as we can double this later to find the total effective distance.

In brief, let f be the position of my friend. If f!=n, use then n must be bribed. Since 1) n can win [n/2+1, n] and become the top while [n/2, n-1] each has a sure win in the segment of [n/4+1,n/2], then we find the cheapest in [n/2, n-1] to bribe to win [n/4+1,n/2] for our friend f — throw out the one bribed. Then consider [n/8+1,n/4] segment in a similar way, bribe the cheapest one in [n/4, n-2] until we have covered everyone stronger than f.

The code is as follows.

include<bits/stdc++.h>

using namespace std;

using ll=long long; // #define _debug

vector a; int s, t, n, f, r; ll cost = 0; vector h;

struct greaters{ bool operator()(const int& a,const int& b) const{ return a>b; } };

int main(){

ifdef _debug freopen("cfinput.txt", "r", stdin); freopen("cfoutput.txt", "w", stdout);

endif

cin >> n; 
a.resize(n + 2); 
h.resize(n + 2);

for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] == -1) f = i; 
}

s = n; 
t = n + 1; 

r = n - f; 

while (r > 0){
    make_heap(begin(a) + s, begin(a) + t, greaters()); 
    //cout << a[s] << endl; 
    cost += a[s];
    t--; 
    a[s] = a[t];
    n /= 2;
    s -= n; 
    r -= n; 
}
cout << cost; 

}

Here's my greedy, it's super simple: Replace all numbers to the left of $$$-1$$$ by zero and remove $$$-1$$$ from the array. Now you can imagine that you are the weakest boxer and the only way to win is by bribing. Obviously you must bribe the strongest boxer, so add the last element of the array to the solution. The second boxer you must bribe must be among the strongest $$$n/2$$$ remaining boxers, so pick the smallest number among those. The next boxer you must bribe has to be among the strongest $$$n/2 + n/4 - 1$$$ remaining boxers, and so on.

Code: 79663574

The strongest player defeats $$$\log{n} - 1$$$ players directly. Now we can think that all players, who were defeated by our player are free and we can use these $$$\log{n} - 1$$$ players to defeat others. Those players also defeat some players directly continuing this recurrent process. So, after some thinking we can get recurrent formula: $$$f(x) = x - 1 + f(x - 1) + f(x - 2) + ... + f(1)$$$ where $$$x = \log{n}$$$. Let's try to calculate some first values of $$$f$$$:

$$$f(1) = 0$$$

$$$f(2) = 1$$$

$$$f(3) = 3$$$

$$$f(4) = 7$$$

$$$f(5) = 15$$$

Now we can notice that $$$f(x) = 2^{x-1} - 1$$$. Let's prove this by induction. This formula obviosly holds for $$$x = 1$$$, so let's prove the formula if we know that it holds for $$$f(1), f(2), ..., f(x - 1)$$$.

$$$f(x) = x - 1 + f(x-1) + ... + f(1) = x - 1 + 2^{x-2} - 1 + ... + 2^0 - 1 = x - 1 + 2^{x-1} - 1 - (x - 1) = 2^{x-1} - 1$$$.

So it is $$$n / 2 - 1$$$. Then we have $$$n / 2$$$ players left and for them it will be $$$n / 4 - 1$$$ and so on.

same i am also not getting and nobody is willing to answer