### BledDest's blog

By BledDest, 3 years ago, translation, , We want to apologize for the issue with problem C. We hope this didn't totally ruin the contest to those who got Judgement Failed on their submissions. Tutorial of Educational Codeforces Round 18 Comments (37)
 » Let me mention the beautiful x&(-x) which is equal to highest power of two that divides x.
•  » » Also we have x&(x-1) which is equal 0 only when x is a power of two(except x == 0).
 » Can someone explain to me the solution of problem C, especially this part: "Then you can easily see that its enough to check only three function outputs: on substrings [a1..n], [a2..n] и [a3..n]"
•  » » The only flaw in the function is that it can't erase first digit of number. So we should feed it with numbers of different sums modulo 3. So sums of these strings are ( a 1 + a 2 + sum, a 2 + sum, sum).Let's notice that if the first digit is 0 modulo 3, then it won't be erased anyway and thus won't affect further number (if we can't make beautiful number of this string, then we won't be able to make it out of any further ones). So now we only care if a 1 and a 2 are either 1 or 2.1) If one of them is 1 modulo 3 and the other is 2 modulo 3, then by deleting both of them you will get sum of original number modulo 3.2) If both of them are the same modulo 3, then check every possible reminder of original sum. If it was 0 modulo 3, then the answer existed anyway. If it was either 1 or 2, then by deleting one or both of this digits you can make sum 0 modulo 3, so the answer will exists, if it existed for original number.I hope that this I made myself more clear.
•  » » » I still did not understand.I want to ask a few questions. How do we write the function which erases the minimum number of digits from the string?I having a problem with this because we have to take care of the leading zeros.So there maybe a case where removing only one non-zero digit may cause a number of zeros also to be removed.Ex-; 2000111 if we remove 2 we'll get 111 ,and we will have to remove the zeros also.So this will not be the minimum case. However if we remove 2 1s we'll get 20001 which is the optimal answer. So how do we take care of this?
•  » » » » Solution that I described in editorial doesn't have separate function that erases minimal number of digits from all the string. It has the function which erases minimal number of digits from string but doesn't touch the first digit. In your testcase we will try running this function on strings "2000111" (returns "20001"), "111" (returns "111") and "11" (returns "-1"). Obviously, max of these is "20001".
•  » » » » » Thanks a lot!
•  » » » » » Thank you, finally with that example i understanded the solution :D
 » The problem C reminded me that i am a primary competitor. sorry for my poor English
 » Hi can anyone explain me the dynamic programming approach of Problem C ? Thanks
•  » » Let dp(i,j) denotes the maximum number of digits we will keep from 1 to i, including i and the number they form modulo 3 = j (or you can say the length of longest subtring ends at i and modulo 3 = j).I will show you how to compute dp(i,0), you can do the same thing with j=1,2 and the special case when s[i]='0'. Let x=s[i] % 3, then dp(i,0) = max(dp(k,y)) + 1 with k = 0..i-1, y + x = 0. To be more detailed, there are 3 cases: x=1: dp(i,0) = max(dp(k,2)) + 1 , however if there is no k that dp(k,2) > 0, which means there is no substring before i that modulo 3 = 2, dp(i,0) should equal to 0. x=2: dp(i,0) = max(dp(k,1)) + 1 , same as above, if there is no k that dp(k,1) > 0, dp(i,0) should equal to 0. x=0: dp(i,0) = max(dp(k,0)) + 1 , this always holds true because if there is no k that dp(k,0) > 0, we can make a new substring starts and also ends at i which has length 1 and modulo 3 = 0. It's a little bit confusing when explain so you can look at my code here: 25856552In my code, I add f[i] denotes the length of longest substring which modulo 3 = i and update it continuously. It replaces max(dp(k,y)) above to reduce complexity to O(length(S)). Since this problem required the number after erasing, we have to trace it after dynamic programming.
•  » » 3 years ago, # ^ | ← Rev. 3 →
 » Sir, in New Bus Route i.e Question A, What if the minimum difference is zero, in that case counting only adjacent pairs won't work for eg. for input case 6 2 2 2 3 5 5 as per your method ans will be 3, but the actual answer is 4 — the 3 pairs of all the 2s and the one pair formed by 5,5
•  » » One tip in competitive programming is to carefully read the problem statement."The first line contains one integer number n (2 ≤ n ≤ 2·105).The second line contains n integer numbers a1, a2, ..., an ( - 109 ≤ ai ≤ 109). All numbers ai are pairwise distinct."
•  » » » My Bad, sorry
 » Can anybody tell me why am I getting a TLE on this submissions of 792A - New Bus Route problem my submission is this 25882029. The complexity is O(nlogn).
•  » »
•  » » » Thanks!
•  » » » » Accepted aa gaya tera fir?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   Yaa, just use Integer in place of int as the datatype of input array.
 » In problem C, why does the function start erasing from the second character? why not first?
•  » » It's done to avoid handling any leading zeros problems.
•  » » » I'm confused why this works. Suppose n = 133. Then starting from the second digit would ignore the optimal case where we take out the first digit right?Please correct me if I'm misinterpreting..
 » Time exceeded on test 30 of problem E, as far as I'm struggling, the complexity is correct but maybe the constant is too large, can someone help me with a more efficient algorithm for calculating the sum of sets?current algorithm: for (int i = 0; i < n; i++) { if (a[i] / size >= a[i] % size) { cnt += min(a[i] / size, (a[i] / (size + 1) + (a[i] % (size + 1) ? 1 : 0))); } else { cnt = 3e18; break; } } 25890955
•  » » 3 years ago, # ^ | ← Rev. 2 →   Well, integer division (as well as modulus) are complex operations, and it's better to get rid of them, if possible. For example, when you write something like (a / b + (a % b ? 1 : 0)), which means a divided by b rounded up, you can replace it with ((a + b — 1) / b), which uses only one division operation and works faster.UPD: And as for more, you can store the array a as int array instead of long long, and int division is also faster than long long division.
•  » » » thanks, got accepted immediately after replace the rounding up division expression. So nice the replace is!
 » Can someone please paste the Problem C accepted solution???
•  » »
•  » » » thanks :)
•  » » » » You're welcome)
 » Hi! Can anyone help? Are there full texts of tests available?
 » but if a1:k what does this mean in problem E
•  » » a1%k==0
 » I am humbled by question-E. so simple yet so beautiful.
 » For anyone wondering about the proof of problem D:the key idea is that the value at any non-leaf node is the number of nodes in the left subtree of the node $+$ the least valued leaf. This is obvious by the recursive algorithm. Then one can prove that $val(parent)-val(leftchild)=2^t$, where $t=k-1$
 » Hey BledDest, pikmike Can you explain the first line in the editorial of problem E ? I am not able to understand why k<=sqrt(a[i]) or x<=sqrt(a[i]) ?Thanks
 » I don't understand E, can someone elaborate? My initial idea was to use gcd of all the numbers. then pairs would be gcd, gcd + 1, or gcd — 1, gcd sizes.