### Roms's blog

By Roms, history, 4 years ago, translation,

1030A - In Search of an Easy Problem

Tutorial
Solution

1030B - Vasya and Cornfield

Tutorial
Solution

1030C - Vasya and Golden Ticket

Tutorial
Solution

1030D - Vasya and Triangle

Tutorial
Solution

1030E - Vasya and Good Sequences

Tutorial
Solution

1030F - Putting Boxes Together

Tutorial
Fenwick Solution
Segment Tree Solution

1030G - Linear Congruential Generator

Tutorial
Dynamic Connectivity Solution
Greedy Solution

1053E - Euler tour

Tutorial
Solution

• +93

 » 4 years ago, # |   +95 Editorial launched even before System testing. I'm loving this !
•  » » 4 years ago, # ^ | ← Rev. 2 →   +59 Next time, editorial before contest ends!
•  » » » 4 years ago, # ^ |   0 It happened already check https://codeforces.com/blog/entry/60209
•  » » » 4 years ago, # ^ |   +16 Why not before contest starts?
 » 4 years ago, # |   +4 :( For most of the time I thought that you can only do one swap per integer in Div1B, guess I need to read more carefully next time
•  » » 4 years ago, # ^ |   0 I thought there were zeros in the array :(
 » 4 years ago, # | ← Rev. 3 →   +1 The functions that defines the limits of the x — y values are changed on the B's picture.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Yes they are. Overlooked it when drew the picture.
 » 4 years ago, # |   0 #include using namespace std; int main () { map mymap; mymap['a']=10; mymap['b']=20; for(auto it=mymap.begin();it!=mymap.end();it++) if(it->first=='a') mymap.erase(it); for(auto p:mymap) cout<
•  » » 4 years ago, # ^ |   +2 Iterating and Erasing simultaneously causes undefined behaviour.
•  » » » 4 years ago, # ^ |   0 Why is it running on almost all other compilers then?Also I came to know a few days back that long and long long are not the same in codeforces but same on almost all other compilers.Why is codeforces compiler different?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +14 long is 4-byte data type while long long is 8-byte. In which compiler they have the same range?
•  » » » » » 4 years ago, # ^ |   +5 See this.All other ide's at https://wandbox.org https://ide.geeksforgeeks.org https://www.codechef.com/ide and my macbook gave the ouput as 9223372036854775807 for both.
•  » » » » » » 4 years ago, # ^ |   0 Strange.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   +19 It's not.In 64-bit systems long will be the 8-byte data type.It's C++ standard. You can read more here: cppreference: Fundamental types.And int has to be less than long but it's not similar on different compilers. Also read cppreference.Check it yourselves. #include using namespace std; int main() { int a; long b; long long c; cout << sizeof(a) << " "; cout << sizeof(b) << " "; cout << sizeof(c) << "\n"; } Codeforces output:  4 4 8 My pc output (64-bit):  4 8 8
•  » » » 4 years ago, # ^ |   0 No. In the C++11 standart method "erase(iterator)" returns iterator on the next element in container. So "it = mymap.erase(it)" is correct code.
 » 4 years ago, # |   0 Can someone explain solution for D? How do you get to sides a and b? Why are we dividing k by 2 if it is even, why are we multiplying later, etc.
