### Nezzar's blog

By Nezzar, history, 8 months ago,

Thanks for joining us today! Here is the editorial for today's problems:

1478A - Nezzar и разноцветные шары

Tutorial
Solution

1478B - Nezzar и счастливые числа

Tutorial
Solution

1478C - Nezzar и симметричный массив

Tutorial
Solution

1477A - Nezzar и доска

Tutorial
Solution

1477B - Nezzar и бинарная строка

Tutorial
Solution

1477C - Nezzar и красивая карта

Tutorial
Solution

1477D - Nezzar и тайные перестановки

Tutorial
Solution

1477E - Nezzar и турнир

Tutorial
Solution

1477F - Nezzar и шоколадные плитки

Tutorial
Solution

• +214

•  » » 8 months ago, # ^ |   0 The intent of the code is obvious to its writers and other experienced participates. No one will know which lines you don’t understand.
•  » » » 8 months ago, # ^ |   +13 Understandable, but it can be quite tricky to understand for beginners, and I would think that the purpose of the editorial would be to help competitors, beginner or advanced. CP code is notorious for being unreadable.
•  » » » » 8 months ago, # ^ | ← Rev. 4 →   +6 Then it would make more sense to make editorial code readable rather than to add comments to unreadable code, but I don't see any readability issues in the code of this particular editorial.
•  » » » » » 8 months ago, # ^ |   +5 Fair enough.
 » 8 months ago, # |   +11 I thought that the problems were really nice. Kudos to all the authors! :)
 » 8 months ago, # |   +44 div1C Furthest PointsPick an arbitrary point, and in each iteration, select the furthest point from previously chosen point among all available points. Indeed, we can prove the correctness by contradiction.what the f**k How did I miss that
•  » » 8 months ago, # ^ |   -16 WHat the fuck!i thought this during contest and thought it is way too simple to be a solution to div1CI should commit suicide
•  » » » 8 months ago, # ^ |   0 Dont even say suicide shit even in saractic way!!!
 » 8 months ago, # |   0 Extremely nice contest! Thank u for your work!
 » 8 months ago, # |   +27 Let $g_0 = \gcd(x_2,x_3,\dots, x_n)$. Should it be "let $g_0 = \gcd(x_2,x_3,\dots,x_{n-1})$"?
•  » » 8 months ago, # ^ |   +9 Thanks! We will fix it later.
•  » » 8 months ago, # ^ |   +9 How can we write $g$ using $g_0$ and $x_n$. And another question is even if we are able to write $g$, how can we generate all multiples of $g$ ?
•  » » » 8 months ago, # ^ |   +11 (0,g) — > (0,g,2g)2*(2g)-g = 3g -> (0,g,2g,3g) 2*(2g)-0 = 4g -> (0,g,2g,3g,4g) ....But with (0,g0,xn) I can't generate g = xn-g0 for example where s=1, t=1
•  » » » » 8 months ago, # ^ |   +1 It's said that $g=sg_0+tx_n$, and there are multiple pairs $(s,t)$. An even $s$ is absolutely existed, so let's regard $s$ as an even one. With $0$, $x_n$, and $g_0$,it's easy to get $\frac{s}{2}g_0$ and $tx_n$, then $g=2\times \frac{s}{2}g_0+tx_n$.
•  » » » » » 8 months ago, # ^ |   +1 Can you please explain why there always exits s that is even? By the way why we can substract x1 for every xi and does not Affect the answer?
•  » » » » » » 8 months ago, # ^ |   +1 I'm so sorry! I made a big mistake in my previous replication, $s$ can be odd! Fortunately, I've already got the true proof. Firstly, it's easily to get $pg_0$ and $qx_n$, $p,q\in\mathbb Z$. If $s$ is even, we can get $g$ with $\frac{s}{2}g_0$ and $tx_n$. If $t$ is even, we can get $g$ with $-\frac{t}{2}x_n$ and $-sg_0$. If $s$ and $t$ are both odd, there must exist $s'=s-\frac{x_n}{g}$ and $t'=t+\frac{g_0}{g}$ also satisfy $g_0s'-x_nt'=g$ by Bézout's Theorem; $s'$ and $t'$ mustn't be both odd since $\frac{x_n}{g}$ and $\frac{g_0}{g}$ are coprime and they mustn't be both even; the problem to construct $g_0s'-x_nt'$ is mentioned before.
•  » » » » » » » 6 months ago, # ^ | ← Rev. 3 →   0 if $\frac{x_n}{g}$ and $\frac{g_0}{g}$ are coprime then how can you say that $s'$ and $t'$ will be of different parity. For example, if $\frac{x_n}{g} = 3$ and $\frac{g_0}{g} = 5$ then $s'$ and $t'$ will be both $even$ provided $s$ and $t$ were both $odd$. But thanks for your explanation, as at least one of them must be $even$.
•  » » » » 7 months ago, # ^ |   0 How can we write 0 on board?
•  » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Dont think of it as zero. Note {a+nb,a+(n+1)b} can be used to make a+(n+2)b as follows $x_{1}+(n+2)g = 2*(x_{1}+(n+1)g) - (x_{1}+ng)$ $\Rightarrow \space we \space have \space all \{ x_{1}+ng \forall n \in Z\} \space using \space \{x_{1}, x_{1}+g \}$Now, if we have g divides k and $\{x_{1},x_{1}+g\} \space generates \space (x_{1}+(k-x_{1}))$thus all we need to do is check if x1+g can be written. Now this x1 does not really matters as it will disappear in most eqations,you can write down yourself and see .In the problem we can write for any x : $x_{i} = x_{1}+(x_{i}-x_{1}) \space and \space operation \space on \space x_{1}+(x_{i}-x_{1}) \space and \space x_{1}+(x_{j}-x_{1}) \space will \space give \space :$ $\\(x_{1}+(V)) , V \space is \space some \space constant$ $so \space just \space remove \space x_{1} \space and \space find \space if \space (x_{2}-x_{1}),(x_{3}-x_{1}),... \space can \space generate \space g$
•  » » » » » » 7 months ago, # ^ |   0 Thank you very much！
 » 8 months ago, # |   +6 Can someone point out a mistake in this code? It gives WA on 10021st token. How is that even possible if total queries are 10000? https://codeforces.com/contest/1478/submission/105762283
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 With q = 10000, test cases t = 9 is also there. So total tokens can be upto 9*10000
•  » » » 8 months ago, # ^ |   +1 and I have no way of getting the case right?
•  » » » » 8 months ago, # ^ |   +1 Try this test case. 1 1 2 89 Expected:YES o/p:NO
•  » » » » 8 months ago, # ^ |   0 it's d = 2, a = 21.21 itself is a lucky number.
•  » » » » » 8 months ago, # ^ |   0 Okay, Got it Thanks. But now I made a solution using unbounded knapsack/ subset sum where I basically used [d, d+10, d+20, ..] as the array to check if a value can be formed using the set. So for d = 2, and set [2,12,22,..] a = 21 cannot be formed right? But my code got accepted. So what is the catch in that? https://codeforces.com/contest/1478/submission/105780118.
•  » » » » » » 8 months ago, # ^ |   0 21 itself has 2 in it. I don't get what you say.
•  » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Doesn't matter got it anyway 21 > 2*10 that's all.
 » 8 months ago, # | ← Rev. 3 →   -8 An alternative solution for Problem Div 2 B — 1478B - Nezzar и счастливые числаFor given d, construct a sequence of elements of length s, that looks like d, d + 10, d + 20, ..., d + (s — 1) * 10  such that d + (s — 1) * 10 is strictly less than d * 10.Observation 1: For a[i] >= d * 10, it's always possible to construct a[i] as sum of lucky numbers. Observation 2: For a[i] < d * 10, it's feasible to brute-force any possibilities of representing a[i] as sum of lucky numbers.
