### awoo's blog

By awoo, history, 12 months ago, 1772A - A+B?

Idea: BledDest

Tutorial
Solution (BledDest)

1772B - Matrix Rotation

Idea: BledDest

Tutorial
Solution (BledDest)

1772C - Different Differences

Idea: BledDest

Tutorial
Solution (BledDest)

1772D - Absolute Sorting

Idea: BledDest

Tutorial
Solution (BledDest)

1772E - Permutation Game

Idea: BledDest

Tutorial
Solution (Neon)

1772F - Copy of a Copy of a Copy

Idea: BledDest

Tutorial
Solution (awoo)

1772G - Gaining Rating

Idea: BledDest

Tutorial Tutorial of Codeforces Round 839 (Div. 3) Comments (50)
 » Can anyone help me with question D Absolute Sorting 185861518 where did i gone wrong?
•  » » 12 months ago, # ^ | ← Rev. 2 →   try these may be you will find your bug. 2 2 1 2 2 1 2 2 3 1 2 3 3 1 2 3 Expected output: 0
 » By the way, a more "natural" way to deduce the relations for D (without doing a lot of casework) is to square both sides of the inequality, because if $|x| \leqslant |y| \Rightarrow x^2 \leqslant y^2$. This gives $(a_i - x)^2 \leqslant (a_{i + 1} - x)^2$ for all valid $i$. This implies that $a_i^2 - 2a_ix + x^2 \leqslant a_{i + 1}^2 - 2a_{i + 1}x + x^2 \Rightarrow (a_i^2 - a_{i + 1}^2) - 2(a_i - a_{i + 1})x \leqslant 0 \Rightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \leqslant 0$, and then we can continue in the same way as editorial.
•  » » Thank you, this is also good
•  » » It's more natural to just binary search the answer 185850639 (I suppose)
•  » » » interesting, could you explain your approach a bit in detail?
•  » » » » First, let's denote min(a) as L, max(a) as H and M as (L + H) / 2, it's pointless to look for a solution where x > H or x < L because they will give array of the same (sortness) as H and L. try x = 5, 6 and x = 3, 2 on a = [5, 3, 5] for example, it'll give [0, 2, 0], [1, 3, 1] and [2, 0, 2], [3, 1, 3], respectively. every binary search loop iteration you loop through the array and check for any abs(M — a[i]) < abs(M — a[i — 1]) (which makes the result unsorted obviously), in case we found it we need to prolong the distance between M, a[i] and shorten it between M, a[i — 1] so we updaet H = M — 1 in case a[i] > a[i — 1] or L = M + 1 in case a[i] < a[i — 1]
•  » » » » » 11 months ago, # ^ | ← Rev. 2 →   how do we know when to do h=m-1 or l=m+1
•  » » » » » » 11 months ago, # ^ | ← Rev. 2 →   absolute value means distance so if abs(m-a[i]) < abs(m-a[i-1]) that means m was closer to a[i] than a[i — 1] when it should have been further or equal, so we we make it closer to a[i-1]. if a[i] > a[i — 1] we need to make m smaller by doing h=m-1 and vice versa
•  » » » » » » » Aight . Got it , Thanks. I actually tried doing it by taking l=0 and h=1e9 and it worked , idk why or how but it got accepted.
•  » » » » » » » so we should check all abs(a[i]-m)my question is in this case what should i do : a-ma-m
•  » » » Damnn , thanks for thisss!
•  » » Thanks a lot,I got it!
•  » » 12 months ago, # ^ | ← Rev. 2 →   If you want to do it more natural, you can apply difference of squares identity: $a^2 - b^2 = (a - b)(a + b)$ i.e. $(a_i−x)^2\le(a_{i+1}−x)^2 \Leftrightarrow (a_i−x)^2 - (a_{i+1}−x)^2 \le 0 \Leftrightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \le 0$
 » could not understand if(mn <= mx) cout << mn << endl; this part why we are taking mn<=mx
•  » » So to check if the obtained range is a "possible" range example, if two numbers are 3 and 6, then >=3 and <=6 is a possible range, but >=6 and <=3 is not a possible range. We are checking if 3 < 6
 » I still don't understand the strategy used in Permutation Game. For me at least, the only possible outcome was a tie, because the other player can mess with the correct ordered ones. For example: 1 2 3 5 4 The first one colors 5 1 2 3 B5 4 The second colors any other to not let the first payer win B1 2 3 B5 4 The first color the last element B1 2 3 B5 B4 The second starts to mess the order of elements B5 2 3 B1 B4 And we have at least two elements out of order for player one, and it will require at least two first movements, but for any of them the other player will undo that movement. So what's the strategy?
