Блог пользователя Okrut

Автор Okrut, история, 4 года назад, По-английски

1362A - Джонни и древний компьютер

Author: Anadi

Tutorial
Solution

1362B - Джонни и его хобби

Authors: Anadi and Okrut

Tutorial
Solution

1362C - Джонни и ещё одно падение рейтинга

Author: MicGor

Tutorial
Solution

1361A - Джонни и вклад

Author: Anadi

Tutorial
Solution

1361B - Джонни и гроссмейстер

Author: Okrut

Tutorial
Solution

1361C - Джонни и ожерелье Меган

Author: Okrut

Tutorial
Solution

1361D - Джонни и Джеймс

Author: Okrut

Tutorial
Solution

1361E - Джеймс и погоня

Author: Anadi

Tutorial
Solution

1361F - Джонни и новая игрушка

Author: Anadi

Tutorial
Solution
  • Проголосовать: нравится
  • +219
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Greate contest,thanks!

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Can't there be cycles in problem D? ( EDIT: Ignore I accidentally looked at D1 D and it said 'tree' so got confused. )

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i assume u mean div2D right?

    i'm pretty sure it doesn't matter u greedy fill solutions starting from the lowest one after checking all the ways in which it could be invalid. ur not traversing the graph ur only checking the connections for each one

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

      I thought greedy won't work, so didn't implement it. Damn, feeling so dumb right now. I spent all my time looking for graph coloring problems as it was quite similar.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem D video Editorial: Solution

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Brute force O(1023 * n * log(n)) ~= O(n^2 * log(n)) solution passed in part B. I simply tested all values of k from 1 to 1023 until one worked.

82505984

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +70 Проголосовать: не нравится
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Actually they are D and E of Div 2

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Oh that's right thanks!

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        In prob E: For converting an odd coefficient to even, why are we taking subarray starting from that point. We can take subset instead of subarray.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Yes, you are correct but you will notice that we only need to consider subarray. Consider that you are at index i where you found odd occurrence.Now to make it even you need P occurrence from (i+1). Assume we have only have X occurrence at (i+1), so we need P*(P-x) occurrence from (i+2) and so on. Now,if I get my extra occurrence from a subset then whatever occurrence we are using from index j it must be first converted to in the form of (j+1) and so on. (indexs are consider after sorting array descendingly)

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

    I edited my comment. Don't press <-- Rev.

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    ur soln for D fails for the following tc:-

    4 3

    1 2

    2 3

    3 4

    1 3 3 1

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    great tutorial this time!!

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    what is that do_calc function is doing in your code for div2E/div1B
    upd:- finally got that amazing solution thank you

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

seemingly simpler solution for problem C

ll res=0;
while(n){
    res+=n;
    n/=2;
}
cout<<res<<endl;
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

    This was my C 2*n-__builtin_popcountll(2*n)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you tell me why this works?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      We first note that the sum of the first 2^k values for any k is 2^(k+1) — 1. One can easily prove this via induction (or basically, noting that the sequence from 2^k + 1 to 2^(k+1) is identical except for the last number, which is increased by 1; then solving the recurrence).

      Next, we use this identical property to our advantage. For a number n, we can write this number in binary as a sum of decreasing powers of 2. The key observation is, using the property, we can see that the first 2^m numbers after a number divisible by 2^n is identical to the first 2^m numbers, for n > m. This means that the sum of the first n numbers is the sum of the sum of the first 2^k numbers for each power of 2 in the decomposition.

      Then, we group the powers of 2 in our sum together and the -1s together. Note that the powers of two are each 2* the original powers in the number; so they sum to 2^n. Next, the -1s appear for each power of 2 in the summation, aka the number of digits in binary. This is the __builtin_popcountll(n).

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can someone explain this solution please, I'm having trouble understanding how this works.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +27 Проголосовать: не нравится

      If you make a sequence of bits from 1st place to 64th place:

      1st-bit place sequence:0 1 0 1 0 1 0 1 0 1 0 1 0 1 0.....(n+1 terms)

      2nd-bit place sequence:0 0 1 1 0 0 1 1 0 0 1 1 0 0 1.....(n+1 terms)

      3rd-bit place sequence:0 0 0 0 1 1 1 1 0 0 0 0 1 1 1.....(n+1 terms) and so on... ..till 64th bit. For each bit sequence, the value added to the distance will be equal to the number of terms in sequence for which s[i]!=s[i-1](i.e. the number of terms which differ from their previous term).

      1st-bit place sequence:Value added = n

      2nd-bit place sequence:Value added = n/2

      3rd-bit place sequence:Value added = n/4 and so on... ..till 64th bit.

      Final answer = n + n/2 + n/4 + n/8 + ......

      Hope this helps you to understand better.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Hello! Thank you for the explanation. I have a doubt in mind regarding choosing n, n/2...

        If our given number is 8 then, for 2nd LSB, our values change after every 2 numbers. The numbers are total (8-0+1)/2 = 4 from 0 to 8. So, there is a bit difference of 4. Whereas, your solution directly gives 8/2 = 4.

        If our n = 13 then, for 2nd LSB we have (13-0+1)/2 = 7 which is odd. That means, that our n, and n-1 had 0 in their 2nd LSB. So, we should subtract one from 7 which should give 6. Your solution gives directly 13/2 = 6.

        Did you choose n/2, n/4,.. instead of the other way that I have mentioned above because it works in all the cases and requires less computation or am I missing something?

        Thank you!

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I am not able to understand on what logic are you deciding to subtract one(as you have mentioned in the third paragraph).

          For eg: if n = 11 then, for 2nd LSB we will have (11-0+1)/2=6 which is even. To be correct we will again have to subtract one from 6 to get 5 (which is the correct value of distance).

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks a lot

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Can you explain how this works,

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      Number of swaps in LSB bit is n, for second last bit n/2 and so on...

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      In case you are asking for C See how each bit changes consecutively for the sequence of numbers from 0 to n , for example, consider $$$0th$$$ bit it changes(means 1 to 0 or 0 to 1) every consecutive element (see it as $$$2^0$$$) now consider the second bit it changes after $$$2^1$$$ times similarly 2nd bit after $$$2^2$$$ times... so the answer becomes $$$n+n/2+n/4$$$....till zero (each term for each bit).I hope this helps.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

I wrote "2*n — #bits set" but it gave WA. Pls correct the tutorial/editorial.

EDIT: Sorry @below, you missed the absurdism

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    did you make sure that you were checking all 64 bits? For ex, in C++, cout << 2 * n — __builtin_popcountll(n);

    use: __builtin_popcountll(n) and not __builtin_popcount(n).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      please explain how did this formula come ?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Let say for ex. we have 11010 which is equal to 10000+1000+10 hence for 10000 we have (2^(4+1))-1 for 1000 we have (2^(3+1))-1 for 10 we have (2^(1+1))-1 because for 2^k answer is (2^(k+1))-1 as explained in ED. so now we have ans as ((2^(4+1))-1)+((2^(3+1))-1)+((2^(1+1))-1) therefore ((2^(4+1))+(2^(3+1))+(2^(1+1)))-(1+1+1) and as we know this ((2^(4+1))+(2^(3+1))+(2^(1+1))) is shifting one bit to the left i.e. multiply by 2 and (1+1+1) are the number of bits where we have '1' hence ans is 2*N-number of set bits Hope this will help

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          for 10000 why (2^(4+1))-1 ?

          pls, anshul565

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            first 10000 means 16 in decimal so for 10000 i.e 2^4 we can calc it by using what we know from ED i.e. for 2^k ans is (2^(k+1))-1 hence for 10000 we have (2^(4+1))-1 Summing these up we get that the result for n=2k is equal to 2k+1−1=2n−1.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

wow fast editorial

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Is there anyone "Wrong answer on test 41" in div1.A like me ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    There are many. Just use the filters in status tab.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I just use a set to count the number of adjacent topic which less than or equal to the current one, and forget to specially judge the topic with the same id with it...

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        lol I wrote in my code as comment

        /* check if possible
         * adj must contain all smaller numbers, and must not contain i.
         */
        

        But did not check for "must not contain i" ;)

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Wait, but doesn't it contradict this requirement: Each pair of blogs that are connected by a reference has to cover different topics because otherwise ? I assumed there are no edges connecting the same topic.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I made the same mistake and I feel very stupid now :(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I got WA on test 41 too.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Did you notice that m and n can be 5e5? I can't see your code at this point, so trying to guess.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well, for me it was Div2D, but same. I couldn't imagine a edge case here :/

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you help me why does checking every neighbour not give TLE? There can be many neighbours of each node right so won't it be O(n2)?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Checking each neighbor means iterating through each edge twice. There are 2*m computations, that's why it won't give tle.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

