Edvard's blog

By Edvard, history, 6 years ago, translation,

710A - King Moves

Easy to see that there are only three cases in this problem. If the king is in the corner of the board the answer is 3. If the king is on the border of the board but not in a corner then the answer is 5. Otherwise the answer is 8.

С++ solution

Complexity: O(1).

710B - Optimal Point on a Line

The function of the total distance is monotonic between any pair of adjacent points from the input, so the answer is always in some of the given points. We can use that observation to solve the problem by calculating the total distance for each point from the input and finding the optimal point.

The other solution uses the observation that the answer is always is the middle point (by index) in the sorted list of the given points. The last fact is also can be easily proven.

C++ solution

Complexity: O(nlogn).

710C - Magic Odd Square

The problem was suggested by Resul Hangeldiyev Resul.

The solution can be got from the second sample testcase. Easy to see that if we place all odd numbers in the center in form of rhombus we will get a magic square.

C++ solution

Complexity: O(n2).

710D - Two Arithmetic Progressions

I wanted to give this problem a lot of time ago. I thought it is very standard problem, but I underestimated its difficulty.

Let's write down the equation describing the problem: a1k + b1 = a2l + b2 → a1k - a2l = b2 - b1. So we have linear Diofant equation with two variables: Ax + By = C, A = a1, B =  - a2, C = b2 - b1. The solution has the form: , where the last equation can be solved by extended Euclid algorithm and p is any integral number. The variable p should satisfy two conditions: and . The values A and B are fixed, so we can get the segment of possible values for the values p. The length of the segment is the answer for the problem.

C++ solution

Complexity: O(log(max(a1, a2))).

710E - Generate a String

The problem was suggested by Zi Song Yeoh zscoder.

This problem has a simple solution described by participants in the comments.

My solution is a little harder. Let's solve it using dynamic programming. Let zn be the smallest amount of time needed to get n letters 'a'. Let's consider transitions: the transition for adding one letter 'a' can be simply done. Let's process transitions for multiplying by two and subtraction by one simultaneously: let's decrease the number i i times by one right after getting it. Easy to see that such updates never include each other, so we can store them in queue by adding the new update at the tail of the queue and taking the best update from the head.

The solution is hard to describe, but it is very simple in the code, so please check it to understand the idea :-)

C++ solution

Complexity: O(n).

710F - String Set Queries

The problem was suggested by Alexandr Kulkov adamant.

Let's get rid of the queries for deleting a string. There are no strings that will be added two times, so we can calculate the answer for the added (but not deleted strings) and for the deleted separately and subtract the second from the first to get the answer. So we can consider that there are no queries of deletion.

Now let's use Aho-Corasik algorithm. The only difficulty is that the strings are adding in online mode, but Aho-Corasik algorithm works only after adding all the strings. Note that the answer for the given set of strings equal to the answer for any part of the set plus the answer for the remaining part. Let's use the trick with converting the static data structure (Aho-Corasik in this case) to the dynamic one.

For the set of n strings let's maintain a set of no more than logn sets of the strings with sizes of different powers of two. After adding new string we should move the sets from the lowest powers of two to the largest until we got an invariant set of sets.

Easy to see that each string will be moved no more than logm times, so we can process each query in O(logn) time.

C++ solution

Complexity: O((slen + m)logm), where slen is the total length of the string from the input.

• +11

 » 6 years ago, # |   0 In problem B , How do we prove that "the answer is always in one of the given points" .
