### fcspartakm's blog

By fcspartakm, history, 2 years ago, translation,

• +37

 » 2 years ago, # | ← Rev. 2 →   0 First of all thanks for the tutorial,But I can't get problem C, I don't understand why looping from 0 to w will guarantee finding a solution(if it exist) I got this observation " The crucial observation is that d wins give us the same amount of points as w draws. Let's use them to solve a problem where we want to minimize the total amount of wins and draws giving p points (if it is not greater than n, we can just lose all other matches) " but I can't understand the rest.
•  » » 2 years ago, # ^ |   +16 Let x be # of wins, y be # of draws, z be # of losses.We need to prove that if there is a solution where y >= w, there will be a solution where y < w.When y >= w, we exchange w draws with d wins. The total points remains the same (from the observation), and we do not overshoot the limit as x'+y' = (x+d)+(y-w) = x+y-w+d < x+y <= n. Thus this will also be a solution.So if we keep exchanging w draws for d wins, we will eventually end up with a solution where y < w and we cannot exchange further.Now that it is proven, we can say that if a solution exists, a solution will exist where y < w. Similarly if there are no solutions where y < w, there are no solutions. Thus, we search y from 0 to w-1 to find a solution, and if we cannot then there is no solution.
•  » » » 2 years ago, # ^ |   -38 If you want to input $\geq$,you can just input: $\geq$ (only one \$)
•  » » » 23 months ago, # ^ |   0 I am still not able to understand how did you proved that if there does not exists solution for y
•  » » » » 23 months ago, # ^ |   0 Since we proved that if a solution exists, a solution will exist where y < w, it is equivalent to saying that if there is no solution where y < w, a solution does not exist. (This is the contrapositive of the first statement)Proof: Assume otherwise: there is no solution where y < w but there is at least one where y >= w. However, we can say that will be a solution with y' = y-w, since (w draws = d wins + w-d losses) in terms of points. We can then also say that there is a solution where y' = y-2w, and so on until we have a solution such that y' < w.Hope this helps.
•  » » » 23 months ago, # ^ |   0 why can't we do the same for x instead of y?
•  » » » » 23 months ago, # ^ |   0 This is because it is optimal to have less draws and more wins, but not the other way round. Wins give you more points than draws.So we can constrain the number of draws, but not the number of wins, as the number of wins can be as large as n (10^12).
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 I don't know if it would still be relevant for you but I solved this problem completely as an abstract number theory problem: Given non-negative integers $n, p, w, d$, find non-negative $x, y, and$ $z$ satisfying $x⋅w+y⋅d=p$ $x+y+z=n$ with $w>d$. Now, express $p$ and $w$ as $k_1*d+c_1$ and $k_2*d+c_2$. This means $y=k_1-x*k_2+(c_1-x*c_2)/d$. Now again express $x$ in terms of $d$ as, say, $k_3*d+c_3$. Now you can iterate over all possible $c_3$ from $0$ to $d-1$ and find the maximum $k_3$ such that $y$ is still non-negative: This is true because it turns out that $x+y$ decreases with increasing $k_3$, so we have more options for $d$ (greedy approach).
 » 2 years ago, # | ← Rev. 3 →   -44 solution of problem E(translated by google translate)The only mid-range question in this competition.Obviously greedy.Sort the series first.To make the minimum value in a series +1, you need to +1 each of the minimum values in the series; to make the maximum value of -1 in the series, you need to have a maximum of -1 for each of the series. ——mangoyang's comment on XJOI (not this question)Now let's categorize the discussion: If the remaining number of operations is sufficient: compare the smaller values of the difference between the left and the right, select a smaller operation If the number of remaining operations is not enough, select an operation with fewer numbers on both sides. In a total of four cases, the code is a bit annoying, be patientIn addition, if the number of times is stable, it will output 0 directly.code:62540846
