### Okrut's blog

By Okrut, history, 8 months ago,

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

Tutorial
Solution

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

Tutorial
Solution

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

Author: MicGor

Tutorial
Solution

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

Tutorial
Solution

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

Author: Okrut

Tutorial
Solution

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

Author: Okrut

Tutorial
Solution

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

Author: Okrut

Tutorial
Solution

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

Tutorial
Solution

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

Tutorial
Solution

• +219

 » 8 months ago, # |   +11 Greate contest,thanks!
•  » » 8 months ago, # ^ |   +17 worst explanation of div2 D.
 » 8 months ago, # | ← 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. )
•  » » 8 months ago, # ^ |   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
•  » » » 8 months ago, # ^ | ← 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.
 » 8 months ago, # |   0 Problem D video Editorial: Solution
 » 8 months ago, # |   +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
•  » » 8 months ago, # ^ |   +9 sum of n over all test cases does not exceed 1024.
 » 8 months ago, # | ← Rev. 2 →   +70
•  » » 8 months ago, # ^ |   +11 Actually they are D and E of Div 2
•  » » » 8 months ago, # ^ |   +4 Oh that's right thanks!
•  » » » » 8 months ago, # ^ |   +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.
•  » » » » » 8 months ago, # ^ | ← 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)
•  » » 8 months ago, # ^ | ← Rev. 2 →   -18 I edited my comment. Don't press <-- Rev.
•  » » 8 months ago, # ^ | ← Rev. 3 →   +8 ur soln for D fails for the following tc:-4 31 22 33 41 3 3 1
•  » » » 8 months ago, # ^ |   +7 Looks like I really got lucky this round :D
•  » » » » 8 months ago, # ^ |   0 xD..great editorial man!way to go!
•  » » » » 8 months ago, # ^ |   0 Sir,will you kindly help me with my solution for problem D? https://codeforces.com/blog/The_mysterio This is the link to my solution.I have clearly stated my algorithm here. Kindly help,already spent 12 hours debugging...
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 The pseudo-code he wrote missed the case where neighbour's colour is the same. It should be something like this:  for(Node node : sortedNodes){ HashSet smallerNeighbours = new HashSet(); for(int connectedBlogs : graph.get(node.blog)){ if(nodes[connectedBlogs].topic < node.topic){ smallerNeighbours.add(nodes[connectedBlogs].topic); } else if(nodes[connectedBlogs].topic == node.topic){ isPossible = false; break; } } if(!isPossible || smallerNeighbours.size() != (node.topic - 1)){ isPossible = false; break; } answer.add(node.blog); } 
•  » » 8 months ago, # ^ |   0 Thanks for the tutorial. +1
•  » » 8 months ago, # ^ |   0 great tutorial this time!!
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 what is that do_calc function is doing in your code for div2E/div1Bupd:- finally got that amazing solution thank you
 » 8 months ago, # |   +18 seemingly simpler solution for problem C ll res=0; while(n){ res+=n; n/=2; } cout<
