### awoo's blog

By awoo, history, 18 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
• +50

| Write comment?
 » 18 months ago, # |   +9 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.
•  » » 18 months ago, # ^ |   +4 It's more natural to just binary search the answer 185850639 (I suppose)
•  » » » 18 months ago, # ^ |   0 interesting, could you explain your approach a bit in detail?
•  » » » » 18 months ago, # ^ |   0 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]
•  » » » » » 18 months ago, # ^ | ← Rev. 2 →   0 how do we know when to do h=m-1 or l=m+1
•  » » » » » » 18 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » » 8 months ago, # ^ |   0 so we should check all abs(a[i]-m)my question is in this case what should i do : a[1]-ma[4]-m
•  » » 18 months ago, # ^ | ← Rev. 2 →   +10 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$
 » 18 months ago, # |   0 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?
•  » » 18 months ago, # ^ |   +4 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.
•  » » » 18 months ago, # ^ |   0 I thought the swap was meant for only two elements, thanks.
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   0 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]
•  » » » » » 18 months ago, # ^ |   0 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.
 » 18 months ago, # |   0 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$.
•  » » 18 months ago, # ^ |   +13 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.
•  » » » 18 months ago, # ^ |   0 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? 
•  » » » » 18 months ago, # ^ |   +12 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.
 » 18 months ago, # | ← Rev. 4 →   0 The checker got me wrong answer to have the array which is not in ascending order in question C. Is this a bug? 186207153
 » 18 months ago, # |   0 can someone confirm How many operations can we make in one second in codeforces ?
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 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)
 » 6 months ago, # |   0 1172A- A+B is very easy solution in python 227321207
 » 3 weeks ago, # |   0 The tutorial for D, the conditions are x <= a[i], and x <= (a[i] + a[i + 1]) / 2 so the union isn'ta[i] <= x <= (a[i] + a[i + 1) / 2. It had me confused so I'm writing for anybody that might come across the same thing.