### azberjibiou's blog

By azberjibiou, 4 months ago,

1788A - One and Two

Problem idea: azberjibiou

Tutorial

1788B - Sum of Two Numbers

Problem idea: azberjibiou

Tutorial

1788C - Matching Numbers

Problem idea: azberjibiou

Tutorial

1788D - Moving Dots

Problem idea: azberjibiou

Tutorial

1788E - Sum Over Zero

Problem idea: azberjibiou

Problem solver: YeongTree

Tutorial

1788F - XOR, Tree, and Queries

Problem idea: azberjibiou

Tutorial
• +148

 » 4 months ago, # |   -17 binary searching on B worked
•  » » 4 months ago, # ^ |   +4 do you have the code?
•  » » » 2 months ago, # ^ |   0
•  » » 4 months ago, # ^ |   +4 please share the code !
•  » » » 4 months ago, # ^ |   -7 You can check his code: https://codeforces.com/contest/1788/submission/192954046
•  » » 4 months ago, # ^ |   0 use string properties it is easy
•  » » 4 months ago, # ^ |   -12 Can you prove that the invariant of binary search holds correct mathematically ?
•  » » » 4 months ago, # ^ |   -13 i didn't, but i think its possible
•  » » 4 months ago, # ^ |   -12 Lol, I was thinking of binary search, but didn't thought it would work awesome man.
•  » » 3 months ago, # ^ |   0 I speculate that you were just lucky that your binary search (192900488) worked.For binary search to reliably work, your data must be sorted by the search key (which is not the case for this problem).There is this sentence in the tutorial: A solution that randomly finds (x,y) passes. My first guess is that your solution were lucky enough to pass due to the same reason a random search would pass :)There is an interesting exercise, by the way: could you find a counter example for your solution (some test case which were absent in system tests but which would break your solution).
•  » » » 2 months ago, # ^ |   0 i thought a lot but couldnt find any such test cases? i would really appreciaite if there are any.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Hmm... now I could not find myself any $n$ for which the submission would not work. I can not explain why it works for this problem. Strictly speaking, the submission implements some algorithm which is similar to binary searches but which is not a binary search. That means that reasoning we usually use for analysing a binary search could be invalid. Example for n=1999:l/mid/r: 0 999 1999 (width=2000) (n-mid) = 1000, (x-y) = 26 l/mid/r: 0 500 1000 (width=1001) (n-mid) = 1499, (x-y) = -18 l/mid/r: 499 749 1000 (width=502) (n-mid) = 1250, (x-y) = 12 l/mid/r: 499 624 750 (width=252) (n-mid) = 1375, (x-y) = -4 l/mid/r: 623 686 750 (width=128) (n-mid) = 1313, (x-y) = 12 l/mid/r: 623 655 687 (width=65) (n-mid) = 1344, (x-y) = 4 l/mid/r: 623 639 656 (width=34) (n-mid) = 1360, (x-y) = 8 l/mid/r: 623 631 640 (width=18) (n-mid) = 1368, (x-y) = -8 l/mid/r: 630 635 640 (width=11) (n-mid) = 1364, (x-y) = 0 1999: 635 1364 In what ways it differs from a binary search: the search range is not divided in half on each step (note width=11 after width=18) it's not obvious that the algorithm must converge with a necessity: abs(x-y) does not get smaller on each step (note (x-y)=12 after (x-y)=-4)
 » 4 months ago, # |   0 can anyone please explain problem A,
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 you need to find the position k that divides the array in a way that the product of elements from the start until element in position k = the product of all elements after this position k
•  » » » 4 months ago, # ^ |   0 why prefix and suffix arrays for storing the multiplication will not work for problem A ?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Because the maximum possible product is 2^1000 and there is not in C++ any data type that can store that value, actually when n equals to 65 and each element in A is equal to 2, the prefix, suffix idea fails
•  » » » » » 4 months ago, # ^ |   0 thanks for the clarification ! got it !
•  » » » » 4 months ago, # ^ |   0 Python will work here , because python can calculate till pow(2,14284) and we need 1000 only.
•  » » » » 4 months ago, # ^ |   0 i don't use prefix multiply, i only use same hint like that. let's call dp[i]=d[i-1]+(a[i]==2), then you find position i that dp[i]=dp[n]-dp[i], you can do it in O(N).
•  » » 4 months ago, # ^ | ← Rev. 2 →   +5 Array only consists of 1 and 2, you can notice that multiplying by 1 does nothing, so we count the number of 2's in the array, to divide the array into two equal parts, there must be an equal number of twos on each part, using a second variable we can loop from N to 2 and check if the array value is 2, if it is, we add 1 to the current variable, and subtract 1 from the original count, when 2 variables are equal, means we can create equal parts by splitting the array at current position
•  » » » 4 months ago, # ^ |   0 Could you please tell me why my code is giving wrong answer instead of counting number of two's I just make prefix and suffix array of multiplication My submission
•  » » » » 4 months ago, # ^ |   0 Its because of the constraints where n=1000. Take the worst case where all are 2 then in the suffix you will have to evaluate 2^1000 which will give TLE.
•  » » » » » 4 months ago, # ^ |   0 okk I undestand Thanks
•  » » » » » 4 months ago, # ^ |   +6 2^1000 will not give TLE. TLE means time limit exceeded. Instead, it will overflow and give WA — wrong answer.
•  » » » 4 months ago, # ^ |   0 I tried to solve this problem in the hard way, but I don't know why it failed on the middle of the test 2. Could you please check my submission here: https://codeforces.com/contest/1788/submission/192980945
•  » » » » 4 months ago, # ^ |   0 Its because of the constraints where n=1000. Take the worst case where all are 2 then in the suffix you will have to evaluate 2^1000 which will give TLE.
•  » » 4 months ago, # ^ |   +8 in the multiplication, only 2 matters. So you need to divide the array such that number of 2's on left part is equal to number of 2's on right part.
•  » » 4 months ago, # ^ |   0 Count the number of twos in the given array and store it in variable two. If the number of twos is odd, then the output will be -1; If the number of tows is 0, that means the output is 1. Otherwise, run a loop until you find the number of two/2 th 2. Once you find that, break the loop. Index of two/2 th 2 is the output in that case. Check this solution.192969686
•  » » » 4 months ago, # ^ |   0 Can you explain the last step in which you did count = two/2; I didn't get that part ?
 » 4 months ago, # |   0 Can I get some help with debugging ? I have implemented exactly same approach as mentioned in the editorial. During contest I got 2 WA :( ... CAN"T figure out what is wrong...