•  » » 6 years ago, # ^ |   +3 Sort the array, and just find the median.
•  » » 6 years ago, # ^ |   +8 I think i can prove it. if n = 1, so the answer will be given point if n = 2, so the answer is between first and second point, and the sum of distances is constant if n > 2, let's take the point with min x and point with max x, and just forget about them. That's all. Sorry for my english.
•  » » » 6 years ago, # ^ |   +5 Why we can forget about them ?
•  » » » » 6 years ago, # ^ |   +8 Because, they're part in the answer is length of the interval, and we can just add this interval in final sum, and then forget
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I just want to detail TaTaPiH's answer a bit more, but he has 100% of the credits (thanks btw). "if n = 1, so the answer will be given point" "if n = 2, so the answer is between first and second point, and the sum of distances is constant" Let the two points be x1 and x2. If you take a point y between x1 and x2 (x1 <= y <= x2) the sum of distances to get to y is (y — x1) + (x2 — y) = x2 — x1, which means that independent of the point y you take, the total distance will be the same (the length of the segment). "if n > 2, let's take the point with min x and point with max x, and just forget about them. That's all. Sorry for my english." Let's sort array x which has the n points, 1-indexed. For example, suppose n = 5. We want to minimize the total sum of distance to some selected point y.Consider points x[1] and x[5]. These 2 points alone will always sum (x[5] — x[1]) to the final sum of distances if you choose some (any) point y between them. (See case n = 2 for explanations). So let's sum that to the final sum and move on.Now we're left with points x[2], x[3], x[4]. For points x[2] and x[4] you should also take a point y between them, because otherwise a point y outside points x[2] and x[4] would sum something greater then the length of that interval to the final answer. Note that a point between x[2] and x[4] is a point between x[1] and x[5] so you can continue this logic without changing the answer for the previous points. Now only one point (x[3]) is left, see case n = 1.So the pattern is: you fix 2 extremes points (one to the left and one to the right), now you'll now that an optimal answer must choose a y between them, and move on to the next points, until you're left with 1 or no points.
•  » » 6 years ago, # ^ |   +1 Assume that we are moving a point from left to right to get the optimal answer, consider the following scenario. (X denotes a point, # denotes the current chosen point)(XXX m points XXX) # (XXX n points XXX)Whenever you move to the right, the resulted total distance changes by n-m since you are moving closer to n points and moving away from m points. At one point, when n becomes smaller equal than m, you need not to continue go right for the answer since we only need the leftmost point as the answer. Hence, the answer is always one of the given points.
•  » » 15 months ago, # ^ |   0 kings move . I can't understand the output . why 3,5,8 ?? what is the reason ?
 » 6 years ago, # |   +10 Where is english version?!
•  » » 6 years ago, # ^ |   -17 Google translate
•  » » » 6 years ago, # ^ |   +10 Does'nt seem to be working well
 » 6 years ago, # |   +14 English version please? :(
 » 6 years ago, # |   +26 This round is important and must have an English Editorial.Codeforces is a good international site.Please don't limit us by only releasing in Russian. I kindly request you to release an English version.
 » 6 years ago, # |   +6 A lot of people are making a great effort to learn english to understand and take place in the community. Are U serious with this EDITORIAL in russian? I hope an english version release of this editorial.In particular I am very interested in the solution for problem F.
 » 6 years ago, # |   +32 Sorry for the delay with English editorial. I'll write it as soon as I can.