div 2 C had so many solutions!

1.  2*n-setbits(n).
2. authors solution.
3.  my solution which I found after an hour of analysis-all 2*n give 1 , all 4*n+1 give 2,all 8*n+3 
   give 3..and so on...
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    yup, I too found a pattern like 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 but wasn't able to code it during the contest.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But that pattern is wrong, the right pattern is like 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I too got the same pattern. My solution: 82542445

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        can you explain your solution?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          You can see that there's a pattern of 1,2,1,3,1,2,1,... Let's say n = 21. Binary representation of 21: 10101

          Observations:

          Number of 1's in pattern = c1 = ceil(21/2) = 11

          Number of 2's in pattern = c2 = floor(21/4) = 5

          Number of 3's in pattern = c3 = ceil(21/8) = 3

          Number of 4's in pattern = c4 = floor(21/16) = 1

          Number of 5's in pattern = c5 = ceil(21/32) = 1

          We take ceil() when ith bit is 1, and floor() when ith bit is 0. (1 <= i <= |s|) Hence, answer = c1*1 + c2*2 + c3*3 + c4*4 + c5*5.

»
4 года назад, # |
  Проголосовать: нравится +98 Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +145 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -92 Проголосовать: не нравится

Div 1 A was so confusing, their output makes ABSOLUTELY no sense. Why can't i just print 1 2 3 instead of 2 1 3?

Order does not matter!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    The desired output is in the order of number of blogs in which they were filled. Please read the question properly. 1 2 3 is not the correct output.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    If you print 1 2 3, the topics on the nodes adjacent to node 1 have not been set yet, so node 1 would have topic 1, and not topic 2 as desired.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

It took me more time to solve A and B then C and D combined. I did not freak out initially and so was able to eventually solve C and D. Overall a great contest for me. Hopefully I will become an expert.

»
4 года назад, # |
  Проголосовать: нравится +86 Проголосовать: не нравится

This round tests participants' English level.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Solution C is a sequence from OEIS. $$$a(n) = a(floor(n/2))+n$$$

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will the solution given by editorial of problem B of div 2 not give tle? Since,the time complexity will be O(T*N*N) which is O(N*N*N)!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    No, because sum over all $$$N$$$ is at most 1024!

    So you can't look at it like maximum of $$$N$$$ and $$$T$$$.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      ok,so does it mean if x1+x2+x3+...+xn<=k => x1*x1+x2*x2+....+xn*xn<=k*k

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

      Even if it were $$$T*N*N$$$, not all of the last step would reach $$$N$$$ if you check for existence and break early. Though that could be quite tight.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "It is guaranteed that the sum of n over all test cases will not exceed 1024"

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Pretests for Div2 C should have been stronger.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain why this code for Div2 C fails:

#include <iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int main() {
  int t;
  cin>>t;
  while(t--){
    ll n;
    ll res = 0;
    cin>>n;
    int highestBit = floor(log2(n)) + 1;
    
    for(int k = 0; k < highestBit; k++){
      res += (n/(pow(2, k)));
    }
    cout<<res<<endl;
  }
}
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    Try using your binary power function, inbuilt pow is quite unreliable.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Your code works, you just have to note that

    1. pow returns a double so you should cast it back to an integral type before doing further computations in order to preserve precision.

    I made this fix an it passed:

    #include <cmath>
    #include <iostream>
    using namespace std;
    typedef long long ll;
    int main() {
        int t;
        cin >> t;
        while (t--) {
            ll n;
            ll res = 0;
            cin >> n;
            int highestBit = floor(log2(n)) + 1;
    
            for (int k = 0; k < highestBit; k++) {
                res += (n / (ll)pow(2, k));
            }
            cout << res << endl;
        }
    }
    
  • »
    »
    4 года назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Same happened with me also. I used inbuilt log2() function present in c++ but got TLE on test case 8. Here is my code https://codeforces.com/contest/1362/submission/82540420

    int fun(int n){

    int x=1ll<<((int)log2(n));
    
    if(n-x==0)
        return (1ll<<((int)log2(x)+1))-1;
    
    return (1ll<<((int)log2(x)+1))-1+fun(n-x);

    }

    This was my function which calculate the answer (sorry for bad implementation) which got wrong due to inbuilt log2 function:(

    2^59=576460752303423488 => (int)log2(576460752303423487)=58 but it given ans as 59 and due to this my submission got wrong.

    This happened due to floating point errors caused by c++ inbuilt functions. After this i come to know that never trust these inbuilt functions:(

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

      use the function written below .. instead of inbuilt log2 function. P.S. " this will work only for gcc compilers "

      int log(long long int x)
      {
      return 64- __builtin_clzll(x) -1;
      }

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Johnny and His Hobbies question will the given solution not give time limit as t value is also upto 1024 and we are using O(n*n) solution so it can go upto 10**9 ??

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is ok because sum of all N over all tests is small, just 1024.

    Look at this comment , and also check others below, maybe it will help you.

    That is the point of the statement from the Input sectoion: "It is guaranteed that the sum of n over all test cases will not exceed 1024."

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In the Div2B editorial:

It uses the observation that if $$$k$$$ satisfies the required conditions, then for every $$$s \in S$$$ there exists such $$$t \in S$$$ ($$$t \ne s$$$) , that $$$t \oplus s=k$$$.

Can someone give proof of this?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if not, then k would not have satisfied the condition.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Given that $$$k$$$ is the answer, lets observe some $$$a$$$ — it will become $$$a \oplus k$$$. Since we said $$$k$$$ is answer, then $$$a \oplus k$$$ is also a number from the original list — that will become $$$a \oplus k \oplus k = a$$$ !

    You can go as far as saying that numbers must come in pair!

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Seems like the pretests were pretty weak in Div2C and Div1A, a lot of solutions failed in System Testing.

»
4 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Will the solution given by editorial of problem B of div 2 not give tle? Since,the time complexity will be O(T*N*N) which is O(N*N*N)! Please if anyone knows ,please explain me!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    In general sum of n over all test cases will not exceed N(1024) means if you put all the testcases in 1 testcase the max n is N(1024). Treat them as 1 testcase and then analyze the complexity for given constraints.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

DIV2 B -> gave TLE in system testing on test case 7 https://codeforces.com/contest/1362/submission/82518343 Can someone please explain the reason

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C was simple. I saw the pattern but couldn't implement it on time.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i have found pattern like 1,2,1,3,1,2,1,3... but my pattern doesnt work can you help why?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      for every power of 2, change increases by 1. 2^0 = 1, 2^1 = 2, 2^2 = 3, 2^3 = 4.

      So the pattern will be 1,2,1,3,1,2,1,**4**(not 3)

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I also got this pattern but could not figure out how to use this for to compute the value for n.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          every odd gives 1, every mult of 2 gives 2, every mult of 4 gives 3, etc. so compute the amount of of 2s,4s, etc. by division

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            This is exactly what I am doing. For each iteration I am counting the number of 1,2,3,4.. so on,

            But I don't no why I am getting WA on TestCase 4. More specifically it fails for larger values of n.

            from math import ceil
            
            for _ in range(int(input())):
                n = int(input())
                i = 0
                ans = 0
                while (1<<i)<=n:
                    ans+=(i+1)*ceil((n-(1<<i)+1)/(1<<(i+1)))
                    i+=1
                print(ans)
            
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    I think editorials solution is complecated. Actually

    First bit changes every time.
    Second bit every second time.
    Third bit every 4th time.
    ...
    

    So we just have to collect the sum:

        int ans=0;
        for(int i=1; i<=n; i<<=1) {
            ans+=n/i;
        }
        cout<<ans<<endl;
    
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Yeah, I have the same solution. I think it's easier to understand.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

In problem D1A, \textbf doesn't work. In fact some of LaTeX's text commands doesn't work in codeforces. (but works in polygon)

Example :

\dots \ldots \textit \texttt \textbf \t \url

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Does there exist an O(n) solution for Div2 B?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    I belive so!

    Idea
    Problem

    If anyone knows how to solve "Problem", i would really appreciated it! :)

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      I have the same idea, but failed 14th test when we have odd number of pairs and xor of all items = 0 :-(

      Fix it and now it is the fastest solution so far https://codeforces.com/contest/1362/submission/82600948

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        your solution is still O(n^2) right?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Cool bro, if you find how to solve that problem when it is $$$N^2$$$, I would love to hear it!

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          MatesV13 take any element x from the set , now if such a k exists then , this x becomes x xor k, then some element must become x , so x and x xor k must exist in pairs, So let say there are 2 elements x and y = x xor k, now k = x xor y, so hence k is one of the pairwise xors of all elements in the given set . All these elements are from 1 to 1023 , which means it has at most 10 bits which are meaningful.

          Let's find what is the maximum xor you can get from any 2 elements of this set. In worst case i can choose any element x from the set, and choose another element such that if the each bit is set in x , it is unset in y, and if bit is unset in x , it is set in y, So this way i will get all set bits , since 0 xor 1 is 1 and 1 xor 0 is 1 hence the maximum i can get would be 1023.

          Hence i can say that if a k exists it is between 1 to 1023 , Now iterate for each k from 1 to 1024, make a new set in each iteration and compare with original set , hence this is O(n^2)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Having macro #define int long long in code for div2B Johnny and His Hobbies gave TLE at test case 7 in the system testing, after removing this macro it passed all the test cases :(. Can someone please explain

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

div2C has easier solution.

If we write down binary representation of numbers from 0 to n in a column. We can notice a pattern:

the first bit(counting from the right) changes its value each time as we go from 0 to n

the second bit changes its value after every second number

the third bit changes its value after every fourth number ...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I dont understand, the solution discussed for B is n^2 complexity right and for 1000 tc, the complexity will be 1000*1000*1000

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +25 Проголосовать: не нравится

For a more general version of the variant you proposed in C (which, sadly is how I read the problem in the first place), there exists an answer if and only if the frequency of the maximum frequent color is $$$ \leq n$$$.

Proof : This condition is clearly necessary as for each $$$i$$$, at max one of $$$p_{2i}$$$ and $$$p_{2i+1}$$$ can have color $$$c$$$.

For sufficiency, consider the strategy where we always choose the most frequent remaining color $$$c$$$, other than the current color (the right end of the rightmost pair) and append a pair such that $$$c$$$ is its left end. We will maintain the invariant that no color has frequency more than half of total remaining length. If $$$2 m $$$ pearls were remaining and the maximum frequency was $$$ \leq m - 1$$$, the invariant holds. Else, if there were two colors $$$p$$$ and $$$q$$$ with frequency $$$m$$$, one can either append a pair $$$(p, q)$$$ if it exists and if it doesn't exist, there must be atleast one pair $$$(p, p)$$$ and one pair $$$(q, q)$$$, and we can append these pairs in one of the two orders. Clearly, the invariant holds for the remaining length of $$$2m - 4$$$. If there is a unique color with frequency $$$m$$$, and it is not equal to the last color, the invariant holds as well.

Only remaining case is when there is only one color with frequency $$$m$$$ and it is the same as the last color. We prove that this never happens. For this, go back till the right end of a pair is not equal to $$$c$$$ (say at position $$$2i$$$), or to the beginning if there doesn't exist such a pair. In front of this pair, no pair could have had left end as $$$c$$$, else we'd have frequency of $$$c$$$ > half remaining pearls at that point. But after the position $$$2i$$$, $$$c$$$ must have been the only maximum frequent color and could have been added as the left end, so a contradiction.

Now, at the end of the process, if the first and last colors are different, we are done, as we can complete a cycle. Else, say the sequence of colors is $$$p_1 = q, p_2, \ldots, p_{2n} = q$$$. Find the last $$$i$$$ such that $$$p_{2i} \neq q$$$ and $$$p_{2i + 1} \neq q$$$ and reverse the suffix after it. If there doesn't exist such an $$$i$$$, the frequency of $$$q$$$ must have been $$$\geq n + 1$$$, as $$$p_1 = p_{2n} = q$$$ and for each $$$1 \leq i \leq n - 1$$$, $$$p_{2i} = q$$$ or $$$p_{2i+1} = q$$$.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

[deleted]

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Does someone mind explaining why Div.1 B works with the given solution? I still don't understand how it works!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Setting OEIS task must be banned it took me 60-70 minutes to just realise the pattern and solving the formula with bitmasking and observations after this task I was not having much time to solve an easy DIV2 D which was purely implementation based and I suck in implementation ,really I suck.

And that compared to another person who just googled it out breaks the spirit of competition and I think codeforces is not meant for such activities . Hope problem setters will not set OEIS tasks in future. Actually those who solve or do the competitive programming for learning or as a hobby and purely for improving their problem solving skills will never google out this things but such contestants are fewer and too fewer nowadays as ratism is prevailing over the programmers and they want to get ratings either by hook or crook ,which in long run is not gonna benefit. Thus Hoping my comment provides message to all those who are googling solutions during the contest.Please be motivated and happy coding

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    You can think of C as an "oeis" type task. To solve it, you have to cast a spell "Oh, it must be on oeis". Than you simply generate first few members of the sequence and google it

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

It would have been nice if the Problem Statement of Div1 A was more clear or Explanation of the 3rd test case was available from the beginning.

»
4 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

The statement of D was very bad. It took me 15mins to understand.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in div1A/div2D since there is no restriction on blogs for which neighbours have not been written, shouldn't a case like

6 5
1 2 
1 3
1 4
1 5
1 6
5 1 1 1 1 1

be doable by writing blog 1 first and then writing the other blogs in whatever order?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The topic of a blog is always the first unused topic of all adj, so it is always restricted.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But for the first blog, since none of its neighbours have been written why should its value be restricted to 1? For example in the example i gave before writing the first blog none of 1's neighbours have any values so it can be set to any value as the described algorithm of topic allocation does not specify what value it should take

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        It is restricted to 1 because the statement says so.

        "...and chooses the topic with the smallest number which is not covered by neighbors."

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

To Contest Committee: I think it's time to feel sorry first for the weak pretests and further for the weak systests.

Here is a submission for D:https://codeforces.com/contest/1362/submission/82565932

And it gets AC despite failing on:

4 3
1 2
2 3
3 4
1 3 3 1
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My submission fails the above test, yet it passed the system tests for Div2 D. A similar test case is:

    2 1
    1 2
    2 2
    
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Lol, woke up this morning and was looking at my D solution proudly, and then I noticed I had used == instead of <= in an if statement by mistake. So, here's another :

    5 3
    1 3
    2 3
    4 2
    1 2 3 1 4
    
    

    But I am really surprised, how was this not a part of the systests lol. They messed up, but still it's fine, shit happens.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

In Div. 1 B, if you were lazy and did not want to (for whatever reason) keep track of $$$s/p^k$$$, it is also possible to pick some prime numbers from a large set of primes (let's say, from the first $$$10^9$$$) at random. If you pick enough of them, then with high probability, $$$s = 0$$$ only when these primes divide $$$s$$$. A good bound can be proven by noting that $$$p^{10^6}$$$ can have at most $$$\approx 10^6$$$ unique prime divisors. So the chance of a comparison failing would be at most $$$10^{-3m}$$$, where $$$m$$$ is the number of primes chosen. Thus, you can do some operations modulo these primes. It was actually possible to pass in the contest by picking some large hardcoded primes, but you would risk getting hacked. But without hacking, there's not really a sure way to block these solutions.

E.g., see this solution, which got uphacked: https://codeforces.com/contest/1361/submission/82528165

»
4 года назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

I suspect from the number of solves on Div1C/Div2F that many people, even in Div1 (myself included), did not know off-hand how to efficiently construct an Eulerian cycle when one exists.

Testing for existence of an Eulerian cycle is well known and easy enough to implement: A graph has an Eulerian cycle if and only if no vertex has odd degree and the vertices of positive degree form one connected component. The constructions for such a cycle I had seen, however, are not easy to directly apply to a problem of this size. The approach I came up with, which I wasn't quite able to implement within contest time, was to use (implicit) linked lists to efficiently combine cycles in the graph, and to find cycles by greedily following and removing edges not already used until there are none left.

This cycle-finding approach uses a simple invariant: At each step, either the current vertex is the start vertex and every vertex has even degree, or the start vertex differs from the current vertex and these two are exactly the vertices with odd degree. In particular, there is always another edge to follow except at the start vertex.

To create a full Euler cycle, pick an arbitrary starting vertex with positive degree, and generate some cycle from that point. Then, traverse this cycle around the graph, but whenever a vertex is reached that still has positive degree, call the basic cycle-finding method at that vertex and insert the basic cycle found at the current point in the cycle being traversed. To see that the resulting cycle includes every edge and is thus an Eulerian cycle, note that it contains every edge out of every vertex visited by the cycle. Since the set of (initially) positive-degree nodes is connected and it starts at some (initially) positive-degree vertex, this means that it visits every (initially) positive-degree vertex and hence includes every edge.

My solution, as it was ten minutes after contest end (i.e. unpolished and poorly documented but functional): 82567455

This isn't quite the approach taken by the solution in the editorial, which (at a quick glance) uses recursion to accomplish something similar using vectors. I thought about taking a similar approach, but was afraid a stack overflow might be possible on some test cases since the recursion depth might reach 250000 on malicious inputs unless special care is taken.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It looks like you were right to be worried about recursion. My recursive DFS solution timed out, and it was fine after I switched it to a stack. Really annoying though...

    The tutorial solution is tail-recursive, which may be the difference, although I am not sure how much the C++ compiler optimizes it.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Which function is tail-recursive in the editorial code? For some reason I'm not able to find it; it seems like just regular use of recursion to me (e.g., in function go(), there is definitely code following the recursion).

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        You are right — it's not tail recursive (not sure what I was thinking).

        It's still a bit of a mystery why my original solution doesn't pass — after comparing my dfs with the tutorial, mine doesn't seem noticeably heavier. Maybe I just did something else wrong (infinite loop?).

        EDIT: After looking over it, my dfs was simply inefficient (for high-degree vertices it went through all their neighbors multiple times). So recursion should work fine.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me why my solution for B is showing tle? https://codeforces.com/contest/1362/submission/82505539

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Div2 problem A if we fix the size of max number of bits to 64 and had allowed overflow then can somebody please suggest me a solution

»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Solution of C is very easy:

while(q--){
    long long int a,c=0; cin>>a;

    while(a){
        c=c+a;
        a=a/2;
    }
    cout<<c<<endl;
}
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank u. Can u explain how it is working? I mean, math behind it ?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Let any number(for e,g. 10 ), then we have to find sum of bit differences from 0 to 10, but instead of comparing 0-->1, 1-->2, 2-->3,... we will take different approach, first let write the numbers in bit form,

      0 -  0 0 0 0
      1 -  0 0 0 1
      2 -  0 0 1 0
      3 -  0 0 1 1
      4 -  0 1 0 0
      5 -  0 1 0 1
      6 -  0 1 1 0
      7 -  0 1 1 1
      8 -  1 0 0 0
      9 -  1 0 0 1
      10-  1 0 1 0
      

      Consider it a matrix of [11][4], so instead of going top to down, we will go comparing right to left (cause we only need sum of all differences so it won't matter sum will be same).

      LOGIC: In the matrix if we go from right to left, we see the last column of the matrix every bit differs by it's neighbouring bit {0,1,0,1,....}, so, sum += 11; Next, second last column every 2nd bit differs by it's neighbouring bit {0,0,1,1,0,0....} so, sum += 11/2; } similarly if we do same till the first column, we get the sequence,

      while(n){
           sum+=n;
           n=n/2
      
»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

language was very tricky in this round...overall good contest...thanks

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

I think the time limit for Div1 B could have been relaxed to 3/4s as the modulo operation is slow. Many solutions failed even if they had the desired asymptotic complexity.

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Div2D/Div1A — Johnny and Contribution The hardest readforces statement ever seen.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I feel there is some issue in question A, i used a simple approach of dividing the maximum of them by minimum and then that dividend must be in powers of 2 and then i applied log to the the power value.

After this i simply from 3 two'2 to get 8 2 two's to get 4 and 1 two to get two, and it's running for the test cases in the problem.

Please help out.

link to the solution : https://codeforces.com/contest/1362/submission/82512703

Thank you

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Since in this testcase the answer is 20, the numbers are fairly huge, like 1 and 1<<60

    Not sure if this is handled correct in python.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have done the same in C++ getting WA in the same test case don't know where the error is

»
4 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

For Div2E/Div1B-Johnny and Grandmaster, why does the strategy given in the editorial works?

  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +9 Проголосовать: не нравится

    So, i understood the editorial in the following way:

    First, if p>1, then we sort the array(that contains powers of p) in non-increasing order. Now, we have a variable $$$s$$$ that will denote the difference between the two partitions. Initially, s = 0. Now, If s = 0, we add the current element to sum.

    If s>0 then we subtract the current element from s. The result will be non-negative. This is because: If current element is $$$p^x$$$ and s>0, then let $$$s = p^{a} - p ^{b} -p^{c} + p^{d}$$$ (The operation among $$$p^i$$$'s can be both addition or subtraction), where a,b,c,d are non increasing sequence. Hence, $$$s = p^d*(p^{a-d} - p ^{b-d} -p^{c-d} + 1)$$$. The second factor can only be positive since s>0 (If second factor is 0 then s = 0). Now if second factor is 1, then s = $$$p^d$$$ and $$$p^x$$$ is less than or equal to $$$p^d$$$. So after subtracting it from s, s can be 0 or positive. If second factor is greater than 1, then $$$s>p^d$$$ the subtraction will yield a positive s.

    Note that till now we are not doing modular addition or modular subtraction. Now, at any element, if $$$\frac{s}{p^x}$$$>n, implies $$$s > n*p^{k_i} $$$, implies $$$s$$$ is so large that even if the rest of the elements are equal to current element (which is largest possible value for them), s will not become 0. (I think here n is the length of array that is not processed yet). So we know that all the other elements belong to one partition. And after this moment, we can do modular subtraction for the rest of the elements.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Do you know how to check if s > n * p^k_i ? I can't understand that part of the editorial. Thanks

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you great posting. I have one question about modulo operation. Why can't we take module before $$$\frac{s}{p^x} > N$$$ is satisfied?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

        Because we need the s value and not s%MOD to take the decision whether the current element goes to first or second partition. Let's say s becomes MOD(so s%MOD becomes zero), then we will add the current element instead of subtracting it. Having s = 0, would mean that both the partition have equal sum and we add the current element because we can keep the current element in any partition. But having s%MOD=0 means that one partition might have MOD problems more and in that case optimal step is to subtract the current element.

        Also, if we consider s%MOD in the condition $$$\frac{s}{p^x}>N$$$, then we want s to be a very high value to satisfy but s%MOD will never exceed MOD, so if we take s%MOD before the condition fulfills, we might never achieve the condition.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You can just calculate the sum modulo the whole time. To check whether to add or subtract, you can use $$$s/p^i$$$ instead, since if $$$s = 0$$$, so does $$$s/p^i$$$.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hey, you described the solution very well. But it does not prove why is this optimal solution. https://codeforces.com/blog/entry/78355?#comment-636627 . This comment gives the proof.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Not solving C cost me Another Rating Drop

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

1362C — Johnny and Another Rating Drop

This was my solution(82558750) but last test case (test case 8) input 2**59 — 1 it failed

log2(2**59 -1) = 59 was evaluated by my code and was giving answer of 2**59 can anyone help what should I do for that

import java.util.*;
public class Rate_Drop {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- != 0) {
            long n = sc.nextLong();
            long final_val = 0;
            while(n >= 2) {
                long log_val = (long)((Math.log(n) / Math.log(2)));
                final_val += func(log_val);
                n = n - (long)Math.pow(2, log_val);
            }
            if(n == 1) {
                final_val += 1;
            }
            System.out.println(final_val);
        }
        sc.close();
    }
    public static long func(long n) {
        long prev = 0;
        for(long i = 0; i <= n; i++) {
            prev = prev * 2 + 1;
        }
        return prev;
    }
}
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In C++ log2 uses floting points with precision up to 1 decimal degit and hence gives the wrong answer. Changing log2() to log2l() helped me to get AC.

    other way is to use bits taking & with (1ll<<i)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone pinpoint what the error is? Problem A (Div. 2) Submission Expected -1, But printed 20.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    You are using floating point arithmetic, your values are casted between long long and double. A double uses less than 64 bits for precision (I think 56, but not sure). So at some point you simply get presission loss and one of your log2() or ceil() call returns not the expected value.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      82561759 Hey, beginner here. Would you mind taking a look at my submission too? I failed at the same test case but I used a while loop instead... is this cause for error similar and how do I fix this in python.

      Thanks in advance!

      Edit: I saw your reply on python on an earlier thread. My bad!

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It seems that it is complecated in python to say how much bit an int has. stackoverflow

        Since the testcase is the one where $$$a==b«{60}$$$ I think that is the problem.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for your reply! So is there a better way to check if a number is an integer? I didn’t want to keep multiplying 2 in a while loop, because some easy math will directly give the power of 2 with which we should multiply.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The problem with floats is that they are silently truncated. So there is actually no way to check if a double is really an int. All you can do is checking if it looks like an int. If it does it maybe is an int, or the part which is different from an int is so small that it was truncated.

        This is error prone. Basically everytime you think you need to check if a floating point variable is an integer your implementation is simply wrong.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          True.

          So maybe after computing x = floor(log2(b/a)), I can check if b == a*pow(2,x) ? That should take care of the issue I guess.

          Thanks again, learned something new!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

nice round fast editorial language of div2D/div1A was too heavy..took me around half an hour to understand....but could not solve during the contest

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Okrut (previous revision, new revision, compare).

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

Another solution for C

Let the position of rightmost zero in nth number be ith position then we know in next number (n+1 th number) all the bits from 0 to ith position will be flipped and only these bits will contribute to our answer so the contribution of any nth number to total answer depends on the location of rightmost zero bit in n-1th number. so we want to find how many numbers are there which have all bits 1 up to i-1th bit and has a zero on the ith bit. It turns out that the number we are looking for has form k*(2^(i+1)) + (2^(i)) — 1. (i = 0, 1, 2 ...) equate it to n for each i find k(take ceil) multiply it by corresponding i and sum them. the total sum will be the final answer

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For Div2 Problem E, can someone please explain me why a simple approach like this does not work?

#include<bits/stdc++.h>
#define M 1000000007
#define pb push_back
#define ll long long int
using namespace std;

ll binexp(ll x, ll y)
{	
	ll res = 1;
	while(y!=0)
	{
		if(y & 1)
		{
			res = (res*x)%M;
		}

		y=(y>>1);
		x = (x*x)%M;

	}

	return res;
}


int main()
{
	int t;
	cin>>t;

	while(t--)
	{	
		int n,p;
		cin>>n>>p;
		int k[n];
		int i;
		for(i=0;i<n;i++)
			cin>>k[i];

		sort(k,k+n);

		ll ans = binexp(p,k[n-1]);

		for(i=n-2;i>=0;i--)
		{	
			ll curval = binexp(p,k[i]);
			if(ans==0)
				ans = curval;
			else
				ans=(ans+(M-curval))%M;
		}

		cout<<ans<<"\n";
	}
	return 0;

}

My guess is that it is because of modulo operation. Can someone explain a little about how it is being handled in the author's solution?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Because the (ans==0) condition may be true even when the absolute difference is not 0. Your solution will change ans to curval (i.e. add curval to it) whereas it may be required to be subtracted.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      This solution can actually pass, if you check the answer modulo multiple primes rather than just one. But it is not as safe, and if you hardcode them, it’s possible to hack.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain with an example?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        If we take p=31623 and then the values of ki's are: 2, 0, 0, 0, 0,.......(around 15000 zeroes), then there will be a case when difference becomes 10^9+7 but since we are keeping it modulo, it will be considered as 0 in the code.

        And the next 1 would be added making ans=1 at that step while correct value should be 10^9+6 at that step.

»
4 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

The writers dont know how to write questions. The Div1 A was kinda encrypted!

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

In Div2 E/ Div1 B, How do I prove that for the optimal solution, the sum of the partition containing the highest power will always be more than the sum of the other partition?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Correct me if wrong but I simply thought in base 'p' representation of number , so like binary we are focusing on comparing the MSB.

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Div1 C was an enjoyable problem, even though I couldn't get it done within the contest. Thanks for making this particular problem! :)

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I don't really understand the editorial of Div. 2 QE, can anyone explain? Thanks!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Me neither, I have no idea what the tutotial is saying. Can someone help explain?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится
    • Sort the $$${k}$$$ array in non decreasing order. Now start from the right most index say $$${n}$$$

    • Suppose if $$$\sum\limits_{i=1}^{n - 1}{p^{k_{i}}} < {p^{k_{n}}}$$$ then we put $$${p^{k_{n}}}$$$ in one set and the remaining powers in other set and compute the powers and their difference.

    • If $$$\sum\limits_{i=1}^{n - 1}{p^{k_{i}}} >= {p^{k_{n}}}$$$ then $$$\exists j : \sum\limits_{i=j}^{n - 1}{p^{k_{i}}} = {p^{k_{n}}}$$$. Then we can put $$${p^{k_{n}}}$$$ in one set and $$$\sum\limits_{i=j}^{n - 1}{p^{k_{i}}}$$$ in other set to make their absolute difference 0. Now go to index $$${j - 1}$$$ and repeat the process.

    • This can be implemented by using a stack and processing the $$${k_{i}}$$$'s from the right most index to the left after sorting in non decreasing order. When you see $$${p}$$$ $$${k_{i}}$$$'s in stack remove them and convert it to one $$${k_{i}}$$$ + 1 and proceed further.

    • Here is my submission for reference 82581557

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      How to prove that there exists such j ? UPD — Convinced myself by thinking in terms of base p.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you write how you are convinced in more detail here

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          I will try — $$${p^{k_{n}}}$$$ = $$${(00..010...)}_{p}$$$ where on-bit is position $$${k}_{n}$$$. Assume $$${k_{n-1}}$$$ is less than $$$k_{n}$$$ otherewise take them in different sets and proceed. Let $$$j$$$ be the largest index such that adding $$$p^{k_{j}}$$$ will result in sum $$$greater$$$ $$$than$$$ $$$or$$$ $$$equal$$$ $$$to$$$ $$${p^{k_{n}}}$$$. Before adding $$$p^{k_{j}}$$$ state will look like — $$${(00...(p-1)(p-1)(p-1)(p-1)...(p-1)00..00)}_{p}$$$. Earlier digits are not set because we are proceeding in non-increasing powers.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      I tried to simplify the implementation and add comment- 82689935

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can anyone please tell me the proof for div2 E

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the solutions! But I wonder why my solution didn't work last night. I checked how many bits the greater one has to shift in order to get the smaller one. I greedily checked how many 3's, 2's and 1's I can shift. However, it didn't work. Can you help me out? Thanks!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution for DIV 2 E seems to give Time limit exceeded on test case 7 .. Can someone point out the issue in my code.. it will be very helpful My Submission

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could anyone please help me debug my code for problem div2A: 82590156. I get wrong answer on test case 2. My idea is to check q = b/a. if q is a power of two then greedily count the steps, if it is not then print -1.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Even I was using the same logic. It seems some implementations with float numbers might fail due to precision errors. Its even mention in editorial div 2 C -- educational round 88.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks, I have found out which test my code fail.

      1 576460752303423483

      or

      1 2^59-5

      The log2 function cannot spot the difference. Maybe I will change it to some bitwise operation.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You know the log2() function comes in severeal flawors. If you use the one working with long double instead of double it would work better.

        But of course, using integer arithmetic is the better solution. I just wanted to point out that it is not the log2() function that causes the error, but the used data type.

»
4 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

can someone help me spot the error div 2 problem B round 647?

include

include<bits/stdc++.h>

typedef long long int ll; using namespace std;

int main()
{ ll t1; cin>>t1; while(t1--) { ll n; cin>>n; ll a[n]; set s1; for(ll i=0;i<n;i++) { cin>>a[i]; s1.insert(a[i]); } if(s1.size()==1) cout<<"0"<<endl; else {

ll f=1; 
   for(ll i=1;i<=1023;i++)
    { f=0;
        for(ll j=0;j<n;j++)
        {
            if(s1.find((a[j]^(i)))==s1.end())
             {

                 f=1;
                 break;
             }
        }
        if(f==0)
        {
            cout<<i<<endl;
            break;
        }
    }
    if(f==1)
     cout<<"-1"<<endl;
   }
}

}

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please prove the observation 2 in the editorial of Div 1A/2D?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    johnny has to color from 1 to target-1 because if any of those numbers are missing then he'll color a number lower than target

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have been stuck in question C like from last night.

It is showing wrong at test case four, I don't know why it is passing all other n <= 10^18

Can somebody please please help me out. Thanks in advance!!

My Solution

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I was trying to do it in O(bit length of n)

    Solution Explanation: Old number in (0,1,2,.....n): difference = 1 like between (1,2) or (3,4) Multiple of 2 : difference = 2 like in (2,3) Multiple of 4 : difference = 3 like in (4,5) or (12,13) Multiple of 8 : difference = 4 like in (8,9) or (24,25) Multiple of 16 : difference = 5 like in (16,17) and so on...

    So I first find these multiple and then multiply with respective differences

    Someone Please help, I don't understand why it not passing Test Case 4!!

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      twos[i] = n/pow(2,i);

      I assume there are huge values of n where you do net get the expected result. Just do not use pow here, instead do 1LL<<i.

      And there is no need to go up to 66, 63 is enough.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can someone please tell the mistake in the solution of my Div1B solution 82594745. If I change LIM = 1<<12 to LIM = n-i, it becomes AC 82595479.
The logic is simple, I keep on subtracting the i-th number until the current value turns 0 in the reverse sorted array. If the value is 0, I make i-th number the current difference.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

could someone explain why this solution fails at A? https://codeforces.com/contest/1362/submission/82596448

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

int main(int argc, char** argv)
{
#ifdef LOCAL
  freopen(strcat(argv[0], ".in"), "ab+", stdin);
#endif
  
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    uint64_t a, b;
    cin >> a >> b;
  
    if (max(a, b) % min(a, b) == 0) {
      uint64_t x = max(a, b) / min(a, b);
      if (a == b) {
        cout << 0 << endl;
      }
      else if (log2(x) == ceil(log2(x))) {
        double p = log2(x);
        cout << ceil(p / 3) << endl;
      }
      else {
        cout << -1 << endl;
      }
    }
    else {
      cout << -1 << endl;
    }
  }
  
  
  return 0;
}

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    try considering that case when u can divide by 4 also ! n%8 will not suffice for the greedy solution

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div1C

Can anyone help me with this submission? 82597192

I don't know why it TLE.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

log2 of the number 576460752303423487 is 59.0 while 2^59 is 576460752303423488 (one more)

I can't understand this unusual behaviour.

Many solutions of DIV2C got TLE because of this.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I got my answer. log() operation uses floating point numbers and offers precision up to one 1 decimal point.

    hence log2 of number 576460752303423487 gives 59 instead of 58.9999999999999999975.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Hello, why does the greedy algorithm for d1B work ? I tried proving it for around an hour during contest but I was far from being confident it was true. I submitted it after seeing so many people solving it. But I can't come up with a satisfying argument for this.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    By induction: The base case is trivial, as the greedy strategy is clearly optimal when n=0 or n=1. The recursive case relies on a parity argument. Suppose without loss of generality that $$$\{p^{k_i}\}_{i=1}^n$$$ is already sorted descending and we have already assigned the first $$$j$$$ terms in a way that minimizes the imbalance of only these first $$$j$$$ terms. Then, the magnitude of this optimal imbalance is clearly a multiple of $$$p^{k_{j+1}}$$$. Now, consider two separate cases: Either this optimal imbalance is positive, or it is zero.

    If it is positive, then it is at least $$$p^{k_{j+1}}$$$, since it is a multiple of that amount, so adding $$$p^{k_{j+1}}$$$ to the smaller side of some optimal configuration reduces the imbalance by $$$p^{k_{j+1}}$$$. But the (reverse) triangle inequality tells us that there is no way any configuration's imbalance can be reduced by more than $$$p^{k_{j+1}}$$$ by adding that term to either week, so reducing an optimal configuration by this amount cannot be improved upon.

    The case of zero imbalance is more subtle. Since switching any $$$p^{k_i}$$$ between the two weeks results in a net change of $$$2p^{k_i}$$$ and zero is an achievable imbalance, every possible assignment for the first $$$j$$$ terms will result not only in a multiple of $$$p^{k_{j+1}}$$$, but a multiple of $$$2 \cdot p^{k_{j+1}}$$$. Thus, applying the (reverse) triangle inequality again, adding $$$p^{k_{j+1}}$$$ to either side of a suboptimal configuration cannot achieve an imbalance of less than $$$2 \cdot p^{k_{j+1}} - p^{k_{j+1}} = p^{k_{j+1}}$$$. But this is obviously also achieved by adding $$$p^{k_{j+1}}$$$ to either side of an optimal configuration, so the greedy strategy again cannot be improved upon in this case.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I think this solution needs and assumes that the problem follows Optimal Substructure Property. How can we prove that this problem follows Optimal Substructure Property?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        This actually is a proof that the problem has the kind of optimal substructure necessary for the greedy algorithm to work. Specifically, the recursive case of the induction argument says that if the greedy algorithm produces an optimal (sub-problem) result after $$$j$$$ steps for some $$$j < n$$$, then the greedy algorithm also produces an optimal result after $$$j+1$$$ steps.

        It's easy to see that the greedy algorithm doesn't have any opportunity to make a mistake after $$$0$$$ or $$$1$$$ steps. (This is the base case I started with.) Then, applying the argument above with $$$j = 1$$$, the greedy algorithm must produce an optimal result after $$$j+1 = 2$$$ steps. But then the argument above can be applied again with $$$j=2$$$ to show that the greedy algorithm produces an optimal result after $$$j+1=3$$$ steps. And then with $$$j=3$$$, $$$j=4$$$, all the way up to $$$j = n-1$$$ to prove that the greedy algorithm produces the optimal (correct) result after $$$j+1 = n$$$ steps. This method of proof is called mathematical induction. Does that clear things up?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you for the proof ! I really had the bad representation for this problem, it is really clear now.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please explain this line?

      But the (reverse) triangle inequality tells us that there is no way any configuration's imbalance can be reduced by more than pkj+1 by adding that term to either week, so reducing an optimal configuration by this amount cannot be improved upon.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am stuck in D . Can anyone Help? Here is my Blog https://codeforces.com/blog/entry/78387

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Div2 problem D really tested participant's patience, concentration, and English. Really interesting set of problems. Thanks!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could you help me please on task A. Why does the checker give -1 in this test?

576460752303423483 1

Img solve
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    the question states divide only when it is divisible by 8,4,2 the first number you have chosen 576460752303423483 is not divisible by 8,4 or 2 So the answer is not possible

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The time limit of Div2-D should have been 1.5 seconds, in order to prevent several brute force solutions.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    the only solution was a brute force solution wdym, and it ran in 1.3s in java so you'd be screwing over slower languages like python by lowering it significantly

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone help me understand why my solution for Div2 A using log2() didn't work (WA)?

My solution: 82539547

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think in the last step you are taking ans as r/3 and then taking count++ for r%3!=0 You haven't checked for r%2 !!! I think You missed that ! You have 8 , 4, 2 and you are just assuming your division from 2 and 8

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Assume b==1 and a==(1<<60)+1

    Your call to log2 will cast a to double which will make the +1 go away because of precission loss. You could try to cast a explicit to long double so that the log2(long double) variant of that function is called.

    Or better, do not use floating point arithmetic for this problem at all.

»
4 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

expected there would be meme with each problem on tutorial

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For DIV2 E, let mod=1000000007, if(difference%mod==0) does that necessarily mean than difference is zero because mod is prime??

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    No. (diff%mod==0) doesn't always mean (diff==0).

    For simplicity, take mod = 7 (prime) and the following testcase:

    n = 3, p = 2, k = [3,0,0]

    Hope, you got it :)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"Observation 2: If for a vertex u with color c there exist a color c′<c such that u has no edge to any vertex with color c′ then the answer is −1."

Can someone please explain this to me. Its not obvious to me at all.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    suppose, we are at node 4 and its color is 5(according to given/desired sequence/coloring), and its neighbor nodes have color 2,3,4. And there is another node lets call it x and it has color 1. But node x is not referencing node 4, then according to the condition we have to color this node 4 with the minimum number of color which has not taken by its neighbor (which is 1 for node 4 in this case), but according to given/desired sequence it has color 5.

    So, contradiction happens. That is why always a node has to be connected to all of colors node (at least one for each color) less than his color. I hope you understood :)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Easiest solution for the Div 2 C