•  » » 4 months ago, # ^ |   +3 I found the error in my code. I made very stupid mistake... Got AC with single line change :( https://codeforces.com/contest/1788/submission/192977880wish I could spot error during contest.
 » 4 months ago, # |   0 I didn't understand the part of taking m = (n-1)/2 and how he choses the pairs in prb C. can anyone explain it plz
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 check out this submission you will understand https://codeforces.com/contest/1788/submission/193067198
 » 4 months ago, # |   0 Any One has code for problem B, I tried binary search it's not working...
•  » » 4 months ago, # ^ |   0
•  » » » 4 months ago, # ^ |   0 Every thing is Nice, But how do you know that we can skip the whole series if the number is not present at (l+r)/2 i.e. abs(f(mid) — f(n — mid)) <= 1, and move to further new l+r/2 which is Log(n); of whole series i think.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Spoiler
•  » » 4 months ago, # ^ |   0
 » 4 months ago, # | ← Rev. 2 →   +8 Tutorial for Problem B: Hint 1Think in term of digits Hint 2Can we divide each digit by 2 and then assign in the two numbers. SolutionLet a and b be empty arrays , from which we form number a1 and b1 later.Traverse from the least significant digit ,Divide each digit by 2 ,now two cases arise : Case1: Digit is even, Then simply push digit/2 in a and b.Case2: Digit is odd ,As We have to maintain the sum of digits of a and b equal to 0 or 1 ,so if there are multiple odd digits then we have to maintain a flag such that we can push (digit+1)/2 and (digit)/2 alternatively in number a and b.for eg .n= 134we traverse the number in the way 431 :initially a={ } b={ } FOR digit 4 , a={2} b={2} 4/2=2 (case of even digit)For digit 3 , a={2,2} b={2,1} as (3+1)/2=2 and (3/2)=1 (case of odd digit).for digit 1 a={2,2,0} b={2,1,1} as we have already push for an odd number in a then this time we will push (digit+1)/2 in b.So final number formed from a is a1=220 and from b is b1= 211 (i am assuming you may know how to form a number from given digits.)mycode . Note : this is one of the approach ,there can be multiple optimized approaches.apologize for my shit English.
•  » » 4 months ago, # ^ |   0 thanks!!
 » 4 months ago, # |   0 NlogXlogN with DSU passes in 2140msimho, giving this as final task of a 6-round 2-hour D2 is rough...https://codeforces.com/contest/1788/submission/192975706
 » 4 months ago, # | ← Rev. 2 →   +97 C, D and F are great problems. I think the editorial for C kinda glosses over inspiration for the construction.Here is my construction ideaConsider 14 13 12 11 10 9 8 1 2 3 4 5 6 7 Currently all pairs have equal sums. If I swap the bottom elements of 2 pairs with difference $d$, then the sum of one pair increases by $d$, and the other reduces by $d$. Over here if I am able to get $+d$ and $-d$ for $d$ from $0$ to $3$, it will produce consecutive sums. 14 13 12 11 10 9 8 1 2 3 4 5 6 7 | | | | | | | |__| | | | |________| |_____| Notice that the odd differences are nested within each other, and so are the even differences. Swapping the shown pairs produces. 14 13 12 11 10 9 8 4 3 2 1 7 6 5 This has consecutive sums from $12$ to $18$. Generalising to arbitrary odd $n$ is not difficult.This also makes it trivial to see, that even $n$ is impossible. You can produce any pairing by swapping elements. Each swap will make one pair increase by $x$, and the other decrease by $x$. Let us consider the final solution. Each final pair will be $2n + 1 + x$ for $x$ in some consecutive range, that adds to $0$. This is impossible for an even length range. If there are more positive elements, the range will be positive, and negative otherwise. This is very trivial to check. Therefore even $n$ is impossible.
