### halin.george's blog

By halin.george, history, 6 years ago, translation, Let's iterate over the first number of the pair, let it be x. Then we need to count numbers from 1 to m with the remainder of dividing 5 equal to (5 - xmod5)mod 5. For example, you can precalc how many numbers from 1 to m with every remainder between 0 and 4.

682B — Alyona and Mex

Let's sort the array. Let cur =  1. Then walk through the array. Let's look at current number. If it is greater or equal to cur, then let's increase cur by 1. Answer is cur.

682C — Alyona and the Tree

Let's do dfs. Suppose that we now stand at the vertex u. Let v be some ancestor of vertex u. Then dist(v, u) = dist(1, u) - dist(1, v). If dist(v, u) > au, then the vertex u makes v sad. So you must remove the whole subtree of vertex u. Accordingly, it is possible to maintain a minimum among dist(1, v) in dfs, where v is ancestor of u (vertex, in which we now stand). And if the difference between the dist(1, u) and that minimum is greater than au, then remove au with the whole subtree.

682D — Alyona and Strings

Let's use the method of dynamic programming. Let d[i][j][cnt][end] be answer to the problem for the prefix of string s of length i and for the prefix of string t of length j, we have chosen cnt substrings. end = 1, if both last characters of the prefixes are included in the maximum subsequence and end = 0 otherwise.

When the state is d[i][j][cnt][end], you can add the following letters in the string s or t, though it will not be included in the response subsequence. Then d[i + 1][j][cnt] = max(d[i + 1][j][cnt], d[i][j][cnt][end]), d[i][j + 1][cnt] = max(d[i][j + 1][cnt], d[i][j][cnt][end]). So the new value of end is 0, because the new letter is not included in the response subsequence.

If s[i] = t[j], then if end = 1, we can update the d[i + 1][j + 1][k] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k]). When we add an element to the response subsequence, the number of substring, which it is composed, will remain the same, because end = 1. If end = 0, we can update d[i + 1][j + 1][k + 1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k + 1]). In this case, the new characters, which we try to add to the response subsequence, will form a new substring, so in this case we do the transition from the state k to the state k + 1.

The answer will be the largest number among the states of the d[n][m][k][end], where the values ​​of k and end take all possible values.

682E — Alyona and Triangles

Let's find the triangle with maximum area among ​​all triangles whose vertices belong to the set of points. (For N2 with the convex hull and the two pointers). We can prove that if we take the triangle, whose vertices are the midpoints of the sides of the triangle with maximum area, the area of ​​such a triangle is not greater than 4S, and it contains all the points of the set. Let us assume that there is a point lying outside the triangle-response. Then we can get longer height to some side of triangle, so we have chosen a triangle with not maximum area(contradiction). Tutorial of Codeforces Round #358 (Div. 2) Comments (141)
 » In E , How can we find the triangle of maximum area in N2 with convex hull and 2 pointers?
