halin.george's blog

By halin.george, history, 8 years ago, translation, In English

682A — Alyona and Numbers

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][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]). 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][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k][1]). 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][1] = max(d[i][j][k][end] + 1, d[i + 1][j + 1][k + 1][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).

  • Vote: I like it
  • +37
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

In E , How can we find the triangle of maximum area in N2 with convex hull and 2 pointers?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :((.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -58 Vote: I do not like it

        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)

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it -21 Vote: I do not like it

          我认为真正的算法竞赛更侧重于算法,而不是代码能力。

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            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.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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!

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

          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."

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

»
8 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Where is the English translation?

UPD: it is here...:)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Editoral in english will be tomorrow.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I see you, I am feeling upset regularly, because rus editorial unavailable

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Will the editorial be made available in English? Google translation does not make things clear :-(

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Editoral in english will be tomorrow.

»
8 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Why TLE ?? it's O( N*N*10*2 ) , I think it's OK code

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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).

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I have the same issue. I guess shuffling array before sorting should help.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got TLE in contest using an integer array, solved it after using PriorityQueue.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What i should do, if i use python? Try to choose other language

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

We can solve E in a similar way NlogN with three pointers using convex hell

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you elaborate?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +38 Vote: I do not like it

        I guess a convex hell would be better than a concave one... right?

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In E, my ternary search TLed on test 66, which is the last one. Why only one maxtest? Other tests pass in 30ms..

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

For A many did O(n) but O(1) solution is also there 18548281.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice, another O(1) solution: 18553601

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Dont know why but not able see the page of your link. Can u explain O(1) solution here.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You did it without loops and I did it with less divisions :D

        But thanks to you, I learnt something new

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
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. 
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    distance from 2 to 8 is 32 while a[8] is just 24

  • »
    »
    8 years ago, # ^ |
    Rev. 5   Vote: I like it +3 Vote: I do not like it

    Corresponding Tree:

    1
                       / +37
                      6
                     /  -34
                    7
                   /   -56
                  3
              -20/  \22
               2.    5
          +32 /       \-3
             8.        4

    Here 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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In C, while calculating the distance why do we have to take the maximum of 0 and cumulative edge length sum?

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +2 Vote: I do not like it

    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..

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem D div2? Any Ideas

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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

»
8 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain why you ignore the input of S variable? Tnx in advance. :)

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It looks like you've found new way to find the max-area triangle!

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Only looks that way at first sight, but it is not the case!

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by halin.george (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

;

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In D div2, is the case s[i] == t[j + 1] && adding both of them to the subsequence concluded?

»
8 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.. :(

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Yeah, I had to reread the statement twice to get the idea behind the task, so no worries ;)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/682/submission/18585400

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Full disclosure: I don't know the actual numbers on overhead. It probably depends on the JVM. 24 bytes is just a guess.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one explain problem A ?

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    check this soln: http://codeforces.com/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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You need to build another triangle, whose midpoints are the vertices of that maximum triangle.

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like 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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

can someone explain part D div 2 clearly using LCS terminology im finding it hard to understand

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 .

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
8 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody help me?

I am getting Runtime Error on Test 11 . Here is my submission :- http://codeforces.com/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/

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    IF problem C vertex <0 how to solve it???

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

IF problem C vertex <0 how to solve it???

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like 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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with the code? I can't find the mistake

http://codeforces.com/contest/682/submission/18889823

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can somebody please help me undesrtand why I get WA on test 17 for problem D? :(

http://codeforces.com/contest/682/submission/18956406

Whay am I missing...? Seems right to me..

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can't use LCS for problem D?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same doubt. LCS was my first intuition but found not even a single person solving it that way

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 D is simply LCS with a difference

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes even i think so . but i am unable to solve it that way , can you please share our solution abj

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't get what you meant by LCS with a difference. Can you please elaborate?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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