Roms's blog

Сodeforces Round 512 (and Technocup — Elimination Round 1) Editorial
By Roms, history, 6 years ago, translation, In English

1030A - In Search of an Easy Problem

Tutorial
Solution

1030B - Vasya and Cornfield

Tutorial
Solution

1030C - Vasya and Golden Ticket

Tutorial
Solution

1030D - Vasya and Triangle

Tutorial
Solution

1030E - Vasya and Good Sequences

Tutorial
Solution

1030F - Putting Boxes Together

Tutorial
Fenwick Solution
Segment Tree Solution

1030G - Linear Congruential Generator

Tutorial
Dynamic Connectivity Solution
Greedy Solution

1053E - Euler tour

Tutorial
Solution
  • Vote: I like it
  • +93
  • Vote: I do not like it

Comments Comments (97)
| Write comment?
»
6 years ago, # |
  Vote: I like it +95 Vote: I do not like it

Editorial launched even before System testing. I'm loving this !

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

:( For most of the time I thought that you can only do one swap per integer in Div1B, guess I need to read more carefully next time

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

The functions that defines the limits of the x — y values are changed on the B's picture.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
#include<bits/stdc++.h>
using namespace std;
int main ()
{
  map<char,int> mymap;
  
  mymap['a']=10;
  mymap['b']=20;
  

  for(auto it=mymap.begin();it!=mymap.end();it++) if(it->first=='a') mymap.erase(it);
  for(auto p:mymap) cout<<p.first<<"  "<<p.second<<endl;
 

  return 0;
}

Why is mymap.erase(it) giving runtime error. I know that it=mymap.erase(it) should be done. But the first one is running in all other compilers like hackerrank, codechef, my mac laptop. Why is it not running here in codeforces?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Iterating and Erasing simultaneously causes undefined behaviour.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is it running on almost all other compilers then?

      Also I came to know a few days back that long and long long are not the same in codeforces but same on almost all other compilers.

      Why is codeforces compiler different?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +14 Vote: I do not like it

        long is 4-byte data type while long long is 8-byte. In which compiler they have the same range?

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No. In the C++11 standart method "erase(iterator)" returns iterator on the next element in container. So "it = mymap.erase(it)" is correct code.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain solution for D? How do you get to sides a and b? Why are we dividing k by 2 if it is even, why are we multiplying later, etc.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    area of the triangle will be (a*b)/2 = (n*m)/k writing it as a*b = (2*n*m)/k we are calculating a in terms of n and b in terms of m. so we could've done something similar to link

    But it will be just writing extra code.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      If a>n can be true how you sure that in 2nd if condition

      here

      b>m will be always false. Can you please explain??

      sorry for bad english.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        since a*b = (2 * n * m) / k; if( a > n ) => b < (2*m/k) since, k>=2 => k/2 >= 1 => b < m / (k/2); => b < m

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Let's consider only the case when one point is at $$$(0,0)$$$. For other cases, you can always move to this case (by shifting the points).

    We'll build a rectangle inside the rectangle $$$n \times m$$$, with area equal to $$$2*m*n/k$$$, and we'll split the rectangle to get the triangle.

    • When $$$k$$$ is even ($$$k=2t$$$), we need to build a rectanble with area $$$m*n/t$$$. This number must be an integer, so $$$m*n$$$ must be divisible by t. This leads to the solution in the editorial. $$$g = gcd(t,n)$$$; $$$n = a * g$$$; $$$m = b * g'$$$ with $$$g' = t/g$$$ and $$$a,b$$$ is the sides of the rectangle

    • When $$$k$$$ is odd, $$$m*n$$$ must be divisible by $$$k$$$. Similarly, we have: $$$g = gcd(k,n)$$$; $$$n = a * g$$$; $$$m = b * g'$$$ with $$$g' = k/g$$$. Note that at this time, $$$a$$$ and $$$b$$$ is the sides of the rectangle with area $$$n*m/k$$$. We need to double one side to get the desired rectangle.

    If $$$a < n \rightarrow g \geq 3$$$ (because $$$g$$$ is neither 1 nor even) $$$\rightarrow a \leq n/3 \rightarrow 2a < n$$$

    If $$$a = n \rightarrow g = 1 \rightarrow g' = k \geq 3$$$ (note that $$$k$$$ is odd). Similarly, we get $$$2b < m$$$

    So we can always double $$$a$$$ or $$$b$$$.

    → Reply
»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Thanks for your effort in writing this editorial.

I wasn't able to solve problem Div.2 E.

When I read the editorial I find you are writing "It can be proven" for the key idea of the problem.

Please mention the proof or mention the intuition behind the two conditions.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Make 0 is equivalent to pairing ones in such way that there is no pair with ones from the same number. If max>sum/2 it's obviously impossible. Otherwise, just divide all ones in two groups of the same size in such way that there is no more than one number with ones in both groups. And there is always a way to pair ones from different groups.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was confused about this . Thanks a lot.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks adedalic. I would just like to point out that we can prove that such a division is always possible since

      1. Sum is even
      2. The number which has ones in both groups is actually the largest $$$b_i$$$.

      And then we can just match pairs from different groups.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Can someone help me understand why I was failing Div 2E, pretest 8? Would be really grateful

https://mirror.codeforces.com/contest/1058/submission/43335816

P.S. I used the same approach that the editorialist used

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I figured it out — it should have been tot[i-1] instead of tot[i], and j-1 instead of j. Passes now

    → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

My code is giving correct answer on local compiler but giving false answer on codeforces compiler. My whole contest went bad due to this error. Atleast my rating should be reverted back. 43309972

I checked test case 10 on codeblocks compiler as well as codechef IDE. Both of them are giving output as "Yes". My code is completely correct but still got WA.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You must check "KpartitionsPossible" until 9 * n

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      The problem is not that, the problem is that the code is giving correct output on codeblocks and codechef ide but not here.

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    you didn't check 'pos' != -1 in line 28

    UPD: i changed line 28 

    else if (prefix_sum[i] - prefix_sum[pos] >  total_sum / K) ->
else if (prefix_sum[i] - (pos == -1 ? 0 : prefix_sum[pos]) > total_sum / K)

    and it was accepted

    43343643

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Thanks for your effort. But why does this give the correct answer on codeblocks and codechef IdE and other compilers?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        because ide can eat some bugs and re)

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it -6 Vote: I do not like it

          So how do I even make sure that my code is correct? This way i'll never know for sure if my code is correct or not before submitting. I still feel this has been a little unfair to me.

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When you try access an index out of bounds, many times, compilers on codechef or other online ones, tend to return zero or garbage value. Basically, it tries to access element at pos*(data_type_size) from the base of the array. So, if pos is -1, it access the element before 0th element of the array.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -16 Vote: I do not like it

        Thanks a lot for your help. I guess i can't even trust compilers when it comes to codeforces. :(

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +18 Vote: I do not like it

          The problem is not in the compiler. Suppose you have the code:

          int arr[2];