•  » » 8 months ago, # ^ |   0 This is pretty much what I did (a[i] > 100 => yes, else brute-force).So many stupid mistakes trying to get a more clever solution....
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Can you please explain this? Observation 1: For a[i] >= d * 10, it's always possible to construct a[i] as sum of lucky numbers. UPD: Got it.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 mercurist i read your code in problem B , i think use bruteforces of case vec[i] < 10 * d in this way help code run faster instead use dfs bool ok = false; for (int j = 1; j < 10; j++) { if (vec[i] - d * j >= 0 && (vec[i] - d * j) % 10 == 0) { printf("YES\n"); ok = true; break; } } if (!ok) printf("NO\n"); Sorry my poor English.
 » 8 months ago, # |   -40 good but all problem are ad-hocplz in next contests add algorithmic problems
 » 8 months ago, # | ← Rev. 2 →   +12 how to avoid getting stuck on A and B in contests ?UPD : It's genuine question.Do you people get stuck on those problems often and what are the reasons behind that ?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +9 solve them.if you feel like you are not making enough progress on a problem then you can try to solve some other problem and come back to that problem after some time.
•  » » 8 months ago, # ^ |   +122 Start from C
•  » » 8 months ago, # ^ |   +15 Yes, I too get stuck in critical observation type problems. Any help on how to improve on problems like that(B of today's contest for example) is appreciated.
•  » » » 8 months ago, # ^ |   0 Another solution for B Just write down all possible ans :)
•  » » » » 3 months ago, # ^ |   0 :O
•  » » » 8 months ago, # ^ |   0 Just code brute force solution and try to find out the relation(idk atleast that's generally works for me)
•  » » » 8 months ago, # ^ |   0 same here :(
•  » » 8 months ago, # ^ |   0 in some contests, i solved a,b,c in div 2 before, but how is some questions in contests so made that i couldnt solve B on this contest?Sometimes, i get accepted on problems where only 3-4k has solved, on this contest, 8k+ solved B but i couldnt
•  » » 8 months ago, # ^ | ← Rev. 2 →   +2 I used to brick my B quite often a few weeks back. I think you're talking about you are expecting yourself to do those questions quickly but you end up doing it wrong or can't get the idea at all. This is what I did, out of contest, I started practicing two problems from easier ranges(one 800-1200 the other 1300-1500 based on comfort level) and noted the time to solve(try to do it right) whenever I was averaging less than 10 mins in the easier range I increased the rating by 100 for those, same for the harder(1300-1500) ones when the avg. is less than 15. In contest, focus on doing it correctly and don't rush it for the next few contests. You will have a good idea of when you're rushing it as now you know very well how much time you take normally in those problems. It took me 4 to 5 more contests after I started practicing this way to eliminate those bad contests and get to a higher rating range.
 » 8 months ago, # |   0 Really nice problems！Though I miss the final time to submit div2F , which leads to a big loss //(ㄒoㄒ)//
 » 8 months ago, # | ← Rev. 2 →   0 Can any one help? why this is giving wrong on PRETEST 3,I checked on my local ide, its giving the right answer. A submission
•  » » 8 months ago, # ^ |   0 got my mistake
 » 8 months ago, # |   +8 I used bubble sort instead of insertion sorting in Div1C, but it seems that only when I sorted the points by their x-positions could I get accepted. Could you please help me find it out?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +11 105754405105754995The 20000 in the second one doesn't matter.It will still get acceptted when I cange it to n.
 » 8 months ago, # |   +65 Div1 C was quite beautiful, however it was the same as this problem
 » 8 months ago, # |   +92 Randomized approach for D1C(D2F):There is three points, $A,B$ and $C$ on the plane.Of course, the three points form a triangle.(this triangle's area can be $0$)Then, two of $\{A \rightarrow B \rightarrow C\ ,\ A \rightarrow C \rightarrow B\ ,\ B \rightarrow A \rightarrow C\}$ are nice beatmaps.For this reason, the following algorithm will work. $p={p[1],p[2],...,p[N]}$ is a permutation of ${1,2,...,N}$. Shuffle $p$. for i = 3 to N 　for j = i to N 　　swap($p[i]$,$p[j]$) 　　if($p[i-2] \rightarrow p[i-1] \rightarrow p[i]$ is a nice beatmap){break;} Then, What is the probability of find a solution with this algorithm?The answer is $(2/3) \times (8/9) \times (26/27) \times ...$It seems that this value goes $\simeq 0.56$ (at least $n \le 5000$).So, try this algorithm about $\frac{1}{0.56} \simeq 2$ times, then we can find a solution.code : 105753764If there is a hack case, please tell me.As a music gamer, I like this problem!
•  » » 8 months ago, # ^ | ← Rev. 2 →   +33 $\frac{2}{3} \cdot \frac{8}{9} \cdot \dots = \frac{3^1-1}{3^1} \cdot \frac{3^2-1}{3^2} \cdot \dots = \left( 1 - \frac{1}{3^1} \right) \cdot \left( 1 - \frac{1}{3^2} \right) \cdot \dots = \prod\limits_{n=1}^{\infty} \left( 1 - \left( \frac{1}{3} \right)^n \right) = \phi \left( \frac{1}{3} \right)$Indeed, this product converges at $\approx 0.56$. You might want to read on q-Pochhammer symbol, it may act as a good probability estimate if you're not sure how many times to run the randomized solution.
•  » » 8 months ago, # ^ |   +16 Can you elaborate how did you get the answer, i.e. probability?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 If there are $k$ points in a set $S$, the probability that there aren't any point $p$ in $S$ such that $X \rightarrow Y \rightarrow p$ ($X,Y$ are some points) is a good beatmap is $(1/3)^k$ ,thinking about the triangle $\Delta XYp$.Then, the probability is $(1-(1/3)^1) \times (1-(1/3)^2) \times ...$The estimation is very rough, so there maybe some hack case...
•  » » 8 months ago, # ^ |   +16 Actually all of three authors are osu player! :o
•  » » » 8 months ago, # ^ |   +13 I'm also, but I'm an osu! mania player ><(By the way, beatmap(s) or beatsmap(s)...? I always think about this when I want to talk about music games(,or rhythm games, music simulation ...?) in English)
•  » » » » 8 months ago, # ^ |   +13 I think it's "beatmap(s)" according to English version osu.
 » 8 months ago, # |   0 I thought that the problems were really nice. Kudos to all the authors!
 » 8 months ago, # |   +23 In the problem Nezzar and Board, can anyone prove that if we have $[0, x, y]$ written on board, then we can construct $a*x+b*y$? What I was able to prove that we can construct $a*x$ and $b*y$ individually.Thanks
