### cyand1317's blog

By cyand1317, history, 9 months ago, ,

Hi, dear contestants!

With the end of Codeforces Round #431 (Div. 1 and Div. 2), some might be complaining behind the screen that problems are too tricky or hard, or have been struggling with some supposedly solvable problem... Yes, this time problems seem hard, but anyways, I hope they provided you with something, say rating, fun, ideas, or experience. I don't want to see anyone losing confidence because of failure (bad luck) in a single contest — please, don't do so.

Here are the hints, tutorials and codes for the problems. Feel free to discuss about problems in the comments, and point out if something is incorrect or unclear. Thank you!

Hint
Tutorial
Model solution

### 849B - Tell Your World

Hint
Tutorial
Tommyr7's solution (first idea)
Model solution (second idea)

### 848A - From Y to Y

Hint
Tutorial
Kalinin's solution
Model solution with knapsack (!)

Hint
Tutorial
Model solution

Hint
Tutorial
Model solution

Hint
Tutorial
Model solution

Hint
Tutorial
O(n^2) solution
Model solution

## Behind the scene and random things (read if tired of problemsolving)

Expand

Thank you for reading. Next round? Perhaps something more traditional, who knows? Believe me, I'll try harder if this happens.

Cheers! \(^ ^)/

UPD Packages for problems are uploaded. They are in Polygon format and contain everything including statements, tests & generators, validators & checkers, and solutions. You can download them from Google Drive or Baidu Drive.

•
• +214
•

 » 9 months ago, # |   +5 No hints for div 1 C?
 » 9 months ago, # |   +43 I would hardly call it editorial...
•  » » 9 months ago, # ^ |   +7 He said in the statement "Detailed tutorials will be available later."Though I don't really understand, why isn't the editorial done before the contest. Why schedule the contest, before the editorial is finished?
•  » » » 9 months ago, # ^ |   +11 Ah, I missed that it is not its final form.
•  » » 9 months ago, # ^ |   +33 "Editorials" originated as things like commentary, related discussions etc. The tutorials are not fully ready by now but I think quick hints may help some. Thank you for your patience.
•  » » 9 months ago, # ^ |   +7 When someone gets too famous for the super tricky problems in his contest
 » 9 months ago, # |   0 Having real tutorials would be nice. That way we could understand what the code is based on. For example what is the idea behind 848A?