•  » » 8 months ago, # ^ | ← Rev. 2 →   +23 This was my C 2*n-__builtin_popcountll(2*n)
•  » » » 8 months ago, # ^ |   0 how did this formula come ?
•  » » » » 8 months ago, # ^ |   0 oeis
•  » » 8 months ago, # ^ |   0 Can you tell me why this works?
•  » » » 8 months ago, # ^ |   +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).
•  » » 8 months ago, # ^ |   0 can someone explain this solution please, I'm having trouble understanding how this works.
•  » » » 8 months ago, # ^ |   +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 = n2nd-bit place sequence:Value added = n/23rd-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.
•  » » » » 8 months ago, # ^ | ← 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!
•  » » » » » 8 months ago, # ^ |   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).
•  » » » » » » 8 months ago, # ^ | ← Rev. 3 →   0 I failed to notice that it doesn't work for n = 11. Thank you for pointing that out.I am trying to understand why we are diving by 2^i. I understand that the first bit(counting from the right) changes its value each time as we go from 0 to n and the second bit changes its value after every second number and so on.Thank you!EDIT: Nevermind, I have rigorously gone through the editorial's solution and found out that why we are dividing it by 2^i, since if d is a multiple of 2^i then, d and d-1 differs. Therefore, we are trying to find how many multiples of 2^i exist in n.
•  » » » » 8 months ago, # ^ |   0 This is for number 2^n . what about the other numbers ? can u explain it for them?
•  » » » » 2 months ago, # ^ |   0 Thanks a lot
•  » » 8 months ago, # ^ |   -8 Can you explain how this works,
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +8 Number of swaps in LSB bit is n, for second last bit n/2 and so on...
•  » » » 8 months ago, # ^ |   +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.
•  » » » » 8 months ago, # ^ |   0 Uff thanks man, that was very useful
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Thanks man for explanation
•  » » » » 8 months ago, # ^ |   0 yr explanation is the most lucid one so far...THX
•  » » » » 8 months ago, # ^ |   0 Thank you so much for the explanation man. It's very intuitive.
•  » » » » 8 months ago, # ^ |   0 What an explanation Sir Ji!
•  » » » » 8 months ago, # ^ |   0 This is THE BEST explanation !!! Thanks mala07
•  » » » » 8 months ago, # ^ |   0 Man it was very very helpful. Thanks
•  » » » » 8 months ago, # ^ |   0 Finally got this! Thanks a ton man!
•  » » » » 8 months ago, # ^ |   +3 Bro, you are not failure, thanks for great explanation!
•  » » » » 7 months ago, # ^ |   0 ohhh man...!!! i wish i could give you thousands of votes for this...great observation...!!!
•  » » 8 months ago, # ^ |   0 did somebody say simplewhile(t-->0) { long n =inputLong();println(2*n-Long.bitCount(n)); }
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 I was trying the same but it failed in Test case four Can you Please help!!!My SubmissionIts a order(bit length of n) solution.My explanation is as follow 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 differencesSomeone Please help, I don't understand why it not passing Test Case 4!!
•  » » 8 months ago, # ^ |   0 If you could can you please explain the logic behind it ?
 » 8 months ago, # | ← 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
•  » » 8 months ago, # ^ |   +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).
•  » » » 8 months ago, # ^ |   0 please explain how did this formula come ?
•  » » » » 8 months ago, # ^ |   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
•  » » » » » 8 months ago, # ^ |   0 for 10000 why (2^(4+1))-1 ? pls, anshul565
•  » » » » » » 8 months ago, # ^ | ← 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.
•  » » » » » 5 weeks ago, # ^ |   0 Great explanation thanks!
•  » » » 8 months ago, # ^ |   0 I'm trying the same but it fail in test case 4Can you help me with the solutionThanks in Advance :)
 » 8 months ago, # |   +3 wow fast editorial
•  » » 8 months ago, # ^ |   +34 btt does'nt seems good !
 » 8 months ago, # |   +7 Is there anyone "Wrong answer on test 41" in div1.A like me ?
•  » » 8 months ago, # ^ |   -10 There are many. Just use the filters in status tab.
•  » » » 8 months ago, # ^ |   +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...
•  » » » » 8 months ago, # ^ |   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" ;)
•  » » » » 8 months ago, # ^ |   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.
•  » » » » 8 months ago, # ^ |   0 I made the same mistake and I feel very stupid now :(
•  » » 8 months ago, # ^ |   0 I got WA on test 41 too.
•  » » 8 months ago, # ^ |   0 Did you notice that m and n can be 5e5? I can't see your code at this point, so trying to guess.
•  » » 8 months ago, # ^ |   0 Well, for me it was Div2D, but same. I couldn't imagine a edge case here :/
•  » » 8 months ago, # ^ |   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)?
•  » » » 8 months ago, # ^ |   +3 Checking each neighbor means iterating through each edge twice. There are 2*m computations, that's why it won't give tle.
 » 8 months ago, # | ← 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... 