•  » » 8 months ago, # ^ |   0 Can you explain how to get $a*x$ that is any multiple of $x$ if $x$ is written on the board?
•  » » » 8 months ago, # ^ |   +9 I can explain with an example, let's assume we have $[0, x]$ written, we want to construct some $a*x$. Assume $a = 2^z - 2^{j_1} - 2^{j_2} .. - 2^{j_k}$. We can write $a$ in this way using the binary expansion. Now let's take an example and see how to construct it.Let's say we want to make $10*x$, $10 = 2^4 - 2^2 - 2^1$. We can obviously construct $2^b*x$ using $2*x$ repeatedly. Now $(2^4 - 2^2 - 2^1)x = 2*(2^3 - 2^1 - 1)x$, therefore we only want to construct $(2^3 - 2^1 - 1)x$ or $(2*(2^2 - 1) - 1)x$. This means we want to construct $(2^2 - 1)x$. Which can be constructed using $2*x$ and $x$. I hope you got the idea. So in $a = 2^z - 2^{j_1} - 2^{j_2} .. - 2^{j_k}$, divide by $2^{j_k}$ and construct the remaining part which is $2^{z-j_k} - 2^{j_1-j_k} - .. - 2^{j_{k-1} - j_k}$ recursively.
•  » » » » 8 months ago, # ^ |   +4 Ok got it. One easier way would be to inductively generate all multiples of $x$. we can generate $2*x$ by simply using $y=0$. Than if we want to generate an even multiple of $x$, we can simply use the $a/2$ multiple and take $y=0$. for generating odd, eg $5$, we can take $3*x$ and $y=x$. This way we can generate both odd and even mutliples of x.
•  » » » » » 8 months ago, # ^ |   +6 Yeah, could have proved using induction also. Can you think on that $a*x + b*y$ now? If $a$ or $b$ is even then it is easy. The problem that I am facing is when both are odd.
•  » » » » » » 8 months ago, # ^ |   0 Me too, $g0*s-xn*t = g$so just need $s$ is even -> we done.But if $s=1.$ It's hard
•  » » » » » » 8 months ago, # ^ | ← Rev. 2 →   +48 Actually, you don't need to construct the both-odd case:)You can obtain $a$ and $b$ that satisfies $ax + by = \gcd(x, y)$ by extgcd. If both $a$ and $b$ happen to be odd, you can shift those coefficients, so: $(a - y')x + (b + x')y = \gcd(x, y)$ where $x' = \frac{x}{\gcd(x,y)}$ and $y' = \frac{y}{\gcd(x,y)}$.Here $x'$ and $y'$ are coprime, so not both are even. Therefore you get $(a-y')$ and $(b+x')$ that are not both odd.
•  » » » » » » » 8 months ago, # ^ |   0 One of the best proofs ever .. Atleast for me personally. Just wanted to appreciate it.
•  » » » » » » » » 8 months ago, # ^ |   0 Thanks!!
•  » » » » » » » 7 months ago, # ^ |   0 Awesome proof!!!!!!
•  » » » » 8 months ago, # ^ |   0 Can you please explain why this is failing (https://codeforces.com/contest/1478/submission/106189636)
•  » » » » » 8 months ago, # ^ |   0 The sample is itself failing. The logic is also incorrect.
•  » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Can You explain why my logic is wrong, I am taking the GCD as written in the editorial and K should be divisible by GCD of all x's is written in the editorial.
•  » » » » » » » 8 months ago, # ^ |   0 Can you prove why K should be divisible by GCD? Also if it is divisible, how does it guarantee a "YES"? Give a proper mathematical proof.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +21 2x-y is the reflection of y w.r.t x. You can do the following to get all multiple of x: Reflect 0 w.r.t to x and get 2x Reflect x w.r.t to 2x and get 3x Reflect 2x w.r.t 3x and get 4x and so on
•  » » » » 8 months ago, # ^ |   0 This reflection argument is simply perfect.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Can you please explain why this(https://codeforces.com/blog/entry/87294?#comment-754679) does not work for this problem. I tried taking GCD of all numbers and checking if its divisible by K as written in the editorial(https://codeforces.com/contest/1478/submission/106189636) but this gives WA
•  » » 8 months ago, # ^ |   +11 As others have mentioned, the problem reduces to construct $x + y$ from the set $\{0, x, y\}$. Can someone come up with such construction? I've been running a simple program for a few minutes and cannot find it.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   -45 I can prove that it is impossible.All our initial numbers are of the form $(nx+my)$. Where at least n or m is even.Whenever you apply an operation, on $(n_1x+m_1y)$ and $(n_2x+m_2y)$, you get $(2n_1-n_2)$ and $(2m_1-m_2)$. It is easily provable by induction that both of the terms can never be odd.
•  » » » » 8 months ago, # ^ |   +29 Let me challenge red's proof:)You can construct $\gcd(x,y)$ from $\{0, x, y \}$ without creating $x+y$. Once you have $\gcd(x,y)$ in your set together with $0$, you can construct any multiple of it, including $x+y$.We get contradiction with the proof... What's wrong?
•  » » » » » 8 months ago, # ^ |   -31 $x + y$ is not always a multiple of gcd.
•  » » » » » » 8 months ago, # ^ |   0 $Gcd(x,y)$ means it divides both $x$ and $y$. So why will it not divide $x+y$?
•  » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   +3 kekw, yeah, don't know what i meant. The thing is x + y = k * gcd = k1 * x + k2 * y, where one of the coefficients is even.
•  » » » » » 8 months ago, # ^ |   -44 I was just explaining why his code "has been running for a few minutes and cannot find it"So you didn't disprove my proof.
 » 8 months ago, # |   0 For ques B whats wrong with this Maths Approach lets say queried number is N and d is given Now For n to be represented as answer will satisfy this equation i guess N = d*x+ 10*y where x ranges from 1 to 10 because if x>11 than it will club into 10*y example d=8 x=12 now it can be 8*2+10*8;
•  » » 8 months ago, # ^ |   0 ???
•  » » » 8 months ago, # ^ |   0 In which order are you calculating x and y?take 27 = 7*3 + 6 (fail) 6%7 != 027 = 10^1 + 17 (fail) 17%10 != 0
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 d = 8, x = 280 + 28 fail8 + 20 fail16 + 12 fail24 + 4 failtake d = 8, x=10 => 8*0+10^1 fail
 » 8 months ago, # |   0 A kind of stupid question, but in the editorial code for D1C: if (1ll*(x[perm[j]]-x[perm[j-1]])*(x[perm[j-1]]-x[perm[j-2]])+1ll*(y[perm[j]]-y[perm[j-1]])*(y[perm[j-1]]-y[perm[j-2]])>=0) What exactly is that checking?
•  » » 8 months ago, # ^ |   0 inner product of two vectors.
•  » » » 8 months ago, # ^ |   0 Can you explain the correctness of this solution?
•  » » » » 8 months ago, # ^ |   0
 » 8 months ago, # |   0 Can someone point out the bug in this submission for Div. 2's C? The program prints YES for the below test case, while the correct answer is apparently NO... 2 486710859466 486710859466 665228107582 665228107582 The link to my submission: Submission
•  » » 8 months ago, # ^ |   0 How did you overcome the error?
•  » » » 8 months ago, # ^ |   0 The bug was in the below condition: //The Bug: if(total - past_sum <= 0 || total % 2 == 1) {flag = true; break;} //The Correct Condition: if(total - past_sum <= 0 || (total - past_sum) % (i + 1) != 0) {flag = true; break;} 
•  » » » » 8 months ago, # ^ |   0 Yes, I had the same.
 » 8 months ago, # |   0 Check out my explanation of problem C — solution
 » 8 months ago, # | ← Rev. 2 →   0 Thanks for the good contest -_-
 » 8 months ago, # |   +108 Congratz, maroonrk!
 » 8 months ago, # | ← Rev. 4 →   +23 We know there are many weird solutions for Div.1C/Div.2F can get AC when their correctness can't be proved. We had tried our best to construct tests already, but some of them are extremely hard to hack. If you come up with an excellent hack, welcome to share it!UPD:For example, 105780521, created by kzyKT and developed by us.Pick a new base point $O'$ and sort all points by polar angle, then try to check point sequence $[1, \frac n2 + 1, 2, \frac n2 + 2, \dots]$ (and those permutations can be derived by shifting) or something similar if they can be valid answers. This pattern will make acute angels appear frequently.if you can't find answer with the current $O'$, you can try many other $O'$. Some specially chosen $O'$ perform literally excellent, like: $( \frac {\sum x} {n}, \frac {\sum y} {n})$ $(inf, inf)$ $(inf, -inf)$ $(-inf, inf)$ $(-inf, -inf)$ So you will have a high chance to get a valid answer sequence if you check each of these $O'$.We spend a long time hacking this solution, but it seems impossible. :(
•  » » 8 months ago, # ^ |   +67 I tried to hack the following solution:Start sequence from $[1, 2]$, then for $i = 3\dots n$ try to insert $i$ at some place at the sequence so that all angles are $<90$. But it can be proved! Indeed, pair of points $p[j], p[j+1]$ blocks us from inserting point $i$ in at most $1$ position — so at most $i-2$ positions are blocked. However, we have $i$ possible positions where to insert! (So we can insert all the points this way)
•  » » » 8 months ago, # ^ |   0 Yes, it's initial solution when triple_a comes up with this problem.
•  » » 8 months ago, # ^ |   0 I construct sequence [1,n,2,n-1...], and it seems can be hacked easily :(
 » 8 months ago, # | ← Rev. 2 →   +5 Alternative Solution for Div2B without DP 1478B - Nezzar и счастливые числа If ai >= 10d then it is always achievable. Because it is possible to subtract a number with d on the ten's place and any number on the one's place. It is possible to choose the one's place number so that the subtracted result is divisible by d (meaning it can be obtained by the sum of d's).If ai < 10d, it is only possible to subtract d from it. So after each subtraction of d, check if ai is divisible by d or ai is divisible by 10 (meaning k*10 + d can be subtracted). Codedef solve(n, d, lst): for i in lst: if i >= d*10: print("YES") else: val = i get = False while val >= d: val -= d if val % 10 == 0 or val % d == 0: get = True print("YES") break if not get: print("NO") for _ in range(int(input())): # Multicase n, d = list(map(int, input().split())) lst = list(map(int, input().split())) solve(n, d, lst) 