•  » » 9 months ago, # ^ |   0 First add same characters together. If you add n characters, the cost will be . Though I can't prove there can't be a better cost, you can achieve it by adding the letters one another, so you have costs 1, 2, 3, ..., n which summarized results in the formula.Secondly you add same character groups together for 0 cost.For a given k you can always greedily take the highest x which for , add x same characters, and deduct from k. Repeating this process will result in a correct answer.
•  » » » 9 months ago, # ^ |   +16 It is actually not hard to prove that this is minimal. We claim that if the letter i appears cnt[i] times in the string, the cost needed to concatenate all the strings will always be . Consider any pair of letter in the string. If they're different, they will not contribute to the cost. If they're the same, the moment the string containing the first letter is concatenated with the string containing the second letter, this pair will contribute 1 to the total cost. Other than that, this pair will not contribute to the cost. Thus, the total cost is just the number of unordered pairs of same letters.
•  » » » » 8 months ago, # ^ |   0 how do you prove the greedy algorithm is correct?
•  » » » 9 months ago, # ^ |   0 Why can we greedily deduct? I did it like given n coins make a sum m but that was obviously an overkill. How to prove that we can use greedy for this one.
•  » » » » 9 months ago, # ^ |   +1 When you concatenate 2 strings the cost is the number of pairs (from the first string, from the second string) for each letter so the total cost is the number of pairs for each letter because each pair will be counted once.The greedy outputs a string of O(sqrt(n)) length.
•  » » » » » 9 months ago, # ^ |   0 We can take a maximum of 26 letters right? So what I did was dynamic programming to find which elements (taken any numbers of time) of the set {1,3,6,10,15,21..} will add up to k. But subtracting the maximum number less than equal to k also works. I couldn't prove that the number of characters used will be less than equal 26. How to do that?
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 You might need to take more than 26 letters... Starting from 26 * 25 / 2 + 1 in fact you need strictly more than 26 letters.Edit: if you meant letters as in 'a' to 'z', as I said the output is O(sqrt(n)) so it's easily less than the limit.
•  » » » » » » » 9 months ago, # ^ |   0 Thank you!
•  » » » » » » 9 months ago, # ^ | ← Rev. 3 →   +15 We work backwards greedily by taking the maximal element in the set you described and subtracting it from n at every step. Then worst case n is one less than an element in the set, or for some k. Then so after each operation, we get at most the square root of what we started with. Now it should be clear that 26 letters are more than enough, since n(1 / 2)26 <  < 1 + ε where n = 105.
•  » » » » » » » 9 months ago, # ^ |   0 Ok got it. Thank you very much! I did an overkill by using dp there :(
•  » » » » » » » » 8 months ago, # ^ |   0 I also use the dp solution, but could you please explain why the greedy algorithm is correct?
•  » » » » » » » 9 months ago, # ^ |   0 Nice!
•  » » » » » 8 months ago, # ^ |   0 how do you prove the greedy algorithm is correct?
•  » » » » » » 8 months ago, # ^ |   0 Each letter you use, transform n into O(sqrt(n)). That converges faster to 1 than dividing by 2 (that would be O(logn) letters needed) so there are enough letters.
•  » » » » » » » 8 months ago, # ^ |   0 thank you
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +3 Cost of adding n characters always is n * (n — 1) / 2. I prove it like this: Lets say cost of adding n characters is f(n), then: f(n) = f(x) + f(y) + x * y, such x + y = n. By induction if f(x) = x * (x — 1) / 2 and f(y) = y * (y — 1) / 2, then f(n) = n * (n — 1) / 2.
•  » » » » 9 months ago, # ^ |   +3 I think this is a really nice and neat proof. I have never thought about using induction to prove this conclusion. Thanks a lot for sharing such a nice idea.
•  » » » » » 9 months ago, # ^ |   0 You're welcome. Also there is another proof that I really like it.Consider a graph with n vertex and no edges at first (for each character we consider a vertex). Each time we merge x characters to y characters, that mean we connect edges between those x vertex to those y one. And our cost is equal to the number of edges we draw (x * y).At the end the graph is complete and the total cost is equal to number of edges of a complete graph with n vertex which is n * (n — 1) / 2.:)
•  » » » 5 months ago, # ^ |   0 actually Gauss prove that every natural number is written as at most 3 triangular numbers
 » 9 months ago, # | ← Rev. 3 →   0 Div2B can be solved with randomized algorithm. You need to choose two points randomly and check if the line going through these points can be one of these two lines which we are looking for. All you have to do now is repeat this about 100 times and you can be 99.999...% sure that if answer is "Yes" you found it at least once. Did anyone get AC using this method?
•  » » 9 months ago, # ^ |   +13 When we have 3 leftmost points there must be a line which is going through 2 of those points.
•  » » 7 months ago, # ^ |   0 Yep , got accepted . Thanks for the idea .Submission
 » 9 months ago, # |   +7 could not even solve A. i want to kill myself.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Hello, the solution to this problem was kept on this. Think about it. If you want, I can explain 29975733
•  » » 9 months ago, # ^ |   +24 Do not worry. As you practice more, you will do better. Trust yourself!
 » 9 months ago, # |   0 Can anyone please provide a more detailed explanation for div 2 D?
 » 9 months ago, # |   +3 Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
 » 9 months ago, # |   -10 Is it editorial or just solution codes?
•  » » 9 months ago, # ^ |   0 Detailed tutorials will be available later.
 » 9 months ago, # |   0 Div2B. What if all of these 3 points are lying on 1 correct line?