solution link : https://codeforces.com/contest/1362/submission/82613654

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

For anybody who didn't implement the solution for DIV 2D thinking of it as a brute-force solution(like the process of going to each node and visiting all of its adjacent nodes ) here's the proof for time complexity

PROOF
LESSON LEARNT

It might be a very obvious thing to observe for many but I was not able to prove it in time during the contest so just thought of writing it so others like me can get it too. Please correct me if you find anything wrong or unclear.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution on Div 2-D is constantly failing on test case 6 and outputs -1. Can anyone suggest the test case where it fails

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A neater solution to problem A using c++ built-ins

Solution
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Does the standard c++ log() function give erroneous results when used for higher numbers? For Div 2A, I first found b/a and if it is a power of 2, then I simply returned

ceil(log(b/a) / log(8) )

This gave error on the case 1 8589934592 Answer should be 11, i.e. log(8589934592)/log(8) But my code returns 12, whereas it works completely fine for the case 1 64

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please explain Div.2E/Div1.B, I couldn't get it from editorial. Thanks in advance.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

DIV 2->C my soln is working fine for smaller numbers but its giving WA for test case like 1 576460752303423487 can anyone help here is the link: https://codeforces.com/contest/1362/submission/82621109

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Am I the only one who solved A with BFS?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can someone prove for Div2E/Div1B why is the optimal sum never negative? I can somewhat see that you can for every negative sum instead find the positive sum with the same absolute value, but I can not prove it in my head at the moment.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I understand why substracting an element will always, if the sum is positive, yield at least 0 as the sum. I am not completely sure why it wouldn't be in some case better to go in the negative sum from the 0 sum.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        In other words, using the technique in the editorial the subset with the largest power has always the larger or at least equal sum compared to the other subset. Not completely sure at the moment how to really prove it, though it does seem a bit intuitive.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Let's assume that when we add a current element to sum, we add that element to first partition and when we suubtract the current element we add the element to the second partition. So, when the sum s is 0, we interprete that the two partitions have equal problems,(s denotes the difference of problems between the two partitions) so the current problem can be kept in any of the partition, Let's say we subtract the element when the sum is 0, mean we add that element to second partition and then when our sum is negative, the optimal way is to add the elements to first partition till sum reaches zero.

        In conclusion, this way is exactly the opposite of what is written in editorial. If s = 0=> subtract the current element. Add the current element till sum is negative.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          i have a doubt Karan123 . Why does the editorial subtracts largest exponent(k[i])with 1e6+10 in the start instead of adding p^k[i] to the s ,as s is initially zero ? And why does the editorial does modular exponentiation before checking the condition s>n*p^k?

          Thank you

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

            Yeah, actually I am also confused about the implementation of the idea. Actually, I came up with some other idea for implementation. First we sort the array in descending order, then according to the logic of the editorial, what we want to do is whenever same elements are present in the two partitions, we want to add the current element in first partition. Then as long as the elements in second partition are less, we keep on adding the elements in second partition. It is confirmed that as long as we know when the elements in the two partitions are equal, we can keep on adding the elements in second partition and also this process will not make number of elements in second partition more than the first partition without making the number of elements equal to each other.

            Now, first I kept a variable p1 that denotes that the number of elements in first partition is $$$p^{p1}$$$. And I add the value of $$$p^{p1}$$$ to the current sum. Now, I will keep on adding all the other elements to second partition as long as the number of elements in two partitions are not equal. Now, I have created a map of int-->int where map[i] will say how many $$$p^i$$$ are there in second partition. If I have current element as $$$p^x$$$, then I will increase map[x] by one. If map[x] becomes p, that means my second partition contains p $$$p^x$$$, that means it has one $$$p^{x+1}$$$. Hence, I can make map[x]=0 and increase map[x+1] by one. Now, if it had been that before this element, there were p-1 $$$p^{x+1}$$$, then it will have p $$$p^{x+1}$$$, Hence one more $$$p^{x+2}$$$. Recursively I ensure that at a given time my map has all map[i] less than p. Now, as I move through the elements if I have map[p1] = 1, that means that the second partition now has $$$p^p1$$$ elements which means both the partitions have same elements.Whenever map[p1] is 1, I have concluded that there are total $$$p^p1$$$ elements in the second partition, since the number of elements in second partition never jumps over the number of elements in the first partition. At this moment, I conclude that the current sum is 0, and I again add the next $$$p^x$$$ in the first partition. I have implemented this idea here:

            https://codeforces.com/contest/1362/submission/82699821

            (Actually prior to writing this comment I was stuck at this problem, but while writing this comment I found the bug and then got AC :) )

            In this idea, the catch is that the number of elements in the partition is equal when map[p1] is 1 and not when s = 0.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              I looked at your accepted submission and this one too and saw that in the accepted code you've used m[p1]==1 for checking if the difference has become 0 or not. Whereas in the Wrong Ans submission(the one I've linked), you used curr_sum==0 to check if the difference has become 0(this is exactly what I earlier was doing and hence getting WA). Can you tell the reason why the curr_sum == 0 not working even when we know that it is 0?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                So, as I said in the earlier comment that if we are doing modular addition and multiplication, we cannot determine whether the first and second partition has equal elements using curr_sum. This is because if the difference between the two partition is $$$10^9+7$$$, then also curr_sum = 0 and this does not mean that the two partitions have same elements. Now, to keep track of the number of elements of the second partition, note that we can always express the number of elements in the second partition as $$$\sum\limits_{i}p^i$$$. Note that if $$$p^{i}$$$ occurs p times then it is equivalent to 1 $$$p^{i+1}$$$. To keep track of number of elements in the second partition use this property along with the fact that the array is in descending order and $$$\sum\limits_{i=0}^np^i < p^{i+1}$$$. Let's say you have array:[5 3 3 3 3]. Now p1 = 5 and next elements are 3 3 3 3 and p = 2. Now you will keep $$$p^5$$$ in first partition. Next since m[p1] will be zero (No $$$p^{p1}$$$ in the second partition), then keep two $$$p^3$$$ in 2nd partition. This will form 1 $$$p^4$$$. Then again keep 2 $$$p^3$$$s in the second partition, this will also form 1 $$$p^4$$$. We have total 2 $$$p^4$$$ and this will form 1 $$$p^5$$$. Hence m[p1]==1 and number of elements are same in both the partition.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here's my submission for problem D. I am getting TLE on test 9 even though the idea seems to be the same as what many other people have implemented.