•  » »
•  » » » I copied the code there, modified, and spent half an hour debugging until I recognised that the code was wrong itself. But then I had only five minutes left :((.
•  » » » » Copied the code? Is that even legal? Why would you ever try to cheat on CF or such contests -.- ( It does not matter if it is just part of code)
•  » » » » » 我认为真正的算法竞赛更侧重于算法，而不是代码能力。
•  » » » » » » You'd better write English comments in codeforces.And you say that "I think the real algorithm competition is more focused on the algorithm, rather than code ability." Code ability is important to make you write robust programs, and can reduce the opportunity to make errors in your programs.As far as I know, in your country, many problems are about data structures and complex search problems, you can't solve these problems without code ability.Wish you to do better and better in algorithm competition.
•  » » » » » Really? But don't worry, dude, i was participating out of competition.By the way, does everyone really code standard algorithms like fast I/O, convex hull, Hungarian, Max Flow?
•  » » » » » » Looks like you are suprised that someone codes standard things (btw. I googled for "Hungarian" thing because I never saw it earlier in any textbook or website, and it does not look standard at all, but nvm)..Also I am suprised to see that someone does not implement these standard things.But I see many people downvoted my comment, so I wont tell any more...Not hating or anything, you have much better rating than me and I dont have right to tell you something, but just telling my opinion, sorry if you find it offensive!
•  » » » » » From the post:http://codeforces.com/blog/entry/456"15. Solutions and test generators can only use source code completely written by you, with the following two exceptions: 1) the code was written and published/distributed before the start of the round, 2) the code is generated using tools that were written and published/distributed before the start of the round."
•  » » 6 years ago, # ^ | ← Rev. 3 →   I beware to say a wrong thing, but I think I could prove that if we fix some point of convex hull, then take two points next to the fixed one clockwise, we should do such process: 1. move the furthest point (from fixed clockwise) clockwise, if it will increase area of traingle 2. else move the closest point clockwise, if it will increase area of triangle If both actions will decrease square, we have found the maximum area of triangle containing the fixed point. Applying that to all points takes N2.
 » 6 years ago, # | ← Rev. 2 →   Where is the English translation?UPD: it is here...:)
•  » » Editoral in english will be tomorrow.
•  » » I see you, I am feeling upset regularly, because rus editorial unavailable
 » Will the editorial be made available in English? Google translation does not make things clear :-(
•  » » Try using Yandex Translate, best option for translate from Russian :)I know it doesn't solve everything and I hope we get the English version soon, but it's a huge improvement compared with Google's translator.
•  » » Editoral in english will be tomorrow.
 » 6 years ago, # | ← Rev. 2 →   Why TLE ?? it's O( N*N*10*2 ) , I think it's OK code
•  » » 6 years ago, # ^ | ← Rev. 3 →   I guess the reason might be in your algorithm because the previous test case was larger and did fine but this test case the letters sequence is the SAME; recheck your recursive conditionals or even test it with a similar case (aaaaaaaaaa).
 » 6 years ago, # | ← Rev. 2 →   How can i solve B with java i have used fast I/O and same approach like everyone did But it gives TLE for last test case. here is my solution "18553075" You can find my solution from ranklist http://codeforces.com/contest/682/standings/page/8 you should took care of it before i have lost my submission :(please tell me if there is bug in my code.
•  » » I have the same issue. I guess shuffling array before sorting should help.
•  » » » If the test data is manually designed then what will be different with shuffled. May be all array elements have same value.
•  » » » » The reason is that the Java's Arrays.sort is a variant of quick sort and potentially could take quadratic time. Therefore a shuffling could potentially avoid this problem. In any case, if you use merge sort (guaranteed nlogn time complexity) it would work.
•  » » I got TLE in contest using an integer array, solved it after using PriorityQueue.
•  » » » Check my previous comment towards admin123 :) in case you are wondering why it works with PriorityQueue.
•  » » What i should do, if i use python? Try to choose other language
•  » » 6 years ago, # ^ | ← Rev. 2 →   Java uses Quick sort for primitive type sorting, and merge sort for Object Sorting.Quick sort runs in O(N^2) in the worst case, so that alone would TLE your solution. ( Also this does not occur in every problem, sometimes random test cases happen to do that, or the author does it on purpose).Alternatively, a nice strategy is to shuffle the array before you sort, or declare it as Integer/Long instead of int/long, that way it becomes an Object and runs in NLogN.
•  » » Instead Of an array I used arraylist, then used collections.sort(), that worked but i don't have any idea why arrays.sort() gave a TLE.
 » Hi! Are you planning to attach a solution code for each problem? Please :)
 » We can solve E in a similar way NlogN with three pointers using convex hell