•  » » 8 months ago, # ^ | ← 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.
•  » » » 8 months ago, # ^ |   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
•  » » » » 8 months ago, # ^ |   0 yes, I found yours only just wrote it wrong by mistake.
•  » » » » » 5 weeks ago, # ^ |   0
•  » » » » 8 months ago, # ^ |   0 I did it using dp 82541393
•  » » » 8 months ago, # ^ |   0 I too got the same pattern. My solution: 82542445
•  » » » » 8 months ago, # ^ |   0 can you explain your solution?
•  » » » » » 8 months ago, # ^ | ← 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: 10101Observations:Number of 1's in pattern = c1 = ceil(21/2) = 11Number of 2's in pattern = c2 = floor(21/4) = 5Number of 3's in pattern = c3 = ceil(21/8) = 3Number of 4's in pattern = c4 = floor(21/16) = 1Number of 5's in pattern = c5 = ceil(21/32) = 1We 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.
•  » » » » » » 8 months ago, # ^ |   0 Okk
•  » » » 8 months ago, # ^ |   0 same happened with me, I was able to find the pattern but couldn't code beacuse this pattern takes a interesting mode after 11, for 12 it was 3 but I didn't understand why? also for 20 it was 4 and I gave up!
•  » » » » 8 months ago, # ^ |   0 Nope bro, every number is surrounded by a smaller number on both the sides. like 2 is always surrounded by 1 -> 1 2 1 and 3 is always surrounded by 2 and hence surrounded by 1 as well -> 1 2 1 3 1 2 1
•  » » » » » 8 months ago, # ^ |   0 Ahh, Now I get it, thanks ):
 » 8 months ago, # |   +98
•  » » 8 months ago, # ^ |   +8 Please don't leave out constructforces XDP.S. No offense to those who hate constructive algorithms. Just a joke :)
•  » » 8 months ago, # ^ |   0 recently bit storm started
 » 8 months ago, # | ← Rev. 2 →   +145
 » 8 months ago, # |   -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!
•  » » 8 months ago, # ^ |   +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.
•  » » 8 months ago, # ^ |   +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.
•  » » 8 months ago, # ^ |   0 Ya !! Infact it seemed that even top sort would pass !!
•  » » 7 months ago, # ^ |   0 true
 » 8 months ago, # |   +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.
•  » » 8 months ago, # ^ |   0 well congrats for becoming an expert
 » 8 months ago, # |   +86 This round tests participants' English level.
 » 8 months ago, # | ← Rev. 2 →   +2 Solution C is a sequence from OEIS. $a(n) = a(floor(n/2))+n$
•  » » 8 months ago, # ^ |   +7 I'll leave the link with the reference for those unfamiliar with OEIS https://oeis.org/A005187
•  » » 8 months ago, # ^ |   0 But mine is not passing test case 4Can you please help!!My SubmissionThanks in Advance :)
 » 8 months ago, # |   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)!
•  » » 8 months ago, # ^ |   +1 No, because sum over all $N$ is at most 1024! So you can't look at it like maximum of $N$ and $T$.
•  » » » 8 months ago, # ^ |   +10 ok,so does it mean if x1+x2+x3+...+xn<=k => x1*x1+x2*x2+....+xn*xn<=k*k
•  » » » » 8 months ago, # ^ |   +11 x1*x1+x2*x2+....+xn*xn <= (x1+x2+x3+...+xn)^2 <= k*k
•  » » » 8 months ago, # ^ |   -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.
•  » » 8 months ago, # ^ |   0 "It is guaranteed that the sum of n over all test cases will not exceed 1024"
 » 8 months ago, # |   +6 Pretests for Div2 C should have been stronger.
 » 8 months ago, # |   0 Can someone please explain why this code for Div2 C fails: #include #include 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<
•  » » 8 months ago, # ^ |   -7 Try using your binary power function, inbuilt pow is quite unreliable.
•  » » 8 months ago, # ^ |   +3 Your code works, you just have to note that 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 #include 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; } } 
•  » » » 8 months ago, # ^ |   0 Let me just drop that link here: https://codeforces.com/blog/entry/21844
•  » » » » 8 months ago, # ^ |   0 you are so kind, thanks!
•  » » 8 months ago, # ^ | ← 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/82540420int 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:(
•  » » » 8 months ago, # ^ | ← 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; }
 » 8 months ago, # |   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 ??
•  » » 8 months ago, # ^ |   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."
 » 8 months ago, # |   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?
•  » » 8 months ago, # ^ |   0 if not, then k would not have satisfied the condition.
•  » » 8 months ago, # ^ |   +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!
•  » » » 8 months ago, # ^ |   +5 Thank you, now I got it.
 » 8 months ago, # |   +4 Seems like the pretests were pretty weak in Div2C and Div1A, a lot of solutions failed in System Testing.
•  » » 8 months ago, # ^ |   0 hacks!
 » 8 months ago, # |   -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!
