BledDest's blog

By BledDest, history, 2 years ago, translation, ,

We are really sorry for the issue with the testing system. We hope that it won't happen during next contests.

• +93

 » 2 years ago, # |   +16 Thanks for fast editorial! :D An easy trick for D: Once you have calculated the sum of minimum in all subarrays, you can just make all the numbers negative ( multiply each of them by -1) and then again calculate the sum of minimum in all subarrays. The sum of maximum will just be the negative of that.
•  » » 2 years ago, # ^ |   +1 Thank u sir for enlightening us with such a good method!! Hats oFf!!
•  » » 2 years ago, # ^ |   0 Can you please tell me why I am getting TLE in 43th test case in problem B. Here is my Java code. https://paste.ubuntu.com/24973949/
•  » » 5 months ago, # ^ |   0 after we are done calculating max and min....isnt the answer equal to max-min ???
 » 2 years ago, # |   +6 C problem also solvable with DP (27810451) works in 183 * 92 * 2. D problem also solvable with D&C approach(27810683) which works in N * log(N).
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Can you explain your dp states for Problem C ?
•  » » » 2 years ago, # ^ |   +4 dp[position in decimal representation][equal or not][sum of digits]
•  » » 2 years ago, # ^ |   +6 what is the D&C approach?
•  » » » 2 years ago, # ^ |   0 Divide and conquer.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 why did this DC solution 27820818 get MLE? could you explain it to me please?
•  » » » 2 years ago, # ^ |   0 hehe inline??????? http://www.cplusplus.com/articles/2LywvCM9/ passed my solution
•  » » » » 2 years ago, # ^ |   0 Can you please elaborate what is your approach, it is interesting.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +5 D problem D&C aprroach linkThis implementation is same as of Kerim.K , just some comments added for ease of understanding.Thanks to Kerim.K for sharing the approach...
 » 2 years ago, # |   +70 There is also another solution for problem C.Since we know that the maximum value for n is 1018, then the maximum sum of digits we can get is for n = 999999999999999999, which is 162. Using this observation, and the proof mentioned in the editorial, we can be sure that all integers in the interval [s + 162, n] are really big numbers. So, what is left now is to check the interval [s, s + 161] with a simple for-loop. Source Code#include using namespace std; int sum(long long n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; } return ret; } int main() { long long n, s; cin >> n >> s; long long res = max(0LL, n - s + 1); for (long long i = s; i <= min(n, s + 161); ++i) { if (i - sum(i) < s) { --res; } } cout << res << endl; } 
• »
»
2 years ago, # ^ |
Rev. 2   -45

#include <bits/stdc++.h>

define ll long long int

using namespace std;

int main() {

ll n,s;
cin>>n>>s;
float y=log10(s);

int k=ceil(y);
if(s==1)
{
k=1;
}
//cout<<k<<endl;
if(n<=s)
{
cout<<0;
return 0;
}
ll ans=n-s-(9*k);
ll l=0;
ans=max(ans,l);
ll p=(9*k)+s;
for(ll i=s;i<=p;i++)
{
if(i>n)
{
break;
}
else
{
ll h=i;
ll sum=0;
while(h!=0)
{
sum+=h%10;
h=h/10;
}

if((i-sum)>=s)
{
ans++;
}
}
}
cout<<ans;
return 0;


}

•  » » 2 years ago, # ^ |   +1 Amazing observation :D
•  » » 2 years ago, # ^ |   0 Observed the same thing. Also while calculating the sum of digits, you can store the parts uptil the thousand's digit(excluding it as it can change). And only calculate the sum for the last 4 digits of a number. OR we could just store the four digits in an array and whenever any one of the digit goes above 9 make update the current to 0 and add 1 to next one.
 » 2 years ago, # |   +1 Can i know the difficulty difference between an educational round and a normal round.How does difficulty of each problem in Normal round map to educational round?
•  » » 2 years ago, # ^ |   +22 It's usually like a standard div2 round + one task slightly harder than div2e.
•  » » » 2 years ago, # ^ |   +2 E and D are good so that people can learn something new from the contest. Though they were standard trie and stack questions . I felt they were educational.Hope u introduce more advance concepts and data structures through educational rounds.
 » 2 years ago, # |   0 I did not understand the editorial to problem B. please explain. thanks :)