•  » » Could you elaborate?
•  » » » Let us construct a convex hell. So we have an array of points in their order. Take three consecutive points. Move one point so that the area is maximum while two other points are fixed. The function of area turns out to be unimodal (or convex, I don't know how it's called). Then in the same way move the second point, after move the third, then the first and so on. In some moment we wouldn't be able to move point, that's the answer. Why? Let us draw three lines parallel to the sides of the triangle through our three chosen points. It's easy to see that all of the points in convex hell lay in the triangle, which is formed by the lines (otherwise we would find a triangle with greater altitude and better answer). It's obvious that we'll do it in linear time as no one point can't jump over other two and the third point won't go more than a circle.
•  » » » » I guess a convex hell would be better than a concave one... right?
 » Okay Mr.Tomorrow
 » In E, my ternary search TLed on test 66, which is the last one. Why only one maxtest? Other tests pass in 30ms..
 » I got a question for C. Let distance(u) is the total sum of the edge from vertex 1 to vertex u. When it's a negative number in total (less than 0) should we change the total distance to 0? If yes, why so?
•  » »
•  » » » nice explanation, thanks for linking that here
 » I did B just as most of them did i guess.i got tle on test case 112.what can be the problem?.i did it in c and used qsort inbuilt function.so max order is nlogn
•  » » Quick sort is fast on average but slow in worst case. Worst case is O(n^2), and that's too slow, that's why you got TLE
 » For A many did O(n) but O(1) solution is also there 18548281.
•  » » Nice, another O(1) solution: 18553601
•  » » » Dont know why but not able see the page of your link. Can u explain O(1) solution here.
•  » » » » Actually all the thing you do is to count the sum of the numbers whose remainders to 5 are {0,1,2,3,4}. So you just have to divide n and m to 5.Then you can find that the number you have got is the sum of every different remainder in [1,n — n Mod 5] and [1, m — m Mod 5]. Then you can count the left numbers and get the answer.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   I guess mine was quite elegant: http://codeforces.com/contest/682/submission/18548146
•  » » » » Indeed :D thanks
•  » » » Mine: 18548716The formula for number of numbers less or equal to n and divisible by 5 with reminder i is (n+(5-i))/5
•  » » » » You did it without loops and I did it with less divisions :DBut thanks to you, I learnt something new
 » 6 years ago, # | ← Rev. 2 →   Somebody,please explain why in problem C : Alyona and the Tree, testcase 4: 8 53 41 22 22 34 95 56 24 3 -20 7 -56 5 -3 3 22 1 37 6 -34 2 32 the correct answer given is 1. Acc. to me answer should be 0. 
•  » » distance from 2 to 8 is 32 while a is just 24
•  » » 6 years ago, # ^ | ← Rev. 5 →   Corresponding Tree: 1 / +37 6 / -34 7 / -56 3 -20/ \22 2. 5 +32 / \-3 8. 4Here as u can see.. The distance between v=2 & u=8 I.e dist(v,u):dist(2,8)=32 which is greater than A[u=8] which is 24.. Hence 8 is sad vertex & we should remove it.. Hope u get it.. :D
 » In C, while calculating the distance why do we have to take the maximum of 0 and cumulative edge length sum?
•  » » 6 years ago, # ^ | ← Rev. 3 →   Let us assume the maximum distance of a node u from its any ancestor is the distance of a node from root i.e 1. But there may exist a node x which is also ancestor of u, such that: dist (1,x)<0 & dist (x,u)>0: then dist (x,u)>dist(1,u)Now, dist (1,u) may be less than A[u] but dist (x,u) may be greater than A[u]. But if we would have taken dist(1,x)=max(0,dist(1,x)) then we would get maximum distance poosible from u to its ancestor.. :DHere take this example: a=a=a=10 (10 10 10)1------->2---------->3where 1->2 has weight -26 and 2->3 has weight 12 then dist (1,3) is -14 which is less than A(which is 10), but vertex 3 is sad as 2 is an ancestor of 3 & dist (2,3)>10..
•  » » » Great explanation bro.
•  » » Ugh ._. I overlooked this critical observation and ended up being 2 lines of code from AC :\
 » How to solve Problem D div2? Any Ideas