•  » » 4 years ago, # ^ |   0 area of the triangle will be (a*b)/2 = (n*m)/k writing it as a*b = (2*n*m)/k we are calculating a in terms of n and b in terms of m. so we could've done something similar to linkBut it will be just writing extra code.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 If a>n can be true how you sure that in 2nd if condition hereif(a>n){ k=kf; x=gcd(n,k); k/=x; a=n/x; x=gcd(m,k); k/=x; b=2*m/x; }b>m will be always false. Can you please explain??sorry for bad english.
•  » » » » 4 years ago, # ^ |   0 since a*b = (2 * n * m) / k; if( a > n ) => b < (2*m/k) since, k>=2 => k/2 >= 1 => b < m / (k/2); => b < m
•  » » 3 years ago, # ^ |   +3 Let's consider only the case when one point is at $(0,0)$. For other cases, you can always move to this case (by shifting the points).We'll build a rectangle inside the rectangle $n \times m$, with area equal to $2*m*n/k$, and we'll split the rectangle to get the triangle. When $k$ is even ($k=2t$), we need to build a rectanble with area $m*n/t$. This number must be an integer, so $m*n$ must be divisible by t. This leads to the solution in the editorial. $g = gcd(t,n)$; $n = a * g$; $m = b * g'$ with $g' = t/g$ and $a,b$ is the sides of the rectangle When $k$ is odd, $m*n$ must be divisible by $k$. Similarly, we have: $g = gcd(k,n)$; $n = a * g$; $m = b * g'$ with $g' = k/g$. Note that at this time, $a$ and $b$ is the sides of the rectangle with area $n*m/k$. We need to double one side to get the desired rectangle. If $a < n \rightarrow g \geq 3$ (because $g$ is neither 1 nor even) $\rightarrow a \leq n/3 \rightarrow 2a < n$If $a = n \rightarrow g = 1 \rightarrow g' = k \geq 3$ (note that $k$ is odd). Similarly, we get $2b < m$So we can always double $a$ or $b$.
•  » » » 23 months ago, # ^ |   0 Thanks. Your explanation is amazing!!
 » 4 years ago, # |   +27 Thanks for your effort in writing this editorial.I wasn't able to solve problem Div.2 E.When I read the editorial I find you are writing "It can be proven" for the key idea of the problem.Please mention the proof or mention the intuition behind the two conditions.
•  » » 4 years ago, # ^ |   +15 Make 0 is equivalent to pairing ones in such way that there is no pair with ones from the same number. If max>sum/2 it's obviously impossible. Otherwise, just divide all ones in two groups of the same size in such way that there is no more than one number with ones in both groups. And there is always a way to pair ones from different groups.
•  » » » 4 years ago, # ^ |   0 I was confused about this . Thanks a lot.
•  » » » 2 years ago, # ^ |   0 Thanks adedalic. I would just like to point out that we can prove that such a division is always possible since Sum is even The number which has ones in both groups is actually the largest $b_i$. And then we can just match pairs from different groups.
 » 4 years ago, # | ← Rev. 2 →   +3 Can someone help me understand why I was failing Div 2E, pretest 8? Would be really gratefulhttps://codeforces.com/contest/1058/submission/43335816P.S. I used the same approach that the editorialist used
•  » » 4 years ago, # ^ |   0 I figured it out — it should have been tot[i-1] instead of tot[i], and j-1 instead of j. Passes now
 » 4 years ago, # |   -8 My code is giving correct answer on local compiler but giving false answer on codeforces compiler. My whole contest went bad due to this error. Atleast my rating should be reverted back. 43309972I checked test case 10 on codeblocks compiler as well as codechef IDE. Both of them are giving output as "Yes". My code is completely correct but still got WA.