•  » » 8 months ago, # ^ |   0 I got most of your solution but can u explain more about checking if val is divisible by 10 ?
•  » » » 8 months ago, # ^ |   0 For example, if d is 7 and the given number is 54.It is only possible to decrease 10*k+7 (k is number from 0 to 9 ) if it is almost 54 from 54. 54 - 7 = 47 (which not divisible by 7) 47 - 7 = 40 (which is divisible by 10) Now this means it is possible to remove 40 by adding it up with previous 7. So subtract 40 and 7 at once (40 + 7 = 47). 54 - (47) = 7 7 - 7 = 0 
•  » » » » 8 months ago, # ^ |   0 i got it now thanks
•  » » 8 months ago, # ^ |   0 It can be shown that the following is necessary and sufficient:Either $a_i \ge 10d$ or $a_i = 10k + dm$, $m > 0$.
 » 8 months ago, # | ← Rev. 3 →   0 105777562 For Div2C I solved it by getting back the original array a. Basically the same idea as tutorial except one more observation is that d[2n] = 2n*a[n]
•  » » 7 months ago, # ^ |   0 Hello, I tried the same approach as you suggested, but I think that I'm missing something. I looked at the example from the problem statement: 6 240 154 210 162 174 154 186 240 174 186 162 210 We have that d[2n] = 210, 2n = 12 ---> a[n] = 210 / 12 = 17.5 Can you please help me figure out what? Thank you!
•  » » » 7 months ago, # ^ |   0 https://codeforces.com/blog/entry/87394 This blog explains it
•  » » » » 7 months ago, # ^ |   0 Great, very nice explanation, thank you!
 » 8 months ago, # |   0 I like how D had such a clean solution.
 » 8 months ago, # |   0 Problems are good for both beginners like me and also for coders who are excellent in coding. Thank you, CodeForces!
 » 8 months ago, # |   0 Thank you for this editorial and same for the contest tooo!
 » 8 months ago, # |   0 Why k % gcd(x_1, x_2,.., x_n) == 0 won't work in DIV2D/1A? Can someone please explain.
 » 8 months ago, # |   +5 How to prove that it's possible in Div1C to take farthest available point on each step?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +56 You can prove it easily. Let's say you pick $B$ as the farthest point from $A$ . 1) If any point is outside the yellow region, it has to have greater distance from point $A$ than $B$, which is a contradiction. So there are no points outside the yellow region.2) Any point in the yellow region satisfies the condition.
•  » » 8 months ago, # ^ |   +3 Even the insertion sort option doesn't seem so obvious to me since swapping two elements can effect both of the adjacent angles. Can you prove that?
•  » » » 8 months ago, # ^ |   +5 see here
 » 8 months ago, # |   +11 Otherwise, we could subtract x1 for x1,x2,…,xn and k why? :(
•  » » 8 months ago, # ^ |   +14 OK, I guess it's because if we have an initial set {a, b, c} and we want to build k, by subtracting a from everything, nothing changes since every number we can build is also shifted by a. Namely:{a, b, c} with target k, e.g. we can build 2b-c.is equivalent to{a-a, b-a, c-a} with target k-a, e.g. we can build 2(b-a)-(c-a) = (2b-c)-a.
 » 8 months ago, # |   0 DIV 2 (A + B) VIDEO EDITORIAL LINK : https://www.youtube.com/watch?v=amNk203dAGQ
 » 8 months ago, # |   -29 Congrats HealthyUG for surviving RED. Happy to see you giving contest even after becoming red,hoping for top 100 rank from you in future. SpoilerBig fan sir
 » 8 months ago, # |   0 Can someone sketch a proof at Div1C for injection sort?
•  » » 8 months ago, # ^ |   0 see here
 » 8 months ago, # | ← Rev. 2 →   +5 In problem D editorial , how subtracting $x_1$ from all other $x_i$ won't effect the answer i.e how to prove that if $k$ can be formed from $x_1,x_2,x_3$ then $k-x_1$ can also be formed from $0,x_2-x_1,x_3-x_1$?Also can some one explain how we can write down $g$ by applying operation recursively ?
•  » » 8 months ago, # ^ |   +7 For an arbitrary interger $d$, $(2x-y)-d=2(x-d)-(y-d)$. That's why we can subtract $d$ from all the elements (including $k$).From the proof of the editorial, we can get $g_0$ and $x_n$. Let we prove one fact that if we get $x$, we can also get $qx$ for all the intergers $q$. In fact, we can use $x$ and $0$ to make $2*0-x=-x$, so that we can add $2x$ and $-2x$ any times to any one element. (i.e. we can get $2*x-(-z)=z+2x$ and $2*(-x)-(-z)=z-2x$ with $z$) So the fact has already been proved.Then we need to discuss about the parity of $s$ and $t$ such that $g_0s-x_nt=g$. If $s$ and $t$ are both even, we can just add $\pm 2g_0$ and $\pm 2x_n$ to $0$ some times. If one of $s$ and $t$ is odd, suppose that $s$ is odd, we can just add $\pm 2g_0$ and $\pm 2x_n$ to $g_0$ some times. If both of them are odd, we can just change $s$ and $t$ into $s+\frac{x_n}{\gcd(g_0,x_n)}$ and $t-\frac{g_0}{\gcd(g_0,x_n)}$. Because $\gcd(\frac{x_n}{\gcd(g_0,x_n)},\frac{g_0}{\gcd(g_0,x_n)})=1$, they can't be both even and it has already been changed into the situation we have talked about.
•  » » » 8 months ago, # ^ | ← Rev. 3 →   +3 Given $g_0$ and $x_n$, then we can get $g_0 * s$ and $x_n * t$.Now $x_1 = x_n * t$, $x_2 = g_0 * s$, we can subtract $x_1$ from all x. We get $0, g_0 * s - x_n * t = g$. And by induction, we can get $q * g$. Now we add $x_1$ back. Because $x_1$ is divide by $g$, suppose $x_1 = t * g$, so we can get $q * g + t * g$ for all $q$, that is equal to $q * g$.
•  » » » 8 months ago, # ^ |   0 So you proved that $g_0s$ and $-x_nt$ can be made individually using the operations . But how to prove that $g_0s - x_nt$ i.e $g$ can be made ?My major doubt is how Bezout's Theorem used here ? In the editorial it's mentioned that we can make $g_0s$ snd $-x_nt$ but how does that proves that any number divisible by $g$ can be constructed ?
•  » » » » 8 months ago, # ^ |   +3 For example, $g_0 s=5g$ and $x_n t =4g$, now we could apply our operation to get $4g*2-5g = 3g$, and recursively we could finally get $g$, which could generate all possible numbers divisible by $g$.
•  » » » » » 8 months ago, # ^ |   0 Thanks for the example , it cleared my doubt regarding what actually editorial wants to say .I have one more doubt , You have shown for one example that how $g$ can be constructed when $g_0s = 5g$ and $x_nt = 4g$ . How to prove in general that if we can make $g_0s$ and $x_nt$ then we can also make $g$ ?
•  » » » » » » 8 months ago, # ^ |   +11 Note that both $g_0s$ and $x_n t$ are divisible by $g$, and their difference is exactly $g$, therefore we may assume that $g_0s=(m+1)g$ and $x_n t=mg$ for some nonnegative integer $m$, which falls exactly into the same argument.
•  » » » » » » » 8 months ago, # ^ |   0 Thanks a lot . This really helped .
•  » » » » 8 months ago, # ^ |   +3 Please note that we can construct $g_0s+x_nt$ for all intergers $s$ and $t$ according to the proof above.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Or you can argue geometrically. Operation $2x-y$ means "mirroring" number $y$ against the number $x$ because $2x-y = x + (x-y)$ and ($x-y$ is a signed distance between $x$ and $y$). Well, and subtracting some arbitrary number $d$ just means shifting whole set by $d$ to the left or to the right. It's clear that if you can achieve $k$ in the original sequence, you can achieve $k-d$ in the shifted one.
 » 8 months ago, # | ← Rev. 2 →   0 Nezzar Can you please give more mathematical proof for DIV1-C, how can we prove this with contradiction like it feels natural but how to prove this first method you suggested.
