Переберем первое число пары, пусть оно равно x. Тогда нам нужно посчитать количество чисел от 1 до m с остатком от деления на 5 равным (5 - xmod5)mod5. Например, можно предпосчитать, сколько чисел от 1 до m с каждым остатком от 0 до 4.
Отсортируем массив. Заведем переменную cur = 1. Пройдемся по массиву. Посмотрим на очередное число. Если оно больше или равно cur, то увеличим cur на 1. Ответ — это cur.
Будем делать dfs. Пусть мы сейчас стоим в вершине u. Пусть v — это какой-то предок вершины u. Тогда dist(v, u) = dist(1, u) - dist(1, v). Если dist(v, u) > au, то вершина u заставляет вершину v грустить. Так что необходимо удалить все поддерево вершины u. Соответственно, в dfs можно поддерживать минимум среди dist(1, v), где v — это предок u(вершина, в которой мы сейчас стоим). И если разность dist(1, u) и этого минимума больше au, то удаляем au вместе со всем поддеревом.
Воспользуемся методом динамического программирования. Пусть d[i][j][cnt][end] — ответ на задачу для префикса строки s длины i и префикса строки t длины j, при том, что подпоследовательность, являющаяся ответом состоит из cnt подстрок. end = 1, если оба последних элемента данных префиксов строк входят в максимальную подпоследовательность и end = 0 в противном случае.
Находясь в состоянии d[i][j][cnt][end], можно добавить следующую букву в строках s или t, при том она не будет входить в ответную подпоследовательность. Тогда d[i + 1][j][cnt][0] = max(d[i + 1][j][cnt][0], d[i][j][cnt][end]), d[i][j + 1][cnt][0] = max(d[i][j + 1][cnt][0], d[i][j][cnt][end]). То есть новое значение end равно 0, поскольку новая буква не входит в ответную подпоследовательность.
Если s[i] = t[j], то, если end = 1, то можно обновить d[i + 1][j + 1][k][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k][1]). Поскольку end = 1, при добавлении элемента к ответной подпоследовательности, количество подстрок, из которых она состоит, останется таким же. Если end = 0, то можно обновить d[i + 1][j + 1][k + 1][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k + 1][1]). В этом случае новые символы, которые мы пытаемся добавить к ответной подпоследовательности, будут образовывать уже новую подстроку, поэтому в этом случае переход из состояния с k в состояние с k + 1.
Ответом будет являться наибольшее число среди состояний вида d[n][m][k][end], где значения k и end принимают всевозможные значения.
Найдем треугольник максимальной площади из всех треугольников, вершины которого — точки из данного набора. (за N2 с выпуклой оболочкой и двумя указателями). Утверждается, что если взять треугольник, на серединах сторон которого лежат вершины треугольника с максимальной площадью, площадь такого треугольника не превосходит 4S, и он содержит в себе все точки из набора. Допустим, что найдется точка, лежащая вне треугольника-ответа. Тогда можно из этой точки более длинную высоту на какую-то сторону опустить, следовательно мы нашли треугольник не максимальной площади(противоречие).
In E , How can we find the triangle of maximum area in N2 with convex hull and 2 pointers?
http://isolvedaproblem.blogspot.in/2011/08/maximum-triangle-area-part-1.html
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.net/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."
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.
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.
Why TLE ?? it's O( N*N*10*2 ) , I think it's OK code
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).
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.net/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.
I got TLE in contest using an integer array, solved it after using PriorityQueue.
What i should do, if i use python? Try to choose other language
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.
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?
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?
Click
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.
I guess mine was quite elegant: http://codeforces.net/contest/682/submission/18548146
Indeed :D thanks
Mine: 18548716
The 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 :D
But thanks to you, I learnt something new
distance from 2 to 8 is 32 while a[8] is just 24
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
Всем привет! Задачу С можно решать без поддержания минимума- запускаемых bfs из очередной вершины(изначально 1,dist(1)=0), смотрим очередного потомка u. Если dist(v)+edge(v,u)>a(u),то удаляем поддерево с корнем u. Иначе проверим,что dist(v)+edge(u,v)>0. Если это так,то dist(u)=dist(v)+edge(v,u),bfs(u),иначе dist(u)=0,bfs(u).
In C, while calculating the distance why do we have to take the maximum of 0 and cumulative edge length sum?
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.. :D
Here take this example: a[1]=a[2]=a[3]=10 (10 10 10)
1------->2---------->3
where 1->2 has weight -26 and 2->3 has weight 12 then dist (1,3) is -14 which is less than A[3](which is 10), but vertex 3 is sad as 2 is an ancestor of 3 & dist (2,3)>10..
Great explanation bro.
Вопрос по задаче С: 682C - Алёна и дерево.
18558082 — Как это решение получает ОК?
Такого не может быть, так на тесте где мы ничего не удаляем и в качестве дерева — бамбук длиной 100000 программа работает за n^2. Позже я увидел, что такого теста просто нет.
Как жаль, что такие ошибки все-таки есть...
How to solve Problem D div2? Any Ideas
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
В разборе задачи D в третьей строчке второго абзаца не хватает параметра [end] у динамики.
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? And
don'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).
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).
;
Looks legit, but can be faster. Here is O(1) time and O(1) space: 18547853.
also check out my submission . 18548281
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.
In D div2, is the case s[i] == t[j + 1] && adding both of them to the subsequence concluded?
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][2] array http://codeforces.net/contest/682/submission/18585400
I'm guessing it's the array overhead. Your innermost array is int[2], and you allocate 10'000'000 such arrays. An int[2] costs, say, 8 bytes for the two ints plus, I dunno, 24 bytes for the overhead. So, an int[2] 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[1001], 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 [2] size as last state. But in c++ [n][m][k][2] 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 ?
check this soln: http://codeforces.net/contest/682/submission/18553601
consider rem[i]=count nos. with remainder i when divided by 5 so we have rem[0],rem[1],rem[2],rem[3],rem[4]
for a given range[1...m] rem[0]=rem[1]=rem[2]=rem[3]=rem[4] = m/5; also remaining m%5 nos. will have to be added to each rem in order
also since (k*5+a)%5 + (j*5+b)%5 = (a+b)%5
where a,b,k,j are constants
so (no. which is divisible by k) + (no. which is divisible by (5-k) ) = no. divisible by 5
so here rem[0] nos. of first input m will pair with rem[4] 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
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.
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 .
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 this
vector<vector<pair<int,int>>> adj
this is huge, usually if im doing adj list, i also make an adj matrix xD
The question on the problem C. 5th test in this problem as follows:
8
2 19 83 95 9 87 15 6
6 16
7 98
5 32
7 90
8 37
2 -34
1 -83
answer: 5 My ans. is 6, because the subtree which top vertex is 6 have six vertexs to be deleted. Can you point out my mistake, please.
In problem C of Div 2, the sample test case given is:
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?
Imagine three nodes 1 -> 2 -> 3 with edges -10 10
From 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
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.net/contest/682/submission/18629666
My 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 just gave a virtual contest.In problem C,at first I made all the variables long long,the time of execution was 951ms — 18645079
Later,I made only the required variables long long,the time was 78ms. — 18645223
I 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.net/contest/682/submission/18772731 Thanks in advance.
I also had a similar approach, failed on test case 18.
http://codeforces.net/contest/682/submission/18863240
But when I do it the other way around — instead of counting the sad ones, I count the non-sad ones.
http://codeforces.net/contest/682/submission/18863306
It 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.
Can anyone help me with the code? I can't find the mistake
http://codeforces.net/contest/682/submission/18889823
Solved
Can somebody please help me undesrtand why I get WA on test 17 for problem D? :(
http://codeforces.net/contest/682/submission/18956406
Whay am I missing...? Seems right to me..
You have ll dp[MAXN+1][MAXN+1][MAXK+1][2];
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
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 abj
https://codeforces.net/contest/682/submission/74829248
I didn't get what you meant by LCS with a difference. Can you please elaborate?
In my code dp[i][j][k][0] 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][1] means the maximum length we have counted so far totally