•  » » 4 years ago, # ^ |   0 You must check "KpartitionsPossible" until 9 * n
•  » » » 4 years ago, # ^ |   -8 The problem is not that, the problem is that the code is giving correct output on codeblocks and codechef ide but not here.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +2 you didn't check 'pos' != -1 in line 28UPD: i changed line 28 else if (prefix_sum[i] - prefix_sum[pos] > total_sum / K) -> else if (prefix_sum[i] - (pos == -1 ? 0 : prefix_sum[pos]) > total_sum / K) and it was accepted 43343643
•  » » » 4 years ago, # ^ |   +4 Thanks for your effort. But why does this give the correct answer on codeblocks and codechef IdE and other compilers?
•  » » » » 4 years ago, # ^ |   +11 because ide can eat some bugs and re)
•  » » » » » 4 years ago, # ^ |   -6 So how do I even make sure that my code is correct? This way i'll never know for sure if my code is correct or not before submitting. I still feel this has been a little unfair to me.
•  » » » 4 years ago, # ^ |   0 When you try access an index out of bounds, many times, compilers on codechef or other online ones, tend to return zero or garbage value. Basically, it tries to access element at pos*(data_type_size) from the base of the array. So, if pos is -1, it access the element before 0th element of the array.
•  » » » » 4 years ago, # ^ |   -16 Thanks a lot for your help. I guess i can't even trust compilers when it comes to codeforces. :(
•  » » » » » 4 years ago, # ^ |   +18 The problem is not in the compiler. Suppose you have the code: int arr[2]; cout << arr[0] << ' ' << arr[1] << endl; What this code is supposed to print? There is no certain behaviour because you haven't assigned anything to 'arr'. It will just print what was laying there in the memory and it may differ from launch to launch. The same thing happened in your case.
•  » » » » » » 4 years ago, # ^ |   -8 Thanks a lot. Made this completely clear to me.
•  » » 4 years ago, # ^ |   -14 Who cares about rating? There's a contest like every 3-4 days.
•  » » » 4 years ago, # ^ |   -9 But when your contest is going good and you would have achieved blue in this very contest and you did not because of such errors,it does feel sad. :(
 » 4 years ago, # |   +17 The tutorial for Div 1E claims that if you have two equal values then there is a subtree between them which can be solved independently of the rest of the problem. But that's not necessarily true e.g. given the input 1 2 0 3 1 the only right answer is 1 2 1 3 1, and the interval 2 1 3 does not describe an Euler tour of a subtree of 1.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +26 I wrote this tutorial about month ago, now I see a lot of small mistakes in it. This is O(n) solution: Solution#include using namespace std; #define st first #define nd second #define PII pair const int N = 1e6 + 7; int n; int in[N]; int ans[N]; bool used[N]; vector unused; int cnt; vector cur; vector getEqual; int reval[N]; int place[N]; vector > order; bool check(){ if(in[1] != 0 && in[n + n - 1] != 0 && in[1] != in[n + n - 1]) return false; for(int i = 1; i + 1 < n + n; ++i) if(in[i] == in[i + 1] && in[i] != 0) return false; int t = 0; for(int i = 1; i < n + n; ++i){ if(in[i] == 0) continue; if(reval[in[i]] == 0){ reval[in[i]] = ++t; place[in[i]] = i; } } cur.push_back({0, 0}); for(int i = 1; i < n + n; ++i){ if(in[i] == 0) continue; if((place[in[i]] & 1) != (i & 1)) return false; while(reval[in[i]] <= cur.back().st) cur.pop_back(); if(place[in[i]] < cur.back().nd) return false; cur.push_back({reval[in[i]], i}); } cur.clear(); return true; } inline int get(){ if(unused.size() == 0){ puts("no"); exit(0); } int ret = unused.back(); unused.pop_back(); return ret; } void go(){ vector help; reverse(cur.begin(), cur.end()); while(help.size() + cur.size() >= 3){ if(help.size() < 3){ help.push_back(cur.back()); cur.pop_back(); continue; } PII v1 = help[help.size() - 1]; PII v2 = help[help.size() - 2]; PII v3 = help[help.size() - 3]; if(v1.st == 0 && v2.st != 0 && v3.st != 0){ ans[v1.nd] = v3.st; help.pop_back(); help.pop_back(); } if(cur.size() == 0) break; help.push_back(cur.back()); cur.pop_back(); } if(cur.size() == 0) cur = help; } void solve(int root){ int need = (cur.size() + 1) / 2 - cnt; if(need < 0){ puts("no"); exit(0); } for(auto &v: cur) if(v.st == 0 && need > 0){ --need; v.st = get(); ans[v.nd] = v.st; } reverse(cur.begin(), cur.end()); go(); if(root == -1 && cur.back().st == 0){ root = cur[0].st; ans[cur.back().nd] = root; cur.pop_back(); reverse(cur.begin(), cur.end()); cur.pop_back(); reverse(cur.begin(), cur.end()); solve(root); return; } reverse(cur.begin(), cur.end()); go(); for(auto &v: cur) if(v.st == 0) ans[v.nd] = root; cur.clear(); } int main(){ scanf("%d", &n); for(int i = 1; i < n + n; ++i){ scanf("%d", &in[i]); used[in[i]] = true; } if(!check()){ puts("no"); return 0; } if(in[1] != 0) in[n + n - 1] = in[1]; else if(in[n + n - 1] != 0) in[1] = in[n + n - 1]; for(int i = 1; i <= n; ++i){ if(!used[i]) unused.push_back(i); used[i] = false; } for(int i = 1; i < n + n; ++i) ans[i] = in[i]; for(int i = 1; i < n + n; ++i){ if(in[i] == 0){ getEqual.push_back({in[i], i}); continue; } if(used[in[i]]){ cnt = 0; while(getEqual.back().st != in[i]){ if(getEqual.back().st > 0){ ++cnt; used[getEqual.back().st] = false; } cur.push_back(getEqual.back()); getEqual.pop_back(); } reverse(cur.begin(), cur.end()); solve(in[i]); continue; } getEqual.push_back({in[i], i}); used[in[i]] = true; } cnt = 0; while(getEqual.size()){ if(getEqual.back().st > 0){ ++cnt; used[getEqual.back().st] = false; } cur.push_back(getEqual.back()); getEqual.pop_back(); } reverse(cur.begin(), cur.end()); solve(-1); puts("yes"); for(int i = 1; i < n + n; ++i) printf("%d%c", ans[i], i == n + n - 1 ? '\n' : ' '); return 0; } And a little bit modified tutorial: TutorialFirst let's try to find some conditions whether it is possible to recover correct euler tour. Of course for every euler tour ai  ≠  ai + 1 and a1  =  a2n - 1 (because we start and finish in root). Moreover if there exist four index i1  <  i2  <  i3  <  i4 such that ai1  =  ai3 and ai2  =  ai4 and ai1  ≠  ai2 than answer is NO (because vertex is an ancestor of another or there is no relation between them) — let's call it "crossing elements" condition.There are more conditions — parity of positions of all occurences of element x are the same (because we visit every edge in our subtree twice) and between two equal elements with distance 2k there can be at most k distinct elements.It turns out that those conditions are sufficient — we will prove it by constructing an answer.So first let's observe that if we have to equal elements it means that there is subtree (or maybe subtrees) between them — we can solve it almost independently from the rest of a tree (all we need to remember is root of this subtree) and then forget about this subtree. So as long as we have two equal elements i  <  j than we can first solve euler tour between them and then delete elements i + 1, i + 2..., j. So now we want to solve euler tour where no element occur more than once. Let's say that this tour has length 2k - 1 then if we have less than k elements we can replace any 0 with any unused elements. We can't have more because of our conditions.Now if there are three elements in a row with values x, y, 0 or 0, y, x than we can replace them with x, y, x and replce it with x. If we get rid of all triplets like this than we have tour in form of a1, 0, a2, 0, ..., 0, ak. It's easy to observe that we can replace every 0 with our root (subtree's root). There is a special case when we don't have any root (if solving for whole tree), than we have to find any vertex which can be root and then solve our problem. Straightforward implementation will be O(n2) but it can be easily reduced to O(nlogn) and it can be even reduced to O(n), but O(nlogn) was enough to be accepted.To solve this in O(n) we should start with making check of some conditions. It's easy to check most of them except "crossing elements" condition and count the number of distinct elements between two equal elements. We will deal with the second condition while generating correct answer. For "crossing elements" we can for every value x compute value rx equal to number of distinct elements which appears in input before first occurence of x. Now just iterate over every non-zero element (in order from 1 to 2n  -  1 with deque/vector of elements with smaller rx than our current element. Then with some easy checks we can determine if our condition is true.After checking conditions we want to create a vector of unused elements (with 0 occurences in our tour). Now we can iterate over array as long as there are no two equal elements in our prefix, if we find two equal elements then we can solve part between them and delete them from our current prefix (details in code). Now add elements as long as in our part of length 2k  -  1 there are less than k elements. If it turns out that we don't have enough "unused" elements it means that the last unchecked condition doesn't hold.How to find all triplets in O(n)? We can make two steps — in first steps find all triplets x, y, 0 (iterate with stack from left to right) and in second step find all triplets 0, y, x (similarly iterate from right to left). At the end replace all zeroes between with root.Big thanks to Grzmot who wrote great statement and helped me with proving that this solution is correct!
 » 4 years ago, # | ← Rev. 3 →   +1 Can someone explain the second condition of Div2E maximal element should be lower or equal to the sum of all other elementsUPD Got it! :)