•  » » You can swap more than two blue elements in one turn. You can reorder them as you want, the only condition is that all red elements stay on their positions.
•  » » » I thought the swap was meant for only two elements, thanks.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   Why cant 2nd player win in [2,3,1] . Why the answer is Tie.first player [2B,3,1]2nd player[2B,3B,1]1st player skips2nd player exchanges [3B,2B,1]
•  » » » » » If the starting configuration is [2,3,1], 1st player wouldn't start by making the 2 blue. The game would go like this:1st player [2,3,1B]2nd player [2B,3,1B]1st player skips2nd player skips1st player skips2nd player skips . . .Neither player can arramge the numbers in their goal orders, and making the 3 blue would allow the opponent to win, so bot players just skip turns and it's a tie.
•  » » » » Me too! I think the problem simply didn't describe this properly. It hints at it, but no example seemed to show this clearly either. It would have been nice to show such a multi-swap, because with that the problem seems simple, without it just confusing.Wait, was that the problem itself? That it was deliberately hard to understand?
 » For Problem G, why can we assume that we require a whole cycle in the reasoning for $x+k(p-m) \geq t_p$? What if $x$ exceeds $t_p$ mid-cycle? Then the number of wins in this particular cycle iteration would be $p+1$ and not $p$.
•  » » The $t_p$ is the rating you need at the start of the cycle to be able to win the $p$-th opponent (i.e. first $p+1$ opponents). If your $x < t_p$ at the start of the cycle — you can't win against the $p$-opponent.
•  » » » can we keep for each i, t[i] = a[i]-i and b[i] = a[i]+1 ? instead of if and else in for loop? 
•  » » » » Nope, suppose array $a = [5, 5, 5, 6]$. Arrays $t = [5, 4, 3, 3]$ and $b = [6, 6, 6, 7]$ don't make any sense.
 » please also post c++ codes
 » i'm new here,anyone could help me in C?,i don't understand what its mean.
•  » » Uh,the meaning of the C question is that two integers marked k and n are given,and you are requested to choose k integers from these integers ranging from 1 to n,then,sort these k integers in ascending order,Thus,an asending array has come into being. Postulate the array is{a1,a2,a3....ak},(a1
•  » » » thanks ! i got a aot from your reply :D
 » My solution for D using Binary Search:I got the idea from this line in the problem:It can be shown that if such an integer x exists, there is at least one such integer between 0 and 10^9.Initially, left = 0, right = 10^9 and x will be our mid, for any x the array should satisfy |a[i]-x| > |a[i-1]-x| for all i (0 <= i < n), if it doesn't, note that |a[i]-x| > |a[i-1]-x| means that x should be closer to a[i-1] than to a[i], so for any x that does not satisfy |a[i]-x| > |a[i-1]-x| we have 2 cases: a[i-1] > a[i] then to move x closer to a[i-1] we should increase x i.e. left = x+1 a[i-1] < a[i] then we should decrease x i.e. right = x-1 My Submission, complexity: O(nlog(10^9)) per testcase
•  » » Nice observations. If we took x closer to a[i-1] in the case of a[i-1] < a[i] then it goes away from a[i] and maximizes the value of |a[i]-x|. Can you say how to observe these types of questions During the contest, I was trying to observe some kind of pattern and failed . Thanks :)
 » 12 months ago, # | ← Rev. 3 →   Here are some testcases for G 1 4 2 10 2 2 2 15 Ans: 14 1 3 1 100000000 1 2 1000000000 Ans: 299999993 1 3 1 1000000000 1 2 10000000000 Ans: 2999999993 1 4 8 15 2 2 2 20 Ans: 11 1 4 5 13 2 2 2 10 Ans: 10 1 4 5 18 2 3 7 10 Ans: 15 1 5 4 17 4 5 6 15 15 Ans: 45 1 5 8 20 4 5 6 15 100 Ans: 32 
 » variety-jonascan you add test case suite to problem G ?
 » 12 months ago, # | ← Rev. 4 →   The checker got me wrong answer to have the array which is not in ascending order in question C. Is this a bug? 186207153
•  » » Here, fixed it for you.https://codeforces.com/contest/1772/submission/186978335The logic was pretty much spot on. The only problem was in your 2nd while loop. In case the calculated cnt is bigger than a, your code would simply print more numbers than are asked for. So, I just added a check there.
 » 12 months ago, # | ← Rev. 2 →   In problem D "Thus, take the minimum over the pairs of one type. Take the maximum over the pairs of another type. If two resulting values are contradictory, then there is no answer. Otherwise, any value inside the resulting range of x works." Why should that satisfied ?
 » For problem F, Shouldn't it pass in O(k^2*n*m) time complexity in 2 seconds, as it is O(10^7) operation? My solution 186467598. Can anyone help with this?
 » can someone confirm How many operations can we make in one second in codeforces ?
•  » » 12 months ago, # ^ | ← Rev. 2 →   I have tested cf servers once and it was approximately $3*10^9$ per second for simple operations like memset which is actually enormously fast (blog with the same question)
 » Different Differencescan someone explain me what does it mean to be "We need to find an array [d1,d2,…,dk−1] so that the sum of elements in it is not greater than n−1"?
