havaliza's blog

Codeforces Round #168
By havaliza, 12 years ago, In English

Hi everybody! :)

Codeforces Round #168 will start in hours. haas and I (havaliza) are the authors of today's match. I'd like to thank Gerald and Delinur for helping us to prepare this contest and MikeMirzayanov for this great platform.

Hope you enjoy solving the problems as much as we enjoyed preparing them. ^.^

Good luck and have fun. :)

UPD1.

Score distribution will be:

Div2 = standard

Div1 = 500-1000-1500-2000-2000

UPD2.

Congratulations to the winners of both divisions. It's nice that after the contest all five winners of first division are red coders and all winners of the second division are first division coders!

Div1:

  1. rng_58
  2. Petr
  3. Komaki
  4. msg555
  5. maksay

Div2:

  1. qph-Jeremy
  2. dojiboy9
  3. FreezingCool
  4. Hellis
  5. yplusplusplusplus

Editorial is out and will be completed soon. :)

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

Comments Comments (124)
| Write comment?
»
12 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Two authors of Round 168 from Iran,BAYAN Contest at Iran. Iran dominates on CF website :) will Iranian authors give us high rates & successful challenges ?

→ Reply
»
12 years ago, # |
  Vote: I like it -40 Vote: I do not like it

GL & HF !!!

→ Reply
»
12 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Most of CF's contests take place in the same days of week, is there any special reason or it is accidental ?!

→ Reply
»
12 years ago, # |
  Vote: I like it -26 Vote: I do not like it

What will the points division in Division 1 ? Thanks .

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Will be announced 5-15 minute before the contest.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -30 Vote: I do not like it

      Thanks for the info . Why is my comment hidden saying " too negative .. " . I was only asking the points division .

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        I'm guessing because everyone asks that before the contest and it's getting annoying.

        → Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

The post says : Score distribution will be: Div2 = standard Div1 = 500-1000-1500-2000-2500 What is standard points division ? I used to think the points division mentioned for Division 1 above is the standard division where every consecutive problems is 500 points more worth than previous problem .

→ Reply
»
12 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Who is mrsa_91 and why he is expert?he haven't enough rating to be expert but he is expert...

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

The scoring for div1 was so weak ...

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone please explain the Div2-D statement? I found it confusing. How can we choose the subtree?

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

    Any subtree containing node 1

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

      Can I only select vertices and edges so that every vertex has a direct path to vertex 1?

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

        If I understood you well, no, you can select bigger subtree too not only the neigboring vertexes to node 1...

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

          I said direct path, not edge. For the tree 1 -> 2 -> 3, can I select subtree 1, 3 ?

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

            but vertexes 1 and 3 are not a tree or I misunderstood you example...

            → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice problems specially Div2-D & Div2-E , but I couldn't solve them on time :)

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

B was harder than C in div-2

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

I didn't have time in contest to finish my E problem, so I'd like to ask if this algorithm is ok for solving this one:

I tried to find all triangles, that are not containing other points in it or at the edge. And from such triangles the answer is diameter of circumscribed circle. What do you think about this. I'm not sure about the limit, because finding such tringles in my implementation is O(n^4) where max(n) is 100...

Is it worth to try to finish it?

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

    no, there is many things more to consider.

    for example obtuse triangle don't create any hole.

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

      iff there is no triangle I'm printing -1

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        you didn't understand me.

        for example test case:

        3
0 0
1 1
2 0

        the answer is -1 although there is one triangle

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I see, now it's clear to me, thanks for your replies ;-)

          edit: it seems that additional check that center of the circle is in the triangle solves this problem

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

            but a square shaped 4 dots will not form a hole with any three of them, but creates a hole eventually in the center of the square

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

            No , take this test:

            4