Here's another submission of mine which got accepted. It is different from the above submission in a few subtle ways such as using vector< bool > instead off bool [] or vector< int > instead of int [].

Any thoughts on why this difference exists? How do I make my implementation more efficient?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Div2, D
For test case
5 3
1 3
2 3
4 2
1 2 3 1 4
How answer is -1.
And why output : 1 4 2 3 5 is wrong.
As node 5 is not connected to any other node, so it can be colored with color 4.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    As you have to assign min topic which is not covered by neighbors of the current blog. Since blog 5 has no neighbors min topic that can be assigned is 1, but the topic required to be assigned to blog 5 is 4, hence the answer is -1. I think this is the case. I am currently in the process of upsolving this question myself.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

I have a (sort of) alternate solution to Div2 F/Div1 C: The first few observations are the same regarding binary searching on the beauty and noting that for beauty b numbers can be replaced with last b bits and you can only link equal numbers, but I didn't think to make a new graph and use Euler cycle. I first check the frequency of each b bit number, to make sure each is divisible by 2. Then, I just linked necklace parts with each other arbitrarily, which will make a bunch of disjoint cycles. We notice that you can merge cycles iff they share a b bit number. So, we continuously merge cycles until we can no longer do so. If there is one cycle, then we are done, otherwise it is not possible (why?).