•  » » 8 months ago, # ^ |   +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.
•  » » » 8 months ago, # ^ |   0 Thanks,I couldn't solve the question only because of this confusion!
 » 8 months ago, # |   0 So fast tutorials, great!
 » 8 months ago, # | ← Rev. 3 →   0 For DIV-2 Problem B, with JAVA 8 it's giving TLE and with JAVA 11 same code got accepted?
 » 8 months ago, # |   0 Can anyone explain why this code is wrong for div 2A. It failed on pretest 2, https://codeforces.com/contest/1362/submission/82554581
 » 8 months ago, # |   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
•  » » 8 months ago, # ^ |   0 I have the same solution in 530ms. Try to use some data structure like set. My code: https://codeforces.com/contest/1362/submission/82564925
 » 8 months ago, # |   0 C was simple. I saw the pattern but couldn't implement it on time.
•  » » 8 months ago, # ^ |   0 i have found pattern like 1,2,1,3,1,2,1,3... but my pattern doesnt work can you help why?
•  » » » 8 months ago, # ^ |   0 your pattern is wrong..its 1,2,1,3,1,2,1,4...
•  » » » 8 months ago, # ^ | ← 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)
•  » » » » 8 months ago, # ^ |   0 I also got this pattern but could not figure out how to use this for to compute the value for n.
•  » » » » » 8 months ago, # ^ |   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
•  » » » » » » 8 months ago, # ^ |   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<
•  » » » » » 8 months ago, # ^ |   0 Observe, that all numbers of form (2*k) add 1 to the answer provided (2*k)+1 <= n. Similarly, I observed numbers of form--> (4*k)+1 add 2 (8*k)+3 add 3 (16*k)+7 add 4 (32*k)+15 add 5... and so on! So my solution is also (t*log(n))! -can refer my solution in case you want to know how I implemented this.
• »
»
»
»
»
8 months ago, # ^ |
-37

@kuchnahiaata

# include

typedef long long ll ;

# define ME(x , y) memset(x , y , sizeof(x))

//ll lcm(ll a , ll b){return a*b/gcd(a,b);} ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;} //int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;} //const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}

# define rson mid+1,r,root<<1|1

using namespace std; const int maxn = 1e5+9;

void solve(){ int n ; cin >> n ; int ans = 0 ; while(n){ ans += n ; n >>= 1 ; } cout << ans << endl; }

signed main() {

//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
int _ ;cin>>_;while(_--)
solve();

} Could u plz tell how this soln is working? Plz

•  » » 8 months ago, # ^ |   +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<
•  » » » 8 months ago, # ^ |   +3 Yeah, I have the same solution. I think it's easier to understand.
 » 8 months ago, # | ← 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
 » 8 months ago, # |   +8 Does there exist an O(n) solution for Div2 B?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +1 I belive so! IdeaFirstly, you need to see that all of the numbers come in pairs, iff $k$ exists.Lets observe some $a$ — it will become $a \oplus k$. Since we said $k$ is answer, $a \oplus k$ is also a number that will become $a \oplus k \oplus k = a$.If there are odd number of pairs, final $\oplus$ of all of the $n$ numbers will be $k$. If there are even number of pairs, final $\oplus$ will be 0.So, if you get $\oplus$ that is not 0, check it, it is the only possible.As you see, you can do all of this in $O(N)$, but i can't find a way to check below $O(NlogN)$, so overall time complexity is $O(NlogN)$.Edit: frequency array will fix the $O(NlogN)$ because numbers are small, so it's only $O(N)$ ProblemIf you get 0 as xor, I can't find a way to be sure that i will find answer nor that it will be minimal...My tries: With sum , With xorIf anyone knows how to solve "Problem", i would really appreciated it! :)
•  » » » 8 months ago, # ^ | ← 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
•  » » » » 8 months ago, # ^ |   0 your solution is still O(n^2) right?
•  » » » » » 8 months ago, # ^ |   +5 Yeah, but only for 1 case
•  » » » » 8 months ago, # ^ |   0 Cool bro, if you find how to solve that problem when it is $N^2$, I would love to hear it!
•  » » » » » 7 months ago, # ^ | ← 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)
 » 8 months ago, # |   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