0 0
0 1
1 0
1 1

            as you say "check that center of the circle is in the triangle solves this problem"

            so you sould answer this test by -1 but the correct answer is sqrt(2)/2

            → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Something is wrong with Div2-B :) Why so many WAs ?

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I got 6 WA on problem c, because of long long :(

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

in problem C(div 2) my algorithm was so

for example n=8 k=3 array(1,6,2,9,3,7,5,4)

sort array: 1,2,3,4,5,6,7,9

I Divide array with sub arrays: {1,3,9},{2,6},4,5,7 so that in each sub array was x,k*x,k^2*x,k^3*x and so on.

and that ans will be sum of (each array length)/2+(each array length)%2+(num of arrays which consist only one element) ans=(3/2+3%2)+(2/2+2%2)+3=6

this solution got WA6 what is wrong?

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it -25 Vote: I do not like it

Test case #11 Problem B div2

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Div1-A failed because of the anti-quick sort cases .. (where Arrays.sort becomes n^2 in java) Second time to lose a problem because of the same problem, I think you guys need to prevent such cases because it's completely ridiculous.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Always shuffle before sort, fellow Java coder!

    public static int[] shuffle(int A[])
	{
	int N=A.length;
	for(int i=1;i<N;i++)
		{
		int j=(int) (Math.random()*100000)%(i+1); // 0<=j<=i;
		int temp=A[i];A[i]=A[j];A[j]=temp;
		}
	return A;
	}
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      or you can just replace int with Integer and long with Long

      long[] a = new long[n]; TLE

Long[] a = new Long[n]; AC

      This is because objects are sorted using merge sort instead of quick sort

      → Reply
»
12 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Fantastic problems. Truly thanks for your great problem set. Wish to see more contests like this. HF & GL!

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it -9 Vote: I do not like it

А что такого в D на 12ом тесте?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Again, my solution 3159034 for C received TL because Arrays.sort seems to be slow for some special cases, I think my solution is efficient.I changed int[] for Integer[] and it got AC(3162097), I guess that the sorting method for Integer[] is not randomized( perhaps a merge sort), is this true?

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

    Integer is object , and all objects are sorted with merge-sort in java.. I got the problem failed for exactly the same reason..

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

      ma 5alas fahamna :D

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        ya 3am mateseeb el ragel fe ely howa feh :D

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

      Mine strangely failed because HashSet is apparently less efficient than a TreeSet in this case.

      3162811 vs 3162830

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

        Blog entry about this test case

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it -6 Vote: I do not like it

          CF really needs top stop messing with java programmers. Can't use this, can't use that! :[

          As a programmer you think to yourself and say HashSet is faster than a TreeSet. But If you force all inserts into one bucket then obviously a HashSet is no better than an ArrayList. I just need to remember to code for the worst case instead of the average case on CF.

          → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Try not using modulo and division. Those are REALLY slow.

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      lol C++ (FTW) :p

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

    Aside from the apparent bias towards C++ programmers, do you guys know why they don't do the same for the C qsort / C++ sort? Is it randomized or very difficult to hack?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      std::sort uses an algorithm called introsort which has a worst case complexity of O(N log N). Basically it initially uses quick sort but switches to heap sort when the recursion depth gets too large.

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

        Now I understand why such anti-quicksort test cases can not be made for C++ sort. Thanks for replying.

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

    Actually, one possible solution is changing the language of the submission to java 7. That way it uses the tim-sort of java 7 which guarantee n log n worst case.

    → Reply
»
12 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Авторам спасибо. норм контест)

→ Reply
»
12 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I got WA in problem B Div. 2 because I've mistyped M with N ... :((

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

OH GOD WHY?

i'm from 1534 to 1699 points :(

can somebody give me one point :(

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I used breadth first search for all vertices with priority Q in Question B Div2. if all black nodes cant be visited the answer is NO and if the no if direction changes >=2 answer is NO the direction changes if the current direction in which a node is accessed is perpendicular to the direction of neighbouring node...

Is this correct approach?

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

    You need to make sure that you can reach every other black node from the black node that you pick as a starting point. Yes, your constraints are correct. I followed a similar approach. 3162770

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

    I solved this problem with a meet-in-the-middle technique approach, O(n^5) I believe this can be improved, but I didn't care too much about this as this passes within the limits...

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

    My solution failed for test 26. Anyone knows what's the complete test case ?

    → Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I cannot wait to see the rating to be updated!

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you very much for contest.

I am very happy right now because my raiting has grown.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any one who got accepted problem B-div2 with O(n^5) algorithm?

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

    There are solutions with O(n^4) complexity, but i don't think there is any solution with O(n^5) algorithm at all

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Consider any 2 black cell & check 2 possible paths between them with O(n + m) ! I know it's the simples algorithm, but I thought it would get TLE! :(

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

        I got AC with O (n ^ 4) for bruteforce and O (n + m) to check path. So O (n ^ 5) Solution successfully passes all the tests. You can see my submission in upsolving :)

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

          O(n+m) can become O(1) if you pre-calculate it

          so total complexity is O(n^4)

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

      My solution is O(n^5) :D

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

    Mine is O(n^5) too. Horrible complexity but no-brain to code :)

    → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