It is actually a huge pain in the ass to do this in linear (times inverse ackermann) time per beauty check and takes a LOT of extra memory to keep track of tons of indices, but still nice to know that you can solve this problem while forgetting about Euler cycle. I also had to do some constant factor optimizations to get it under the TL, i.e. had to be careful about using map vs unordered_map, unordered_map vs vector when possible, etc. If you want to test your implementation skills this is probably good practice.

The keen reader will notice that this solution is actually just a gross unpacking of the proof that all even degrees implies existence of Euler cycle, i.e. just make a cycle and then stitch it together with another cycle and repeat. Perhaps I should have been tipped off by the "divisible by 2" part.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help why my code is failing for Div2 A https://codeforces.com/contest/1362/submission/82589559

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you are swapping them and that's where you went wrong. take them as it is and apply simple approach.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How does swapping make a difference? Could you please list a test case where it might fail ?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        ok.so, at first look it seemed that the problem is with swapping but this is the case where your code failed:

        1 576460752303423483

        expected -1 found 20

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks for the test case but I don't understand why log2(576460752303423483) is giving 59 even though the number 576460752303423483 is an odd one.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            log2(576460752303423483) gives 59 because it actually returns 58.99... which gets rounded off to 59. When using such functions like this one you need to be careful with floating point precision. I got a wrong answer verdict too when using log2(). It's better to simply have a loop in which you do n /= 2 and count++ as long as n % 2 == 0.

            Here's my submission with the loop -> 82602732.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain how to approach Div2 E / Div1 B ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Yeah, you can have a look at the simpler solution, 82595479.
    We traverse the numbers in decreasing order, if the current value of answer is not equal to 0, subtract this number from the answer, else set this number as the answer.
    It is definite that the i-th number cannot make the answer negative after we subtract it from the answer since pk can always be represented as sum of lower powers, so the number will always become 0 if it has to become negative. :)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      if the current value of answer is not equal to 0, subtract this number from the answer, else set this number as the answer.

      I am not able to understand intuition behind this part ?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

        Assume p = 3 and array is 5 4 4 3 3 3 3 2 2.
        Answer at each step:
        Step 1. 3^5
        Step 2. 3^5 — 3^4
        Step 3. 3^5 — 2 * 3^4
        Step 4. 3^5 — 2*3^4 — 3^3
        Step 5. 3^5 — 2*3^4 — 2*3^3
        Step 6. 3^5 — 2*3^4 — 3*3^3 = 3^5 — 3*3^4 = 3^5-3^5 = 0
        Step 7. 3^3
        Step 8. 3^3 — 3^2
        Step 9. 3^3 — 2*3^2 = 3^2 = 9.

        At each step, we try to reduce the current value of answer. There is no possibility of a minimum answer than this. It wouldn't have been the case if the number at ith position was not divisible by all the numbers ahead of it. In this particular case, all the numbers can either make the answer 0 or can reduce the value of answer. We also note the answer is always divisible by all the numbers ahead of it.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Still don't understand why this greedy solution gets us the optimal answer

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        At step 1, we are sure that the answer is pk1. Now at second step, the number can be either equal to first number, or be equal to pk1-x. Now, if we add it into the same group, the chances that we will reach zero will decrease. Moreover, we observe that if there is an optimal solution by adding it to same group, then there will be definitely an optimal solution by adding it to another group.
        Example: p = 3, and are = [5 5 4 4 4 4 4 3 3 3], then the optimal solutions can be [5 5], [4 4 4 4 4 3 3 3] or [5 4 4 4], [5 4 4 3 3 3]. Now if there were one less 4 in the array, the the answer would have jumped to 34 whereas it could have been 33.
        At each step the answer is either 0 or the answer is a multiple of pki. Therefore we must subtract it, otherwise we will be decreasing our chances of reaching the minimum value.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