•  » » 4 months ago, # ^ |   +1 Notice that the odd differences are nested within each other, and so are the even differences. Swapping the shown pairs produces. Wow, this is exactly what I thought about but I couldn't get the last observation of nested swapping for the same parity. It took me the whole round thinking about how to perform swapping in vain.
•  » » 4 months ago, # ^ |   +7 Nice idea, maybe better than my construction idea.Here is my construction idea.For some integer $x$ and $y$, $(x, y), (x+1, y+1), \ldots, (x+k, y+k)$ will give an arithmetic sequence of common difference $2$. Arithmetic sequence from $x_1+y_1$ will cover the even part, and another arithmetic sequence from $x_2+y_2$ will cover the odd part. After some work, you can find $x_1, y_1, x_2, y_2$.
•  » » » 3 months ago, # ^ |   0 Nope, I found your idea much more intuitive than the one mentioned above. I was dead stuck on the problem and knew I was missing something for sure but after reading you comment here, solved it in the next 10 mins.
•  » » 4 months ago, # ^ |   0 Super intuitive solution for C
•  » » 4 months ago, # ^ |   0 Note that n is only possible when (3*n+3) is divisible by 2, can be proved by equalizing the total sum and the sequence sum.
•  » » 4 months ago, # ^ |   0 Nice idea, but I am unable to implement it. Can anyone share the implementation?
•  » » 4 months ago, # ^ |   0 how you were able to construct this idea so fast? Will studying number theory help me with this problem?
•  » » 4 months ago, # ^ | ← Rev. 4 →   0 Hi Everule,I think I have a much simpler construction for this problem. A bit of math will tell you that the smallest sum will be 3(n + 1)/2.Let,S = 3(n + 1)/2Now break up the sequence [1, 2n] in two parts [1, n] and [n + 1, 2n].First pair is (1, S — 1)Second pair is (2, S — 1 + 1)and so on...Just make sure to loop around the first number of the pair in the range [1, n] and second number in the range [n + 1, 2n]. You will generate all sums in the range [S, S + n — 1].Proof left as an exercise for the reader. :)https://codeforces.com/contest/1788/submission/193235034
•  » » » 4 months ago, # ^ |   +11 Adding proof because some people asked for it.Lemma 1: Smallest sum (S) = 3(n + 1)/2 Lemma 2: S - 1 is the middle number, i.e, the ceil(n / 2)th number in the range [n + 1, 2n], so if [n + 1, 2n] had 5 numbers S - 1 would be the 3rd. For example if [n + 1, 2n] was [6, 10], S - 1 would be 8. Terminology: Lets call sums with even difference from S, even sums.Lets call sums with odd differences from S, odd sums.So [S, S + 2, S + 4, S + 6, ...] are even sums.And [S + 1, S + 3, S + 5, ...] are odd sums. Main Proof:We have to make n sums in the range [S, S + n - 1], since according to Lemma 1, smallest sum must be S and we have to make n consecutive sums. So, we have to make ceil(n / 2) even sums and floor(n / 2) odd sums.Visually, we have to make  S S + 1 S + 2 S + 3 ... S + n - 1 ^ ^ ^ ^ ^ even odd even odd even  S + n - 1 will have same parity as S, since n is odd. (This also comes from Lemma 1.) Lets take this as our first pair.[1, S - 1], clearly this makes sum S one of even sum. Next pairs will be -[2, S],[3, S + 1] ....[ceil(n / 2), 2n] This is the key point.The last pair will have [ceil(n / 2), 2n] because of Lemma #2. S - 1 was the middle number and we move till end so the first number in the pair becomes ceil(n / 2).Consequently, we have ceil(n / 2) pairs and the sum of each pair is greater than the previous by 2, so we have generated all the Even Sums.After this we are going to loop around the range [n + 1, 2n] for the second number of the pair.So, next pair will be[ceil(n / 2) + 1, n + 1] The sum will be (n + 1) / 2 + 1 + n + 1 = S + 1. Now if we keep generating subsequent pairs until we reach[n, S - 2], we will have generated all the odd sums starting from S + 1.Both Lemmas can be easily proved with a bit of math.
•  » » 4 months ago, # ^ |   0 I suppose the edi glossed over it because there are a lot of valid constructions.For example mine https://codeforces.com/contest/1788/submission/193410581.I realized all the sums have to be different mod n so if I increase one of the numbers by 1 and decrease the other by 2 it it will always be different mod n.
 » 4 months ago, # | ← Rev. 3 →   0 In problem C you provided one of the possible pairings but how can someone prove it? Or is it just random guesses?
