PikMike's blog

By PikMike, history, 12 days ago, translation, In English,

1260A - Heating

Idea: adedalic

Tutorial
Solution (adedalic)

1260B - Obtain Two Zeroes

Idea: Roms

Tutorial
Solution (Roms)

1260C - Infinite Fence

Idea: adedalic

Tutorial
Solution (adedalic)

1260D - A Game with Traps

Idea: BledDest

Tutorial
Solution (BledDest)

1260E - Tournament

Idea: Roms

Tutorial
Solution (Roms)

1260F - Colored Tree

Idea: RDDCCD

Tutorial
Solution (RDDCCD)
 
 
 
 
  • Vote: I like it
  • +89
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Here for a nice explanation by iica

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Search about diofantic equations.

  • »
    »
    11 days ago, # ^ |
    Rev. 10   Vote: I like it +7 Vote: I do not like it

    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

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        11 days ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        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)

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How do you get the idea of using Gcd?

»
12 days ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    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.

»
11 days ago, # |
  Vote: I like it +44 Vote: I do not like it

Here 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

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let x be number of times we subtract 1 from a and y be number of times we subtract 1 from b.If solution exists then following equations hold true:

    $$$ a - x - 2y = 0 $$$
    $$$ b - 2x - y = 0 $$$

    Adding these two equations we get:

    $$$ a + b = 3(x + y) $$$

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

»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

In the tutorial of problem B, why a.2 >= b. Please someone explain.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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:

    $$$ \left\{ \begin{array}{lcr} a-2x-y&=&0\\ b-2y-x&=&0 \end{array} \right. $$$

    It's easy to make it simple:

    $$$ \left\{ \begin{array}{lcr} 3x&=&2a-b\\ 3y&=&2b-a \end{array} \right. $$$

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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:

    $$$a - x_1 - x_2 - ... - x_k - 2y_1 - 2y_2 - ... - 2y_m = 0$$$
    $$$b - 2x_1 - 2x_2 - ... - 2x_k - y_1 - y_2 - ... - y_m = 0$$$

    Or...

    $$$a - (x_1 + x_2 + ... + x_k) - 2(y_1 + y_2 + ... + y_m) = 0$$$
    $$$b - 2(x_1 + x_2 + ... + x_k) - (y_1 + y_2 + ... + y_m) = 0$$$

    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:

    $$$a = X + 2Y$$$
    $$$b = 2X + Y$$$

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

    $$$b = 2(a - 2Y) + Y$$$
    $$$b = 2a - 3Y$$$
    $$$3Y = 2a - b$$$
    $$$Y = (2a - b) / 3$$$

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

»
11 days ago, # |
  Vote: I like it +5 Vote: I do not like it

This contest is so great!I love it!

»
11 days ago, # |
  Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ritesh1340

       for (int i = n - 1; i >= 0; i--) {
              if (ar[i] == -1) break;
              smaller.insert(ar[i]);
              if (Integer.bitCount(i + 1) == 1) {
                      ans += (smaller.getLowest());
                      smaller.remove(smaller.getLowest(), 1);
              }
      }
      

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

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Wow,can you please explain your solution?

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Anyone explain A

  • »
    »
    10 days ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    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 sum/c \rfloor}^2 \cdot (c - (sum \ mod \ c)) + (\lfloor sum/c \rfloor + 1)^2 \cdot (sum \ mod \ c)$$$

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

" All of this can be done with HLD" What's the meaning of HLD?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me as to why do we need to do a * 2 >= b for problem B? I didn't really get it :(

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I explained it here.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me to understand the tutorial solution of problem C

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Excuse me, what are event processing algorithms ?

»
10 days ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My first approach was same as the one you described.

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

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My algo outputs 24.

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

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B using binary search?

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I did not understand In problem D

req_time += s.y - s.x + 1;
lastr = s.y;

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 ?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone, Please Explain how to solve E?

  • »
    »
    4 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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; 
    

    }