•  » » 6 years ago, # ^ | ← Rev. 2 →   Its similar to lcs problem. There are four cases to be considered.Say u found the answer for p strings.Now 1. if (s[i]==t[j]),we can combine the current character with pth string only if pth string ends with the match at index i-1 of s and j-1 of t or 2. if(s[i]==t[j]) we can make a transition to p+1 string with s[i] as the starting character of the p+1 th string or 3. increment i or 4 increment j Answer is max of all these four cases
•  » » » can someone explain part D div 2 clearly using LCS terminology im finding it hard to understand im a noob so pls a easy and detailed approach will be deeply appreciated
•  » » » hello. thanks for the logic. i had followed this logic without reading it. but somehow my test case 2 fails every time. can someone help me sort out the problem in my code.even some advice would be beneficial for me.here is my code; http://codeforces.com/contest/682/submission/26141571
 » 6 years ago, # | ← Rev. 2 →   In E, I got AC for an alternative solution. One may note that instead of the max-area triangle ABC, it suffices to find a triangle ABC such that for each D the inequality holds:area(ABC) >= max(area(ABD), area(BCD), area(CAD)), where A, B, C, and D are in the input set. These inequalities mean precisely that each point D lies inside the triangle that has A, B, C for edge midpoints.To find such ABC, simply start with an arbitrary nondegenerate ABC. If the inequality is violated for some D, replace one of A, B, or C, with D. Repeat until the inequality becomes true for all D. The area of ABC keeps growing, so the process will end eventually.The obvious upper bound for this is O(N^4): inequality verification takes O(N), and the triangle can grow O(N^3) times. I was expecting a TLE, but got AC. Maybe this solution has a better provable upper bound, but it's not obvious. It's also not that obvious how to make an input that will result in TLE.The code is here: 18563426.
•  » » PS: I'm talking about oriented areas here, of course, otherwise the inequality doesn't imply containment in the "doubled" triangle. Also, area(ABC) > 0.
•  » » » Oops, looks like I'm wrong here, and the same solution should work for non-oriented areas as well. But that's not important. The interesting thing here is execution time.
•  » » Your submission is same as 18555613. Isn't your solution linear time? Anddon't you find the triangle with largest area as described in editorial?
•  » » » Why would it be linear time? The inner loop is linear, but the number of iterations of the outer while loop may be large.And no, this solution won't necessarily find the triangle with the largest area, although it may seem so at first sight. For a counterexample, consider 6 points: A(0, 0), B(2, 0), C(0, 2), P(2, 2), Q(-1, 2), R(2, -1). If we begin with triangle ABC, it will satisfy all the inequalities and will be printed in the output, even though triangle PQR has greater area.
•  » » Could you please explain why you ignore the input of S variable? Tnx in advance. :)
•  » » » I ignore it because, as you can see, it doesn't appear in my solution plan. My solution outputs a triangle A'B'C' whose edge midpoints are A, B, C. Obviously, area(A'B'C') = 4*area(ABC), and area(ABC) <= S because this is guaranteed in the problem statement (recall that points A, B, C belong to the input set). So we have area(A'B'C') <= 4S automatically.The same applies to the solution in the editorial, by the way.
•  » » » » Thank you!
•  » » It looks like you've found new way to find the max-area triangle!
•  » » » Only looks that way at first sight, but it is not the case!
 » Auto comment: topic has been updated by halin.george (previous revision, new revision, compare).
 » 6 years ago, # | ← Rev. 5 →   [deleted]
 » In problem A, I don't think we need to use any array as I came up with this solution in O(n + m) time and O(1) space For each i <= n, we will get the pairs which sum up to i + 1, i + 2, ..., i + m, and we can calculate the numbers of mutiples of 5 in O(1). int res = 0; for (int i = 1; i <= n; ++i) res += (i + m) / 5 - i / 5 ;