•  » » 8 months ago, # ^ |   +18 Consider three points $A$, $B$, $C$.You are in $A$ currently. Assume that the furthest point is $B$, then $C$ is between $A$ and $B$ so $\angle ABC$ is acute; if $\angle ABC$ is not acute, the furthest point from $A$ should be $C$ instead of $B$.
 » 8 months ago, # |   +4 I didn't understand the editorial of 1477A — Nezzar and Board Can someone please explain the editorial?
•  » » 8 months ago, # ^ |   +22 I also struggled to understand it. Here's my detailed understanding:(1) Note that if you had zero available and another number $a$, then you can build every multiple (positive and negative) of $a$. For example, from $(0, a)$ you can get $-a$ and from $(-a, a)$ you can get $3a$ and so on.(2) Note that shifting all numbers $x_i$ and $k$ by the same amount, does not change the answer. If you had numbers $x_0$, $x_1$ and $x_2$ and you wanted to obtain $k$, you could subtract $x_0$ from everything and every number obtained from this new process is also shifted by $x_0$. For example, you would get $x_0-x_0=0$, $x_1-x_0$, $x_2-x_0$ and $k-x_0$ and if you combined $x_1-x_0$ and $x_2-x_0$, you would end up with $2(x_1-x_0) - (x_2-x_0) = (2x_1-x_2)-x_0$.(3) Note that since you can get 0 by shifting the input and you can get the multiples of all the remaining numbers, you can basically get every number of the form $u(x_i-x_0) + v(x_j-x_0)$, which is another way of saying that you can get every multiple of $gcd(x_1-x_0, x_2-x_0, ...)$, and nothing else. (See Bézout's identity).(4) Finally, using the previous observations, if $k-x_0$ is a multiple of $gcd(x_1-x_0, x_2-x_0, ...)$ then the answer is "YES". Otherwise, it is "NO".Sample Solution: 105781653
•  » » » 8 months ago, # ^ |   +15 Can you prove point (3)? Given [0, x, y], try to construct x+y.
•  » » » » 8 months ago, # ^ |   0 if and y are coprime for ex - {0,3,5} then if we have to calculate 8, then 2*x -y = 8; Lets take x = 5, so y would be equal to 2, 2 can be made via, 3*2-5 =1 1*2 -0 = 2 we got 2, hence 8 can be madeand similarly for when x and y are not coprime.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 It is impossible, does this mean that the editorial is wrong?
•  » » » » » 8 months ago, # ^ |   +3
•  » » » 8 months ago, # ^ |   0 ok, we can write down $g_0, g_0s, x_nt$. Explain please, how we can write down $g_0s-x_nt$? if s is even, i understand, but if not
•  » » » » 8 months ago, # ^ |   0 Let's say we want to get $x_{n}t$ and we have $t = 13$. Our operation is $2a - b$. We can set $a = 4x_n, b = x_n$, so it becomes $8x_n - x_n = 7x_n$. And then we set $a = 7x_n$ which we got before, and $b = x_n$, and it becomes $14x_n - x_n = 13x_n$. And of course, we can get any $kx$ being $k = (2^{exp})$ if we set $a = \frac{k}{2}x$ and $b = x_1$ (remember $x_1 = 0$ because of the shifting). That is to say, we can get $2x$ with $x$ and $0$, $4x$ with $2x$ and $0$, and so on.
•  » » » » » 8 months ago, # ^ |   0 i understand how to get $kx$ from $(0, x)$, if we have ((k-2)x, (k-1)x) then $2*(k-1)x - (k-2)x = kx$. Ok we got $g_0s, x_nt$, what we should do to get $g_0s - x_nt$?
•  » » » » » » 8 months ago, # ^ | ← Rev. 4 →   0 Bézout's theorem states that there exists $x$ and $y$ so that $ax + by = gcd(a,b)$. So you can say having $g_0s-x_nt$ that there exists $s$ and $t$ such that it equals $gcd(g_0,x_n)$. Note that you only need to say if it's possible, not how would you get the number on the board. So once you get $g = gcd(g_0,x_n)$ (I call it $g$ to be consistent with the naming in the editorial, as $g_0 = gcd(x_2,x_3,x_4,\dots,x_{n-1})$) by some amount of operations on the board, it means $k$ has to be a multiple of $g$ to be possible to write in the board, and you would do it the same way you got all other gcds before. So that's why at the end we check if $k \equiv 0 \pmod{g}$.
•  » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Note that you only need to say if it's possible, not how would you get the number on the board.we need prove it. By induction we got $g_0$,now we need get $g$. by Bézout's theorem states there're exist $s, t$ such that $g_0s - x_nt = g$, but why we can get $g$, using operatin $2x-y$ and some numbers already written down on board like $0, x_2, \dots , x_n-1,x_n, g$, previosly found gcd's and something else.
•  » » » » » » » » 8 months ago, # ^ |   0 The editorial describes the process where you get to $g_0$ as "recursive". And as I far as I understand and was mentioned in the comments, it means first you had to get $x_2s-x_3t = gcd(x_2,x_3)$ on the board first, let's call it $v_1$. Then you got $v_2 = v_1s - x_4t = gcd(v_1,x_4)$, then $v_3 = v_2s - x_5t = gcd(v_2,x_5)$ and so on. With that method you got to the last step where in the same way you get to write $g$ on the board. Therefore, if $k$ is equal to $g$ or some multiple of it, it can be written on the board.Also, thinking it logically, it makes sense. If all numbers previously written are multiple of some number, multiplying them by two and subtracting another of the numbers in an operation, means you'll never have a way to write some number which is not multiple of it. That's even what's in part described in the first direction of the proof in the editorial.About making a really formal proof, I'm not used to making them, so unfortunately I'm unable to come up with one. But based on what's said in the editorial, what was commented by other people and with my logic, seems to work for me. If you still feel unconvinced of the correctness of the solution, you can try to prove it by yourself, try solving as many cases as you want to get to a conclusion. After all, I think it's pretty rare to be proving some solution during a contest, and it always depends more if you are convinced of a solution. Of course I'm also trusting that the authors have made all the possible things they could to be sure of the correctness of the solution. But nevertheless if you find some way it doesn't work, you can always point it out.
•  » » » » » » » » » 8 months ago, # ^ |   0 omg, it's common words about why this solution correct. I believe that it's correct, but me need a prove of correctness, only one part of it i don't understand. In induction we need to strictly prove base case and jump from $n$ to $n+1$, it does not matter that we assumed until $n$ we wrote down other gcd's not clear how.
•  » » » » » » » 8 months ago, # ^ |   0 $g$ should be written down on the board, then we can write down k
•  » » » 8 months ago, # ^ |   0 Great explanation thank you.
•  » » » 8 months ago, # ^ |   0 Thanks a lot kirjuri. Now I am able to understand the problem.
•  » » » 8 months ago, # ^ |   0 This is one of the explanation, I could understand better Thanks, buddy
•  » » » 7 months ago, # ^ |   +1 This is so much better than the editorial's explanation.
 » 8 months ago, # | ← Rev. 2 →   +19 Nezzar For F, it looks like the coefficient of $x^{k-1}$ in $Q_j$ should have $1/(k-1)!$ instead of $1/k!$.
•  » » 8 months ago, # ^ |   0 Thanks! it is fixed now.
 » 8 months ago, # |   0 Can someone explain me Div2D/Div1A? I don't get the intution behind the solution in editorial.
 » 8 months ago, # |   0 Missed the part in DIV2C that integers of the array will be distinct. smh.Can it be solved if elements of the array were not distinct?Like, $d[] = 16, 16, 16, 18, 20, 22, 22, 26$here, $a[] = 1, -1, -1, 2, -2, 3, 3, -3$
•  » » 8 months ago, # ^ |   0 Please read the statement, array a[] should contain distinct numbers.
•  » » » 8 months ago, # ^ |   0 Yes. I'm just asking if the elements were not distinct could it be solved.
•  » » » » 8 months ago, # ^ |   +1 I think it technically can be solved but the code will be extremely diffcult to write or read.
•  » » » » » 8 months ago, # ^ |   0 Hey Nanako, check this. For it to be solved with non distinct elements, the statement should be modified as freq(0) is multiple of 2 and freq(i) should be equal to freq(-i) for each i in the A. Then, it would make sense.
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 can you please tell me what the array $a$ will be for the following case? $d = [4,4,4,4]$ why the elements of $d$ shouldn't be distinct? UPD : I just found out my mistake.sorry!
 » 8 months ago, # | ← Rev. 2 →   0 Div2D, what is the meaning of sentence "(Otherwise, we could subtract x1 for x1,x2,…,xn and k)"?We can somehow transform x1 to 0, if yes, how?