About div1 D, if multiple answers exist, anyone will do, right?

for 

4 4
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

Answer 1 2 3 4 and 4 3 2 1 are both valid. Am I right?

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

    Yes.

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

    Yes, you are. There are 24 different correct answers possible here. Of course, [1, 2, 3, 4] and [4, 3, 2, 1] are among them.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Thanks for the good contest! (at least for me) Looking forward to see official solutions

→ Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I can't wait to see the tutorial for E in div 2... I've seen some ac codes, but I don't know the correctness of the solution. Simply they are finding acute triangle circumcircle center, then find if there are rectangles to form are new hole. Then find the max radiuses of these centers. But how to prove that this solution is right?

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

    "But how to prove that this solution is right?" — hm, it's not :P Look at example: 4 0 0 6 0 3 5 3 2 Aaand if you want to rush with something like "excluding acute triangles with other points inside them" take this one: 4 0 -100 0 100 400 0 -1 0 :) Much more complicated problem than it seems to be.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting for tutorial...

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Promlem D DIV2:Is the head of the tree a vetex numbered 1?Whick is the head? How to understand "Select the subtree of the given tree that includes the vertex with number 1."?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    No, the root of tree do not need to have value 1.

        2
   / \
  1   2
 / \
2   3

    in this tree there are many subtrees including vertex with value 1, for example:

    1.
    2
   / \
  1   2
 /
2 

2.

    2
   /
  1 
 / \
2   3

3.

  1 
 / \
2   3
    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "Select the subtree of the given tree that includes the vertex with number 1." just means the subtree containing the root which is number 1, but its value isn't always one.

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

      where in sentence "Select the subtree of the given tree that includes the vertex with number 1." is the word "root"?

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

        Well, I just wanted to point out that the vertex with number 1 is the node with number 1, not the nodes that have value 1. I think this is what he's confused about the head of the tree... (I just represented it to be the root of the tree).

        → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you post tutorial for this round?

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

    Sorry for annoying, I did not see that some guys have already asked.

    → Reply
»
12 years ago, # |
  Vote: I like it +38 Vote: I do not like it

I have a question about problem div1 E. Why does the answer become so small, that is all answers are no more than 200000, and brute force can pass all the tests??? just because k — the number of the blocked cells is small? I think maybe we can construct an input data to make a larger answer and make brute force TLE.

In all, I think the test data of problem div1 E may be too weak and let the solutions that are not optimized enough pass.

Would the problem setter of this problem please give me a reply??

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Yes, even 100000 x 99999 empty board will produce a huge answer.

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +37 Vote: I do not like it

    You're right. I didn't manage to generate the tests for this problem more carefully because I didn't have much time before the contest to prepare the tests and obviously I missed lots good of tests. Also random tests with the dimensions I used (mostly both n and m were powers of 10) seemed to have very small answers.

    Now I've updated the tests and I've added a lot more tests with huge answer. So the brute-force solutions won't pass anymore.

    I'm sorry about this. Hope I do better in my next contests. :)

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

      And another little problem is that previous submissions are still there without being rejudged. Would you please rejudge them?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        Gerald told me that it's impossible to do, because It would be unfair to those who've got AC. :)

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

          But now the shortest solution is by me and it's brute force... //also just because this can I find the problem about the tests...

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            I got the permission to rejudge it :) Thanks!

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it +2 Vote: I do not like it

              Thanks for rejudging my wrong submissions! In fact only some of my submissions are correct!Would you please rejudge all of my submissions in order not to mislead others. And I think majority of the solutions of the guys that previously tried to solve this problem and then got AC are correct, would you please also rejudge them in order to show the correct real execution time?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it +2 Vote: I do not like it

                I think it really doesn't matter that much. I rejudged your solutions, but it's not good to rejudge others'. I think everything's ok right now. :)

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it +17 Vote: I do not like it

                  Thank you for your hard work！ You've made an excellent and enjoyable CF round！ I am looking forward to your next CF round！

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

                  Thanks! ^.^

                  → Reply