•  » » 3 months ago, # ^ | ← Rev. 4 →   +1 It became obvious for me after I wrote down on paper the pairings (and the sums) by the formula for n=9 (m=4, k=15).
•  » » » 3 months ago, # ^ | ← Rev. 5 →   0 Trying to attach the photo: mivael-cdfr-1788C-n9-example.png
 » 4 months ago, # |   -32 shit contest , constructive force
•  » » 3 weeks ago, # ^ |   0 not shit but hard, atleast for me
 » 4 months ago, # |   0 Was a good Contest, struggled on B for a bit but finally got it. Thanks for the fast tutorial!
 » 4 months ago, # |   +11 Could someone give an explanation on why binary search works for problem B?I've seen submissions like this one 192978163 and can't figure out why it passes.
•  » » 3 months ago, # ^ |   0 My guess is above.
 » 4 months ago, # |   +43 1788E and 1667B are similar
 » 4 months ago, # | ← Rev. 3 →   +3 For B, I brute forced many numbers and eventually found a patternFor even you can just do n / 2, n / 2 For odd you will find answer (n + 1)/2 + x, (n — 1)/2 — x Where x = 4, 49, 499, 4999, ..., 8, 89, 899, 8999, ...Can somebody please prove my solution? #include #define int long long int void solve(){ int n; std::cin >> n; auto f = [&] (int x) { int s = 0; while(x) { s += x % 10; x /= 10; } return s; }; if(std::abs(f(n / 2) - f(n - n / 2)) <= 1) { std::cout << n / 2 << " " << n - n / 2 << "\n"; return; } int i = 4, x = (n + 1) / 2, y = (n - 1) / 2; while(i < n) { if(std::abs(f(x + i) - f(y - i)) <= 1) { std::cout << x + i << " " << y - i << "\n"; return; } i = i * 10 + 9; } i = 8; while(i < n) { if(std::abs(f(x + i) - f(y - i)) <= 1) { std::cout << x + i << " " << y - i << "\n"; return; } i = i * 10 + 9; } } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // ONLINE_JUDGE int t = 1; std::cin >> t; for(int i = 1; i <= t; i++) { solve(); } } 
 » 4 months ago, # |   0 Can anyone explain the pairing part of C?
•  » » 3 months ago, # ^ |   0 Maybe you'll find this useful.
 » 4 months ago, # |   0 https://codeforces.com/contest/1788/submission/192980925Can anyone plz help me why I am getting runtime error on this Java code I have tried different approach on B.
 » 4 months ago, # |   0 Can anyone please tell me what is wrong in my code for question A. Instead of counting 2's I just maintain prefix and suffix array of multiplication My submission