•  » » 4 years ago, # ^ |   0 Explain it, please.
•  » » » 4 years ago, # ^ |   +1 Suppose you have numbers: 1111111111 (10x1) 0000001111 (4x1) 0000000011 (2x1) 0000000011 (2x1) Can you change the position of bits so the xor of the numbers equals to zeros? By xoring with number with N-bits you can remove no more than N-bits. Xoring with 0000001111 will remove no more than 4 bits. Xoring with 0000000011 will remove no more than 2 bits. Xoring with 0000000011 will remove no more than 2 bits. In total you can only remove 4+2+2 bits but you have 10 bits in the number 1111111111 so you cannot remove two last bits and thus this sequence is bad.
•  » » » » 4 years ago, # ^ |   0 Can You please explain why these two conditions are sufficient?
•  » » » » » 4 years ago, # ^ |   +3 Let me give it a try.I hope you understand why, even bits are required. Let me try to explain the other condition.Lets say for in a subarray for size K, [a1,a2,a3,...,ak] is count of set bits (setbits array). Also, lets assume a1 >= a2 >= a3 .. >= ak, so a1 is the maximum in the setbits array. Now, I will try to greedily nullify the a1 bits. So, first I nullify a2 bits of a1 using a2. Now, (a1-a2) bits of a1 are left, and a2 is nullified. Now I will greedily use, a3 bits to nullify those (a1-a2) bits of a1. Two cases arise: a3 <= (a1-a2) a3 > (a1-a2) For the first case, I use, all of a3, and now I need to nullify (a1-a2-a3), so I go ahead with using a4, and move ahead. Again, two similar cases arise.For the second case, so I can at max use (a2-a1) bits of a3, and will be left with (a3-a2+a1) bits,(say x, for simplictity) of a3. I don't want that.So, basically, what I will do is, I will take x bits from a2, and x bits from a3, such that, a2+a3-2x = a1, so now a1 can be nullified, and then x bits from a2 and x from a3 can nullify each other, so we are left with zero.Although, this is not a very formal proof, I hope I was able to give enough intuition for the constructive algorithm to arrange the bits when the two conditions are satisfied.
•  » » » » » » 4 years ago, # ^ |   +3 Thank you lohit_97.
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Hello what about this exapmle 1111 1111 1100 sum of 1's is even and max elemnt is lower or equal to sum of all others but those numbers do form not good sequence! UPD:I got it
•  » » » » » » 4 years ago, # ^ |   0 I not understand the editorial for Div2-F.Please can you or someone else explain that too?Thanks!
•  » » » » » » » 4 years ago, # ^ |   0 I also need that. Can someone please explain us??
•  » » » » » » 4 years ago, # ^ |   0 For the second case your explanation gives x=(a2+a3-a1)/2.How do u prove that this is an integer?
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 If it isn't then there is a number with an extra bit after it which will help us nullify it.EDIT: I was so waiting for someone to ask this :P
 » 4 years ago, # | ← Rev. 2 →   0 Loved the tutorial of problem E.....Thanks a lot.
 » 4 years ago, # |   0 Roms Test cases of D problem seems to be weak :( . Some users coded for smaller k like k=2(and the test cases don't include 'yes' with k=3 or more for the worst case) and got AC.