•  » » 8 months ago, # ^ |   +2 It is probably because of tight TL. XOR between two long long is slower than between ints, they have more bits, and you are not using them, so you can save time by just using int.I know XOR should be superfast, but it's like division and modulo, they should work in O(1), but modulo is like four times slower... Thats that, I'm guessing your passed solution had tight TL? So thats explanation, it's just slower!
•  » » » 8 months ago, # ^ |   0 passed solution is 670ms.
•  » » » » 8 months ago, # ^ |   0 I used #define int long long but got Accepted :p
•  » » » » » 8 months ago, # ^ |   0 Can u please check below codes sir[WrongAnswerOnTest1] https://codeforces.com/contest/1362/submission/82518343 https://codeforces.com/contest/1362/submission/82567052
•  » » » » » » 8 months ago, # ^ |   0 What should I check? I think MatesV13 is right.
•  » » » 8 months ago, # ^ |   +5 that's actually a really interesting case where long and int makes a big difference, gotta keep that in mind
•  » » » » 8 months ago, # ^ |   0 My question is that my JAVA solution only takes up like 300ms...I just used a hashset and compared sizes and numbers, then printed out if it was valid or not. I don't see how you could ever get a 670 ms or even a TLE on this problem.
 » 8 months ago, # | ← 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 nthe second bit changes its value after every second numberthe third bit changes its value after every fourth number ...
 » 8 months ago, # |   0 I was stuck on A, was checking if b/a (assuming b>a) is a power of 2. I used '(x & (x-1)) == 0' to check if it is so, turns out this doesn't work for large numbers like 2^47,2^48 even though I use uint64_t to initialize num = b/a. What is the way to do this?
 » 8 months ago, # |   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
•  » » 8 months ago, # ^ |   0 It is guaranteed that the sum of n over all test cases will not exceed 1024.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Spoiler
•  » » » 8 months ago, # ^ |   0 I see, I got confused because generally its 1e5, and I take it for granted that we need to perform O(n), function but here we needed to do n^2
 » 8 months ago, # | ← 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$.
 » 8 months ago, # | ← Rev. 2 →   0 [deleted]
 » 8 months ago, # |   0 The questions were really creative. Thanks for the contest!
 » 8 months ago, # |   +22 Does someone mind explaining why Div.1 B works with the given solution? I still don't understand how it works!
 » 8 months ago, # |   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
•  » » 8 months ago, # ^ | ← 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
 » 8 months ago, # |   +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.
 » 8 months ago, # |   +45 The statement of D was very bad. It took me 15mins to understand.
 » 8 months ago, # |   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?
•  » » 8 months ago, # ^ |   0 The topic of a blog is always the first unused topic of all adj, so it is always restricted.
•  » » » 8 months ago, # ^ |   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
•  » » » » 8 months ago, # ^ |   +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."
•  » » » » » 8 months ago, # ^ |   +3 I guess you are right. Thanks.
 » 8 months ago, # |   +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/82565932And it gets AC despite failing on: 4 3 1 2 2 3 3 4 1 3 3 1 
•  » » 8 months ago, # ^ |   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 
•  » » 8 months ago, # ^ |   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.
 » 8 months ago, # | ← 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
•  » » 8 months ago, # ^ |   +8 Can you please explain why the greedy solution in the editorial is optimal.
 » 8 months ago, # |   +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): 82567455This 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.
•  » » 8 months ago, # ^ |   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.
•  » » » 8 months ago, # ^ |   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).
•  » » » » 8 months ago, # ^ | ← 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.
 » 8 months ago, # |   0 For the C problem, I found a pattern for the sum value corresponding to the number of bits. If the number is a power of 2, the value is = number of bits + summation(0-number of bits-1) of (2^k-1) = number of bits + 2^(number of bits) — (number of bits — 1) -2. But this formula is giving me a WA on test cases, that too only in the last 2-3 digits. Sample test cases pass. Can anyone help please? public static void main(String[] args) throws IOException { FastScanner fs = new FastScanner(); Print printer = new Print(); int t = fs.nextInt(); while (t > 0) { long n = fs.nextLong(); long nbits = (long) (Math.log(n) / Math.log(2) + 1); long ans = 0L; while (nbits >= 0) { long num = 1L << (nbits - 1); if ((n & num) != 0L) { ans += nbits + Math.pow(2, nbits) - (nbits - 1L) - 2L; } nbits--; } printer.println(ans); t--; } printer.close(); } 