•  » » 2 years ago, # ^ |   0 A very simple approach to problem B: Sort the array containing the numbers. Pick the first three. Now, we can prove that the minimum product will always contain only these three elements and nothing else. Thus, we next count occurrences of these first three letters in the whole sequence. Let the first, second and third numbers be a, b and c. And their repetition in the whole sequence be countA, countB, countC, and let they all be different. Then, ans is countA*countB*countC. But, if b repeats, then b is equal to c (sorted order). Then ans is countA* (ways of choosing 2 elements from countB elements). Similarily if a is repeated two times. Ans is countB only(any other repetition of a will cause it to be equal to c). If all three are same. Then ans is (no. of ways of choosing 3 elements out of countA elements). Here, the no. of ways of choosing 3 elements out of n elements = n*(n-1)*(n-2)/6 Here, the no. of ways of choosing 2 elements out of n elements = n*(n-1)/2
•  » » » 2 years ago, # ^ |   0 I did the same thing for B, but I keep TLE-ing on test 43. I'm convinced there's some kind of error in the judger or the data, because every other test takes less than 200 ms, including the 100000-length ones. I even bit the bullet and used BufferedReader instead of Scanner...no difference.Take a look at my submission. Can you see some weird degenerate case that would cause my solution to not be O(NlongN + N)? I'm going crazy over here!
•  » » » » 2 months ago, # ^ |   0 solutioncheck it out..this might help.
•  » » » 2 years ago, # ^ |   0 Can you please explain why the number of ways to choose 3 elements out of n is n*(n-1)*(n-2)/6 ?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0
•  » » » » 2 years ago, # ^ |   0 number of ways of choosing 3 elements out of n is n * (n-1) * (n-2).but this overcount's. for example this formula counts (1, 2, 3) 3! times. so we divide by 3! = n*(n-1)*(n-2) / 6
 » 2 years ago, # |   0 I am not getting problem A ,I mean why does not (x2-x1)%x==0 and (y2-y1)%y==0 work?Please explain.
•  » » 2 years ago, # ^ |   0 because let's say one is even positive and other is odd positive, then the answer would be NO.
•  » » 2 years ago, # ^ |   0 it works but you also have to check if it's possible to reach the point doing movements in L. like a horse on chess. It will be reachable if the number of moves performed in the x axis + the number of moves performed in the y axis is even. This happens because when you move, you always do a move in both axis.
•  » » » 2 years ago, # ^ |   0 this is fine,but no of moves can't be given by (x2-x1)/x and (y2-y1)/y because there can be intermediate nullified moves in between too.
•  » » » 2 years ago, # ^ |   0 but also number of moves in x and y-axis can't be given by (x2 — x1) / x, (y2 — y1) / y because in 0 0 0 6 and x=2,y=3,no of moves in x axis is not(0-0)/2
•  » » » » 2 years ago, # ^ |   0 So what? Yes, it isn't 0, but we only care of the parity of this number and (0 + 0)/2 + (0 + 6)/3 is even, so the answer exists.
•  » » » » » 2 years ago, # ^ |   0 Thanks.Got it.
•  » » » » » 2 years ago, # ^ |   0 can you please explain why we looking only for parity, and why not the number of moves given by (x2-x1)/x, (y2-y1)/y .plz explain using this case ( 0 0 0 6 and x=2,y=3).Thanks in advance
•  » » 2 years ago, # ^ |   0 (x2-x1)%x==0 and (y2-y1)%y==0, only guarantees that we can reach x2 from x1 and y2 from y1 separately, but we need to reach them in the same number of steps, for that to be possible (abs(x2-x1)/x)%2 and (abs(y2-y1)/y)%2 should either be 0 or 1. You cannot reach both x2,y2 in same number of steps if one of abs(x2-x1)/x,abs(y2-y1)/y is odd and other is even.
•  » » » 2 years ago, # ^ |   0 this is fine,but no of moves can't be given by (x2-x1)/x and (y2-y1)/y because there can be intermediate nullified moves in between too.
•  » » » 2 years ago, # ^ |   0 but also number of moves in x and y-axis can't be given by (x2 — x1) / x, (y2 — y1) / y because in 0 0 0 6 and x=2,y=3,no of moves in x axis is not(0-0)/2
 » 2 years ago, # |   0 I think it's nature for most of us to use DP to solve Problem C…… But the prove is easy and important.....
 » 2 years ago, # |   0 How to approach a problem like 'B'? I mean how does the right technique strike? Are there any pointers(in the limits or similarity to a classic problem) to the right way? Any help would be appreciated.
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Hmm. I don't really know :) I used the approach from the editorial in couple of other problems, though I can't remember any in particular. I guess that if this one doesn't seem intuitive then you can always try the other one. Where you just check some cases on the amount of the elements less than the third minimum of the array. Most people implemented this solution. UPD: the author of this task told me that the similar approach is used here
•  » » » 2 years ago, # ^ |   0 Thanks a lot, PikMike.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 i would request the author to provide the implementation described in the editorial Thanks for the help PikMike Also i have seen many people doing sorting will that not affect the ordering (i
•  » » » » 2 years ago, # ^ |   +5 ordering will not be affected because if there is 3 indices in sorted array then there will be 3 indices in previous array. Isn't it .
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Here it is.Reorders will not affect answer. Why should they? You will just take the same triplets but indices in each will be in other order.
•  » » » » » 2 years ago, # ^ |   0 sorry my bad you are correct thanks for the explaination
•  » » 2 years ago, # ^ |   0 I solved it differently. First sort array a. Then take three smallest values, let them be a,b,c in this order. Also, while doing input of array, keep array cnt[x], which tells how many times x appeared in input. case a!=b!=c Then number of ways is cnt[a] * cnt[b] * cnt[c] (simple combinatorics) case a == b but b!= c (if b!=c then a!=c as well, because a,b,c are sorted) then there are cnt[a] * (cnt[b] — 1) /2 ways to choose pair (a,a) and cnt[c] to choose c, so to get total multiply these two. case a != b, b == c Similar to 2. case 4.case a == b == c then answer is cnt[a] * (cnt[b] — 1) * ( cnt[c] — 2) / 6 (again simple combinatorics) That covers all cases.
•  » » » 2 years ago, # ^ |   0 Can you explain how did you get these formulas?
•  » » » » 2 years ago, # ^ |   0 SaynorPRO You may see these formulae as "n choose r". If we denote this value with the function c(n,r), c(n,r) = n!/(r!(n-r)!). So here, in case 1: It is simple product-rule of combinatorics case 2: It is c(cnt[a],2) that we need; because that gives us the number of ways to choose a(and hence, b). case 3: Like case 2. case 4: It is c(cnt[a],3). Hope this helps.
•  » » » 2 years ago, # ^ |   0 True. The condition i
 » 2 years ago, # |   0 Hello, In problem D I don't know why did I get a Wrong answer on test 12. Can you please help me?27814997