•  » » 9 months ago, # ^ |   0 Then answer will be No.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 like (1, 1), (2, 2), (3, 3), (4, 5), (5, 6). Why no??
•  » » » » 9 months ago, # ^ |   0 it's yes
•  » » » » 9 months ago, # ^ |   0 You asked "What if all of these 3 points are lying on 1 correct line?" the case of only 3 points.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 doesn't matter , because we are searching the set of points which doesn't belong to that line in the solution above marked with visited[i] =false; if no points found then no; if one point found then yes; else we check the rest of points belongs to the same line and it's parallel to the first one
•  » » 9 months ago, # ^ |   0 The first idea works without modification.You will check the same line three times, which will find the solution if the answer is Yes, and fail otherwise, because there must be one line passing through all three points in this case.
 » 9 months ago, # |   0 Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
 » 9 months ago, # |   0 Did anyone got accepted Div.1 C using sqrt query caching? i.e. blocking queries into sqrt blocks and solving the problem for each block. Time complexity of my solution is but my solution got failed (TLE).
•  » » 9 months ago, # ^ |   0 My solution with same time complexity passed(29992066).
•  » » » 9 months ago, # ^ |   0 My solution is exactly the same as yours... I think the problem is I used too many vectors.
 » 9 months ago, # | ← Rev. 3 →   0 Could someone explain the solution to div2B? (29992706) def chk(limit): return len(set(2 * yi - limit * i for i, yi in enumerate(y))) == 2 s = 2 * (y[1] - y[0]), 2 * (y[2] - y[1]), y[2] - y[0] print('Yes' if any(chk(x) for x in s) else 'No') 
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 you need to find out is there exisit two linesy = ax + b1 and y = ax + b2such that every points on it, and each line should have at least one point, so you could check for three cases: first point and second point at the same line first point and third point at the same line second point and third point at the same line (just like Tommyr7's solution (first idea) above)and 29992706 just try to find out if there exist b1 and b2, by counting 2by = ax + b2y = 2ax + 2b2b = 2y - 2ax
•  » » » 7 months ago, # ^ |   0 when you find a,b when, for example: y=7 5 8 6 9 so we have x= 1,2,3,4,5 what will you do with your function: y=ax+b ?
•  » » » » 7 months ago, # ^ |   0 y=ax+b is a form of line, so if you got a, b, then you got a line
•  » » » » » 7 months ago, # ^ |   0 thank you, btw, please answer me what is the main idea of Tommyr7's solution ?
•  » » » » » » 7 months ago, # ^ |   0 I think the main idea of Tommyr7's solution is that there only have 3 cases, just the same as what I've said above.
•  » » » » » » » 7 months ago, # ^ |   0 ok i get it, thank you.
 » 9 months ago, # |   +10 When I don't believe that div2 A is solving in so simple way and write dp :D
•  » » 9 months ago, # ^ |   +4 I know that feeling :D 29975756
•  » » 9 months ago, # ^ |   0 I know i'm not the only one :)
 » 9 months ago, # |   0 The problems were good yesterday. I was only able to solve only the first problem, but I got some satisfaction upon being able to solve it. It wasn't purely implementation-based, but also needed a good observation.Overall, Short, clean statements. Problems with some insight, not purely implementation. Model solutions enclosed in editorial in a nice format with drop down menus and hints I appreciate the writers of this contest for these points. However, it is difficult to understand for a beginner. Some more explanation would be good.
 » 9 months ago, # |   0 Div2D:Dancers in the same group will move on the same x + y line (a line of slope  - 1), and however collisions take place, they will keep current relative order of x and y.What does this mean? What is an x+y line?
•  » » 9 months ago, # ^ |   0 Their coordinates will always have the same x + y during movement. If A and B have the same x + y, and xA ≤ xB holds at the beginning, it will hold throughout the whole process.
 » 9 months ago, # |   0 Div2B In the first approach, " ans|=check(1.0*(a[3]-a[2]),a[2]*2-a[3]); " I cannot make the sense out of putting a[2]*2-a[3] in the second argument. In the check function, author has assumed the starting point to be 1. Ugh not making any sense to me, someone please explain!
•  » » 9 months ago, # ^ |   0 The b argument is the interception of the line. With the third case it should be a2 - (a3 - a2) = 2a2 - a3.
 » 9 months ago, # |   0 really wonderful tutorial !
 » 9 months ago, # | ← Rev. 2 →   0 Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).It would take a few minutes for the tutorial to get from Polygon to CF, stay tuned.
 » 9 months ago, # |   0 in question A how can u say if n is odd and a[0] and a[n-1] is "only case" where answer is yes.there may be some other cases......
•  » » 9 months ago, # ^ |   +8 If a valid way exists, then n, a1 and an are odd.If n, a1 and an are odd, then a valid way exists.So this condition is necessary and sufficient.
•  » » » 9 months ago, # ^ |   0 can you prove if n is odd or even and a[n-1] is not odd there cannot exist odd number of subsets[problem:849A]
•  » » » » 9 months ago, # ^ |   0 See the third example. It clearly illustrates that you need to use all the numbers given. That being said, we know the subsequence chosen should start and end by odd number, so if any of the endpoints i.e. 0th index or n-1 index is even cannot be included in any division since the above condition is violated. Hence proved.
•  » » » » 9 months ago, # ^ |   0 The answer is No not because of this. It's because if the last element is even, in every possible way to divide the sequence we'll have a segment that doesn't end with an odd number, which makes the whole division invalid.
•  » » » » » 9 months ago, # ^ |   0 what if n is even and a[n-1] is odd.Thanks in advance.
•  » » » » » » 9 months ago, # ^ |   0 For an odd number of segments of odd length each, the sum of their lengths has to be odd (say, sum of three odd numbers is odd, sum of five odd numbers is odd etc.). So for an even n there is no solution.
•  » » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 what if we have a sequence like 0 1 0? we can still get segment {1} which is odd?
•  » » » » » » » » 7 months ago, # ^ |   0 The entire sequence need to be divided, and all resulting subsegments should meet the requirement.In your case there will be two more subsegments consisting of only one element 0, which are invalid.
 » 9 months ago, # |   0 Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
 » 9 months ago, # |   0 Div2 D What is the custom sort doing. My implementation required a vector of tuple and two more 2D vectors of pair of ints. Can you explain what is happening in your sort. I cannot follow through.Also a general question, I have a hard time reading and understanding other's code. Any suggestions on how you approach it?
•  » » 9 months ago, # ^ |   0 For each x + y group, before everything starts, go down the left border of the stage and go rightwards along the bottom, record the order in which you meet dancers in it.After everything finishes, go rightwards along the top and then go down the right border and record the order. These two orders will be the same because they're actually sorting the dancers by their order from top-left to bottom-right, that is, "initial x values" (after moving them backwards in the first place) in the tutorial.
 » 9 months ago, # |   0 Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
 » 9 months ago, # |   +4 How to do 849B — Tell Your World if number of lines is a variable ?
•  » » 9 months ago, # ^ | ← Rev. 3 →   +18 SpoilerLet this number be m.Use the second idea from the tutorial. But instead we should iterate over a pair of points which is on the same line, and find out the slope k.Then we need to check whether all the points can be connected with m lines of slope k. For each point (i, yi), we calculate the interception bi = yi - i × k. Find out how many different bi's are there, and if this equals m, then the answer is Yes.This works in if sorting or std::set is used, or O(n3) if hash tables are used. I wonder whether a better solution exists.Thanks for the variation, I find it interesting :)
•  » » 9 months ago, # ^ |   +35 I set a more advanced version of this problem for CS Academy this summer, feel free to try it:https://csacademy.com/contest/round-38/task/parallel-lines/statement/
•  » » » 9 months ago, # ^ |   +14 Great, thank you!
•  » » 9 months ago, # ^ |   0 Great! Thanks both of you!
 » 9 months ago, # | ← Rev. 2 →   0 Found a test case for Div2 B but Can not find why the answer should be "YES"Test case:45 7 11 17Any help would be appreciated .
•  » » 9 months ago, # ^ |   +8
 » 9 months ago, # |   0 is div 2 B test case 13 wrong?5-954618456 -522919664 -248330428 -130850748 300848044try excel scatter chartGrade outputs yes, but I don't think so
•  » » 9 months ago, # ^ |   +11
 » 9 months ago, # |   0 I don't understand how to build the segtree for div1C — How should the tree handle the b.first >= l condition while the segment [l,r] remains as a continuous segment?
•  » » 9 months ago, # ^ |   +10 After dividing query on log to some nodes of segtree they transform to "get sum value of all b.first >= l from all elements which are controlled by fixed node", so if you sort all b.first in fixed node you get query on suffix.
•  » » » 9 months ago, # ^ |   0 Thanks for the details, now I get it. I've never thought of building the tree in this way before, I was stucked with having a fixed size node simliar to 2D BIT... =P
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 How to take care of updates?
 » 9 months ago, # |   0 Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
 » 9 months ago, # | ← Rev. 2 →   0 I don't understand Div2D/Div1B , so can anyone help me to explain this problem more clealy ? (sorry for my poor English :((( )
 » 9 months ago, # | ← Rev. 2 →   +3 Tutorial for 848B-Rooter's SongTwo points in the second paragraph, maybe it shall be...?(xi-ti, 0) -> (xi, -ti)(0, yi-ti) -> (-ti, yi)
 » 9 months ago, # |   0 In Tommyr7's solution for Div2.B, why is the second argument of the check function equal to 2*a[2]-a[3]? Shouldn't it just be a[2]?
 » 9 months ago, # |   0 Anyone who knows how to solve div1.C by Wavelet Tree?
 » 9 months ago, # | ← Rev. 2 →   +23 I have got a better algorithm on div1.E.At first we get a recursion, just like what the tutorial says.Let g0(x) = g(x) * x2, g1(x) = g(x) * (x + 1)2, g2(x) = g(x) * (x + 2)2.Then we use the generated function of sequence g0, g1 and g2, as well as sequence f0, f1 and f2Then we get equations below.F0(x) = G0(x) + G0(x)F0(x)x + G1(x)F1(x)x3F1(x) = G1(x) + G1(x)F0(x)x + G2(x)F1(x)x3F2(x) = G2(x) + G1(x)F1(x)x + G2(x)F2(x)x3Solve it, we getWe just need to calculate the first n+1 numbers of sequence f0, f1 and f2, so we can solve the equations modulo xn + 1, The complexity is just O(nlogn), better than the algorithm mentioned above.Here is my code.
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 How do you solve the equations?
•  » » » 8 months ago, # ^ |   0 The equations are all linear! Just like guass' algorithm, function G0(x), G1(x), G2(x) are all constants. At first we solve the previous two equations, we got F0(x) and F1(x), then there is F2(x).
•  » » 8 months ago, # ^ |   0 I had thought of solving the problem with polynomial multiplicative inverse, but due to my lack of familiarity with it, I kept the current constraints and the model solution. (Apparently I have a weak mind > <)Sorry for necroposting, but kudos! It's great to see a solution more elegant than the original one.
 » 8 months ago, # |   0 Did anyone got accepted Div.1 C using treap inside each node of segment tree? I am getting TLE with that approach, I expect the time complexity to be O((N+Q)log^2(N))
 » 8 months ago, # | ← Rev. 2 →   0 I have a question for div1E, when calculating the final answer.ans += g[i — 1] * (i — 1)_ * (i — 1)_ * f0[n — i — 1]_ * i _;The basic idea of counting rotations without duplication is multiplying (i-1) if the second opposite pair appears at index i. However I thought this could lead to counting one answer multiple times. For example, consider n=9 (18 flowers) with opposite pairs of (1,10),(4,13),(8,17) This would be counted 3 times because the second opposite pair appears at index 4. However if you rotate two units, it becomes arrangement with opposite pairs of (1,10),(3,12),(6,15) which will also be counted because its second opposite pair appears at index 3.If I misunderstood the solution, can someone help me?
•  » » 7 months ago, # ^ |   0 The original arrangement is counted three times: rotated by 0, 1 and 2 units anti-clockwise, respectively. The derivative you mentioned is the original one rotated by 2 units clockwise, hence it's not included in this case but counted in its own case instead.
 » 7 months ago, # |   +10 For Div2 C, this can also be used. Each number can be represented as the sum of 3 triangular numbers. ( A variation of the 3 squares theorem ) Just find 3 squares such that their sum is equal to 8*n+3.
 » 7 months ago, # | ← Rev. 2 →   0 I cannot help expressing my gratitude to the author,especially [Prob.E Shake it].Because the words expressed so clearly and I think the problem gave me much great thoughts.