•  » » 4 months ago, # ^ |   0 2^1000 is huge.
 » 4 months ago, # |   0 Can anyone explain me problem B, I am unable to understand it properly.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Process each digit ($d$) separately. Divide the digit in two smaller digits:$a = \lfloor\frac{d}{2}\rfloor$$b = d - a First time when a \ne b, place a to x, b to y.Second time when a \ne b, place a to y, b to x.... Example:1094038 can be represented as (52014 + 1042024):n: 1 0 9 4 0 3 8 (sum of digits: 25)x: 0 0 5 2 0 1 4 (sum of digits: 12)y: 1 0 4 2 0 2 4 (sum of digits: 13)  » 4 months ago, # | 0 Why can't E use the method of binary search monotone stack to realize it •  » » 4 months ago, # ^ | 0 counter-test for your last submission:-1 -1 2 -2 -1 1your solution returns 4 (segment [3, 6]), while the answer is 5 (segments are [1, 3], [5, 6]). •  » » 4 months ago, # ^ | ← Rev. 3 → +19 Here's how alternate solution you said works.Note the recurrence in the official solution: dp_i = \max(dp_{i-1}, \underset{p_k \leq p_i}{\max}(dp_k-k)+i)Solving it with brute-force costs O(n^2) time. But we can solving it in almost linear time with a technique similar to Monotonous Queue.We find that when there's a pair of index (x,y) s.t. dp_x-x  » 4 months ago, # | 0 Could anyone tell me why the following code to solve problem A didn't work? it failed at the middle of the test 2:int leftProduct = 1; int k = -1;for (int i = 0; i < length; i++) { leftProduct *= arr[i]; int rightProduct = 1; for (int j = i+1; j < length; j++) { rightProduct *= arr[j]; } if (leftProduct == rightProduct) { k = i + 1; break; } }printf("%d\n", k);Here is the submission link: https://codeforces.com/contest/1788/submission/192980945 •  » » 4 months ago, # ^ | ← Rev. 2 → 0 You evaluate 2 ^ 1000 in worst case, you must use MOD if you want to handle the results:int MOD = 1e9 + 7;rightProduct = (rightProduct * arr[j]) % MOD; •  » » » 4 months ago, # ^ | 0 Ah, Thanks! I didn't notice that. Can I use MOD in C normally? and does is have Cons (disadvantages)? •  » » » » 4 months ago, # ^ | ← Rev. 2 → 0 As a Gray I don't recommend it unless you know there won't be any collisions given the constraints of the problem or your submission could be hacked or it will just give WA, actually I didn't think about that when I answered you, it works for this problem because the constraints are smallYou can use Mod in C. •  » » 4 months ago, # ^ | 0 same approach i used it failed on tc2 also https://codeforces.com/contest/1788/submission/192882231  » 4 months ago, # | ← Rev. 2 → 0 In E, what does it mean to "use coordinate compression on p_i" where p is the prefix sum array of a ? •  » » 4 months ago, # ^ | ← Rev. 2 → +3 precompute all the possible prefixes of the given array and then map them to the range 0 — k-1 based on their relative values (k is the number of unique prefixes). eg- if the prefixes or -3 4 2 -1 then this will be converted to 0 3 2 1. My Submission •  » » » 4 months ago, # ^ | 0 Makes total sense, thank you !  » 4 months ago, # | 0 Any dp solution for D? •  » » 4 months ago, # ^ | 0 my solution was something like dp[i][j][dir] -> number of collisions if you are standing on the ith index, you chose the jth index before you and the jth index had a direction left/right. •  » » » 4 months ago, # ^ | 0 what would the transitions be? •  » » » » 4 months ago, # ^ | ← Rev. 2 → 0 let K be the first index such that dist[i]-dist[j] <= dist[k]-dist[i] dp[i][j][dir] = dp[i+1][i][right] + ... dp[k-1][i][right] + dp[k][i][left] + ... dp[n-1][i][left] + {2^(n-k) if (dir == right) because for all these subsets we will have a collision point between i and j } My Submission •  » » » » » 4 months ago, # ^ | 0 All right thank you! •  » » » 4 months ago, # ^ | 0 Thank you. Can you clarify a bit more about what do you mean by, you chose the j-th index before you and the j-th index had a direction left/right. But the problem says each dot moves in the direction of the closest dot (different from itself) until it meets another dot. So doesn't it mean each dot has their directions fixed ? •  » » » » 4 months ago, # ^ | 0 I am assuming that There is no element chosen between the j'th and the i'th element The j'th element has its direction fixed ie. either its moving right towards the ith element (which is closest for it), or left (to some other closer element on its left as compared to the ith element, we dont care what that element is, only the direction matters to us). My final answer is the sum of dp[i][[j][right] for all pairs of i and j.If you are thinking that maybe the dp[i][j][left] is not a valid state because j has no closer element on its left w.r.t to i. Then that state will never be calculated in our answer. •  » » » 4 months ago, # ^ | 0 I had a similar sol but couldn't implement it-tons of debugging :(  » 4 months ago, # | 0 Can anyone please explain the condition of excluding the unnecessary dots from the subsets in problem D ?  » 4 months ago, # | 0 in problem D what according to author i will move to right and j will have to move left but while solving we are taking a lower-bound of 2*a[i]-a[j] and not 2*a[i]-a[j]-1, can any one explain where am i wrong •  » » 4 months ago, # ^ | 0 It is because in the question it is mentioned that if its a tie the point will move left so if a point is equal to 2*a[i]-a[j] i will move left instead of right.  » 4 months ago, # | ← Rev. 2 → +8 For problem F, in the formula \bigoplus_{k \in L} p_{r_k} \oplus c, the value of c is the xor-sum of every path from p_{r_k} to every vertex in G_k, right?Then, wouldn't changing the value of p_{r_k} also change the values of p_i for some vertices in G_k? If I understand this correctly, we are getting the initial values of p_i with dfs in each component of G', setting its value to the xor-path from the dfs root to vertex i. So, if r_k is in the middle of the path, the value of p_i would also change.I'm guessing that I'm not understanding that part correctly, where does the constant c comes from? Is that the way to get the initial values of p_i?Thanks. •  » » 4 months ago, # ^ | +3 If you change p_{r_k}, p_i would also change. Here is one example.If G' has 3 vertices, r_k=2 and the edges are (1, 2, 3), (2, 3, 1)$$p_3=p_2 \oplus 1$ and $p_1=p_2 \oplus 3$.Odd degree vertices are $1$ and $3$, so we get $p_1 \oplus p_3 = p_2 \oplus 1 \oplus p_2 \oplus 3 = 2$In this case, $c=2$.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Thanks a lot! I get it now. I should have reviewed that part more thoroughly.
 » 4 months ago, # |   0 For problem E,is there a conclusion that "for dp[i], we solve it greedyly.the answer is the leftmost k which p[k]<=p[i]." it means: dp[i]=min(dp[i-1],dp[j](p[j]<=p[i]&&(∀kp[k]>p[i])));thx.(pls forgive my poor English:-)
 » 4 months ago, # |   0 I think problem B can be solved by Binary search. Maybe tag it for binary search