•  » » 2 years ago, # ^ |   +13 I think you should put all the codes in a spoiler. That will reduce the size of the comments.
•  » » » 2 years ago, # ^ |   -45 It is sorry that I don't know how to use spoiler,so i use link.
•  » » 2 years ago, # ^ |   0 I'm not really able to see why E is greedy.Suppose k was 20 and we have the following frequency table1 -> 16 2 -> 1 3 -> 1 4 -> 1 5 -> 50 6 -> 10 7 -> 10Wouldn't greedily first reducing 7 and then reducing 6 be worse than increasing 1, 2, 3 and 4
•  » » » 2 years ago, # ^ | ← Rev. 3 →   -38 Because my English is not very well,I don't quite get your question.greedy means "choose the less cost one that can influence to the answer"In fact,you can see the example 1: 4 5 3 1 7 5 reducing 7:1 3 5 6reducing 6:1 3 5 5increase 1:2 3 5 5increase 2:3 3 5 5then,whatever you do,the $Maxnum-Minnum=2$so the answer is 2
•  » » » 23 months ago, # ^ | ← Rev. 2 →   0 You will decrease or increase whichever group of numbers in top or bot that have less quantity (just compare top and bottom groups).10<16 so go from top: "1 -> 16 2 -> 1 3 -> 1 4 -> 1 5 -> 50 6 -> 20" now 16<20 so go from bot but because 16>k (k is 10 now) we can't do anything and program terminates.Python code: 62526246
•  » » 23 months ago, # ^ |   0 I tried something similar during the contest but failed. My idea was to compare which side was cheaper, but it did not work. Can somebody point out what is wrong with this logic? 62484346
•  » » » 23 months ago, # ^ |   0 you should first compare which cost less,then compare $k$ is enough or not.
 » 2 years ago, # | ← Rev. 2 →   -36 solution of problem G(translated by google translate)This is one of the four best questions (ABDG) that can be done in this competition.Simple constructionSince the output order is independent of the correctness of the answer, we assume that one of the two sequences of the output is in the order from $1$ to $n$.We find a property: the sum that can be made by the permutation is $[\sum_{i=1}^n i,\sum_{i=1}^n max(i,n-i+1)]$So the output of $<\sum_{i=1}^n i$ $-1$, $\geq \sum_{i=1}^n max(i,n-i+1)$ is a fake example 2 outputNow the range of $k$ becomes $[\sum_{i=1}^n i,\sum_{i=1}^n max(i,n-i+1))$Construction method:Set the current unfilled interval to $[L,R]$, and fill in $R$ if $\leq k$ after $R$ is filled in, otherwise fill in $L$code:62537353
 » 2 years ago, # | ← Rev. 3 →   -21 solution of problem F(translated by google translate) a bit late,sorry!The harder one of the two questions (CF) in the competitionWe found a property: if the consecutive $k(k \geq 2)$ colors are the same, then their color will not change.Then, it will only change type like $\dots BWBWBW \dots$.Every time you change, the left and right ends will become the final color, and the other middle will become a different color($B \rightarrow W,W \rightarrow B$).Then we can simulate directly.The time complexity of the simulation is $O(min(n,k))$why?For each operation (time complexity is $O(1)$), it must change the value of two characters, and each character changes at least once.Code:62554014
 » 23 months ago, # |   +14 The greedy for E:The idea is to sort the array, and start with the initial maximum difference, and try decreasing it while we have operations left.We need only 1 operation to decrement answer by one, if we increment the leftmost number. We can keep incrementing it until it becomes equal to the next number. After that, we need 2 operations (increment both of them) to decrement answer by one, and so on.The same is symmetrical for the right side too.So, we greedily move towards center from both ends together, minimizing the answer at each step.62586395
