### Dalgerok's blog

By Dalgerok, history, 4 weeks ago, ,

•
• +176
•

 » 4 weeks ago, # |   +2 thanks for tutorial and your effort
 » 4 weeks ago, # |   -27 Thank you for fast editorial!
•  » » 4 weeks ago, # ^ |   +8 Please stop this shit
 » 4 weeks ago, # |   -37 Thanks for the quick editorial.
 » 4 weeks ago, # | ← Rev. 2 →   +65 Nice Problem Fast System Testing Quick Editorial Overall Great contest :)
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 + First time to be Specialist . :)
•  » » » 4 weeks ago, # ^ |   +3 Ya :)
•  » » 4 weeks ago, # ^ |   +12 Wasn't perfect — placement of B and D was wrong
 » 4 weeks ago, # |   0 Here's how i did problem D. 52982122Just sort the array according to the below comparator. bool comp( pair< int ,int > a, pair< int, int > b){ if(a.first + b.second > a.second + b.first) return true; else return false; } Proof: Let there be two pairs a and b. The dissatisfaction is i*(a1 + a2 — b1 — b2 ) + n*(b1 + b2) — a1 — a2 . We have to just consider the i term as rest are constant terms. Sort it according to a1 — b1 > a2 — b2
•  » » 4 weeks ago, # ^ |   0 Thx! Easy to understand !!
 » 4 weeks ago, # | ← Rev. 4 →   +4 I used divide and conquer in E. Let $f(l,r)$ equals answer for segment $[l;r]$ and $half = (l+r)/2$ then $f(l,r) = f(l,half) + f(half+1,r) - min(arr[half], arr[half+1]) * (n - max(arr[half], arr[half+1]) + 1)$.
•  » » 4 weeks ago, # ^ |   0 Oh! Egor Letov is alive!
 » 4 weeks ago, # | ← Rev. 2 →   -12 This is boolshit))
•  » » 4 weeks ago, # ^ |   +16 Have you coded your solution? I'm sure that it is wrong. Firstly, I think that $m_{i, i} \neq m_{i, j}$. Secondly, you can't compute the answer by multiplying the probabilities (your last sentence), because they are not independent.
•  » » » 4 weeks ago, # ^ |   +2 You are right! I am stupid))
 » 4 weeks ago, # |   -6 For problem D, you don't really need to sort by index. "array d in non-decreasing order". I solved without sorting D.
•  » » 4 weeks ago, # ^ |   +8 Yes, It is already sorted :)
 » 4 weeks ago, # |   0 It is very thankful for brilliant tutorial.
 » 4 weeks ago, # |   0 can somebody explain me problem c and I have seen some solution like (calc(R) — calc(L — 1) + mod) % mod here he is adding mod, why? if we are not adding mod then 6 test case fail.please help me. Thank u
•  » » 4 weeks ago, # ^ |   +5 It depends on your language. Languages like C and C++ don't return values between $0$ and $MOD-1$ while taking mod of a negative number. Instead they return the 'negative mod'. $-5mod4$ should be $3$, but $-1$ is returned. While $-1$, is correct, it's not what we want. So, we add an extra $MOD$ and take mod again to ensure the result lies between $0$ and $MOD-1$. Adding an extra mod should always be done if you're subtracting 2 numbers and taking their mods.
•  » » » 4 weeks ago, # ^ |   +9 Thanks bro
 » 4 weeks ago, # |   0 Please add Solutions when published editorials. it's helped a lot.
 » 4 weeks ago, # | ← Rev. 2 →   0 For problem C, this is my solution https://codeforces.com/contest/1151/submission/53005511 The solution uses the logic given in the editorial. I have tried placing MOD in all possible location and still not getting the correct answer. Anyone help? :)
•  » » 4 weeks ago, # ^ |   0 Anyone please :)
•  » » » 4 weeks ago, # ^ |   0 In your fun(), it's enough if you just calculate the pow(2, i) without the mod. By subtracting, what you're essentially doing is just dividing the variable x by 2. So taking mod on the variable x would affect the loop because modular division is not similar to modular addition or subtraction where you can take mod wherever and it wouldn't affect the answer. So, using pow(2, i) on line 39 and removing line 50 would be the way to go.
•  » » » » 4 weeks ago, # ^ |   +1 Yeah thanks bro :)
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 The problem probably lies in how you implemented the power() function. The way you iterate it is not obvious to me, and I'm not sure y = y/2 is the right way to do it.
 » 4 weeks ago, # |   0 Can anybody explain to me how to work a code in B
 » 4 weeks ago, # | ← Rev. 3 →   +4 DalgerokIN E editorial, Shouldn't it be:we must find the number of pairs (l,r) such that ai is not on the range [l,r] and ai−1 is on the range [l,r]. instead of:we must find the number of pairs (l,r) such that ai is on the range [l,r] and ai−1 is not on the range [l,r].