•  » » 8 months ago, # ^ |   0 Never mind, I found the solution. Apparently, Math.pow(n,e) loses precision after reaching the 15 digit limit, which is why the numbers were appearing slightly different. Using BigInteger solved the problem.
 » 8 months ago, # |   0 Can anyone tell me why my solution for B is showing tle? https://codeforces.com/contest/1362/submission/82505539
•  » » 8 months ago, # ^ |   0 Instead of endl try using '\n'.
•  » » » 8 months ago, # ^ |   0 Thanks it worked.
•  » » 8 months ago, # ^ |   0 you have written an O(n^3) solution try to scale it down
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 "#define int long long int"Comment this line and you are good to go for this question!! long long and long long int take a larger time than int to run.
•  » » » 8 months ago, # ^ |   0 Thanks it worked
 » 8 months ago, # |   0 Div 2C 82559719
 » 8 months ago, # |   0 Is there any constraint on taking log2 in C++? For div2C , the bit shifting done in editorial is done by me by taking the log2 of the number then subtracting the power of that log from original number and doing it again. This way I supposedly did the same thing but my code failed on system testing but when I switched the log thing with bit shifting, my same logic worked!! Does anyone have idea about this? original submission: https://codeforces.com/contest/1362/submission/82561526 Changed: https://codeforces.com/contest/1362/submission/82569836
 » 8 months ago, # |   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
 » 8 months ago, # | ← Rev. 2 →   0 hi for problem A I cant't understand where my code fails. Even after looking at the solutions i can not understand for which test it is failing. some test(no 256 on pretest 2) where answer should be -1 but my code shows 19. Cant view the test. its embarrassing to ask others to debug your code but i am not getting it. https://codeforces.com/contest/1362/submission/82558153Edit: Found the problem. log does not return the no of 2's or 8's that divides completely
•  » » 8 months ago, # ^ |   0 I'm facing the same issue in c++. Could you elaborate on what you found?
•  » » » 8 months ago, # ^ |   0 just take a number for example 72. int(log(72,8)) gives 2 but what we needed is 1 as 8 only divides 72 completely one time. 72=8*9 as 9 is larger than 8 it is giving 2 :(
 » 8 months ago, # |   -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<
•  » » 8 months ago, # ^ |   0 Thank u. Can u explain how it is working? I mean, math behind it ?
•  » » » 8 months ago, # ^ | ← 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 
•  » » » » 7 months ago, # ^ |   0 nice explanation
 » 8 months ago, # | ← Rev. 2 →   -10 " It is guaranteed that the sum of n over all test cases will not exceed 1024. " Please mention this in bold from next time. . . -_-
 » 8 months ago, # | ← Rev. 2 →   0 language was very tricky in this round...overall good contest...thanks
 » 8 months ago, # | ← 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.
 » 8 months ago, # |   +19 Div2D/Div1A — Johnny and Contribution The hardest readforces statement ever seen.
 » 8 months ago, # |   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/82512703Thank you
•  » » 8 months ago, # ^ |   0 I did the same. Some edge case is failing with this approach. If you find it notify here.
•  » » 8 months ago, # ^ |   0 Since in this testcase the answer is 20, the numbers are fairly huge, like 1 and 1<<60Not sure if this is handled correct in python.
•  » » 8 months ago, # ^ |   0 I found the problem. we needed to use a while loop. log does not return the correct value. lets say int(math.log(72,8)) even the answer we want is 1 it will return 2
•  » » » 8 months ago, # ^ |   0 bro the answer should be 2 only as 8**2=64 and 72>64. But, i agree that there was some issue in using log so what i did was after calculating the answer i verified that whether my answer is correct or not. look in the solution link attached.link to my soolution: https://codeforces.com/contest/1362/submission/82575238P.S: it's a shout out to the authors that please ensure that such intricates errors are not counted for, I did knew how to solve the question in the first 5 minutes itself but spent the next 1 hour or so in debugging only to find out there is some glitch in python. Please, ensure that such thing never happen.Thank you , although loved the questions!!! i hope to become a DIV 1:)))
•  » » 8 months ago, # ^ |   0 I have done the same in C++ getting WA in the same test case don't know where the error is
•  » » » 8 months ago, # ^ |   0 Same with me
 » 8 months ago, # |   +27 For Div2E/Div1B-Johnny and Grandmaster, why does the strategy given in the editorial works?