•  » » 4 months ago, # ^ |   0 Can you prove it?
 » 4 months ago, # | ← Rev. 2 →   0 my solution for B: if n even , result is n/2 and n/2 else we need to assure that the sum of digits of first number and second number differ by at most 1let's say the big number is x1 x2 x3 x4 .. x(i)we count sum=x1+x2+x3+x4 and we give the first number a counter of sum/2 and the second number a counter of (sum/2) or ceil(sum/2) (don't use ceil , use (sum+1)/2) after that we go through the string of the big number and we give the first number the max between (sumForFirst-x(i),0) and we give the second the max between max(sumForSec-restX(i),0)why this works? because we can only use x1+x2+x3+x4 and we will spread them by the digit, so this will work . ( and the addition of first and second number can't mess things up because the maximum digit is 9 --> so there is no carry when we add the two numbers ) this is my submission : https://codeforces.com/contest/1788/submission/193001440
 » 4 months ago, # | ← Rev. 5 →   +1 With how vague the editorial is about finding a matching for C, I'm convinced that it's really just a pattern-finding problem after the initial steps of removing even $n$ from consideration and finding the target sums for odd $n$. Now I don't feel so bad for not being able to solve it.For those who did solve C, can anyone please elaborate on the thought process on how you arrived at a correct matching?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 I didn't participated in the contest, but I solved after . my thought process: proofing if n is even we have no solutionafter that I randomly tested bunch of ways to solve the match, one worked for all(and kinda proofed that it always work for n odd (like the editorial with the m thing), so I coded it . that's really it.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Pattern finding is the case for me. I first tried getting the sum of $(a_1 + b_1)$ with a little bit of math which turned out to be $\frac{(3n + 3)}{2}$ and noticed that from pair $(a_i,b_i)$, we can get to the next sum $(a_{i+1}, b_{i+1})$ with a difference of $1$ by adding $+2$ to $a_i$ and $-1$ to $b_i$. After randomly testing many ways to do the matching, setting $a_1 = 1$ and $b_1 = \frac{(3n+3)}{2} - 1$ worked. I also stress-tested this with a bunch of random test cases to confirm. (I left out some details which you can check in my submission if interested).
 » 4 months ago, # |   0 For B We can divide every digit "n" to two parts n / 2 and n — n / 2. if n is odd, the first time we give the first answer the bigger part, at nxt time we give the bigger part to the second.There is a example: 135246 -> 113123 and 022123
 » 4 months ago, # |   0 In problem C if k is a integer, then how can we gurantee that n pairs always exists such that their sum is consecutive when sorted?
•  » » 3 months ago, # ^ |   0 We could probably prove it by construction. (I did not formally prove that myself but maybe this illustration on paper will help to get the idea in that direction.)
 » 4 months ago, # |   0 can anyone please tell what i am doing wrong, wrong answer on test 2 , 61st numbers differ — expected: '316', found: '71' 193009289
•  » » 4 months ago, # ^ |   +5 You're trying to compute the products, but this would not even fit long long if there are many 2s. If there are 1000 $2$s, the result is $2^{1000}$, which requires around 1000 bits. The long long type only supports 64 bits. Rather than calculate the products directly, I would suggest that you instead keep track of the power of 2 that the product has, i.e., how many 2s were present in this desired product.
•  » » » 4 months ago, # ^ |   0 thank u brother , i solved
 » 4 months ago, # |   +1 Can someone explain the solution of D problem? Thanks in advance