•  » » 4 years ago, # ^ |   0 Can provide link to one such submission?
•  » » » 4 years ago, # ^ |   0 https://codeforces.com/contest/1058/submission/43318617 : works for 5s on k=3,n=m=1e9-1
•  » » » » 4 years ago, # ^ |   +3 It also depends on the processor of your machine. Maybe your machine is slow.
•  » » » » » 4 years ago, # ^ |   0 I checked it on custom invocation, btw the solution is O(sqrt(n*m/k)), which takes O(1e9) in worst case
•  » » » » » » 4 years ago, # ^ |   0 Pretest 10 was 1000000000 1000000000 2LOL
•  » » » » » » » 4 years ago, # ^ |   +3 "the test cases don't include 'yes' with k=3 or more for the worst case"
 » 4 years ago, # |   +3 Hi! I tried my best to understand the editorial for Div2-F https://codeforces.com/contest/1030/problem/F but could not understand it.My doubts are in understanding the proof that keeping 1 box unmoved is optimal and how does that total cost of shifting left parts in the end equal to a_k*S(l,k-1) — sum(w_i*a_i)?Thanks!
 » 4 years ago, # |   0 Can somebody explain DIV2 E editorial with the sample test case 1? 3 6 7 14 
 » 4 years ago, # |   +15 F can also be done with only BIT in O(logn)