•  » » 4 weeks ago, # ^ |   +3 No, because $b_i$ must be $1$ and $b_{i-1}$ must be $0$.
•  » » » 4 weeks ago, # ^ |   0 Got it thanks :)
 » 4 weeks ago, # |   0 The explanation of problem B is not helpful! Can anyone explain it?
•  » » 4 weeks ago, # ^ |   0 first take element from first column from each row and take their XORs. If xor!=0, simply print the index of elements and exit. If xor==0, then iterate all elements of the table. If in a given row, current element is different from element in first column, then , if we replace the first element with this element, our xor will become non-zero.
•  » » » 4 weeks ago, # ^ |   0 thanks mate
•  » » » 4 weeks ago, # ^ |   0 thanks for this simple and easy explaination. can you plz explain problem C also??
•  » » » » 4 weeks ago, # ^ |   0 to find sum of numbers from L to R, you need to do (sum of first m numbers in this sequence)- (sum of first L-1 numbers in the sequence). This is a simple observation, you can check this by taking first 10 natural numbers.Now, to find sum of first L-1 numbers , you need to count the number of odd no. and number of even nos. till (L-1). To count both, start a loop from i=1 , double it on every iteration while increasing count of odd and even numbers alternatively. But, keep in mind the last count which you will add, which may not be power of 2.finally, suppose, you got 'a' odd numbers and 'b' even numbers. then sum= a*a + b*(b+1) (simple AP series sum formula) you can do similar calculation for first M numbers.
•  » » » » » 4 weeks ago, # ^ |   0 http://codeforces.com/contest/1151/submission/53007448check my code to see how I have done it.
•  » » » » » » 4 weeks ago, # ^ |   0 Thank you!!☺
 » 4 weeks ago, # |   0 The last problem is so awesome! By the way, is there some problem that has similar "style" to the last one? I mean, its not dp on the book, it's like... creativeness on how to define dp state?
 » 4 weeks ago, # | ← Rev. 2 →   0 Can anyone please tell me for problem 'B' why I am getting WA on test 9 while I ran same thing on my machine and it's shows correct output? link While after that I tried doing same thing using for loop and guess what, go AC!! link
•  » » 3 weeks ago, # ^ |   0 Anyone?? :/
 » 4 weeks ago, # |   +1 For F, how do we use matrix exponentiation when the dp has more than 1 dimension?
•  » » 4 weeks ago, # ^ |   0
•  » » 4 weeks ago, # ^ |   +5 When $f[i][j]$ can be represented as a linear combination of $f[i - 1][k]$ for some $k$'s, it is possible to define a transition matrix from $f[i - 1]$ to $f[i]$. Let this matrix be $M$. Then by multiplying $M^n$ with the vector $f[i]$ you can jump to $f[i + n]$.
 » 4 weeks ago, # |   0 Here's my submission for B. https://codeforces.com/contest/1151/submission/52967808Could someone explain the judge's verdict of XOR being less than 0 for testcase 24?
•  » » 4 weeks ago, # ^ |   0 It means the sequence you provided as the answer arrives at a XOR value of $0$, which implies that it is not a valid sequence.
 » 4 weeks ago, # |   0 For the problem D. Why my solution https://codeforces.com/contest/1151/submission/53019943 is getting runtime error.
•  » » 4 weeks ago, # ^ |   0 when I change the compare function now it gives WA. what is the problem now and before. https://codeforces.com/contest/1151/submission/53019888
•  » » » 4 weeks ago, # ^ |   0 Anyone Please :)
•  » » » » 4 weeks ago, # ^ |   0 I don't really know about JAVA, but in C++, for a false comparison, you have to return 0. Why don't you try changing the -1 to 0.
•  » » » » » 4 weeks ago, # ^ |   0 https://codeforces.com/contest/1151/submission/52980095 This is the same code written in c++ but it is also giving runtime error on test case 8.
•  » » » » » » 4 weeks ago, # ^ |   0 I tried out your code, with a single change. I changed your compare statement, from f>=0 to f>0 and it worked.Runtime Error — https://codeforces.com/contest/1151/submission/53027297As to why this happens, I am clueless. Maybe someone can give some insight to this.
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Thanks. But someone please tell why it was not working previously.
 » 4 weeks ago, # |   0 In Problem B we can also use RANDOM SHUFFLE!!!.We can Random Shuffle all the elements in each row and then check the xor for each column that whether it is greater than zero or not.P.S.-I have applied random shuffle 200 times.Luckily it passes all the tests :PHere's link to my solution : 53025553