•  » » 2 years ago, # ^ |   +1 I guess integer overflow in the last for loop
 » 2 years ago, # | ← Rev. 2 →   0 How to solve the problem D when imbalance is defined as (max-min)^2 or (max-min)^k with k>=2 in better than O(N^2)?
 » 2 years ago, # | ← Rev. 2 →   +5 WHat is the movement of source: 2 -5 destination: -8 8move: 2 1 . in Problem A ? How this is YES ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 0 -4, -2 -3, -4 -2, -6 -1, -8 0, -8 1, -8 2, .. .. .., -8 8
•  » » 2 years ago, # ^ |   +5 (-2,+1) (-2,+1) (-2,+1) (-2,+1) (-2,+1) (+2,+1) (-2,+1) (+2,+1) (-2,+1) (+2,+1) (-2,+1) (+2,+1) (-2,+1)
•  » » » 2 years ago, # ^ |   0 Thanks everyone :)
 » 2 years ago, # | ← Rev. 4 →   0 Why my MEX queries does not work? Here's my code: Solution#include using namespace std; typedef long long ll; struct interval { int a, b; int k0; int k1; bool L[2]; //L[0] - i ka pakeisti visus neesamus //L[1] - i ka pakeisti visus esamus interval *left = NULL; interval *right = NULL; void fix() { if (L[0] == 0 && L[1] == 1) return; if (left) { if (left->L[0] == 0) left->L[0] = L[0]; if (left->L[0] == 1) left->L[0] = L[1]; if (left->L[1] == 0) left->L[1] = L[0]; if (left->L[1] == 1) left->L[1] = L[1]; } if (right) { if (right->L[0] == 0) right->L[0] = L[0]; if (right->L[0] == 1) right->L[0] = L[1]; if (right->L[1] == 0) right->L[1] = L[0]; if (right->L[1] == 1) right->L[1] = L[1]; } if (L[0] == 0 && L[1] == 0) { k0 = (b - a + 1); k1 = 0; } if (L[0] == 1 && L[1] == 1) { k0 = 0; k1 = (b - a + 1); } if (L[0] == 1 && L[1] == 0) swap(k1, k0); L[0] = 0; L[1] = 1; } void init(int x, int y) { a = x; b = y; k0 = (b - a + 1); k1 = 0; L[0] = 0; L[1] = 1; if (x != y) { left = new interval; right = new interval; left->init(x, (x + y) / 2); right->init((x + y) / 2 + 1, y); } } void q1(int l, int r) { fix(); if (r < a) return; if (b < l) return; if (l <= a && b <= r) { L[0] = 1; L[1] = 1; fix(); return; } left->q1(l, r); right->q1(l, r); k0 = left->k0 + right->k0; k1 = left->k1 + right->k1; } void q2(int l, int r) { fix(); //1 -> 0 if (r < a) return; if (b < l) return; if (l <= a && b <= r) { L[0] = 0; L[1] = 0; fix(); return; } left->q2(l, r); right->q2(l, r); k0 = left->k0 + right->k0; k1 = left->k1 + right->k1; } void q3(int l, int r) { fix(); if (r < a) return; if (b < l) return; if (l <= a && b <= r) { L[0] = 1; L[1] = 0; fix(); return; } left->q3(l, r); right->q3(l, r); k0 = left->k0 + right->k0; k1 = left->k1 + right->k1; } int MEX() { fix(); if (k0 == 0) return b; if (k1 == b - a + 1) return b + 1; if (a == b) return a; if ((left->MEX()) != ((left->b) + 1)) return left->MEX(); return right->MEX(); } }; int main() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); int n; cin >> n; ll t[n], l[n], r[n]; setX; for (int i = 0; i < n; i++) { cin >> t[i] >> l[i] >> r[i]; X.insert(l[i]); X.insert(r[i]); X.insert(r[i] + 1); } X.insert(1); mapID; mapID_; int u = 0; for (ll i : X) { u++; ID[i] = u; ID_[u] = i; } interval *M = new interval; M->init(1, u); for (int i = 0; i < n; i++) { int a = ID[l[i]]; int b = ID[r[i]]; if (t[i] == 1) M->q1(a, b); if (t[i] == 2) M->q2(a, b); if (t[i] == 3) M->q3(a, b); cout << ID_[M->MEX()] << "\n"; } } 
 » 2 years ago, # |   +3 aren't NlogN solutions supposed to pass for D ?? Mine got TLE because it uses insert and lower_bound in a set n times ! and I know their complexity is logN http://codeforces.com/contest/817/submission/27808174