•  » » Looks legit, but can be faster. Here is O(1) time and O(1) space: 18547853.
•  » » » also check out my submission . 18548281
•  » » look at my comment above that is exactly what I did also how is that O(n + m) looks O(n).
•  » » how you think this,,i could't think this type,,only brute force approach just come to my mind.. i feel sad for me that i can't optimization solving
 » 6 years ago, # | ← Rev. 3 →   For problem A, I tried with this solution, http://codeforces.com/contest/682/submission/18580227 . Comments pls..
 » 6 years ago, # | ← Rev. 2 →   Hello guys, could someone clarify the problem A to me? I tried to understand the Editorial and others codes, but it was not clearly for me. Sorry for my inability on this.During the contest I tried to get some patterns between each set, but I failed. A pattern that I found was round(n*m/5)works, it works in almost case.Thanks!!
•  » » round((n*m)/5) doesn't always work. I got +100 points cause someone used the same round((n*m)/5) formula and I hacked him ;) . The way to think about is is like this.for any given x you can at most have (x+m)/5 such y's that x+y%5==0; however out of those n/5 are not possible as y can't be less than or equal to 0look at my comment above.
 » Can someone explain me how can we remove subtree in problem C? Generally, how can we remove vertex from graph, or tree..Literally delete it from adjacency list/update in adjacency matrix/etc. or?
•  » » You shouldn't focus on actually deleting nodes from the Tree. As far as you find the maximum distance from each node to any of it's ancestors (not just the root, as the root sometimes is closer than others). If it's at a furthest distance than it's current number, you have to take it out and it's whole subtree (because you have to remove it's leaves first before actually taking it out itself).
•  » » You can do it in reverse way actually (me do the same). Other than search for how many "sad vertex", you can count how many "not sad vertex" in the tree and get the answer by subtracting N and no. Of not sad vertex.As long as you maintain the maximum distance from vertex u from its parent, you can decide whether it's a sad vertex or not.
•  » » Just count the number of nodes in subtree you want to remove and add this number to answer . You dont actually have to remove it.
 » In D div2, is the case s[i] == t[j + 1] && adding both of them to the subsequence concluded?
 » 6 years ago, # | ← Rev. 2 →   I have problems with understanding Problem C, not solution but description and sample test case.Lets talk about sample test case Why do we need to remove vertexes 4 and 9? Maybe I dont know definition of subtree, but I dont know why 4 and 9 are making any other vertex before them sad! Now, tell me if I dont know what is subtree; I think that vertex 4 does not have any vertexes in its subtree. Also, vertex 4 is in subtree of only root of tree, so it does not make root sad and we dont need to remove it.Please respond because I want to understand the problem. UPD: I got it, didnt read the task well
•  » » Vertex v is sad when the distance from v to another vertex u that is in its subtree is bigger than a[u]. Distance from vertex 1 to vertex 4 is equal to 67, which is bigger than a4, thus it makes vertex 1 sad, so we have to remove it. Similarly, distance from vertex 1 to vertex 9 is equal to 78, which is bigger than a9, so we have to remove vertex 9, and consequently, the whole subtree of vertex 9 too.
•  » » » Oh I didnt read problem well, I thought that vertex is sad if its distance to another vertex is bigger than number on ITSEFL, not the number on that vertex.. :(
•  » » » » Yeah, I had to reread the statement twice to get the idea behind the task, so no worries ;)
 » In D , why is my soln giving memory limit exceeded on n=1000 m=1000 k=10 I have used dp[n+1][m+1][k+1] array http://codeforces.com/contest/682/submission/18585400