For Prob Div2B if n is odd the answer will only be k=0, thus no solution possible for K>1; Since a1(xor)x=a2 where a1 and a2 be any 2 numbers not arr[0] && arr[1] then x=a2(xor)a1 and thus a2(xor)x=a2(xor)(a2(xor)a1)=a1; Similarly for other pairs also. hence they occur in pairs and if n is odd we will have one pair a1(xor)x=a1 then x=0;

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution for div2 D is failing on test 5. If someone could help to find the mistake or a test case at which it will fail, then it would be appreciated. Here is the link to my solution: https://codeforces.com/contest/1362/submission/82657443

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What a terrible statement of D1C. I did not know it was that terrible until I read the editorial. When I read it I couldn't understand why can we connect only vertices with the same last bits. Then I re-read the statement 100 times more and I discovered that it should divide the xor, not be included in it...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good contest,thanks!

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

In div2 D, how to calculate the time Complexity, I can't understand it.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    for every node, check every connection for the conditions.

    there are only M connections, thus you have to make o(n+m) for the checking validity stage.

    then, sort (nlogn) and greedy fill from bottom up. idk how u do it in o(n) but nlogn is sort.

    nlogn is a bigger factor than n+m so only nlogn is included in compleixty

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you, so the overal complexity of that 3 Nested for loop in editorial is only o(m)?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        o(n+m), because o(n) for each node and o(m) for each connection (because theres only a maximum of 'm' connections for the whole thing so some nodes u get long strings of checking and some nodes u get a little bit of checking)

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you help me with this solution https://codeforces.com/contest/1362/submission/82657443 for div2d. Its failing on test 5.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        im not too familiar w/ c++ so forgive me if i'm wrong but i'm not sure if

        for(auto a : mp[node]) { if(t[a]==ref) flag = true; if(t[a]==ref+1) flag1 = false; }

        is correct. if (t[a] == ref) flag = true means that if another blog has the reference the flag is true (this flag should automatcally falsify since that means this node can't be the target value anymore) and t[a] == ref+1 falsifying the node isn't correct either because it doesn't check for nodes below itself (you don't really care about nodes above taget, only below and equal to it).

        remember, two conditions:

        1) all connected blogs must have a set of numbers such that they are below target number

        2) it must not have a blog connected such that it is equal to target

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks for replying. But I think you did'nt understood my solution. ref is target-1. but, I understood my mistake. thanks anyway

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When I solved Div.2 D using BFS I got TLE, but when I used DFS with same logic it got accepted.