•  » » 6 years ago, # ^ |   0 TNX ;))
•  » » 6 years ago, # ^ |   0 Now,Thanks!
 » 6 years ago, # | ← Rev. 2 →   0 Hi, Can somebody perhaps explain the motivation behind the solution for problem C? After reading the code in this tutorial I can verify that it works, but still I cannot imagine how one comes up with this solution.Thank you!^resolved now with the English tutorial
 » 6 years ago, # |   +3 Longing For Solution in English...
 » 6 years ago, # |   0 Can someone please explain to me the logic behind problem E. I have used a 1-D array to store the least time to generate i no. of a's.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +6 Let dp[i] be the optimal cost to produce string of length i. We have two cases:If i is even, then the optimal cost for dp[i] is the minimum of dp[i-1] + x (add new char) or dp[i/2] + y (copy from half the length)If i is odd, then the optimal cost for dp[i] is the minimum of dp[i-1] + x (add new char) or dp[(i+1)/2] + x + y (copy then remove). For example, you can get string of length 15 either by adding from length 14, or copy from length 8 then removing 1 character(Note: I don't know if this is the logic used in the editorial code)
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 I have previously implemented the same.But it is showing incorrect. This approach fails in the following case.Suppose we want to produce the string of length 30 then according to above approach dp[15]=min(dp[8]+x+y,dp[14]+x)dp[30]=min(dp[15]+y,dp[29]+x)you can see that we are having an extra x seconds(which is the same time spent in removing an extra 'a' generated from doubling 8 a's) while calculating dp[30]. Now if we want to produce a string of higher length then there would be more and more extra x seconds while calculating the cost.Hence this approach won't work.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 First of all, how do you know that dp[15] must be dp[8] + x + y? It could also be dp[14] + x, depending on the x y values.Secondly, I don't quite get what you mean by "more and more extra x seconds", but looking at your submissions, I guess your mistake is implementing the dp when i is odd as min(x + v[i/2] + y, v[i-1] + x). It should be v[(i+1)/2]
•  » » » » » 6 years ago, # ^ |   0 I got my mistake.Thank you so much.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 I don't get somethingLets say i is even, then you that dp[i] is the minimum of dp[i-1] + x or dp[i/2] + y, but why can't it be dp[i+1]+x, like if we can get to 31 faster then to 29, and we need to get to 30. Same question if i is odd.EDIT: Nvm figured it out
•  » » » » 3 years ago, # ^ |   0 Can you please explain why we aren't considering dp[i+1]+x, I am having the same doubt?
•  » » » » » 2 years ago, # ^ |   0 for those still having this doubt..consider the case when i is even say 30..then one possible choice for making 30 is cost(30)=cost(15)+y which is considered in the above recursion...but another possible choice can be cost(30)=cost(16)+2*x+y when cost(16) is lesser than cost(15)..in this case cost(15) maximum value can be cost(16)+x..so replacing the maximum value of cost(15) in the equation cost(30)=cost(15)+y it becomes->cost(30)=cost(16)+x+y which is still lesser than cost(16)+2*x+y...so when i is even we can say that its optimal answer will be among cost(i-1)+x and cost(i/2)+y only..we can similarly prove it for the odd case..
•  » » » 5 years ago, # ^ |   0 can u please explain dp recurrence a little?
 » 6 years ago, # |   0 I solved problem 710E - Generate a String using Dijkstra, but it got AC with 1918ms :D almost TLEcould anyone explain the other solution using Dynamic programming?! i did not understand what is written in the editorials!!!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Hi, my interpretation of the solution was that instead of using Dijkstra, they managed to use a slightly-different graph that was a DAG, so finding shortest paths is O(N).You can note that between doubling operations (after the first one, of course), there is at most one + or — operation, because otherwise you could be more efficient by moving them before the previous doubling operation. (for example, the sequence +*++ -> 4 could be done as ++*). If you take a graph with only these edges, it becomes a DAG, and dijkstra is not necessary.EDIT: Here is incredibly simple solution with this idea http://codeforces.com/contest/710/submission/20469970
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 If you still interested)) DP solution is far easier than Dijkstra.(I'm specialist but I found out it) Here is my solution http://codeforces.com/contest/710/submission/25821459. If you don't understand how to get the formula, try to think from what values we can get an answer. And don't forget that we can delete chars and it costs x./////Sorry if my English is poor)
•  » » » 2 years ago, # ^ |   0 DAG approach is inplemented using forward dp and your code implements backward dp. Both are easy and exctly same
•  » » 5 years ago, # ^ |   0 Can I see your code please? my code works with Dijkstra but I got TLE I wanna see if I can do any thing about it!
 » 6 years ago, # |   0 Did anyone solve problem D?I know how to derive x0, y0, where Ax0 + By0 = C by using Extended Euclidean Algorithm, but I don't know proceed from here to . Also, it seems to me that . Am I misunderstanding something? If not, can somebody perhaps elaborate more on this step? Thank you!
•  » » 6 years ago, # ^ |   0 .Also obviously , so the first equation is also true.The only difficulty thing is to prove that all solutions can be described in the given form. It is a standard fact and I think you can easily find the prove in the internet.
•  » » » 6 years ago, # ^ |   0 Thank you for the reply!I know how to prove that all solutions can be described in this given form now, but still I cannot understand three lines in your program, which relates to the lower bound L and upper bound R after staring at it for a long time.li L = _ceil(r * g — x0 * C, B);li R = _floor(l * g — x0 * C, B);R = min(R, _floor(y0 * C, A));Can you give me some more explanations regarding these three lines, or direct me to a link? Thank you!
 » 6 years ago, # |   0 I found that no one can solve Problem F by Java 8 because of TLE in test case #19 (demands flush*300000) though problem statement refers to Java's flush.Did writers&testers check whether it can be solved by Java 8?
•  » » 6 years ago, # ^ |   0 +1. I ran into the same trouble here.
 » 6 years ago, # | ← Rev. 2 →   0 I wonder why F a O(N*sqrt(N)) gets a TLE. Here is my code 20350890 Anyone can help? UPD: Trouble solved.
 » 6 years ago, # |   0 Hello,Here is my submission for problem B.I am sure that my idea is correct but maybe there is a tiny bug in the implementation. Any help?
 » 4 years ago, # | ← Rev. 2 →   0 What is the "floor (y0*C, A)" in the end of problem D's code for? Why is it here ? How did we get to "y0*C/A" ?
 » 4 years ago, # |   0 Hi, Can someone explain the motivation behind the solution for problem C? After reading the code in this tutorial I can verify that it works, but still, I cannot imagine how one comes up with this solution.Thank you!
 » 2 years ago, # | ← Rev. 2 →   0 Proof of Problem E , DP — Solution abs(dp[i]-dp[i-1])<=x assume worst case dp[i-1]=x+val,dp[i]=val dp[(i-1)*2]=x+val+y dp[i*2]=val+y now using dp[i*2] to calculate dp[(i-1)*2] we get dp[(i-1)*2]=val+y+x+x assume another worst case dp[i-1]=val, dp[i]=x+val dp[(i-1)*2]=val+y dp[i*2]=val+y+x now using dp[i*2] to calculate dp[(i-1)*2] we get dp[(i-1)*2]=val+y+x+x+x as you can see in both case it is always unoptimal to subtract >=2 times 
 » 2 years ago, # |   0 This might be 4 years too late but anyways. Can someone help me find the problem in my code as it got TLE. [submission:83865729]I don't think there is any way to optimize my code. Maybe it's the fault of Java 11.
 » 2 years ago, # |   0 Hello can someone explain why I got a TLE on test B?Here is the code: https://codeforces.com/contest/710/submission/91295249.I believe it is because I use Java but I am not sure. Is that correct?
 » 2 years ago, # |   0 In problem D, can someone explain why max(0,L) <= (C*x0+B*p)/g <= R and max(0,L) <= (C*y0-A*p)/g <= R? Doesn't it should be L<=x<=R? But it seems to me that x is not equal to (C*x0+B*p)/g or (C*y0-A*p)/g .
 » 2 years ago, # |   0 In ques D, I first calculated solution of x0,y0 using extended Euclid algo, and then i found the value of x=a1*x0+b1, and from their i found the req. resutlt as possible solutions will lie at a jump of lcm(a1,b1) from x. BUT, while calculating x, x is getting overflow because of large value of x0 and a1, in test case 78, can anyone tell me how to solve it. Thanks
 » 2 years ago, # |   0 I have a (logn)^2 approach to solve problem, could be reduced to O(logn) if map is not used.I have a assertion that,let j=log2(i); the best way to reach i is, 1). either reach j and then use operation 1 (x) to reach i.2). either reach j+1 and then use operation 1 (x) to reach i.3). if i is even then reach (i/2) and use operation 2 (y) to reach i and if i is odd then reach (i/2 and do operation 1 and operation 2 to reach i) or reach (i/2+1 and do operation 1 and operation 2 to reach i ).These are the possible best transitions, and we easily calculate best way to reach i if i is power of 2.My submission:- https://codeforces.com/contest/710/submission/93869685
 » 23 months ago, # |   0 For C, the normal magic square solution also works ..since in that case the row,column and diagonal sums are equal to n*(n**2+1)/2 ..if you take n = 2*k + 1, n**2 + 1 = 4k**2 + 4*k + 2 ,so (n** + 1)/2 is odd..hence n*(n**2+1)/2 is also odd for odd n..this might be overkill though! https://www.geeksforgeeks.org/magic-square/
 » 22 months ago, # |   0 Problem F — String Set Queries can be solved using hashing. It seems easier to me than Aho-Corasik solution.
 » 8 months ago, # |   +10 Wow, I actually managed to solve a 2400 problem without looking at the solution! >.