•  » » 4 weeks ago, # ^ |   0 You may want to actually calculate the probability of getting false negative in the worst case (only one element is different in one of the rows). It might be surprisingly small.
•  » » 4 weeks ago, # ^ |   0 That was just a lucky try. I might get WA on submitting the same solution
 » 4 weeks ago, # |   0 Can anyone provide a prerequisite for understanding solution of problem C for mortals like me? I can't even ...
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You may take a look at my solution of C. Not exactly the approach of the editorial (in that the editorial is more straight forward in counting the size of each group), but it could possibly help you get a better perspective.
•  » » » 4 weeks ago, # ^ |   0 Wow ! very detailed answer ! Thank you.
•  » » » 4 weeks ago, # ^ |   0 Amazing... Better Than editorial Thanks for posting
 » 4 weeks ago, # |   0 I have done following in problem C. Function calculates the sum in set till number n.ev — next even sequence start od — next odd sequence startthen for each iteration, I calculate start and end of that sequence and calculate their sum by AP. It is giving wrong answer on test case 1 1e18. Is there an overflow ? I cannot find the bug in function calc.code link CODE#include #include #include using namespace std; #include #include using namespace __gnu_pbds; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; // s.order_of_key(x); // gives order of x in the set #define For(i,x,n) for(long long i=x;i>l>>r; cout<<(calc(r)-calc(l-1)+MOD)%MOD; //cout<<"\nTime used = "<(clock())/(CLOCKS_PER_SEC)<<"s"< hm; ll i; for(i=2 ; i*i<=15000002 ; i++) if(isprime[i]==0){ for(ll j=2*i ; j<=15000001 ; j+= i) if(isprime[j]==0) isprime[j]=i; isprime[i]=i; hm[i] = cc; cc++; } for( ; i<15000002 ; i++) if(isprime[i]==0) isprime[i]=i,hm[i]=cc,cc++; } ll choose(ll n,ll k) { if(k==0) return 1; return (n* choose(n-1,k-1))/k; } void showArray(ll a[], ll n){ For(i,0,n){ cout< eps && fabs(y) > eps) { if (x > y) x -= floor(x / y) * y; else y -= floor(y / x) * x; } return x + y; } ll power(ll x,ll n) { if(n==0) return 1; else if(n%2 == 0) //n is even return (power((x*x)%MOD,n/2))%MOD; else //n is bal return (x*power((x*x)%MOD,(n-1)/2))%MOD; } ll power1(ll x,ll n) { ll num = 1; For(i,0,n){ num = (num*x)%MOD; } return num; } 
 » 4 weeks ago, # |   0 I have found a solution with O(1) complexity for Problem C. See 53051961Can anyone tell is it really a O(1) complexity? (I am just new to algorithm and I don't know is it right)Thank you :)
•  » » 4 weeks ago, # ^ |   0 No, it is $O(\log{N})$.
 » 4 weeks ago, # |   +6 Can someone explain the approach behind E problem ? Whats the logic for calculating f(l,r) ?
 » 4 weeks ago, # |   0 For problem D .By changing the compare statement, from f>0 to f>=0 my code gets runtime error.Runtime Error — https://codeforces.com/contest/1151/submission/53027297As to why this happens, I am clueless.Someone please tell why it started giving runtime error.
•  » » 4 weeks ago, # ^ |   0 Someone Please reply :(
 » 4 weeks ago, # |   0 i still cant understand problem c can anyone explain me?
 » 4 weeks ago, # |   0 For Problem E — The editorial states "using technique contribution to the sum". What is this technique ??
•  » » 4 weeks ago, # ^ |   0
 » 4 weeks ago, # |   0 Great Editorial!
 » 4 weeks ago, # |   0 My solution for Problem C works fine for smaller size of input but it failed for larger value. But, I'm pretty sure that I took the modulo correctly. Tried a lot to debug but failed. Could you please give a look in my code?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You should multiply by inverse modulo values instead of dividing on them.
•  » » » 4 weeks ago, # ^ |   0 Are you talking about the lines even /= 3;, odd /= 3;?
•  » » » » 4 weeks ago, # ^ |   0 Yes
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Actually, in those lines, I was finding the length of total odd and even numbers not the sum itself.
 » 13 days ago, # |   0 why i am getting wrong output for test case 21 in problem B 53825407 waiting for response.