BFS submission

DFS submission

Can someone please explain to me why this happened?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Consider a graph which is nearly connected(as TC 8 on which you got tle). As at each node you are checking all it's adjacent nodes assume at each node you got 1000 nearby nodes.So O(1000*n) time complexity.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      since the maximum number of edges is 500000, won't the complexity for DFS and BFS both be O(V+E)?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I haven't seen your dfs code but in your bfs code for each node you check its neighbor's if they are visited then also you are checking them.Because of it your bfs code complexity can be roughly given as O(N*max_neighbours) as for each node you check all its neighbor's.Hope you got it what I want to say.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please someone tell me whats the problem in my code for C part div2 https://codeforces.com/contest/1362/submission/82531892

I am taking last significant bit and add ans corresponding to that bit and then subsequently remove last significant bit. Then repeat the process till n not reaches 0.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.com/contest/1361/submission/83105695 can someone help me with test case 6 of problem D Div 2

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For Div 1E, does anyone know how you're supposed to keep track of the lone ancestor that has an edge from your subtree when there is only one such edge? I managed to get this working by keeping track of all ancestors that have an edge from $$$v$$$'s subtree and then using some gross small-to-large merging thing, but it seems that there is a way to do it without any such log^2 factor; I've been trying to read people's code but I'm not totally sure what the idea is that people are using.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solution to E is short and brilliant, i was struggling in anything like this but i haven't find the solution, thank you by the editorial.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Don't you think for problem D(div 2) test case 40:-

4 4

1 2

1 3

2 4

3 4

1 2 2 3

ans should be 1 2 3 4

but judge shows ans to be -1......

why?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    - From Condition 2 : HERE
    -vertex 4 have immediate neighbors [2(color 2) and 3(color 2)] but there is no neighbor of 
     color 1
    -If we want to assign vertex 4 color 3 then there should be other vertex available of color 1 to 2
    
»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Div2 B can be solved in O(nlogn) time with a segment tree and hashing. Surprised nobody noticed this yet! Code: 126126788

Brief explanation: let S be the upper bound on elements, then consider the binary string s of length S, where s[i] == '1' means the set contains i. Build a segment tree on that string, where each node stores a polynomial hash of the corresponding substring of s. Then the root node of that segment tree stores the hash of the whole string.

To permute the string according to the xor thing in the problem with input k, we can rebuild the segment tree where some nodes treat their children as swapped when computing the hash (the less significant bits of k correspond to nodes closer to the root). Now here is the important part: if the segtree is currently permuted according to some k, then to switch to having it be permuted according to k+1, we don't need to touch any of the nodes corresponding to a bit on the prefix where k and k+1 match -- for example if we are transitioning from 00101 to 00110, then we can ignore the last three layers of nodes and only process the two layers closest to the root.

Now say we run through all possible k from 1 to S-1 -- each time we will check if the current root hash matches the root hash for the original, unpermuted string. If it does then we found a candidate answer. To analyze the complexity, let's think about how many times each node gets recalculated. Each leaf get recalculated 1 time, the nodes right above the leaves get recalculated 2 time, the next layer 4 times, then 8, ..., and the root gets recalculated S times. Each layer contributes S to the answer, and there are log(S) layers, so the total runtime is O(SlogS).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Good idea! We can also build another segment tree.

    Let's recursively build an array of hashes of all possible sets that we can get. So, $$$tree[v][x]$$$ stores the hash of $$$s \oplus x$$$, where $$$0 \le x < 2^h$$$, where $$$h$$$ is the height of the vertex $$$v$$$. Note that we can do it without recursion like in merge sort.

    Code: 126167404.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div1-A problem is so confusing!!