•  » » I'm guessing it's the array overhead. Your innermost array is int, and you allocate 10'000'000 such arrays. An int costs, say, 8 bytes for the two ints plus, I dunno, 24 bytes for the overhead. So, an int is 32 bytes. And you are allocating that times 10 million, which is 320M — beyond the limit.Maybe your solution will pass if you change the order of indices, so that the innermost array is int, the losses on overhead will become way smaller.I may be wrong, of course, but this is my best guess.Also, this may be useful: http://stackoverflow.com/questions/2972578/how-calculate-java-array-memory-usage
•  » » » Full disclosure: I don't know the actual numbers on overhead. It probably depends on the JVM. 24 bytes is just a guess.
•  » » » Thanks. That was the problem To do further checking i checked some passed solutions in java None had the  size as last state. But in c++ [n][m][k] state array had been succesfully passed . I guess in java its better to initialize in increasing order of sizes
•  » » » » Yep. In C++ multidimensional arrays aren't that different from one-dimensional ones: it's just a chunk of memory of n*m*k*2 ints, with no overhead, so the order doesn't matter.
 » can any one explain problem A ?
•  » » 6 years ago, # ^ | ← Rev. 3 →   check this soln: http://codeforces.com/contest/682/submission/18553601consider rem[i]=count nos. with remainder i when divided by 5 so we have rem,rem,rem,rem,rem for a given range[1...m] rem=rem=rem=rem=rem = m/5; also remaining m%5 nos. will have to be added to each rem in orderalso since (k*5+a)%5 + (j*5+b)%5 = (a+b)%5where a,b,k,j are constantsso (no. which is divisible by k) + (no. which is divisible by (5-k) ) = no. divisible by 5so here rem nos. of first input m will pair with rem nos. of 2nd input n to give nos. divisible by 5.The solution is clear
 » in the editorial you said: "We can prove that if we take the triangle, whose vertices are the midpoints of the sides of the triangle with maximum area, the area of ​​such a triangle is not greater than 4S, and it contains all the points of the set."In the example a triangle with maximum area is (0; 0), (1; 1), (1; 0). If we take midpoints of each side, the resulting triangle doesnt cover all points. Where am i mistaken?
•  » » You need to build another triangle, whose midpoints are the vertices of that maximum triangle.
•  » » » thanks I got it.
 » Can anyone tell why this solution is getting TLE for problem D. I have applied recursive solution with memoization. I think its because of memory declaration. Just creating array of 1000 x 1000 x 10 x 2 will give TLE in Java?
•  » » This solution passed quite easily. I changed the order of dp array. Now its size is 2 x 10 x 1000 x 1000. From now onward I'll always declare array in increasing order of sizes.
 » can someone explain part D div 2 clearly using LCS terminology im finding it hard to understand
•  » » You can refer to my code. I have written the detailed idea in my comment.
 » 6 years ago, # | ← Rev. 2 →   In problem C, I didn't understand why when dist(v, u) > a(u) we should remove a(u) with the whole subtree , because in that subtree we can find a a vertex w satisfying dist(v, w) <= a(w), so no need to remove it ,right ?
•  » » Well, that's an interesting question. I was confused for about 30 minutes in the contest about the right of the algorithm.However, it is right that there is only one way to build such a tree which is satisfied the condition of the problem.Proof: Vertex u becomes a leaf, if and only if all of the subtree of vertex u has been removed before. So if there is an ancestor of u, for example v, such that dist(v, u) > a(u), we have to remove u with its whole subtree, although we can find a vertex w satisfying dist(v, w) <= a(w), as you said.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   Well i think i misread this part "Thus Alyona decided to remove some of tree leaves" i thought we can remove any vertex , thanks for your reply .
•  » » » Where is the proof?!
 » 6 years ago, # | ← Rev. 2 →   Did anyone find or made proof for E (proof that area of constructed triangle is < 4S? Also, did anyone solve the problem without constructing our triangle from midpoints of max triangle? Because this solution is really weird for me...Its logical to look at largest triangle, obviously, BUT HOW IN THE WORLD WOULD YOU COME UP TO IDEA TO CONSTRUCT A NEW TRIANGLE BY USING VERTICES FROM LARGEST ONE AS MIDPOINTS FOR NEW ONE?Also, I dont understand proof that all points will be inside contructed triangle..Its literally one-line proof and I dont even think its legitimate proof.. UPD: I proved that area of constructed triangle is <4S, proof is actually really trivial and I got it when I went to sleep, after I wrote this comment xD Also, I think i understood why all points will lie inside constructed triangle, this link helped me to understand, so maybe you will want to check it; http://isolvedaproblem.blogspot.ba/2011/08/maximum-triangle-area-part-1.html
 » how to save the distances of the vertex in problem C?i did something like int adj[n][n], since n<=10000, it got memory limit exceeded