•  » » 4 years ago, # ^ |   0 You are right, so did segment tree.
•  » » 4 years ago, # ^ |   0 How?
 » 4 years ago, # |   +1 In tutorial of the problem Div:2-D, how to prove b=(m/k') is always an integer.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 Notice that the area is always a multiple of one-half.So after you divide k by 2 ,(n*m)/k' will be a integer.Let's make an assumption that m/k'=x/y (gcd(x,y)=1),Because (n*m)/k' is a integer,n/(gcd(n,k))should be a multiple of y,That comes to a contradiction because you should divide n by y(both n and k have the factor--y).As a result,m/k' is always an integer.
•  » » » 4 years ago, # ^ |   0 %%% Got it!thank u dalao
•  » » » 4 years ago, # ^ |   0 Finally understood! Beautiful Explanation, Thanks a lot!
 » 4 years ago, # |   +6 In problem E, How to prove that if maximal element is lower or equal to the sum of all other elements then the subsequence is good ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 if this condition holds and the sum of the sequence is even, you can decrease the two biggest numbers by one and preserve this property. so, at every step you can decrease the sum of the sequence by 2 and eventually it's sum will become zero, which means this squence is good.proof: let k be the number of occurences of the maximal number x in a sequence with even sum and 2*x<=sum. in case k=1 or k=2: the operation above decreases the maximal number at least by one and decreases the sum exacly by two so the invariant still holds.in case k>=4, after the operation there are at least two numbers with max value x so the sum is at least 2*x which means the invariant holds.in case k=3, after the operation the max element is x and the sequence has sum of at least x+(x-1)+(x-1)=3*x-2 which is greater or equal 2*x for every x>=2. the case x=1 can't happen because the sum of the sequence will be odd, so also in here the invariant hold
•  » » » 4 years ago, # ^ |   0 "and eventually it's sum will become zero, which means this squence is good." why this means sequence is good? Me also waiting proof of this
•  » » » » 4 years ago, # ^ |   +3 Decrease two numbers corresponds to position two ones in the binary representation of the original numbers at the same place. When the ones are at the same place in both numbers, the XOR will cancel one with the other, and we can ignore them. If the sum of the sequence reached zero it means that every one has another which cancels it, and the XOR result is zero.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Ah, thanks. I was thinking about partition problem. I was trying to find counter example that if you have array satisfying this two conditions, and it can't be devided into two of equal sums. But your proof is not related to partition problem, because here you can use bits of single number in any pair.
 » 4 years ago, # |   0 Can someone explain to me why doubled area of any triangle with integer coordinates is always integer? How can we demonstrate that?
•  » » 4 years ago, # ^ |   +3 https://en.wikipedia.org/wiki/Cross_productArea of triangle (0, 0), v = (x1, y1), u = (x2, y2) is |x1 * y2 — x2 * y1| / 2
•  » » 4 years ago, # ^ |   +11 you can draw the minimal rectangle with sides parallel to the x and y axis that blocks the triangle (for example, the rectangle corrisponding to triangle (0,0), (1,5) , (2,4) is (0,0) , (5,0), (5,4) , (0,4)). it's divided into 4 triangles, the original one and 3 more Straight-angle triangles. it's clear that each one of them has integer doubled area, and the rectangle's area is also an integer, so the original triangle must also have integer doubled area.
•  » » 4 years ago, # ^ |   +3 Thank you!
 » 4 years ago, # |   +5 In problem F, how can we actually do this part: find k in(nlogn) by "descending" down the Segment Tree in
 » 4 years ago, # |   0 In the fourth paragraph of the 1053E, the "than" in the first row should be "then".
 » 4 years ago, # |   0 “Problem B” Can anybody explain me,why x+y=d — diagonal?
 » 4 years ago, # |   0 In DIV2 Problem E, Something Strange is happening. Here: http://codeforces.com/contest/1058/submission/43418325 in Testcase 1 and same code on IDEone: https://www.ideone.com/iiTZkx Getting WA on test case 1 on Judge but produces correct output on my machine.Also, I am interested in knowing the result of test case 5.I am using prefix sum here. My program produces 7 as result, Because no. of set bits are: 8 16 16 18 22. So, for 8, there are 0 prefix, 16 : 0 prefix, 16 : 2, 18: 2 prefix and 22: 3 prefix. Total equals to 7. Please explain how the answer is 3 for this test case?