•  » » 2 years ago, # ^ |   0 I also have the same problem...Here is my code.
•  » » 2 years ago, # ^ |   0 NlogN solutions were supposed to pass but in your solution the constant factor is large (around 5).In your code the complexity is : Sort — NlogN First loop — 2*NlogN Second loop — 2*NlogN Overall Complexity — 5*NlogN (Worst Case) = 5*(10^6)*(20) = 10^8.And only those O(10^8) solutions pass in 2 sec which are highly optimised. In your case the hidden constant factor of set insertion also affects your code complexity.Other NlogN solution which passed : 27810683 by Kerim.K
 » 2 years ago, # | ← Rev. 2 →   0 I solved Problem C by searching for the first 'Really Big Number' greater than 's' and less than or equal to n by running a loop.I considered the fact that if a number suppose i=25 doesn't satisfy the 'Really Big Number' condition then no number from 20-29 will satisfy the condition and thus I can jump from i=25 to i=30.By following this, if i found the first valid number less than or equal to n then our answer will be 'n-i+1' otherwise '0'. My question is whether my approach is correct or not because i got accepted but i couldn't proved why my approach is correct. Here is my accepted code.
•  » » 2 years ago, # ^ |   +9 Your approach is absolutely correct since you have used binary_search.As you can observe from the value of num-sumD(num), it is always increasing. For num = 1 to 9 : num-sumd(num) = 0 For num = 10 to 19 : num-sumD(num) = 9 For num = 20 to 29 : num-sumD(num) = 18 . . . For num = 999999999999999990 to 999999999999999999(18 times) : num-sumd(num) = 999999999999999872 And since the value of num — sumD(num) is strictly non-decreasing, take the lower limit to be 1, higher to be n + 1 and search for the appropriate num such that for values less than num (num — sumd(num)) is less than s and for values greater than or equal to num (num — sumd(num)) is greater than or equal to s.So your approach is alright. For more clarification you can see my code : 27802867
•  » » » 2 years ago, # ^ |   0 Thank u priyanshupkm
 » 2 years ago, # |   0 #include using namespace std; int main() { long long a,s,q; cin>>a>>s; if(s%9!=0) q=s/9+1; else q=s/9; if (a-10*q>=0) cout<
