Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
int c, sum;
inline bool read() {
if(!(cin >> c >> sum))
return false;
return true;
}
inline void solve() {
int d = sum / c;
int rem = sum % c;
cout << rem * (d + 1) * (d + 1) + (c - rem) * d * d << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int n; cin >> n;
while(n--) {
read();
solve();
}
return 0;
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for t in range(int(input())):
a, b = map(int, input().split())
if a > b:
a, b = b, a
print ('YES' if ( ((a + b) % 3) == 0 and a * 2 >= b) else 'NO')
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
li a, b, k;
inline bool read() {
if(!(cin >> a >> b >> k))
return false;
return true;
}
inline void solve() {
li g = __gcd(a, b);
a /= g;
b /= g;
if(a > b)
swap(a, b);
if((k - 1) * a + 1 < b)
cout << "REBEL";
else
cout << "OBEY";
cout << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int tc; cin >> tc;
while(tc--) {
read();
solve();
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int, int> pt;
#define x first
#define y second
int m, n, k, t;
vector<int> l, r, d, a;
bool can(int x)
{
int mn = int(1e9);
for (int i = 0; i < x; i++)
mn = min(mn, a[i]);
vector<pt> segm;
for (int i = 0; i < k; i++)
if (d[i] > mn)
segm.push_back(make_pair(l[i], r[i]));
int req_time = 0;
sort(segm.begin(), segm.end());
int lastr = 0;
for (auto s : segm)
{
if (s.x <= lastr)
{
req_time += max(0, s.y - lastr);
lastr = max(s.y, lastr);
}
else
{
req_time += s.y - s.x + 1;
lastr = s.y;
}
}
req_time = 2 * req_time + n + 1;
return req_time <= t;
}
int main()
{
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d %d %d %d", &m, &n, &k, &t);
a.resize(m);
for (int i = 0; i < m; i++)
scanf("%d", &a[i]);
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
l.resize(k);
r.resize(k);
d.resize(k);
for (int i = 0; i < k; i++)
scanf("%d %d %d", &l[i], &r[i], &d[i]);
int lf = 0;
int rg = m + 1;
while (rg - lf > 1)
{
int mid = (lf + rg) / 2;
if (can(mid))
lf = mid;
else
rg = mid;
}
printf("%d\n", lf);
return 0;
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int LOGN = 20;
const int N = (1 << LOGN) + 99;
const long long INF = 1e18;
int n;
int a[N];
long long dp[LOGN+2][N];
int sum[100];
long long calc(int cnt, int pos){
long long &res = dp[cnt][pos];
if(res != -1) return res;
if(a[pos] == -1) return res = 0;
int rem = sum[cnt] - pos;
res = INF;
if(cnt < LOGN)
res = calc(cnt + 1, pos + 1) + a[pos];
if(rem > 0)
res = min(res, calc(cnt, pos + 1));
return res;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d", a + i);
for(int i = 1, x = n / 2; i < 100; ++i, x /= 2)
sum[i] = sum[i - 1] + x;
reverse(a, a + n);
memset(dp, -1, sizeof dp);
printf("%lld", calc(0, 0));
return 0;
}
```

Idea: RDDCCD

**Tutorial**

Tutorial is loading...

**Solution (RDDCCD)**

```
#include<bits/stdc++.h>
using namespace std;
int n ;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7 ;
vector<int> E[maxn];
vector<int> in[maxn] , out[maxn];
int cm = 0;
int l[maxn] , dfn = 0 , dep[maxn];
int g[maxn];
int siz[maxn] , top[maxn] , h[maxn] , f[maxn];
///-----segment tree
struct seg
{
int l , r;
int sum , add ;
}Node[maxn * 4];
void build(int u,int l,int r)
{
Node[u].l = l , Node[u].r = r;
Node[u].sum = Node[u].add = 0;
if(l == r) return ;
build(u<<1 , l , (l + r >> 1));
build(u<<1|1 , (l + r >>1) + 1 , r);
return ;
}
void pd(int u)
{
Node[u].sum = (1LL*Node[u].add*(Node[u].r - Node[u].l + 1) + Node[u].sum) % mod ;
if(Node[u].l == Node[u].r) {
Node[u].add = 0 ;return ;
}
(Node[u<<1].add += Node[u].add ) %= mod;
(Node[u<<1|1].add += Node[u].add ) %= mod;
Node[u].add = 0 ; return ;
}
void modify(int u,int l,int r,int v)
{
if(Node[u].l == l && Node[u].r == r) {
(Node[u].add += v ) %= mod;
pd(u) ; return ;
return ;
}
pd(u) ;
if(Node[u<<1].r >= r) {modify(u<<1 , l , r , v) ; pd(u<<1|1);}
else if(Node[u<<1|1].l <= l) {modify(u<<1|1 , l , r , v) ; pd(u<<1) ;}
else {
modify(u<<1 , l , Node[u<<1].r , v) ;
modify(u<<1|1 , Node[u<<1|1].l , r , v);
}
Node[u].sum = (Node[u<<1].sum + Node[u<<1|1].sum) % mod;
return ;
}
int query(int u,int l,int r)
{
pd(u) ;
if(Node[u].l == l && Node[u].r == r) return Node[u].sum ;
if(Node[u<<1].r >= r) return query(u<<1 , l , r) ;
else if(Node[u<<1|1].l <= l) return query(u<<1|1 , l , r);
else return (query(u<<1 , l , Node[u<<1].r) + query(u<<1|1 , Node[u<<1|1].l , r)) % mod;
}
///---segment tree end
void dfs(int fa,int u,int d)
{
f[u] = fa;
dep[u] = d;siz[u] = 1;h[u] = -1;
for(int i = 0;i < E[u].size();i++) {
if(E[u][i] != fa) {
dfs(u , E[u][i] , d + 1) ;siz[u] += siz[E[u][i]];
if(h[u] == -1 || siz[E[u][i]] > siz[E[u][h[u]]]) h[u] = i;
}
}
return ;
}
void dfs2(int fa,int u)
{
l[u] = ++dfn;
if(h[u] != -1) {
top[E[u][h[u]]] = top[u] ;
dfs2(u , E[u][h[u]]);
}
for(int i = 0;i < E[u].size();i++) {
if(E[u][i] != fa && i != h[u]) {
top[E[u][i]] = E[u][i] ;
dfs2(u , E[u][i]) ;
}
}
return ;
}
int fpow(int a,int b)
{
int ans = 1;
while(b) {
if(b & 1) ans = (1LL * ans * a) % mod;
a = (1LL * a * a) % mod ;b >>= 1;
}
return ans;
}
void add(int u,int v)
{
while(u) {
modify(1 , l[top[u]] , l[u] , v) ;
u = f[top[u]] ;
}
return ;
}
int cal(int u)
{
int ans = mod - query(1 , 1 , 1);
while(u) {
ans = (ans + query(1 , l[top[u]] , l[u])) % mod;
u = f[top[u]] ;
}
return ans;
}
int main()
{
scanf("%d",&n) ;
int P = 1;
for(int i = 1;i <= n;i++) {
int l , r;scanf("%d%d",&l,&r) ;
in[l].push_back(i) ;
out[r + 1].push_back(i) ; cm = max(cm , r);
g[i] = fpow(r - l + 1 , mod - 2) ;
P = 1LL * P * (r - l + 1) % mod;
}
for(int i = 1;i < n;i++) {
int u , v;scanf("%d%d",&u,&v) ;
E[u].push_back(v) ; E[v].push_back(u) ;
}
dfs(0 , 1 , 0) ; top[1] = 1;
dfs2(0 , 1) ;
build(1 , 1 , n) ;
int ans = 0 , cur = 0;
int d1 = 0 , d2 = 0 , u , d3 = 0;
for(int i = 1;i <= cm;i++) {
for(int j = 0;j < out[i].size();j++) {
u = out[i][j] ;
d1 = (d1 - 1LL * dep[u] * g[u] % mod + mod) % mod;
d2 = (d2 - g[u] + mod) % mod ;
d3 = (d3 - 1LL*dep[u]*g[u] % mod * g[u] % mod + mod) % mod;
add(u , mod - g[u]) ;
cur = (cur - 1LL * g[u] * cal(u) % mod + mod) % mod;
}
for(int j = 0;j < in[i].size();j++) {
u = in[i][j] ;
d1 = (d1 + 1LL * dep[u] * g[u]) % mod;
d2 = (d2 + g[u]) % mod;
d3 = (d3 + 1LL*dep[u]*g[u]%mod*g[u]) % mod;
cur = (cur + 1LL * g[u] * cal(u)) % mod;
add(u , g[u]) ;
}
ans = (ans + 1LL * d1 * d2%mod - 2LL*cur - d3) % mod;
ans = (ans + mod) % mod;
}
ans = 1LL * ans * P % mod;
printf("%d\n",ans);
return 0;
}
```

I did not understand 1260C - Infinite Fence. Can anybody give me a detailed explanation?

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 cellsExtended 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`

coloredblue, we have`(pos + g)`

coloredred(here , two consecutive blue cells

`pos and pos+b`

)generally , we have to use color

redfor 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 leastk redcells in between`(pos,pos+b)`

so rebel,

if`(g+(k-1)*r)<b`

;elseobeyhey this may sound silly but can you please explain why in our case ax-by=gcd(a,b) works

say , we colored

`b*y`

blue. Now, smallest number greater than`b*y`

that must be colored red is`b*y+q`

. (q>0)so

`r*x = b*y+q`

; what will be the minimum positive value of q ?By extended euclidean we know that

`r*x - b*y = ?`

has smallest positive integer solution gcd(b,r)How do you get the idea of using Gcd?

Can you please explain, how can we say that the x and y obtained are positive? (Because for our requirement they must be positive, suppose x and y are both negative, then also rx -by = 1 will be satisfied, however this is not what we would like) Extended Euclidean states there exists integer x, y such that ax + by = gcd(a,b). I am not able to connect the dots in a proper way. Thanks!

You have explained very well but you haven't explained why are we dividing

`r and b`

with`GCD(r,b)`

please reply i am very weak in GCD questions.why are we diving

`r and b`

with`GCD(r,b)`

somebody please explain in turorial its written very shortly someone plzz explainFor the problem C, should not we just check k*r>b. why do we check for (k-1)*r + 1 > b. can some explain this.

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

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.

Assume R<=B

this gives wrong ans... can you explain why?

I guess your R and B happen to have gcd > 1, don't they?

You had to assume gcd(a, b) = 1 ....

What is wrong in the following approach ?

Assume (r < b)

We start putting red from index pos+gcd(r, b), and we check if we can put more than k red till pos+b. It is equivalent to we have b-1 places, we start marking from index gcd(b, r) and mark each rth index. If we mark >= k index, answer is RABEL. which translates to (b-1)-(g-1) >= k*r : RABEL

Upd: Figured out. The equation translates to 1 + ((b-1)-(g-1)-1)/r < k.

Then what will be answer if

`GCD(r,b) > 1`

and in tutorial why there the asking to consider separately if GCD is not 1Here I provide another solution for

F. Colored Tree.Suppose that there are $$$c_{max}$$$ moments and each node appears at some moment $$$t$$$ if and only if $$$l_i\le t\le r_i$$$.

At each moment there appears several nodes on the tree, and each pair of these nodes $$$(x,y)$$$ at this moment makes contribution of $$$\prod_{i=1}^n (r_i-l_i+1)\times \frac{1}{r_x-l_x+1}\times \frac{1}{r_y-l_y+1}$$$ to the answer.

We "add" and "delete" the nodes base on moments they "appear" and "disappear" one by one and there are only $$$O(n)$$$ such events. For each event we calculate the changes of the contribution among the current nodes. This can be done in $$$O(\log n)$$$ doing

divide-and-conquer on the tree. Specifically, let $$$w_x$$$ be $$$\frac{1}{r_x-l_x+1}$$$, and if $$$(x,y)$$$ meet at node $$$z$$$, the contribution they make is $$$(dis_{x,z}+dis_{y,z})\times w_x\times w_y=dis_{x,z}\times w_x\times w_y+dis_{y,z}\times w_x\times w_y$$$, where $$$\prod_{i=1}^n (r_i-l_i+1)$$$ will be calculated later. Each half can be calculated independently as we can maintain $$$\sum w_x\times dis_{x,i}$$$ and $$$\sum w_x$$$ on each node $$$i$$$. As we know, this can be done in $$$O(n\log n)$$$.After those events taking place at moment $$$t$$$, we add up the current contribution to the answer. Don't forget that in the end the real answer should be $$$ans\times\prod_{i=1}^n (r_i-l_i+1)$$$.

View code to see details.

Code1 ($$$O(c_{max}+n \log n$$$): 65904158

Code2 ($$$O(c_{max}+n \log^2 n)$$$ with a smaller constant): 65902583

Why a+b mod 3 is zero in Problem B. Would someone please explain the idea

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.

Let

xbe number of times we subtract 1 fromaandybe number of times we subtract 1 fromb.If solution exists then following equations hold true:Adding these two equations we get:

So, $$$a + b$$$ is a multiple of 3. Therefore $$$(a + b) \bmod 3 = 0$$$

In the tutorial of problem B, why

`a.2 >= b`

. Please someone explain.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$$$

Thanks. I got it.

This solution must be in the tutorials.

mathematically we can prove this as: we are given two numbers a and b,lets assume a<b (for a!=b), in order to obtain two zeroes simultaneously, we have to reduce a and b into two numbers of the form say t and 2t. Also for reducing we can use numbers of the form say x and 2x. Thus the equations become: a-x=t and b-2x=2t now let us assume that b>2a, so let b=2a+1; substituting in the equation above,we get: (2a+1)-2x=2t or 2(a-x)+1=2t or 2t+1=2t (substituting a-x=t from 1st eq) which is not possible, thus the maximum possible value of b should be 2a. The logical explanation for this can be that while reducing a and b to t and 2t form, the highest possible value of t would be min(a,b)=a, but for obtaining its corresponding 2t value from b, we need to reduce b further keeping a constant, since b>2a. Thus b always needs to be reduced by an additional (b-2a) value every time while trying to obtain results. You can try this using an example where a=12 and b=34

How did you get the intuition that we should also check for b >= 2a along with (a+b) mod 3 condition? I am new to problem solving , just asking so that I can improve

IN Q-2...why 2a>b...this condition is required? plz tell me the idea

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

This contest is so great!I love it!

PikMike E is a simple greedy. Look at the solution. 2 line logic. 65862147

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

ritesh1340

It's just that whenever i is power of 2, remove the smallest element and add it into answer. You can use priority queue.

Wow,can you please explain your solution?

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

Can somebody explain the formula of 1260A — Heating to me....I am so confused..

d = sum / c; rem = sum % c; answer = rem * (d + 1) * (d + 1) + (c — rem) * d * d <----- this formula

I don't understand even read the editorial...

Anyone explain A

I explained it here.

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.

Thank you so much !!

Hey can you explain the proof given in the editorial?

＂ All of this can be done with HLD＂What's the meaning of HLD?Heavy-Light Decomposition

Thanks, cool.

Can anyone help me as to why do we need to do

a * 2 >= bfor problem B? I didn't really get it :(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.

Please help me to understand the tutorial solution of problem C

Excuse me, what are event processing algorithms ?

Task E, why this approach is incorrect? This our array:

...-1(i).........a(n)

For the first round a(n) plays with max on [i+1, n-1]

If a(n-1) is free it plays with next max on [i+1, n-2]

And so on...

If there is last free player on [i+1, n] (let it be j) it plays with the first free player from the beginning

If the first free player from the beginning is out i, than ans+=a(j)

Next round...

And so on until only player i stays My code: https://codeforces.com/contest/1260/submission/66071106

My first approach was same as the one you described.

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

Problem E: My approach is this: I want my friend boxer to face the boxers with lower strength so that there is no need to pay bribe. So,I match my friend with a less strength boxer. Also, i try to match less strength boxers among themselves so that more of them remain till the end. Also,I make the strongest boxer match with the one that takes most bribe. Then match the next strongest unmatched boxer to the next unmatched boxer who takes the most bribe and so on....

I repeat the process log n times. I am getting wrong answer on test case 6. Can anybody point out the mistake in this approach. Thanks in advance.

Problem E

Please help me find why this approach is incorrect ?

Why can't we greedily make the strongest boxer defeat n/2-1 boxers which demand the highest bribe and our stronger than our friend boxer ?

Then we repeat for the remaining boxers ?

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

My algo outputs 24.

But can you give me a tournament with ans 23 ?? (Tried a lot to come up with an example)

Okay found one, (1,2)(3,4)(5,-1)(12,7)(9,10)(11,8)(13,14)(15,16)

(2,4)(-1,7)(10,8)(14,16)

(4,-1)(8,16)...............pay 7 bribe

(-1,16)

-1.............pay 16 bribe

Total 23

How to solve B using binary search?

Why problem D,we should use this greedy strategy ？If two trap have union,we needn't return. orz~~

I did not understand In problem D

Why we should do (s.y — s.x +1) ?

I thought req_time +=(s.y — lastr); lastr = s.y;

So I wrong answer!

Could you explain this problem ?

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`

.Someone, Please Explain how to solve E?

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

}

How to solve D in O(nα(n)) ?

Assume

R<=B(k-1)*R + 1 <B) then REBELWhy this is

not workingcan anyone explain me?Can someone please explain the solution for E? I don't get how the strongest player can defeat 'n/2-1 other players' which is written in the editorial. He will participate in log2(n) games at most, how can he defeat n/2-1 others? If someone can also explain the greedy approach to this problem, it would be highly appreciated by everyone who has been searching for it

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

Hi, thank you for replying. I get the point that the last player (nth one) must be bribed, as otherwise our player would never win. But why should we chose the best among the n/2 strongest for our second bribe? Isn't it possible that one of n/2 strongest was defeated in previous rounds?

Because the strongest boxer cannot beat all $$$n/2$$$ of them you have to bribe at least one. The strongest boxer can only beat $$$n/2-1$$$ other boxers.

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.

prob -- infinite fence can anybody explain why are we taking GCD of r and b.. like can you explain me with an example where i will get an wrong answer if i did not take the gcd..

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

In case you still need help

https://codeforces.com/blog/entry/71755?#comment-560847

I am not able to spot the mistake in my code 84677601 for D. Can someone give me a small testcase on which it fails.

Can someone explain how to apply binary search in problem B. I came to this question by seeing the binary tag but here's no sign of that. Someone please explain it by binary search.Somebody please help me with F question ... I have done centroid decomposition and its giving TLE and the complexity if nlog2n in that case which seems correct .. https://codeforces.com/contest/1260/submission/92880641