•  » » 23 months ago, # ^ |   0 I had come up with something similar, and it seemed to work on whatever examples I could find, but I can't prove correctness. Could you prove intuition on how I would go about proving this is always optimal? Thank you.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   0 Look at it like this,1) let's agree that it's always your best choice to either increase the minimum number or decrease the maximum number since those are what bring you your result.2) does it matter if you choose to increase the minimum by one or decrease the maximum by one ? the answer is No since both will make the final answer decrease by one 3) so now we're at the point where we must choose to either increase the minimum or decrease the maximum what will be my greedy choice is the number or occurrence of eachsay we have 5 5 7 8 9 9 9 9If we choose to increase the minimum we will need 2 moves to decrease the final answer by 1 ( 1 for each 5 )If we choose to decrease the maximum we will need 4 moves to decrease the final answer by 1 ( 1 for each 9 )hence it's always optimal to choose the once with the minimum number of occurrence
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 here I used the same but got out of memory...then TLE after removing one vector https://codeforces.com/contest/1244/submission/77981716
•  » » » » 17 months ago, # ^ |   0 Rahul's approach seems good, his solution makes use of difference array
•  » » 14 months ago, # ^ | ← Rev. 2 →   +8 is this a usual way to code or something?like after taking examples i understood why your code worksbut did u think of this approach? how this performs on an array like 1 2 3 16 25 36 (say k = 5) is very interesting(for me)...
•  » » » 14 months ago, # ^ |   0 This type of approach often occurs in similar type of problems.You generally learn these by coming across similar problems and looking at different approaches of top competitors, who usually solve it in simpler way. Also, the linked submission is of practice, it probably wasn't the first approach that came to my mind.
 » 23 months ago, # |   0 Please someone explain me how to solve Problem C using Linear Diophantine Equations.I read this Comment but his ans is not clear to.
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 From extended gcd we get (x0, y0) such that ax0 + by0 = g = gcd(a, b). We then scale this to satisfy ax + by = p; x = (p/g)x0; y = (p/g)y0 We can now shift our obtained solution to (x + kb', y - ka') where a' = a/g and b' = b/g [you can verify this]Now we have 3 inequalities: x >= 0 or k >= -x/b' y >= 0 or y/a' >= k x + y <= n or k >= (x + y - n)/(a' - b') Just pick a k which satisfies all the inequalities or return -1.---Keep in mind that scaling will lead to an overflow in cpp. We can overcome this using the fact that there's a solution with y < w' from the editorial.
 » 23 months ago, # |   0 How is the solution gauranteed to have minimum cost?? Problem D
 » 23 months ago, # | ← Rev. 3 →   +1 Can someone please take a look at my code for problem D. I can't figure out why is giving runtime error. 62637783 or wa
 » 23 months ago, # |   0 I am new in trees. How can we implement D? Please help.
•  » » 23 months ago, # ^ |   0 if you are using c++ then tree/undirected acyclic graph can be represented as array of vectors. if tree contains n nodes represent it as vectorvec[n+1]. to make the n-1 connections in the tree number=n-1; while(number--) { ll int a,b; cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } for more basic info refer to hackerearth theory section regarding graph.
•  » » » 23 months ago, # ^ |   0 Thank you very much
 » 23 months ago, # |   0 Editorial for F?
 » 23 months ago, # |   0 What is s in the Staircase problem?
 » 23 months ago, # |   0 fcspartakm editorial for f ?
 » 23 months ago, # |   0 Why L or R must belong to the same array. Can someone explain it in more detail.
 » 23 months ago, # |   0 How'd you go about implementing D?Assume you've initially marked the last edge of the input with 2 colors, how do you find which vertex to run the DFS on? Anyone got their solution they could link me to? Would be p cool
 » 23 months ago, # |   0 In problem C, " The crucial observation is that d wins give us the same amount of points as w draws" i didn't get this. Can someone please explain?