•  » » 11 months ago, # ^ | ← Rev. 3 →   Let's do some cases and math to understand it. Let $k=n=4$. So $a$ will be $[a_1, a_2, a_3, a_4]$ and $d$ as $[d_1, d_2, d_3]$ or, specifically, $[a_2-a_1, a_3 - a_2, a_4-a_3]$. Start all elements of $d$ in $1$ (which is the minimum possible, since $a_{i+1}> a_{i})$, so $d=[1,1,1]$. Note the sum of $d$ is $3$ which is not greater than $n-1 = 3$. If you were to change $d$ for $d=[2,1,1]\Rightarrow a = [1, 3, 4, 5]$, note that this violates the statement "Construct an increasing array of k integers from 1 to n" because $a_4=5>n$ . Therefore, you can increment elements of an initialized $d = [1, 1, 1]$ such that the sum of it is not greater than $n-1$. Let's do other example with $k=3, n=4$. Now, $a = [a_1, a_2, a_3]$ and $d=[d_1, d_2] = [a_2-a_1, a_3-a_2]$ Initialize $d = [1,1]$ (you know an array $d$ of size $k$ full of 1s is always the minimum possible solution because $a_{i+1} > a_i$ and $k \leq n$). The sum of $d$ is $2$ which is not greater than $n-1=3$, Note this time if you increase one of his elements, i.e., $d=[2,1]$ it actually maintains the condition of the sum ($3$) not being greater that $n-1 = 3$. Between these two possibilities the second one has the maximum possible characteristic which is 2 different elements, while the first one only has 1. So using the second $d\Rightarrow a = [1, 3, 4]$, which is one plausible solution. I hope this was helpful.PD: Math part for deep understanding¿where is coming from this "weird" condition of the sum of $d$ not greater than $n -1$? Well, you can actually take any strict increasing finite sequence such as $a = 1,2,3,4$ or $a = 7,23, 50, 51$ and take the first difference $d$ and see that the last element of the sequence is always greater that the sum of $d$. For the first sequence, $d=1,1,1$ and the sum of it (3) is less than the last element of the sequence (4). For the second one, $d=16,27,1$. Taking the sum (44), it is still less than its last element of (51). Even though you can see this apparently works, you must prove it for all $k\geq 2$Take a finite strict-increasing sequence of $k$ elements $a=[a_1, a_2, a_3, ..., a_k]$. The sum of $d=[a_2-a_1, ..., a_k - a_{k-1}]$ is $\sum_{i=2}^k (a_i - a_{i-1}) = (a_2-a_1) + (a_3-a_2) + \dots + (a_k-a_{k-1})$.Then the statement you want to prove is simply $\sum_{i=2}^k (a_i - a_{i-1}) < a_k$ and this can be proved easily by induction (left to the reader).Therefore, if the sum of $d$ is greater or equal to $a_k$ (or following the tutorial, simply greater than $a_k -1$) there is no finite strict-increasing sequence $a=a_1, ..., a_k$. So, when you are checking for all the possible $d$'s, if the condition is not satisfied then the $d$ that does not satisfy cannot lead to a finite strict-increasing $a = a_1, ..., a_k$, which was exactly what happened in the very first example $k=n=4$ when we tried with $d=[2,1,1]$.
•  » » » Thank you for that brief explanation. I really appreciate your effort in this.
 » Can anyone help me understand the solution for C? It really looks like there are two magic observations, which are key to unlock the solution
 » 11 months ago, # | ← Rev. 3 →   For Problem C, why these outputs are not accepted?1 2 4 7 9 1 2 4 7 11 1 2 3 1 2 4 1 2 3 4 1 2 4 6 1 2 4 7 8 9 10 11 Edit: Got accepted, no worries!
 » 11 months ago, # | ← Rev. 2 →   What's wrong with problem E? For Arrangement of "1 2 4 3" How First Can Win?Optimal Steps — for initial state of 1(R) 2(R) 4(R) 3(R) moves - First Player — R to B for 3, current state 1(R) 2(R) 4(R) 3(B) Second Player — R to B for 1, current state 1(B) 2(R) 4(R) 3(B) First Player — R to B for 4, current state 1(B) 2(R) 4(B) 3(B) Second Player — swap (1, 4), current state 4(B) 2(R) 1(B) 3(B) and keeps going on.The Optimal steps can lead to a tie. Because of we can skip our moves. Am I getting the problem in the wrong way? Can anyone guide me? *NOTE — Many have come to the conclusion that 1st operation of rearranging should be done only if there is an instant win. But Is it really? We can use that operation to let the opponent suffer from winning too right? like I won't win but you won't too.
•  » » Second Player — swap (1, 4), current state 4(B) 2(R) 1(B) 3(B) First Player -- rearrange: 1 2 3 4, win. Players do not just swap the two elements. Each turn, a new permutation is produced. In other words, they are free to change the order of all the blue elements at the same time.
•  » » » Oh! Thanks, man, I misread :3
 » what's wrong with this solution for part C? I'm getting wrong answer in test 2 #include using namespace std; int main() { // Your code goes here; vector g; for(int n=1; n<40; n++) g.push_back(n*(n+1)/2); int t; cin>>t; while(t--){ int k, n; cin>>k>>n; vector ans(k); for(int i=0; i
 » 197560571 whats wrong with this can anyone help