cout << arr[0] << ' ' << arr[1] << endl;

          What this code is supposed to print? There is no certain behaviour because you haven't assigned anything to 'arr'. It will just print what was laying there in the memory and it may differ from launch to launch. The same thing happened in your case.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

            Thanks a lot. Made this completely clear to me.

            → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    Who cares about rating? There's a contest like every 3-4 days.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      But when your contest is going good and you would have achieved blue in this very contest and you did not because of such errors,it does feel sad. :(

      → Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

The tutorial for Div 1E claims that if you have two equal values then there is a subtree between them which can be solved independently of the rest of the problem. But that's not necessarily true e.g. given the input 1 2 0 3 1 the only right answer is 1 2 1 3 1, and the interval 2 1 3 does not describe an Euler tour of a subtree of 1.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +26 Vote: I do not like it

    I wrote this tutorial about month ago, now I see a lot of small mistakes in it. This is O(n) solution:

    Solution

    And a little bit modified tutorial:

    Tutorial

    Big thanks to Grzmot who wrote great statement and helped me with proving that this solution is correct!

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Can someone explain the second condition of Div2E maximal element should be lower or equal to the sum of all other elements

UPD Got it! :)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Explain it, please.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Suppose you have numbers:

      1111111111 (10x1)
0000001111 (4x1)
0000000011 (2x1)
0000000011 (2x1)

      Can you change the position of bits so the xor of the numbers equals to zeros?

      By xoring with number with N-bits you can remove no more than N-bits.