•  » » 23 months ago, # ^ |   0 xw + yd = p, x=d,y=w.
 » 23 months ago, # |   0 I have a very peculiar doubt in question C.I got the part "_The crucial observation is that d wins give us the same amount of points as w draws. Let's use them to solve a problem where we want to minimize the total amount of wins and draws giving p points (if it is not greater than n, we can just lose all other matches_"But why are we comparing y ans w to get the solution?
 » 23 months ago, # |   0 In problem C, if i am doing the same thing for x =0 to d-1 then why it is giving WA? It should be correct ?
 » 23 months ago, # |   0 has anyone implemented problem D with the second approach told in the tutorial?
 » 23 months ago, # |   0 In Problem E's editorial, can someone explain the 2nd para with an example ?
•  » » 23 months ago, # ^ |   0 consider sample: 10 12 1 2 3 6 7 8 9 13 14 15 2nd paragraph tells you that if there is answer that reach $(min, max) = (4, 12) = (L, R)$ then there are same amount of numbers that you need to increase, so there are also answers $(3, 11)$ and $(5, 13)$ but among them are those with $L$ or $R$ from input array. Now, other sample: 9 11 1 2 6 7 8 9 13 14 15 Think of $(L, R) = (4, 12)$ again. It require $5+6 = 11$ to make it. It's not optimal because there are two numbers that we increase, and three that we decrease, so we can move $L$ and $R$ up by one to $(L+1, R+1) = (5, 13)$, so each decreasing number will need one step less, and each increasing number will need one step greater. So, total difference will be $\# L - \#R$, where $\#L$ is number of increasing numbers, and $\#R$ is number of decreasing numbers. And, because $\#L < \#R$ this difference is negative, so result will be better. It was requiring 11 and $\#L - \#R = 2 - 3$ so it will require $10$. By anology, if $\#L > \#R$ you can change to $(L-1, R-1)$.And... of course in this case $(4, 12)$ is not answer, because this is reason why answer must have one of bounds if amount of increasing and decreasing numbers are not equal. If they equal, then answer may have bounds from initial array or not, but there is always answer that has $L$ or $R$ from initial array.
•  » » » 23 months ago, # ^ |   0 Thank you so much..! I got it now.
 » 21 month(s) ago, # |   0 Why approach is wrong? https://codeforces.com/contest/1244/submission/68103624
 » 17 months ago, # |   0 C can be solved in O(1) time the best lower bound for y is (y = ((p / g) % (w / g) * modInverse(d / g, w / g)) % (w / g)). Just check for this (y) if there is a suitable non negative x satisfying the bound (x + y <= n) and (x * w + y * d = p)
 » 17 months ago, # |   0 DP solution for D : https://codeforces.com/contest/1244/submission/62501364
 » 14 months ago, # | ← Rev. 4 →   0 Solution for Problem C :Given: $w.x + d.y =p$ (eqn 1) and $x+y+z= n$ Also we know $x>=0$ , $y>=0$ and $z>=0$ . Let $x + y = k$ (eqn 2) where $k=n-z$ and as $z>=0 ,$ $k<=n$ Next we multiply eqn 2 with $w$ to form eqn 3. Solving eqn3 and eqn1 for x and y, we obtain x to be $\dfrac{p - d.k}{w - d}$ and y to be $\dfrac{w.k - p}{w - d}$. We put in the newly found values of $x$ and $y$ in $x>=0$ and $y>=0$ to obtain $k>=\dfrac{p}{w}$ and $k<=\dfrac{p}{d}$ Thus we iterate k from $\dfrac{p}{w}$ to $\min(\dfrac{p}{d},n)$ Code Link ![ ]()
•  » » 14 months ago, # ^ | ← Rev. 4 →   0 Ingenious! I was looking for such a solution for a long time, thanks! Btw, could you please explain why you're checking p%__gcd(w,d)==0 why if this is false, then the solution doesn't exist? I made two submissions, the first one was this -without this p%__gcd(w,d)==0 condition, got TLEthe second one was this -with this p%__gcd(w,d)==0 condition, got AC
•  » » » 14 months ago, # ^ |   +1 The simplest linear Diophantine equation takes the form ax + by = c, where a, b and c are given integers. This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b. Source link
•  » » 13 months ago, # ^ |   0 Thank you very much. It was really helpful