•  » » 8 months ago, # ^ | ← 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.
•  » » » 8 months ago, # ^ |   0 Do you know how to check if s > n * p^k_i ? I can't understand that part of the editorial. Thanks
•  » » » 8 months ago, # ^ |   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?
•  » » » » 8 months ago, # ^ |   +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.
•  » » » » » 8 months ago, # ^ |   0 I could finally understand!!
•  » » » » » » 8 months ago, # ^ |   0 Hey, I implemented this problem. If you are still stuck see at https://codeforces.com/blog/entry/78355?#comment-637076
•  » » » » 8 months ago, # ^ |   0 comparison after modding would be dumb. That's the whole point of dividing by p^x so that we can compare a very big number without modding.
•  » » » » 7 months ago, # ^ |   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$.
•  » » » 8 months ago, # ^ |   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.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Thanks, it was really helpful :)
 » 8 months ago, # |   0 Not solving C cost me Another Rating Drop
•  » » 8 months ago, # ^ |   +3 kripya yaha par na royein
»
8 months ago, # |
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;
}
}

•  » » 8 months ago, # ^ |   0 I had this exact same issue and hence I could not pass the same test case.Apparently,I don't know why but stl log2(2^59-1) gives 59.However,it should clearly have returned 58.So,wrote a function myself to compute log2;
•  » » 8 months ago, # ^ |   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<
 » 8 months ago, # |   0 Can someone pinpoint what the error is? Problem A (Div. 2) Submission Expected -1, But printed 20.
•  » » 8 months ago, # ^ |   +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.
•  » » » 8 months ago, # ^ | ← 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!
•  » » » » 8 months ago, # ^ |   0 It seems that it is complecated in python to say how much bit an int has. stackoverflowSince the testcase is the one where $a==b«{60}$ I think that is the problem.
•  » » » » » 8 months ago, # ^ |   0 Hey, thanks for the reply. Appreciate it!
•  » » » 8 months ago, # ^ |   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.
•  » » » » 8 months ago, # ^ |   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.
•  » » » » » 8 months ago, # ^ | ← 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!
 » 8 months ago, # |   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
 » 8 months ago, # |   0 Hello all, please help me out in DIV2 C problem. My code uses the same idea as in the editorial but gives wrong answer for Test case 8. It passes all the protests but sadly failed the main tests. ll a;cin>>a; ll ans=0; while(a>=1){ ll k = log2(a); ans += (ll)pow(2,k+1)-1; a = a-(ll)pow(2,k); } if(a==1)ans++; cout<
•  » » 8 months ago, # ^ |   0 Ok, I got it accepted by just changing log2() to log2l(). Bad day.
 » 8 months ago, # |   0 i was not able to solve the first question itself :( :(
 » 8 months ago, # |   0 Can you tell me please the test on which this package falls? It’s just very interesting that I tested a lot and can’t understand what the problem is :c82564849
 » 8 months ago, # |   0 Auto comment: topic has been updated by Okrut (previous revision, new revision, compare).
 » 8 months ago, # | ← Rev. 4 →   +1 Another solution for CLet 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
 » 8 months ago, # |   0 For Div2 Problem E, can someone please explain me why a simple approach like this does not work? #include #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>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<
•  » » 8 months ago, # ^ |   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.
•  » » » 8 months ago, # ^ |   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.
•  » » » 8 months ago, # ^ |   0 Can you explain with an example?
•  » » » » 8 months ago, # ^ |   +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.
 » 8 months ago, # |   -15 The writers dont know how to write questions. The Div1 A was kinda encrypted!
 » 8 months ago, # |   +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?
 » 8 months ago, # | ← Rev. 2 →   0 Isn't the answer for Div-2 B question be 1025 for test case 1 -- t 2 -- n 1024 1. -- n[0], n[1] The editorial solution is showing -1 instead.
 » 8 months ago, # |   +13 Div1 C was an enjoyable problem, even though I couldn't get it done within the contest. Thanks for making this particular problem! :)
 » 8 months ago, # |   +6 I don't really understand the editorial of Div. 2 QE, can anyone explain? Thanks!
•  » » 8 months ago, # ^ |   +3 Me neither, I have no idea what the tutotial is saying. Can someone help explain?
•  » » 8 months ago, # ^ |   +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
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 How to prove that there exists such j ? UPD — Convinced myself by thinking in terms of base p.
•  » » » » 8 months ago, # ^ |   0 Can you write how you are convinced in more detail here
•  » » » » » 8 months ago, # ^ | ← 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.
•  » » » 8 months ago, # ^ |   +1 I tried to simplify the implementation and add comment- 82689935
»
8 months ago, # |
-39