•  » » 8 months ago, # ^ |   0 You can imagine that he moves base point $O$ from $x = 0$ to $x = x_1$ in $x$-axis.
•  » » » 8 months ago, # ^ |   0
•  » » » » 8 months ago, # ^ |   0 The answer depends on the relative positions of $x[]$ and $k$ instead of the absolute positions, so substracting $x_1$ from all elements at the same time won't change the answer, then we get $x_1=0$.
•  » » » » » 8 months ago, # ^ |   +3 can you please explain the last line of editorial of Div2 D , Therefore, we could write down $g$ applying operation recursively. I didn't understood how to do that.
•  » » » » » » 8 months ago, # ^ |   0 According to the editorial you can write down gcd of two numbers. "recursively" means then you can write down gcd of three numbers (by using the previous gcd and another number), and then gcd of more numbers, until gcd of $n$ numbers.
•  » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Isn't that saying that because we can make $g_0$ and $x_nt$ and thus we can some how make $g_0s-x_nt = g$ by applying the operations ?In second part of proof we need to show that any number divisible by $g$ can be written down . If we show that $g$ can be written down then it's obvious that anything divisible by $g$ can written down by taking $y=0$ .
•  » » » » » » » » 8 months ago, # ^ |   +3 I think it means the same if you understand how to write down gcd of two numbers. The difference is, my explanation is from gcd of two numbers to gcd of n numbers, editorial is from gcd of n numbers to gcd of two numbers (cuz it's induction).
•  » » » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Ok , so you mean that because for $n=2$ our statement holds , thus we can say that $g$ can be created out of $g_0$ and $x_nt$ . And thus we can say that all number divisible by $g$ can be created .So in last part of proof , we are using the fact for $n=2$.
•  » » » » » » » » » 8 months ago, # ^ |   0 Editorial derive $g$ from $g_0$ and $x_n$, and you can also imagine, before that, you derive $g_0$ from ${g_0}_0=\gcd(x_2,\dots,x_{n-2})$ and $x_{n-1}$. Keep similar operation then you will realize the whole process is all correct.I can't really get what makes you confused. Maybe learning "What is Induction" would help you.
•  » » 8 months ago, # ^ |   0 "substract x1 from x1,x2,...,xn and k"
•  » » » 8 months ago, # ^ |   0 Lets say we have three numbers a, b, c. How can we construct 0 from them, by using that operation 2x-y?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +9 You convert $(x_1, x_2, x_3, k)$ into $(0, x_2 - x_1, x_3 - x_1, k - x_1)$. They are equivalent because $2(a - x_1) - (b - x_1) = (2a - b) - x_1$
•  » » 8 months ago, # ^ |   +8 You can see that any solution in the transformed set is a solution in the original set because $2x - y$ is the reflection of $y$ over $x$, and these reflections are invariant to shifts such as in the transformed set.
•  » » » 8 months ago, # ^ |   +1 omg, I thank you all for trying to explain ;) But such sentence with another 3 or 5 new terms is not helpful.I understood that for some reason we can shift all numbers by any amount, and for another reason we do shift by x1, so we transform that element to 0.Then, for some reason, we can directly use the gcd() of the remaining numbers to check if k is a multiple of it, which determines ans.
•  » » » » 8 months ago, # ^ |   +4 Try picking a couple $x$ and $y$ pairs and draw them in the number line, along with $2x−y$. Try to find a pattern there, it might be useful to get an intuition to why we can find a solution using the numbers with a fixed offset.The reason we want one element to be $0$ is because then we can use it allows us to construct some more predictable and useful numbers. For example if we do the operation $2x−y$ with $x=0$, the result is $−y$, and if we do it with $y=0$ the result is $2x$, see some discussions above to more details on why this will help solve the problem. Also we can shift by any other number, not necessarily $x_1$.The argument for the gcd I still have not figured it out. This editorial is pretty obscure (not surprising, sadly).
•  » » » » 8 months ago, # ^ |   +1 Operation we apply : $2x - y$ . Suppose we subtract $x_1$ from $x$ and $y$. Then $2*(x-x_1) - (y-x_1) = 2*x-y-x_1$ . So you can see that final answer is subtracted by $x_1$.Thus converting to $k$ from $x$ and $y$ is same as converting to $k-x_1$ from $x-x_1$ and $y-y_1$.I showed for only one operation but it's not hard to see for multiple operations.
 » 8 months ago, # |   0 1477B - Nezzar и бинарная строка can be solved without a segment tree. The idea is to keep subarrays with equal digits in a set. The complexity of the operations for each move is $O(\log(n))$ amortized.AC submission: 105757658
•  » » 8 months ago, # ^ |   +3 You are right! Because of 896C - Уильям, Ктолли и Сениориус some people would like to call it "Chtholly Tree". :)
•  » » » 8 months ago, # ^ |   0 I think my solution is deterministic: for each query, I add up to $3$ new intervals and I remove all the intervals I visit. Hence, I visit $n + 3q$ intervals in the worst case.
 » 8 months ago, # |   0 105785851 Why does this brute force sol work for div2 B? Shouldn't it give a TLE in the worst case?
•  » » 8 months ago, # ^ |   0 Many numbers contain $d$ so it won't spend too much time finding a valid answer. I think this sol is also a correct sol.
 » 8 months ago, # |   +1 problem D editorial proves the solution but doesn't gives any intuition behind coming up with the solution . Can some one tell their lane of thought which brought them to the solution ?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +6 I can offer my thinking process in this problem.Noticed that $2x-y=x+(x-y)$, so actually for a $x$ we can move it to $x + k \cdot dis(x, y)$ for any $k$ and available $y$. Then according to Bézout's Theorem, I found that $x$ can be moved to any $x + k \cdot \gcd(dis(x, others))$.A fun observation is, in $2x-y$, coefficients are $2,-1$ and the sum of them is $1$. Actually, I think it seems impossiable to solve if we change it to $3x-y$, but $3x-2y$ or $3x-y-z$ or something seems much more solvable. I can't explain it well because my English suck, sorry.
•  » » » 7 months ago, # ^ | ← Rev. 4 →   0 Hey NanakoI found that X can be moved to any X+K*gcd(dis(X,others)).how you found that!?What if the k*gcd is smaller than the diffs we can add !? Example: K=52 arr=[7, 27, 42] so the gcd(diffs)=gcd(20, 15)=5 42 + 2*5 = 52 to get 52 we need to add 2*5 to 42, but we can't do that using the real diffs (20, 15) I know we can get it using some (subtractions , additions) of these diffs but I'm not sure how I can think about it intuitively.
•  » » » » 6 months ago, # ^ |   +1 Sorry for replying lately. I guess it will become more and more intuitive after you solve more and more problems about Bézout's Theorem and ex-gcd (Chinese nickname of Extended Euclidean algorithm? lol) and other number theories. :)
•  » » 8 months ago, # ^ |   0 https://www.youtube.com/watch?v=yYxQ9_EL69Q see if the above link helps
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 Given x and y, we can get $x + t * (y - x)$ for all t. So this is an arithmetic sequence. We draw it on an axis.Now given another number z. We find a closest point on the axis and draw the new arithmetic sequence produced by z and the closest point. If the distance of z and the closest point divides $y - x$, then all points is just one arithmetic sequence which is $z + t * distance(z, closest point)$. Otherwise, we can find another two more close points and produce more points. You can see that only when the distance of two closest points divides both $y - x$ and $z - x$ and $z - y$, the process will stop. So $z + t * gcd(y - x, z - y)$ can be produced.You can draw it on a paper and get the intuition.
 » 8 months ago, # |   +4 1477A — Nezzar and BoardExplain me how we can write down $g_0s-x_nt$ which is equal $g$?
 » 8 months ago, # |   0 video editorial for problem D, if theres anyone whos stuck! https://www.youtube.com/watch?v=yYxQ9_EL69Q