•  » » 4 months ago, # ^ |   +13 Suppose you take a specific subset of $\geq 2$ dots. You can then represent each dot as L or R based on whether it moves left or right, and construct a string of Ls and Rs. String always begins with R and ends with L. The number of distinct stopping coordinates for this subset is equal to the number of instances of the substring "RL" (each R stops at the same place as its next L, and each L stops at the same place as its previous R).Therefore, the objective is to output the sum of the number of RL substrings in ALL possible subsets of size 2. However, this can be rephrased as follows: for each pair of dots $i$ and $j$, count the total number of subsets where dot $i$ and dot $j$ form an RL substring, and output the sum for all pairs.Given $i$ and $j$, when will dot $i$ and dot $j$ form an RL substring? This arises only in a subset for which dot $j$ is the closest dot to dot $i$ (no ties allowed, since $i$ breaks ties by going left, away from $j$) and dot $i$ is the closest dot to dot $j$ (ties allowed, since $j$ breaks ties by going left, towards $i$). To count how many of these there, we can first count the number of dots, excluding $i$ and $j$, such that the presence of these dots will not prevent $i$ and $j$ from moving towards each other. Let $d = x_j - x_i$. Dots with positions $< x_i - d$ are allowed, since $i$ still moves to $j$, and the dots with positions $\geq x_j + d$ are also allowed, since $j$ still moves to $i$. We can count how many such dots there are with two binary searches: one for $x_i - d$ and another for $x_j + d$. If we have $s$ such dots, then there are $2^s$ subsets of these $s$ dots that we can include alongside $i$ and $j$ to generate a subset (of all dots) where $i$ and $j$ form an RL pair. The final output is the sum of $2^s$ for each $(i, j)$ pair, modulo $10^9 + 7$. My submission: 193040606. The pw vector stores the powers of 2 modulo $10^9 + 7$. The variables lsz and rsz denote the number of allowed dots that are left of $i$ and right of $j$ respectively. The way the built-in lower_bound is defined conveniently fits with how ties are handled in this problem.
•  » » » 3 months ago, # ^ |   0 Great Explanation Thanks.
•  » » » 3 weeks ago, # ^ |   0 It looks kind of contribution technique. I understood that nubers of points for a given subset is no of LR transititons LLL..RRRR..LLL..RRR. I was kind of trying to fix i and j as first and last indexex in given subset and i guess it's a deadend i went nowwhere from there
 » 4 months ago, # |   0 Can anyone tell me the Intuition behind the pattern for finding matching pairs given in the editorial (1,3m+3,),(2,3m+4)....so on).
•  » » 3 months ago, # ^ |   0 I found the intuituion after writing down the pairs and the sums for n=9.
 » 4 months ago, # |   0 Please, someone help me to understand the problem A
 » 4 months ago, # | ← Rev. 2 →   0 Why does question B take a brute force approach to the pre-test 1 error, can it provide the data of test 1?
 » 4 months ago, # |   0 What is the output when n = 19, 39,59.... For B.
•  » » 4 months ago, # ^ |   0 14 5 24 15 34 25For 19, 39, 59 respectively but Why??
 » 4 months ago, # |   0 How did they reached to that solution for problem B? Is it just intuition or it came from some kind of theorem, formula etc?
 » 4 months ago, # |   0 Why is binary search working for B?
 » 4 months ago, # |   0 in C can anyone explain i got k = 3*(n+1)/2 now how to generate pairs like k, k+1, k+2----k+n-1 as sum. Why this tutorial hs considered m as n-1/2 how we got.. pls someone clear the doubt
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 If you reorder the proposed sequence of pairs (make the pairs be sorted by their sums), then you get the $k, k+1, k+2, \ldots$ sequence. Sorted:$(m+1,2m+2), (1,3m+3), (m+2,2m+3), (2,3m+4), (m+3,2m+4), \ldots$ Correspondent sums:$3m+3, 3m+4, 3m+5, 3m+6, 3m+7, \ldots$ The first sum is k:$3m+3 = 3\frac{n-1}{2}+3 = 3(\frac{n-1}{2}+1) = \frac{3}{2}(n+1) = k$
 » 4 months ago, # |   -8 https://codeforces.com/contest/1788/submission/192882231 why this approach doesnt work i calculated the product suffix and prefix and when prefix of i == suffix of i+1 i break the loop so why it doesnt work ?
 » 4 months ago, # |   0 I want code.
 » 4 months ago, # | ← Rev. 2 →   0 I did not find the similar approach for C so here it is:Let's pair all numbers at 1..n(left) with numbers from n+1..2n(right).Let's start with 1 and some x, their sum is (x + 1) so for next pair sum should be (x + 2). I can't take 2 as next left number cause then I must take x as right number for sum to be (x + 2). So I take 3 as next left number and x-1 as right number. Next pair will be 5 and x-2 and so on. That's how I construct pair with odd numbers from 1..n: I increase left by 2 and decrease right by 1 to make step=1 in sums of pairs.Then I need to deal with even numbers. After last odd number I need to go to first even number 2. It means I need to decrease left by (last_odd — 2) and increase right by (last_odd — 2) + 1.Then again I increase left by 2 to iterate over even numbers and decrease right by 1 to make step=1 in sums of pairs.To make it all work we need to choose x at the beginning. The most critical part is when we go from last odd number to first even number: we need to increase right by (last_odd — 2) + 1 which is equals to n-1 because last_odd=n. So to not overflow 2n limit we need to have right number as 2n-(n-1)=n+1 at most. Apparently this is the least right number we can get from n+1..2n.So x at the beginning should be (n+1)+(count_odd_numbers_in_1..n — 1)examples: n=31 53 42 6 n=51 83 75 62 104 9 n=71 113 105 97 82 144 136 12 submission 192961794
 » 4 months ago, # |   0 Problem C. Using the formula for the sum of an arithmetic progression, we found that the sum of the first pair is (3n+3)/2. Now how do we restore all pairs? Thank you.
 » 4 months ago, # |   0 Great contest! you can find the video editorials for problem C and D here .hope this helps you! happy coding!
 » 4 months ago, # | ← Rev. 2 →   0 In question D can someone explain me "Now let's solve the problem for subsets. Instead of counting number of adjacent dot that moves toward each other for each subset of dots, we will count the number of subset for each possible 1≤i