•  » » 4 years ago, # ^ |   0 Hi, I suggest compiling with the flag -WallIn lines 59 and 73 you have the condition j > (i-66, 0), maybe you forgot a max? Also, the variable maxm is not initialized in 0 so it could have garbageI don't know if this is the only problem but I hope it helps
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Thanks.fixing maxm worked. solved for those cases. Learnt about __builtin_popcountll(), __builtin_popcount was giving wrong number of bits.
 » 4 years ago, # | ← Rev. 2 →   0 hey can anyone tell why this solution is giving WA for second task?...... when i am submitting like this it is giving AC - int sum=pow(2,freq)-1; link for correct solution. https://www.codechef.com/viewsolution/20327375 but when i am using this- cout pow(2,freq)-1 ; it is not giving AC link...https://www.codechef.com/viewsolution/20329958 thanks in advance..... @arpa
•  » » 4 years ago, # ^ |   0 Function pow probably return float value, try convert to int like that: (int)pow(2,freq)-1. And use please logic operations, pow(2,freq) equal 1 << freq.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 problem link https://www.codechef.com/problems/MGCSET but why this solution is giving AC for subtask-1 when i am printing the answer like this cout pow(2,freq)-1 ; solution link https://www.codechef.com/viewsolution/20329958 @Alexit thanks in advance...
•  » » » » 4 years ago, # ^ |   0 because if float value >= 1e6 you print exponentially value. cout << pow(2,20)+1 << "\n"; //print 1.04858e+06 cout << (int)pow(2,20)+1 << "\n"; //print 1048577
•  » » » » » 4 years ago, # ^ |   0 thanks a lot man...u are amazing....
 » 4 years ago, # |   0 In Div2 D, Doubled area of any triangle with integer coordinates is always integer. Can anyone explain this statement.Why is it always true?
•  » » 4 years ago, # ^ |   0 https://www.mathopenref.com/coordtrianglearea.html — Area of a triangle when the three vertices are known. Since all points need to be integral, the formula will always yield a whole number or a (whole number/2). Hence!
 » 4 years ago, # | ← Rev. 2 →   +3 Div2E does it means when r-l>60 and sum(l,r)%2==0 and max(l,r)*2<=sum(l,r), you can always divide the ones into two groups with same size? how to prove that?
 » 4 years ago, # |   +10 My solution of problem E:If i < j and ai = aj ≠ 0, a[i..j] is an Euler tour, we can deal with a[i..j] and replace it with ai.Since a[i..j) doesn't contain the same elements except 0's, we can do this operation:If there are 3 consecutive elements ai - 1, ai, ai + 1, ai ≠ 0 and ai - 1, ai + 1 contain exactly one 0 (or ai - 1 = ai + 1 ≠ 0), we can regard ai as a leaf and let ai - 1 = ai + 1 (equals to the non-zero element), then remove ai and ai + 1. It can be proved correct.After operations, combine the first and the last element to form a cycle, if there are two consecutive non-zero elements, there mustn't be any zero and no solution exists (because a tree with two or more vertices must contain a leaf). Otherwise, any two non-zero elements aren't neighbors, all the elements can be regarded as leaves, it's easy to construct.After there aren't any i < j that ai = aj, we can deal with the whole series using the same way.All operations can be done by stack in linear time.Time complexity: O(n).
 » 4 years ago, # |   0 In DIV2 E, can someone explain " Let's find a way to decide whether fixed segment is good or not. It can be proven that two conditions must be met. At first, sum of bi at this segment should be even. At second, maximal element should be lower or equal to the sum of all other elements." How about this case: b1=3, b2=4, b5=5, i think this satisfy the condition, but this case is not good. Am i right?