•  » » 8 months ago, # ^ |   0 i still don't understand, how from (0, a, b) get $a * s - b * t = gcd(a, b)$ using $2x-y$ operation
•  » » » 8 months ago, # ^ |   +3 If s is even, then we can get a * s/2 and b * t first, then $2 * (a * s/2) - b * t$ is $gcd(a,b)$. If s is odd, then we can get $2 * (a * (s+1)/2) - b * t$ is $a + gcd(a, b)$. Given a and $a + gcd(a, b)$, by induction, we can get $gcd(a, b)$.
•  » » » » 8 months ago, # ^ |   0 thaks, i undertood) Really is it so obvious, that it's not required to point in editorial? Only how to get $gcd(a, b)$ from $a$ and $a+gcd(a, b)$ took me 5 minutes. We can get $a - gcd(a,b)$, than $a - 2*gcd(a,b)$ and so on until we get $gcd(a, b)$.
•  » » » » » 8 months ago, # ^ |   0 It is not obvious. They should include this comment in editorial.
 » 8 months ago, # |   0 for 1478B, here is my solution https://codeforces.com/contest/1478/submission/105779176 in a bit different style than author ;) , although I fucked up during the contst!:(
 » 8 months ago, # | ← Rev. 3 →   +1 For problem B I assume that $x$ can be represented as $x = y + w.d$. Then, $y = x - w.d$ and just check that $y$ has at least one digit equal to $d$. By brute force I concluded that $w$ is at most $9$ because for $x >= 10.d$ the answer is always YES.
 » 8 months ago, # | ← Rev. 2 →   +52 The system test of problem C is weak! Some people use double and sqrt to calculate distance, it can be hacked, like this, but it passed the system test.I noticed this and resubmitted my code, after the contest, I know that the original code could pass, if I didn't resubmit, I'll be International Master! ):update: This seems to work only for GNU C++17 (64).
 » 8 months ago, # | ← Rev. 2 →   0 Could anyone help me about this https://codeforces.com/blog/entry/87299 ? Thanks!
 » 8 months ago, # |   0 In problem D of div2, why always subtracting x1 from all other numbers works? Means the cases can't be there such that we need to subtract x2 from all the numbers and take gcd after that?
•  » » 8 months ago, # ^ |   +1 k is a linear combination of all x. And you can see that sum of coefficients is always 1. So subtracting x1 from all x results in subtracting x1 from k.
 » 8 months ago, # |   +19 For anyone not knowing what WLOG means in editorial for Div.2 C,WLOG = Without Loss Of Generality.
 » 8 months ago, # |   +3 Very nice problems!I like div.1C very much.
 » 8 months ago, # | ← Rev. 3 →   0
 » 8 months ago, # |   0 For Div2 B how can N=21 and D=2 gives answer yes?
•  » » 8 months ago, # ^ |   0 If you are talking about taking some ai = 21 and d = 2, then 21 itself is a lucky number as it contains d = 2 in its representation already and doesn't need to be expressed as sum of other lucky numbers, So, answer is YES.
•  » » » 8 months ago, # ^ |   0 my bad i understood question wrong
•  » » 8 months ago, # ^ |   0 21 itself is lucky number.
 » 8 months ago, # |   0 Can someone tell the mistake in the following code of mine for Div2B: 105802694 For each integer i from 1 to 9 I stored the smallest integer 1<=j<=10, that give the unit digit (i*j)%10 when multiplied with as a[i][(i*j)%10] = j So if the number in query (say c) had a unit digit l that can be found in a multiple of d, I check if c is greater than or equal to the minimum multiple of d that gives that unit place. If yes, then I output YES as I think all such numbers can be represented using lucky numbers. Else, I output NO as d in unit places has minimum effect, so if we have even one d in tens place, then it becomes greater than c. Now if the units place l in c cannot be found in a multiple of d, then I check if c/10 is greater or equal to d. If yes then I print YES else no, as d cannot even come in tens place then. Can I get a testcase where this fails?
•  » » 8 months ago, # ^ |   0 Your mistake is that you forgot to put a continue after cout << NO << endl in the first if block of your code :)
•  » » » 8 months ago, # ^ |   0 Ya it works now! Thank you!
 » 8 months ago, # | ← Rev. 2 →   +1 Problem B :say d = 7, so 70->79 already lucky, we can generate 80->89 as follows 72 + 17 = 89 71 + 17 = 88 70 + 17 = 87 79 + 7 = 86 78 + 7 = 85 77 + 7 = 84 76 + 7 = 83 75 + 7 = 82 74 + 7 = 81 73 + 7 = 80 similarly, we can generate 90-99 from 80-89 and so on ...... so, any number >= 10*d is lucky
•  » » 4 months ago, # ^ |   0 Thanks!
 » 8 months ago, # |   +3 Nezzar please explain DIV2CWhy in you solution following code gives $a_1$ in $b[n-1]$? for (int i=1;i
•  » » 8 months ago, # ^ |   0 Bazalt If you are clear with this part, can you please explain the divisibility check ( (b[i-1]-b[i])%(2*(n-i) )and the d[i] array? for (int i=1;i
•  » » » 8 months ago, # ^ |   0 As Nezzar says, $d_{2i} - d_{2i - 2} = (2n - 2i)(a_i - a_{i - 1})$. He did not prove that, but he give example for i = n; You can easily find it, probably with induction.And in this code, which you show he just calculating array of $a_i - a_{i - 1}$ for all possible i, he named it d[i] array. Before that he just using divisible check for 2n — 2i.
 » 8 months ago, # |   0 can any tell me why i am getting WA on 2nd TCmy solution for prbolem B (Div 2)
 » 8 months ago, # | ← Rev. 2 →   0 Nanako Can you please explain the relation in the editorial of Div2 C ? This one.. "More importantly, we have the following relation:".
•  » » 8 months ago, # ^ |   +5 Main observation is, when there are $n - x$ elements smaller than the current position and $n + x$ elements bigger than the current position, if you move left for 1 unit length, $\sum |curpos - a_i|$ will increase $2x$.
 » 8 months ago, # |   +28 I found this contest really nice (especially div1 D). Thanks for the contest :)
 » 8 months ago, # |   0 Chinese round! Unfortunately I still can't take part in due to the time (.
 » 8 months ago, # | ← Rev. 3 →   0 On div2 D, if((arr[0]%gcd) == (k%gcd)) printf("YES\n"); ... => WAif((k-arr[0])%gcd == 0) printf("YES\n"); ... => ACI really wonder why this thing happens.
•  » » 8 months ago, # ^ |   0
 » 8 months ago, # |   0 I approached Div2 B as follows: (let input be n) Consider the largest multiple of d <= n (call it x) We need to add exactly (n — x) to x. The goal is to subtract some multiple of d from x and add some 'lucky' number, such that (lucky_number — multiple_removed) = (n — x) Brut force on this got accepted. Here's my solution.I would like to know if there is any hack possible on my approach.
 » 8 months ago, # | ← Rev. 2 →   0 div2C symmetric arrayI tried another approach:Assume that the "d" array (the sum array) and the "a" array (initial array) are sorted. I redefined the "a" array so that it would only contains positive numbers.Since the two arrays are sorted $a[n - 1]$ and $d[n - 1]$ would become the largest element of respective array. I observed that if we choose any index i (0 <= i < n), then the sum $|a[n - 1] - a[i]| + |a[n - 1] - (-a[i])|$ would become $|a[n - 1] - a[i]| + |a[n - 1] + a[i]| = a[n - 1] - a[i] + a[n - 1] + a[i] = 2a[n - 1]$ (since a[n — 1] is the largest element). This applies to every other index 0 <= j < n — 1. Then a[n — 1], or the largest element of the "a" array (initial array) can be calculated using this formula: $d[n - 1] = a[n - 1] * 2(n - 1).$ By expanding more, I could also prove that: $d[n - 2] = 2a[n - 1] + 2(n - 2) * a[n - 2].$Hence I could restore the initial array with following formula: $d[j] = \sum\limits_{i=j+1}^{n - 1}{2a[i]} + 2j * a[j]$, with j being the index in the sorted array. Furthermore, since all d[j] % 2 == 0 from above formula, I could throw away any cases that had any d[i] that is odd. The problem is I can't make sure if the array constructed was right or wrong. So I tried calculating everything again from the constructed array, and also noticed if any element in that array was 0 it was wrong. Can anybody pls check it out lol105799882