»
12 years ago, # |
  Vote: I like it -22 Vote: I do not like it

"A subtree of a tree T is a tree with both vertices and edges as subsets of vertices and edges of T." This is not true :-/ Also, when I asked for clarifications about this I got "No comment".

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Why it's not true? In problem statement you was given a definition of subtree, which you needed to use. Not any other definition from wiki or another place.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it -13 Vote: I do not like it

      Ok, maybe it's true, but definitely not complete. We cannot pick ANY subset of vertices and edges. They do not specify that all vertices must have a path to vertex 1.

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

        Not ANY subsets, you skipped the first part of the definition..."A subtree of a tree T [IS A TREE] with both vertices and edges as subsets of vertices and edges of T"

        → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Editorials??

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    It should be uploaded in about 24 hours. Thanks for you patience. :)

    → Reply
»
12 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Here's an idea for Div 2 E: construct a Delaunay triangulation of all the given points (doable in N log(N)). Delaunay triangulation satisfies the property that a circumcircle of points that are connected by the edges of triangulation doesn't contain any other points (except possibly some points lie directly on the circumcircle and not inside of it).

Then for every triangle in the triangulation, check that the circumcenter of the triangle lies strictly inside of the triangle. The triangle with the largest radius of the the circumcircle is the answer. You will also need to handle the "special case" when the circumcenter lies on on of the sides of triangle ABC (let it lie on side AB). A "hole" will be created only if there is a fourth point D on the circumcircle of ABC which is connected by the edges of the triangulation to A and B.

Delaunay triangulation is constructable in N log(N) time, but not sure if it is codable in the contest time.

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Anyone knows why Scala is so slow on Codeforces. I tested my program for Div2-B locally and it's as fast as Java, but it failed to pass on OJ.

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I am stuck on http://mirror.codeforces.com/contest/275/problem/D . Can anyone help me .??

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

    this problem is solvable with a simple dynamic idea.

    run dfs on graph and find for every vertex value of a_i and b_i, in order minimum number of increase and decrease to make value of all vertex in subtree of vertex i equal zero.

    for leafs we can calculate it simple, and for non-leafs vertex (i) we can calculate it by this way : for every j that j is children of i

    a_i = max(a_i, a_j); b_i = max(b_i, b_j);

    and at last we should calculate number of operations that we need to make value of vertex i equal zero.

    w = value[i] — b_i + a_i;

    if(w<0)

    a_i -= w

    else

    b_i += w

    proof of this algorithm is very simple . sorry for my poor English, I hope this help you.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    So, my solution is as follows:

    • root the tree in vertex 1; for each vertex, determine its children

    • recursive approach: for each vertex, calculate the minimum number of adding and of subtracting operations (each separately) which must be applied on it so that it and all its descendants would get a value of 0

    • first, calculate the numbers for all its children; then, the minimum for each type of operations is clearly at least the maximum of minimums of this type of operation for all the children (due to the rooting, if an operation is applied on a vertex, it's applied on all its ancestors); by applying these operations, its value v_i changes and you need a minimum of additional v_i subtractions (if v_i is positive) or -v_i additions (if it's negative) to get it to 0

    There exists a suitable construction of these operations such that the resulting tree truly is a zero tree — you may think about it.

    In any case, the answer is minimum number of additions+subtractions for vertex 0 (by definition). The overall complexity is then optimal O(N).

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D in div1: it said the brother erased some intergers and change the order of some of its columns. But it also said when "If there exists no possible reordering of the columns print -1" and I think this is a contradiction because we can awalys change it back to the original order against the brother's order. I also the answer of sample 3 is "-1" :(

→ Reply
»
12 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I have a question.(maybe silly)

Is the word "editorial" correct? shouldn't it be the "tutorial"?

Sorry for my poor English.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Testing speed is amazing. Thank you. That was related to Round 170.

→ Reply