•  » » 4 months ago, # ^ |   0 We need to count pair of dots that adjacent to each other amony all subsets, and instead of iterate the subsets, it's eaiser to iterate all pairs of dots that moves toward each other and count how many subsets contain them. (my english is bad, if you still can't understand I don't blame you QAQ)
•  » » » 4 months ago, # ^ | ← Rev. 6 →   0 Yeah, I got it now. I just have to change the order of summation in that double summation.image source: https://youtu.be/HkGdJod75Po
 » 4 months ago, # |   0 Easiest div2 contest so far, yet I got slain by mere problem D :(
 » 4 months ago, # |   0 I have a question about Problem B: Since I need to find 2 numbers, A and B, for the input number N such that, a) A + B = N and b) sumofdigits(A) — sumofdigits(B) is at most 1, could I not just use the approach where I do the following: if N is even, assign N/2 to both A and B; --> ensures that sumofdigits(A) — sumofdigits(B) = 0 if N is odd, assign N/2 to A, and (N/2)+1 to B; --> ensures that sumofdigits(A) — sumofdigits(B) = 1 Could someone please clarify this for me, since I think I misunderstood the question?
•  » » 4 months ago, # ^ |   0 I think you understood the question, but your approach is incorrect. Consider $N = 19$, where $N/2 = 9$ (whose digits sum to 9) and $N/2 + 1 = 10$ (whose digits sum to 1). There are many other edge cases (like if you have consecutive 9s) that this kind of approach would not be suitable.
•  » » » 4 months ago, # ^ |   0 Ah, I see your point. Thank you for your help! :D
 » 4 months ago, # |   0 can someone explain me the the solution for problem EI cant understand how the dp state is defined in the editorial?I tried solving this using recursion with dp but getting TLE on Test 4 Submission Link
 » 4 months ago, # |   0 can anyone explain problem 1788D editorial?
 » 4 months ago, # |   0 video editorial for Chinese：BiliBili
»
4 months ago, # |
0

# include<bits/stdc++.h>

using namespace std; int main(){ int t;cin>>t; while(t--){ int n;cin>>n; if(n%2==0){ cout<<"NO"<<endl; continue; } vector<pair<int,int>> p; cout<<"YES"<<endl; int i=1,j=2*n; while(i<j){ p.push_back({i,j}); i+=2; j--; } i=2; while(i<j){ p.push_back({i,j}); i+=2; j--; } sort(p.begin(),p.end()); for(int i=0;i<p.size();i++){ cout<<p[i].first<<" "<<p[i].second<<endl; } }

}

Ques C) Can anyone tell me what is the error?

 » 4 months ago, # |   +5 Lately I receive a message that my submission 192896600 is same as 192935411.I cheked it and find that his solution to the problem is different from mine.I guess may be comments at the end of the code is the reason why two submissions is thougt as same.In addition, I can give evidence that I used this template before him. mine:188824606 his:189071540[user:KAN][user:MikeMirzayanov][user:azberjibiou]
 » 4 months ago, # |   -13 For competitive programming, seek the light, Of knowledge, hard work and perseverance bright, For in its glow, you'll find a winning path, With endless hours of coding, building strength.Though algorithms may seem complex, so tough, And bug-ridden code will make you frown, Stay true to your dreams, and find a way, And victory shall come to you one day.A love for logic and a curious mind, Are all that's needed, to leave all behind, For coding is an art, with endless rules, That with each win, shall bring greater jewels.So don't despair, when challenges arise, For in them lies the key to your prize, And if you're down, and cannot find your way, Just take a break, then come back to play.For in this game, no player truly loses, For every problem solved, a victory chooses, And so keep pushing, keep trying, don't stop, For the greatest programmer, is the one who never stops.
 » 4 months ago, # | ← Rev. 2 →   0 In problem B, my code passed in a weird way. Can someone help me prove it a little more rigorously?For the case of n being odd, I set p=(n-1)/2 and q=(n+1)/2, and then I keep doing "p+=5" and "q-=5" to get the answer.Here is the link to my code:https://codeforces.com/contest/1788/submission/192988232 I hope someone can help, because I need to perfect my solution.
 » 3 months ago, # |   0 thanks for the editorial. <3
 » 3 months ago, # |   0 Problem B can also be solved with just randomly choosing $x$ until you find good one.