•  » » You don't need to store distance between all the points.You just need maximum distance of given point from all the ancestors of that point.With that you can decide whether you need to remove this point or not.And obviously that memory you are using is too much.
•  » » just read someones code, turns out you can modify the adj list like thisvector>> adjthis is huge, usually if im doing adj list, i also make an adj matrix xD
 » In problem C of Div 2, the sample test case given is: 9 88 22 83 14 95 91 98 53 11 3 24 7 -8 1 67 1 64 9 65 5 12 6 -80 3 8 The problem could be solved in 3 moves I guess: First when you are at node 1, you will calculate distance of all nodes from 1. You will find that nodes 2, 4, and 9 have distance from 1 greater than the value associated with the respective nodes. So we need to remove just three sub-trees: 4, 2 and whole sub-tree of 9. Am I going wrong somewhere?
•  » » 6 years ago, # ^ | ← Rev. 2 →   Imagine three nodes 1 -> 2 -> 3 with edges -10 10From node 1 to 2 it's -10, and from 1 to 3 it's 10 not 0, the problem statement says that if the distance from vertex U and a vertex V in sub tree of U exceeds a certain value then V is a sad vertex, 1->3 isn't sad but 2->3 is, so you need to be careful while calculating max distance to V vertex: max(0, distance_so_far) + edge to V vertex, as the distance so far can be negative, so we don't necessary regard vertex 1 as the U vertex in all cases
•  » » » I think I get your point! Thanks! :-)
 » The proof for Problem E with a picture (and other similar problems) can be found in Problem-Solving Strategies by Arthur Engel, as an example in his section on the extremal principle (some basic info about it is here: http://www.cut-the-knot.org/WhatIs/WhatIsExtremalPrinciple.shtml, which also uses this problem as an example), a proof technique that relies on using the extrema of given sets in often non-trivial ways.
 » Can somebody help me? I am getting Runtime Error on Test 11 . Here is my submission :- http://codeforces.com/contest/682/submission/18629666My convex hull generating code is probably correct because I got AC on this SPOJ Problem :- http://www.spoj.com/problems/MTRIAREA/
•  » » int -> long long
•  » » » I tried that too . Still not working. Here is my submission with long long getting RE :- http://codeforces.com/contest/682/submission/18629979
 » Can someone help me on problem D? My code doesn't generate error on my machine but it says Runtime Error on codeforces.I didn't use the method written in the tutorial. Instead, I used a recursive method(The method can be further improved). I will use the 2nd given example in the problem when describing my solution. The idea is following: We find the longest common substring(abbreviated as LCS) in s and t. For example, in s = bbaaababb, t = abbbabbaaaba, the LCS is bbaaaba, which is s[0:7), t[5:12). Then we push the length 7 to a vector. Next, we recursive on the remaining string. Since we have to preserve the order. We can only compare s[0:0) and t[12:12) which is a base case since left index == right index and return from the function. We keep doing above two steps until the function return. Now the vector ans has several numbers. We do a sorting in decreasing order. Then we take the first k numbers if ans.size() >= k or all the numbers if ans.size() < k. In this example, there is only 1 number 7 so we take it. The final answer is always correct. The reason is that even we only have 1 number, but we need 4, we can always break this substring of length 7 into 4 different parts. My code is here. Please help me find why there is a Runtime Error. Thanks!
 » I just gave a virtual contest.In problem C,at first I made all the variables long long,the time of execution was 951ms — 18645079Later,I made only the required variables long long,the time was 78ms. — 18645223I know operations on long long takes time.But This is a huge difference. Why this much difference?
•  » » IF problem C vertex <0 how to solve it???
 » IF problem C vertex <0 how to solve it???
 » In Problem C I got wrong answer in test case 27. My logic is:For a node if summation of edge values from ancestor greater than a[node] or summation of continuous positive edge values [which must be connected to that node] greater than a[node] remove and count all the childs including that node is the answer.Source code: http://codeforces.com/contest/682/submission/18772731 Thanks in advance.
•  » » I also had a similar approach, failed on test case 18.http://codeforces.com/contest/682/submission/18863240But when I do it the other way around — instead of counting the sad ones, I count the non-sad ones.http://codeforces.com/contest/682/submission/18863306It works like magic, I guess somewhere somewhere somewhere in the sad sub-tree contains a trap which causes our algorithm to miscount, but still , I have to idea what is the exact cause of this.
 » In C, i am getting wrong answer on test case 27. plz help. http://codeforces.com/contest/682/submission/18877016
 » In C, i am wrong answer on test 27. plz help http://codeforces.com/contest/682/submission/18877016
 » Can anyone help me with the code? I can't find the mistakehttp://codeforces.com/contest/682/submission/18889823
•  » » Solved
•  » » » Hello! Seems that you had the same problem I have now. On test 17, I get 239 the answer. How did you solve it? Could you tell me what did you change and why, please? Here's my submission:http://codeforces.com/contest/682/submission/18956406
 » 6 years ago, # | ← Rev. 2 →   Can somebody please help me undesrtand why I get WA on test 17 for problem D? :( http://codeforces.com/contest/682/submission/18956406Whay am I missing...? Seems right to me..
•  » » You have ll dp[MAXN+1][MAXN+1][MAXK+1];But at the code you work with the third dimension from 1 .. p (inclusive). But MAXK+ 1 == 10, instead of 11, fix it
 » Why can't use LCS for problem D?
•  » » same doubt. LCS was my first intuition but found not even a single person solving it that way
 » 6 years ago, # | ← Rev. 3 →   In problem B I have seen code of mkirsche for problem http://codeforces.com/contest/682/status but not getting any idea what's the use of this part of code: ~~~~~ Random r = new Random(); for(int i = 0; i<100000; i++) { int a = r.nextInt(n), b = r.nextInt(n); int temp = as[a]; as[a] = as[b]; as[b] = temp; } ~~~~~It seems that it is only swapping two random index but not getting idea what the use of it before sorting, Will it do sorting faster ? help me
•  » » That is the part of code which he has used for testing his solution.
 » For the problem Alyona and Mex, why is a Java solution accepted when an array of type Integer[] is used but TLE when the same algorithm is used with an array of type int[] or long[]?URL to problem, accepted, and TLE solutions are given below: Problem URL:http://www.codeforces.com/problemset/problem/682/B Accepted:http://www.codeforces.com/contest/682/submission/19309197 TLE: http://www.codeforces.com/contest/682/submission/19309219
 » i didn't understand the tutorial could some one explain it easier from where he got this formula
 » Div2 D is simply LCS with a difference
•  » » yes even i think so . but i am unable to solve it that way , can you please share our solution abhj
•  » » »
•  » » » » I didn't get what you meant by LCS with a difference. Can you please elaborate?
•  » » » » » In my code dp[i][j][k] means the maximum length we have counted so far including the kth sequence where we necessarily take s[i]==t[j] in the kth sequence and dp[i][j][k] means the maximum length we have counted so far totally
 » In problem A , we are fixing one number and getting all other numbers with rem = 5 — x%5 which can be 1,2,3,4how we are calculating such numbers with 1+((y-rem)/5) can someone explain???code: int x, y; cin >> x >> y; int cnt{ 0 }; for (int i = 1; i <= x; ++i) { int x = (i % 5); int rem = (5 - x); if (rem <= y) cnt += 1 + ((y - rem) / 5); } cout << cnt;