# Bits Solution for the Problem 1362A

import java.util.Scanner;

public class Problem1362a {

private static Scanner sc;

public static void main(String[] args) {
// TODO Auto-generated method stub

sc = new Scanner(System.in);

int t = sc.nextInt();

while(t-- > 0)
{
long a = sc.nextLong();
long b = sc.nextLong();

System.out.println(solve(a, b));
}
}

private static long solve(long a, long b)
{
if(a == b)
return 0;

else if(a > b)
return (r(a, b));

else if(a < b)
return (l(a, b));

else
return -1;
}

public static int getFirstSetBitPos(long n)
{
return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
}

private static long l(long a, long b)
{
long x = getFirstSetBitPos(a);
long y = getFirstSetBitPos(b);
long n = Math.abs(y - x);

if((a << n) == b)
{
if(n % 3 == 0)
return n/3;
else
return (n / 3 + 1);
}

else
return -1;
}

private static long r(long a, long b)
{
int count = 0;
long n = getFirstSetBitPos(a);

if(n == 1)
return -1;

else if(n > 1)
{
while(a != b && n > 1)
{
a >>= 1;
count ++;
n--;
}

if(a != b)
return -1;
else if(count % 3 == 0)
return count / 3;
else
return (count / 3 + 1);
}

else
return -1;
}


}

 » 8 months ago, # |   +5 Can anyone please tell me the proof for div2 E
•  » » 8 months ago, # ^ |   +5
•  » » » 8 months ago, # ^ |   +5 I mean the proof for it's correctness
•  » » » » 8 months ago, # ^ |   0 Sorry I'm not able to frame words to explain its correctness.
 » 8 months ago, # |   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!
 » 8 months ago, # |   0 Can anyone help why my code is failing for Div2 A https://codeforces.com/contest/1362/submission/82589559
 » 8 months ago, # |   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
 » 8 months ago, # |   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.
•  » » 8 months ago, # ^ |   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.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Thanks, I have found out which test my code fail. 1 576460752303423483or 1 2^59-5The log2 function cannot spot the difference. Maybe I will change it to some bitwise operation.
•  » » » » 8 months ago, # ^ |   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.
»
8 months ago, # |
-14

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

# 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;
}
}

}

•  » » 8 months ago, # ^ |   0 I think looping it till 1024 will make it work
 » 8 months ago, # | ← Rev. 2 →   0 Can someone please prove the observation 2 in the editorial of Div 1A/2D?
•  » » 8 months ago, # ^ |   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
 » 8 months ago, # |   0 what is the use of LL in 1LL in 3rd ques?
•  » » 8 months ago, # ^ |   0 To convert 1 to a long long number type Now if we multiply it with something then the result will be stored in a long long data type ,that is, 64 bits If we have simply did 1 then it would go into a int data type.Correct me if wrong:)
 » 8 months ago, # |   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^18Can somebody please please help me out. Thanks in advance!!My Solution
•  » » 8 months ago, # ^ |   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 differencesSomeone Please help, I don't understand why it not passing Test Case 4!!
•  » » » 8 months ago, # ^ |   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<
•  » » » » 8 months ago, # ^ |   +3 Thanks Man,You were a day saver for me ;)Its working great now!!
 » 8 months ago, # |   0 In Div2.C we can solve it in O(floor(log2(n))).i.e., ans = 2*n — set_bits_of(n);
 » 8 months ago, # |   +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.
•  » » 8 months ago, # ^ |   +3 Found the mistake, wrote 1<<12 instead of 1e12.
 » 8 months ago, # | ← Rev. 2 →   0 could someone explain why this solution fails at A? https://codeforces.com/contest/1362/submission/82596448 #include #include #include 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; } 
•  » » 8 months ago, # ^ |   0 try considering that case when u can divide by 4 also ! n%8 will not suffice for the greedy solution
 » 8 months ago, # |   0 Div1CCan anyone help me with this submission? 82597192I don't know why it TLE.
 » 8 months ago, # | ← 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.
•  » » 8 months ago, # ^ |   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.
 » 8 months ago, # | ← Rev. 2 →   -22