•  » » 2 years ago, # ^ | ← Rev. 4 →   0 This is for itachi_2016's approach.Try the following test case and you will realize your mistake. 109 91
•  » » » 2 years ago, # ^ |   0 Thank you FazleRahmanEjazi I now understand where I went wrong..
 » 2 years ago, # | ← Rev. 2 →   0 Problem B reminds me of atcoder beginner contest 057 problem D (link). The idea of precomputing a combinations table can be also be used here since the problem is also to count how many ways to swap the last element.My solution: here
 » 2 years ago, # |   0 Can anyone help me with sqrt decomposition solution for 817F - Запросы на MEX (According to editorial its possible).I can't figure how this approach can be used to solve Problem F.
•  » » 2 years ago, # ^ |   +4 It's not much different from the segment tree one. Numbers are also compressed and the queries are the same. You process assigning on a segment and xor of the segment by dividing original array into sqrt blocks, for each block you maintain its sum. Lazy propagation is used too. Just every query works in instead of . We decided not to force participants to use solutions.
•  » » » 2 years ago, # ^ |   0 Lazy propagation in sqrt decomposition? Anyone has some resources for that?
 » 2 years ago, # |   +4 Similar problem as D are : http://practice.geeksforgeeks.org/problems/maximum-of-minimum-for-every-window-size/0http://agc005.contest.atcoder.jp/tasks/agc005_bSame approach can be use in these problem , next smaller , next greater using stack .
 » 2 years ago, # |   0 Can someone please tell why my code is getting WA ??? Link .Thanks in advance !!!
 » 2 years ago, # | ← Rev. 5 →   0 Problem B In the tutorial "Let's also store set of three elements which give minimal product of the array". In c++ how do you calculate the product if all the numbers are greater than 10^9?
 » 2 years ago, # |   0 Problem B In the tutorial "Let's also store set of three elements which give minimal product of the array". In c++ how do you calculate the product if all the numbers are greater than 10^9?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +5 hiwe don't calculate product of three numbersand question is "how many ways are there to choosing three minimal numbers"because minimal numbers give us minimal product
 » 2 years ago, # |   +1 There is also one more solution of problem C.All numbers bigger than s+9*18 and not more than n are really big. So we can check numbers from s to s+9*18 and add max(0, n — s-9*18) to answer. Sorry for my English
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 t = s+10-s%10 while(t-sum(t)
 » 2 years ago, # | ← Rev. 2 →   +12 Problem F in such constraints can also be solved with coordinates compression and bitmasks in obvious way.BTW, it's fastest solution at this moment. (171 ms without fastIO). 27832302
•  » » 2 years ago, # ^ |   0 can you explain your approach . it is diificult to understand from code
•  » » » 2 years ago, # ^ |   +1 Global idea as it is in the editorial: The first two types of queries are translated to "assign value 1 or 0 on a segment" (set the number on some position is either present or not). The third is "for each i in segment [l, r] assign xi to xi^1" (this will inverse the segment as described in statement). Let's store this array of zeros and ones as bitset, it means that each byte of array will represent 8 values in 8 bit. Then you can perform first two queries on 32 values at once as simple assignment of int variable a[i] = 0 or a[i] = -1, and third query as a[i] = ~a[i]. To find the answer after each query you should find first value in array not equal -1 and find first zero bit index in it.
 » 2 years ago, # | ← Rev. 2 →   0 Can anyone explain me D&C solution for D? Because solution with stacks looks awful. I was thinking D&C on contest but couldnt solve it. Edit: got it. this solution helped me http://codeforces.com/contest/817/submission/27832753
 » 2 years ago, # | ← Rev. 2 →   0 Hello,In problem E how do we insert pi in the trie? I didn't get the explantation given by the editorial. What is the criterion of insertion in binary trie?
 » 2 years ago, # |   0 Detailed approach for D???
•  » » 2 years ago, # ^ |   +12 Considering finding the sum of minimum values for all subsegments, the solution tries to know for each index i how many times a[i] will be the answer. If x is the number of subsegments that contain index i and a[i] is the minimum value, then ans[i] = x·a[i]. The final answer will be .For the correctness of the algorithm, if a subsegment have more than one cell with the same value, we will consider the answer to be the leftmost cell.For index i, Let: L[i] be the rightmost index j < i and a[j] ≤ a[i] R[i] be the leftmost index j > i and a[j] < a[i] Clearly, All cells in the range [L[i] + 1, i - 1] have values greater than a[i] and all cells in the range [i, R[i] - 1] have values greater than or equal to a[i]. Now, we can say that index i can be the answer to any subsegment whose startpoint is in the range [L[i] + 1, i] and endpoint is in the range [i, R[i] - 1]. So, ans[i] = (i - L[i])·(R[i] - i)How to compute the array L? Keep a stack with you and go from left to right. The stack is initially empty and will contain indices. Now, we are at index i: If the stack is empty, L[i] =  - 1. If top of the stack is j and a[j] ≤ a[i], then L[i] = j If top of the stack is j and a[j] > a[i], then pop this element and do the same check for the new stack top. If j is popped from the stack, then for k > i, can L[k] = j? The answer is no, because a[j] > a[i] and i is closer to k from j, so if a[i] ≤ a[k], then L[k] = i. Otherwise, a[j] > a[i] > a[k]. That's why we remove j from the stack because it will never be used again.After finding L[i], push i onto the stack.You can compute the array R in a similar way from right to left.
•  » » » 9 months ago, # ^ |   0 Shouldn't the L array be calculated on right of i'th element instead of j < i and similarly for R array , If I'm wrong correct me , you are trying to calculate for each i'th element the no of elements which are lesser than a[i] to its left and right (to whatever position we can extend the left and right boundaries )
•  » » » » 8 months ago, # ^ |   0 The objective is to find, for each index i, the closest element to its left side that is not greater than ai, and similarly to the right side.
 » 2 years ago, # |   0 In editorial of 817A, why did we calclate cntx and cnty?
 » 2 years ago, # |   0 What does cntx and cnty signify?
•  » » 2 years ago, # ^ |   0 These signify the number of moves in x-axis and y-axis respectively to reach dest from source.These are the number of moves to reach the destination from source assuming only one axis at a time, i.e. we can move only in a straight line, or independent of other axis as constrained by the problem.As each move in original situation changes parity from odd -> even -> odd ... we can check if the parity of both are same, apart from checking whether the no. moves are integral or not.
 » 2 years ago, # |   0 Thanks shubham_827.I understood it now.
 » 2 years ago, # |   0 Hi, In problem E, why should we search for the numbers li(xor)pi when count the warriors?Can you give me same problems like this one?Can you give me a Tutorial about xor properties needed in programming contests.Thank you in advance.
 » 2 years ago, # |   0 Can any one tell me why we are doing mod 2 in problem A.
•  » » 2 years ago, # ^ |   +2 hiit is difficult to explain butif there modes in 2 aren't equal then we can't arrive from x1 to x2 and y1 to y2 in the same timeand if there modes in 2 are equal then imagine that:x2 > x1 and y2 > y1 and (abs(x2 — x1)/a) > (abs(y2 — y1)/b)then you can simply do x1 + a, y1 + b and x1 — a, y1 + b k times and you will have(abs(x2 — x1)/a) and (abs(y2 — y1) + b*2k)/band you can chose correct k to get (abs(x2 — x1)/a == abs(y2 — y1)/b + 2*k) because their modes in 2 are equals.for another cases you can do like this.
•  » » 2 years ago, # ^ |   +3 if mod 2 is 1, then we can reach target with odd number of moves. Otherwise, we can reach target with even number of moves. So, the parity (odd/even) must be the same for both horizontal and vertical moves.
•  » » » 2 years ago, # ^ |   0 can you explain the logic of problem D. I have read it many times still it fails to strike me . I understand upto how to calculate left[i] and right[i] after that how he is finding no of segments and rest of solution. please help
•  » » » » 2 years ago, # ^ |   +4 Check this comment
 » 2 years ago, # |   0 Can anyone explain Problem D?? I read the solution many times but not getting it.
•  » » 2 years ago, # ^ |   +4 Check this comment
•  » » » 2 years ago, # ^ |   0 Thanks for the detailed explanation.
 » 2 years ago, # |   0 Is there an online solution for F ?I thought of having a sorted set of ranges . Insertion and deletion can be done in O(qlog(q)) amortised time . But I'm not sure how to implement flipping efficiently .
•  » » 2 years ago, # ^ |   0 You can use Dynamic Segment Tree.I've tried to do it, but got Memory Limit Exceeded. I think my implementation is still not good enough. If you want some idea on how to code, this is my code: 27989735I think that I would receive Accepted if memory limit was higher.
•  » » » 2 years ago, # ^ |   0 Can you please briefly explain your approach.
•  » » » » 2 years ago, # ^ |   +1 Imagine that you will solve this problem with a standard segment tree with range update (10^18 nodes and lazy propagation).The only thing that change in the dynamic segment tree is that you do not declare an static array with size 4 * 10^18, you just create those nodes that you really need to, because there will not exist 10^18 queries.Here is an example, if you do not have any query in range [10^5, 10^10], simply don't create those nodes.And if you want to flip some interval [l, r], just do this: new_value = (r - l + 1) - previous_value; 
 » 2 years ago, # |   0 How is the complexity for B (as per the solution given in editorial) is O(n)? How will you find the 3 smallest no.s in O(n), i.e without sorting( which would take O(nlogn) )?
•  » » 2 years ago, # ^ |   +2 hiyou can save 3 smallest numbers in 3 Variable and save their counteven it isn't necessary to store all numbers.
•  » » » 2 years ago, # ^ |   0 Oh right, my bad thanks
 » 2 years ago, # |   +1 Can someone please tell why my code is getting WA at test 12? Link Thanks in Advance!
•  » » 2 years ago, # ^ |   0 There was overflow in some operations (maybe l * r), here is your code without overflow: 28011406
 » 2 years ago, # |   0 Why does my solution to the problem : 817B: Makes and the product giving TLE in test case 43. Here is my Java solution: https://paste.ubuntu.com/24972497/ Someone Please help.
 » 2 years ago, # |   0 Anyone there who can help me with my previous post. Please help me. Don't know what is the problem with my code. Why my code gives tle in 43th test case.
•  » » 2 years ago, # ^ |   0 I'm not sure but this can probably be Java anti-sort test. Arrays.sort over an array of primitive types uses quicksort and may work in O(n2). Try replacing it either with Collections.sort or with array if Integer values.
 » 2 years ago, # | ← Rev. 2 →   0 I am getting WA on test case 7. Can anyone tell me which case I am missing??? The method I used to solve this problem is almost identical to the editorial... I just put the values L and R+1 in a set and then constructed segment tree from there... Any help is appreciated. :) My Code#include using namespace std; #define mx 200007 struct Q { long long type, l, r; Q(long long type, long long l, long long r) : type(type), l(l), r(r) {} }; long long tree[mx*4], lazy[mx*4]; long long convert[4][4]; void setvalue(long long node, long long type, long long start, long long fin) { if(type==1) { tree[node]=fin-start+1; lazy[node]=1; } if(type==2) { tree[node]=0; lazy[node]=2; } if(type==3) { tree[node]=fin-start+1-tree[node]; lazy[node]=3; } } void handle_lazy(long long node, long long start, long long fin) { long long type = lazy[node]; if(start!=fin) { long long mid = (start+fin)/2; long long left = node*2, right = left+1; long long t1 = convert[lazy[left]][type]; long long t2 = convert[lazy[right]][type]; setvalue(left, t1, start, mid); setvalue(right, t2, mid+1, fin); } lazy[node]=0; } void update(long long node, long long start, long long fin, long long l, long long r, long long type) { if(lazy[node]) handle_lazy(node, start, fin); if(start>r || fin=l && fin<=r) { setvalue(node, type, start, fin); return; } long long mid = (start+fin)/2; long long left = node*2, right = left+1; update(left, start, mid, l, r, type); update(right, mid+1, fin, l, r, type); tree[node]=tree[left]+tree[right]; } long long mex(long long node, long long start, long long fin) { if(lazy[node]) handle_lazy(node, start, fin); if(start==fin) { return start; } long long mid = (start+fin)/2; long long left = node*2, right = left+1; long long lim1 = mid-start+1; long long lim2 = fin-mid; if(tree[left] v; set s; s.insert(1); s.insert((1e18)+1); for(long long i=0; i values(s.begin(), s.end()); long long sz = values.size() - 1; for(long long i=0; i