•  » » 8 months ago, # ^ |   0 I used the same approach and got AC. To check if $a_i$ is correct, I checked that it was positive and it hadn't been found before.
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 snacache Err... Sir, I still haven't managed to debug my code. Would you bother helping me out? UPD: got TLE on test case 19 106071246
•  » » » » 8 months ago, # ^ |   0 You don't need that inner cycle to calculate $A_i$
 » 8 months ago, # |   0 In Div2 C how are we checking that whether a[0] can be made form d[0]. The a and d I am refering to are problem statement a and d.
 » 8 months ago, # |   +8 Div1 D is awesome . Thank you!It took me about 4 hour to come up with the solution . A very nice problem !
 » 8 months ago, # |   0 Nezzar and lucky number can be done in O(1) Solution: Observation1: x>= 10*d , it is always possible. Observation2: for x<10*d, let h be a multiple of d, If((h%10==x%10) && (h>=x)) => Yes Else => NoSolution: 1) make array of size 10 nad initialise with -1. 2)For i (0 to 9) K=d*i If arr[k%10]==-1 , arr[k%10]=k 3) if (arr[x%10]!= -1 && arr[x%10]>=x) => Yes Else if (x>= 10*d) => Yes Else => no
 » 8 months ago, # |   0 In Div1.A why can we assume $x_1=0$? I can't understand.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 I understand is now by reading senyaa's comment, thanks
 » 8 months ago, # | ← Rev. 2 →   0 For Div1B (Nezzar and Binary String), could someone explain how the 3rd sample input test is possible? I've been thinking a while but I'm quite confused. 10 6 1111111111 0110001110 1 10 5 9 7 10 1 7 3 5 6 10 If we follow the editorial, we should work backwards starting at 0110001110, we need 6-10 to be the same before the last night's inspection so it becomes 0110011111. Then we need 3-5 to be the same so it becomes 0100011111. Then we need 1-7 to be the same so it becomes 0000000111. Then we need 5-9 to be the same and it becomes 0000000001. Finally we need 1-10 to be the same so it becomes 0000000000, but this is not 1111111111, so it doesn't seem to be possible?Edit: Thanks Nezzar, I wrote the math for this out like 5 times on notebook paper and kept getting the same result, I have no idea how I missed that query every time..
•  » » 8 months ago, # ^ |   +5 You missed the 3rd query
 » 8 months ago, # |   0 I'm confused by some of the implementation in Div1 D. I think the dfs function creates the spanning tree of the complement graph, is this right? The loop with while(d.size()) seems to do the decomposition into stars, but if I'm not mistaken it doesn't use the same method described in the editorial. What I get from this is that you choose an unassigned node from d in idx, then choose one of it's neighbours f to be the center of your star graph? Why this particular ordering of vertices in d?
•  » » 8 months ago, # ^ |   +5 Sorry if it causes any inconvenience. Codes were written by me while tutorial for d1D was written by Nezzar. Approach to decomposite spanning trees into stars in the code was to choose an arbitrary leaf in the tree, find its neighbor vertice $u$, and choose all neighbor vertices of $u$ with degree $1$ to form a star. It can be shown that the remaining graph after deletion of this chosen star is still a tree with more than $1$ vertices or empty.(Therefore, we could decompose tree into stars applying this method recursively.)
•  » » » 8 months ago, # ^ |   0 That makes sense, and is very simple. Thanks!
 » 8 months ago, # |   +21 For div1F, the $m$-th coefficient of $Q_j$ should be $\frac{1}{m!}(1 - q_{m,j})\left(\frac{L_j}{L}\right)^m$and the OGF of $k! \sum_{n \geq 0} \binom{n + k}{k}C^nx^{n+k} = k! \frac{x^k}{(1-Cx)^{k+1}}$
 » 8 months ago, # |   0 Can someone clearly explain what happened in Nezzar and board?
 » 8 months ago, # |   0 In Div 2 C editorial, "And observe that |ai−an|+|ai+an|=2an is a constant independent of index 1≤i≤n."Why is this the case?
 » 8 months ago, # |   0 A much better solution for div2 B than DP is that if the number is $\geq 10*d$ then it is always possible, otherwise we can observe that the only numbers less than $10*d$ that contain $d$ are, $10 + d, 20 + d, 30 + d, \dots$ Hence, if a number is feasible then it can be represented as: $10*x + d*y$ where $x$ and $y$ are variables.I'm livid I didn't come up with this during the contest lol.
•  » » 8 months ago, # ^ |   0 same as my approach
 » 8 months ago, # |   0 In Problem C : Can anyone explain why the biggest element in array d is always 2*n*(biggest element in d) supposing arrays d and a are sorted then a[n]*2*n=d[n] why?
•  » » 3 months ago, # ^ |   0 Each element has a positive and negative value. Supposing the positive value is $x$, and the absolute difference to $(y, -y)$ would be $| x - y | + | x + y |$. Similarly, for $-x$, that would be $|-x - y | + |-x + y |$, which is also $|x - y| + |x + y|$. For $|x - y| + |x + y|$, we have two different cases. For $x > y$, $|x - y| + |x + y|$ would be $2 * x$. For $x > y$, $|x - y| + |x + y|$ would be $2 * y$. Now we know that $|x - y| + |x + y|$ = $2 * max(x, y)$.For each $d[i]$, it is the sum of each absolute differences from $a[i]$ to all integers. Combined with the previous finding, we got $d[i] = \sum_{j=1}^{2n} max(abs(a[i]), abs(a[j]))$Supposing the max element is $a[n]$. As $a[n]$ is greater than other elements, Then, we have $d[n] = \sum_{j=1}^{2n} a[n]$Therefore, you got $d[n] = a[n] * 2 * n$.
 » 8 months ago, # | ← Rev. 2 →   0 Can anyone please elaborately explain me B ( Lucky number one ) I'm struggling to understand the solution by Dp, I am a newbie so please be considerate, CF is extremely harsh and often hostile to beginners.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Try thinking about it like this: Suppose the number you are trying to check is $x$, If $x$ is achievable then it can be represented as $x = a + b$, where $a$ is a number with $d$ as one of it's digits and $b$ is a number that is also achievable.The only possible values for $a$ are: $d, 10+d, 20+d, 30+d, \dots$The line: dp[10*i+d+j]|=dp[j]; is checking just that! $10*i + d$ represents all possible values of $a$ and $j$ represents any number that is achievable. Hence, if $j$ is possible then $10*i + d + j$ is also achievable.Hope it helps!
•  » » » 8 months ago, # ^ |   0 Why "The only possible values for a are: d,10+d,20+d,30+d,…"?If d = 4, for example, the lucky number 40 can't be represented in that way.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 I was only explaining the DP part. Otherwise for any number $x \geq 10*d$ is always possible no? Thanks for pointing that out though.. could've been confusing for others.
 » 7 months ago, # |   0 could someone explain how for div1 B (1477B), how the second sample test case is impossible? 2 1 00 01 1 2 on the 1st day, the string that is inspected is "00" on the 1st night, you can change 1 character in the inspected string, so can't you change "00" to "01" and finish the test case successfully?
 » 7 months ago, # |   0 Wouldn't X(i) — X(i-1) always = 1? I'm confused...
 » 7 months ago, # |   0 Div2D was a very nice task, but i miss a more detailed editorial's explanation.
 » 7 months ago, # |   +1 For 1478D - Nezzar и доска, suppose we have the numbers 0, a, b, c. Then how can we generate 3a — b + 5c? Since we are using Bezout's Identity, then ax + by + cz = d must exist ${\forall}$ x,y,z ${\epsilon}$ $\mathbb{Z}$
 » 5 months ago, # |   0 I used a greedy approach for problem B and it accepted! Thanks for such a nice clean code for problem B.
 » 3 months ago, # |   0 Problem B got me :((
 » 3 months ago, # |   0 In the Nezzar and Board problem, I find it difficult to understand why "If g = GCD(x1,x2,x3,....,xn) divides k, then YES, else NO" doesn't work, but the given logic in the Editorial does. Also, I am not able to comprehend the proof given. Can someone explain? Thanks in advance!
 » 3 months ago, # |   0 In the solution of 1478B, for the nested loop we can do j = j+d instead of ++j right?