•  » » 4 years ago, # ^ | ← Rev. 5 →   0 Let's see, how we can get zero in this case. As we can move the ones we can get something like this:111111111011100Shift the bits of b2 to two positions to the right, make the xor of b2 and b5(I mean the xor of numbers from which b2 and b5 were got) and then you can get zero as you get two numbers which contain 3 ones.
•  » » » 4 years ago, # ^ |   0 I understand, thx
 » 4 years ago, # |   0 Problem in DThe answer is the triangle with vertices (0,0),(a,0),(0,b)How can I be sure that there is a right angle triangle with area of n*m/k?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Here, area matters, you can draw right angled-triangle from any given area. Think like this, no matter what area you have you can increase any side of a right angle infinitely or diminish it infinitely so as to get to the required area.
 » 4 years ago, # |   0 I am getting test case failed 24 for problem c.. i got the logic of problem correctly but not been able to submit it..here is my code link https://ide.geeksforgeeks.org/eKvDSFGmTv
 » 4 years ago, # |   0 How do people come up with the intuition for problems like div1 C? Once I read the editorial it's so clear but I thought for half an hour and I didn't even get to the first observation. Is "solve more problems" the only way?
 » 4 years ago, # |   0 Can someone explain the editorial for problem B
•  » » 2 years ago, # ^ |   0 It can also be done using geometry and complex number for more details see Antti Laaksonen's "Guide to Competitive Programming Book"(in Geometry Chapter). First we need to calculate for every $p = \{x,y\}$ $result = (p - s1) \times (p - s2)$Here, p is the cordinates of points constituting a vector s1 ,s2 = two points in the same line × = cross product of vectors\$ If $result > 0$ then point is on left side of the line else if $result < 0$ point is on right side of the line else $(result == 0)$ point is on the line Then for every given x,y we need to check Here, $e = \{0,d\}$ $f = \{n-d,n\}$ $g = \{d,0\}$ $h = \{n,n-d\}$ p = (x,y) is on e's and f's opposite side and g's and h's opposide side. If the condition is true then the answer is YES. otherwise the answer is NO. Sorry for bad english. Here is my Solution
•  » » » 15 months ago, # ^ |   0 Thanks a lot for your explanation. Quite newbie to the geometry section didn't come up with such simple intuition, helped a lot. Submission
 » 4 years ago, # | ← Rev. 2 →   0 Interesting problems...
 » 3 years ago, # |   0 Can we do vasya and triangle question using binary_search on base<=n and get the answer? I tried this and it went into infinite loop in some higher test case... How should i write efficient binary_search conditions
 » 3 years ago, # |   0 For Problem D. Can Anybody Explain why this works?k=n*m*2/k; cout<<0<<" "<<0<
 » 2 years ago, # |   0 75073623 1030A - In Search of an Easy Problem please someone explain why this is not working.thanks in advance !!
 » 2 years ago, # |   0 Why I am getting the wrong answer in 1030A?? my code is here in python,import random n= int(input()) li=[] for i in range(n): x = random.randint(0,1) li.append(x)if 1 in li: print 'Hard' else: print 'Easy'
•  » » 2 years ago, # ^ |   0 google how does online judges workyou take input not generate randomize input yourself
 » 2 years ago, # |   0 Can someone explain me the line "That's why if length of the segment ≥61, condition on the maximum is always true." given in the explanation of problem E.I am unable to get it!
 » 17 months ago, # |   0 My solution to problem D:Check if $k$ divides $2nm$. If it does not, report that there is no solution. Otherwise, fix a point at $(0,0)$. Now, in order to find the other two vertices of the triangle, get all the prime factors of $2nm \div k$ using Shanks's square forms factorization. Then, find all the divisors of $2nm \div k$ from its prime factors recursively. This will fit in the TL because the number of divisors of $10^{18}$ is $103680$. Finally, iterate over all divisors until you hit an divisor $d$ such that $d \leq n$ and $2nm \div dk \leq m$. The other two vertices will be $(d,0)$ and $(0, 2nm \div dk)$.
 » 6 months ago, # |   0 This is My Solution for Problem D And I Wonder Why I didn't Get Time Limit exceeded . Is This because Test cases weren't be enough Or Something Else ????????????????????????? https://codeforces.com/contest/1030/submission/150139674