Xoring with 0000001111 will remove no more than 4 bits.
Xoring with 0000000011 will remove no more than 2 bits.
Xoring with 0000000011 will remove no more than 2 bits.

      In total you can only remove 4+2+2 bits but you have 10 bits in the number 1111111111 so you cannot remove two last bits and thus this sequence is bad.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can You please explain why these two conditions are sufficient?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Let me give it a try.

          I hope you understand why, even bits are required. Let me try to explain the other condition.

          Lets say for in a subarray for size K, [a1,a2,a3,...,ak] is count of set bits (setbits array). Also, lets assume a1 >= a2 >= a3 .. >= ak, so a1 is the maximum in the setbits array. Now, I will try to greedily nullify the a1 bits. So, first I nullify a2 bits of a1 using a2. Now, (a1-a2) bits of a1 are left, and a2 is nullified. Now I will greedily use, a3 bits to nullify those (a1-a2) bits of a1. Two cases arise:

          1. a3 <= (a1-a2)

          2. a3 > (a1-a2)

          For the first case, I use, all of a3, and now I need to nullify (a1-a2-a3), so I go ahead with using a4, and move ahead. Again, two similar cases arise.

          For the second case, so I can at max use (a2-a1) bits of a3, and will be left with (a3-a2+a1) bits,(say x, for simplictity) of a3. I don't want that.

          So, basically, what I will do is, I will take x bits from a2, and x bits from a3, such that, a2+a3-2x = a1, so now a1 can be nullified, and then x bits from a2 and x from a3 can nullify each other, so we are left with zero.

          Although, this is not a very formal proof, I hope I was able to give enough intuition for the constructive algorithm to arrange the bits when the two conditions are satisfied.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Thank you lohit_97.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Hello what about this exapmle 1111 1111 1100 sum of 1's is even and max elemnt is lower or equal to sum of all others but those numbers do form not good sequence! UPD:I got it

              → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I not understand the editorial for Div2-F.Please can you or someone else explain that too?

            Thanks!

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I also need that. Can someone please explain us??

              → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            For the second case your explanation gives x=(a2+a3-a1)/2.How do u prove that this is an integer?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              If it isn't then there is a number with an extra bit after it which will help us nullify it.

              EDIT: I was so waiting for someone to ask this :P

              → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Loved the tutorial of problem E.....Thanks a lot.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Roms Test cases of D problem seems to be weak :( . Some users coded for smaller k like k=2(and the test cases don't include 'yes' with k=3 or more for the worst case) and got AC.

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi! I tried my best to understand the editorial for Div2-F https://mirror.codeforces.com/contest/1030/problem/F but could not understand it.

My doubts are in understanding the proof that keeping 1 box unmoved is optimal and how does that total cost of shifting left parts in the end equal to a_k*S(l,k-1) — sum(w_i*a_i)?

Thanks!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain DIV2 E editorial with the sample test case 1? 

3
6 7 14
→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

F can also be done with only BIT in O(logn)

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In tutorial of the problem Div:2-D, how to prove b=(m/k') is always an integer.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Notice that the area is always a multiple of one-half.

    So after you divide k by 2 ,(n*m)/k' will be a integer.

    Let's make an assumption that m/k'=x/y (gcd(x,y)=1),

    Because (n*m)/k' is a integer,n/(gcd(n,k))should be a multiple of y,

    That comes to a contradiction because you should divide n by y(both n and k have the factor--y).

    As a result,m/k' is always an integer.

    → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In problem E, How to prove that if maximal element is lower or equal to the sum of all other elements then the subsequence is good ?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    if this condition holds and the sum of the sequence is even, you can decrease the two biggest numbers by one and preserve this property. so, at every step you can decrease the sum of the sequence by 2 and eventually it's sum will become zero, which means this squence is good.

    proof: let k be the number of occurences of the maximal number x in a sequence with even sum and 2*x<=sum. in case k=1 or k=2: the operation above decreases the maximal number at least by one and decreases the sum exacly by two so the invariant still holds.

    in case k>=4, after the operation there are at least two numbers with max value x so the sum is at least 2*x which means the invariant holds.

    in case k=3, after the operation the max element is x and the sequence has sum of at least x+(x-1)+(x-1)=3*x-2 which is greater or equal 2*x for every x>=2. the case x=1 can't happen because the sum of the sequence will be odd, so also in here the invariant hold

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "and eventually it's sum will become zero, which means this squence is good." why this means sequence is good? Me also waiting proof of this

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Decrease two numbers corresponds to position two ones in the binary representation of the original numbers at the same place. When the ones are at the same place in both numbers, the XOR will cancel one with the other, and we can ignore them. If the sum of the sequence reached zero it means that every one has another which cancels it, and the XOR result is zero.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          Ah, thanks. I was thinking about partition problem. I was trying to find counter example that if you have array satisfying this two conditions, and it can't be devided into two of equal sums. But your proof is not related to partition problem, because here you can use bits of single number in any pair.

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain to me why doubled area of any triangle with integer coordinates is always integer? How can we demonstrate that?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    https://en.wikipedia.org/wiki/Cross_product

    Area of triangle (0, 0), v = (x1, y1), u = (x2, y2) is |x1 * y2 — x2 * y1| / 2

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    you can draw the minimal rectangle with sides parallel to the x and y axis that blocks the triangle (for example, the rectangle corrisponding to triangle (0,0), (1,5) , (2,4) is (0,0) , (5,0), (5,4) , (0,4)). it's divided into 4 triangles, the original one and 3 more Straight-angle triangles. it's clear that each one of them has integer doubled area, and the rectangle's area is also an integer, so the original triangle must also have integer doubled area.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you!

    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In problem F, how can we actually do this part: find k in(nlogn) by "descending" down the Segment Tree in

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the fourth paragraph of the 1053E, the "than" in the first row should be "then".

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

“Problem B” Can anybody explain me,why x+y=d — diagonal?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In DIV2 Problem E, Something Strange is happening. Here: http://mirror.codeforces.com/contest/1058/submission/43418325 in Testcase 1 and same code on IDEone: https://www.ideone.com/iiTZkx Getting WA on test case 1 on Judge but produces correct output on my machine.

Also, I am interested in knowing the result of test case 5.I am using prefix sum here. My program produces 7 as result, Because no. of set bits are: 8 16 16 18 22. So, for 8, there are 0 prefix, 16 : 0 prefix, 16 : 2, 18: 2 prefix and 22: 3 prefix. Total equals to 7. Please explain how the answer is 3 for this test case?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, I suggest compiling with the flag -Wall

    In lines 59 and 73 you have the condition j > (i-66, 0), maybe you forgot a max? Also, the variable maxm is not initialized in 0 so it could have garbage

    I don't know if this is the only problem but I hope it helps

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

hey can anyone tell why this solution is giving WA for second task?......
when i am submitting like this it is giving AC -
int sum=pow(2,freq)-1;
link for correct solution. https://www.codechef.com/viewsolution/20327375 but when i am using this-
cout pow(2,freq)-1 ;
it is not giving AC
link...
https://www.codechef.com/viewsolution/20329958
thanks in advance..... @arpa

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Function pow probably return float value, try convert to int like that: (int)pow(2,freq)-1. And use please logic operations, pow(2,freq) equal 1 << freq.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div2 D, Doubled area of any triangle with integer coordinates is always integer. Can anyone explain this statement.Why is it always true?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Div2E does it means when r-l>60 and sum(l,r)%2==0 and max(l,r)*2<=sum(l,r), you can always divide the ones into two groups with same size? how to prove that?

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

My solution of problem E:

If i < j and ai = aj ≠ 0, a[i..j] is an Euler tour, we can deal with a[i..j] and replace it with ai.

Since a[i..j) doesn't contain the same elements except 0's, we can do this operation:

If there are 3 consecutive elements ai - 1, ai, ai + 1, ai ≠ 0 and ai - 1, ai + 1 contain exactly one 0 (or ai - 1 = ai + 1 ≠ 0), we can regard ai as a leaf and let ai - 1 = ai + 1 (equals to the non-zero element), then remove ai and ai + 1. It can be proved correct.

After operations, combine the first and the last element to form a cycle, if there are two consecutive non-zero elements, there mustn't be any zero and no solution exists (because a tree with two or more vertices must contain a leaf). Otherwise, any two non-zero elements aren't neighbors, all the elements can be regarded as leaves, it's easy to construct.

After there aren't any i < j that ai = aj, we can deal with the whole series using the same way.

All operations can be done by stack in linear time.

Time complexity: O(n).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In DIV2 E, can someone explain " Let's find a way to decide whether fixed segment is good or not. It can be proven that two conditions must be met. At first, sum of bi at this segment should be even. At second, maximal element should be lower or equal to the sum of all other elements." How about this case: b1=3, b2=4, b5=5, i think this satisfy the condition, but this case is not good. Am i right?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Let's see, how we can get zero in this case. As we can move the ones we can get something like this:

    11111

    11110

    11100

    Shift the bits of b2 to two positions to the right, make the xor of b2 and b5(I mean the xor of numbers from which b2 and b5 were got) and then you can get zero as you get two numbers which contain 3 ones.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do people come up with the intuition for problems like div1 C? Once I read the editorial it's so clear but I thought for half an hour and I didn't even get to the first observation. Is "solve more problems" the only way?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Interesting problems...

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is My Solution for Problem D And I Wonder Why I didn't Get Time Limit exceeded . Is This because Test cases weren't be enough Or Something Else ????????????????????????? https://mirror.codeforces.com/contest/1030/submission/150139674

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem B? Vasya and Cornfield ?

→ Reply