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:**

**Div2:**

Editorial is out and will be completed soon. :)

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 ?

GL & HF !!!

if someone says GL & HF will get negative votes then if someone says "Bad luck & don't have fun" will he get positive votes =)

just a joke :)

my comment :)

there was no haters there :)

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

organized system

ds

What will the points division in Division 1 ? Thanks .

Will be announced 5-15 minute before the contest.

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

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

Good luck :)

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 .

I corrected it :)

ignore this post, posted after correction

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

he is just lucky guy)

The scoring for div1 was so weak ...

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

Any subtree containing node 1

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

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

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

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

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

B was harder than C in div-2

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?

no, there is many things more to consider.

for example obtuse triangle don't create any hole.

iff there is no triangle I'm printing -1

you didn't understand me.

for example test case:

the answer is -1 although there is one triangle

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

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

No , take this test:

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

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

tricky B

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

I used division instead of multiplication and i used INT

+1, brother, you are not alone. I got AC with the same code + __int64)

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?

You need to use LL to calculate k*x or k=1000000000 x=100000000 will kill you

thanks,

Test case #11 Problem B div2

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.

Always shuffle before sort, fellow Java coder!

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

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

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

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

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?

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

ma 5alas fahamna :D

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

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

3162811 vs 3162830

Blog entry about this test case

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.

I love C++ <3 :)

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

lol C++ (FTW) :p

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?

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.

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

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.

double pivot quick sort its used for primitives

Oh yes I see [here].(http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/DualPivotQuicksort.java#DualPivotQuicksort.sort%28int%5B%5D%2Cint%2Cint%29).

But I also see on the code that they use merge-sort sometimes, at least it seems not too easy to hack...

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

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

OH GOD WHY?

i'm from 1534 to 1699 points :(

can somebody give me one point :(

Bad luck, bro :D. Look at my first contest :D http://codeforces.com/profile/Swistakk

Me to Stuck at 1699 :P

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?

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

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

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

I cannot wait to see the rating to be updated!

Thank you very much for contest.

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

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

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

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

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

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

so total complexity is O(n^4)

My solution is O(n^5) :D

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

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

for

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

Yes.

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.

Thanks.

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

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?

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

Waiting for tutorial...

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

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

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

I got it！thx

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

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

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

Could you post tutorial for this round?

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

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

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

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

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

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

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

I got the permission to rejudge it :) Thanks!

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?

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

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

Thanks! ^.^

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

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.

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.

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"

You are right, thank you! :)

Editorials??

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

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.

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.

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

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.

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

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

I have a question.(maybe silly)

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

Sorry for my poor English.

Both of them are correct! ;)

~~Testing speed is amazing. Thank you.~~That was related to Round 170.Anyway, thank you! :D

As I am a beginner ,can anyone explain me 275A?thank you in advance