### havaliza's blog

By havaliza, 7 years ago, ,

Hi everybody! :)

Codeforces Round #168 will start in hours. HamedSaleh 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. :)

• +263

 » 7 years ago, # |   +32 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 ?
 » 7 years ago, # |   -40 GL & HF !!!
•  » » 7 years ago, # ^ |   -17 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 :)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +16
•  » » » » 7 years ago, # ^ |   -8 there was no haters there :)
 » 7 years ago, # |   +38 Most of CF's contests take place in the same days of week, is there any special reason or it is accidental ?!
•  » » 7 years ago, # ^ |   0 organized system
•  » » 7 years ago, # ^ |   -8 ds
 » 7 years ago, # |   -26 What will the points division in Division 1 ? Thanks .
•  » » 7 years ago, # ^ |   +10 Will be announced 5-15 minute before the contest.
•  » » » 7 years ago, # ^ |   -30 Thanks for the info . Why is my comment hidden saying " too negative .. " . I was only asking the points division .
•  » » » » 7 years ago, # ^ |   +22 I'm guessing because everyone asks that before the contest and it's getting annoying.
 » 7 years ago, # |   -17 Good luck :)
 » 7 years ago, # |   +12 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 .
•  » » 7 years ago, # ^ |   +28 I corrected it :)
•  » » 7 years ago, # ^ | ← Rev. 3 →   -6 ignore this post, posted after correction
 » 7 years ago, # |   +43 Who is mrsa_91 and why he is expert?he haven't enough rating to be expert but he is expert...
•  » » 7 years ago, # ^ |   +2 he is just lucky guy)
 » 7 years ago, # | ← Rev. 2 →   -13 The scoring for div1 was so weak ...
 » 7 years ago, # |   +5 Can someone please explain the Div2-D statement? I found it confusing. How can we choose the subtree?
•  » » 7 years ago, # ^ |   +6 Any subtree containing node 1
•  » » » 7 years ago, # ^ |   +1 Can I only select vertices and edges so that every vertex has a direct path to vertex 1?
•  » » » » 7 years ago, # ^ |   +1 If I understood you well, no, you can select bigger subtree too not only the neigboring vertexes to node 1...
•  » » » » » 7 years ago, # ^ |   +5 I said direct path, not edge. For the tree 1 -> 2 -> 3, can I select subtree 1, 3 ?
•  » » » » » » 7 years ago, # ^ |   0 but vertexes 1 and 3 are not a tree or I misunderstood you example...
 » 7 years ago, # |   +5 Nice problems specially Div2-D & Div2-E , but I couldn't solve them on time :)
 » 7 years ago, # |   +4 B was harder than C in div-2
 » 7 years ago, # | ← Rev. 2 →   +10 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?
•  » » 7 years ago, # ^ |   0 no, there is many things more to consider.for example obtuse triangle don't create any hole.
•  » » » 7 years ago, # ^ |   0 iff there is no triangle I'm printing -1
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » 7 years ago, # ^ |   +5 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
•  » » » » » » 7 years ago, # ^ |   0 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
 » 7 years ago, # | ← Rev. 2 →   +2 Something is wrong with Div2-B :) Why so many WAs ?
•  » » 7 years ago, # ^ |   +4 tricky B
 » 7 years ago, # |   +2 I got 6 WA on problem c, because of long long :(
•  » » 7 years ago, # ^ |   0 I used division instead of multiplication and i used INT
•  » » 7 years ago, # ^ |   0 +1, brother, you are not alone. I got AC with the same code + __int64)
 » 7 years ago, # | ← Rev. 3 →   0 in problem C(div 2) my algorithm was sofor example n=8 k=3 array(1,6,2,9,3,7,5,4)sort array: 1,2,3,4,5,6,7,9I 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=6this solution got WA6 what is wrong?
•  » » 7 years ago, # ^ |   0 You need to use LL to calculate k*x or k=1000000000 x=100000000 will kill you
•  » » » 7 years ago, # ^ |   +1 thanks,
 » 7 years ago, # | ← Rev. 3 →   -25 Test case #11 Problem B div2
 » 7 years ago, # |   +2 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 Always shuffle before sort, fellow Java coder! public static int[] shuffle(int A[]) { int N=A.length; for(int i=1;i
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +6 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
 » 7 years ago, # |   +25 Fantastic problems. Truly thanks for your great problem set. Wish to see more contests like this. HF & GL!
 » 7 years ago, # | ← Rev. 4 →   -9 А что такого в D на 12ом тесте?
 » 7 years ago, # |   0 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?
•  » » 7 years ago, # ^ |   +1 Integer is object , and all objects are sorted with merge-sort in java.. I got the problem failed for exactly the same reason..
•  » » » 7 years ago, # ^ |   0 ma 5alas fahamna :D
•  » » » » 7 years ago, # ^ |   +9 ya 3am mateseeb el ragel fe ely howa feh :D
•  » » » 7 years ago, # ^ |   0 Mine strangely failed because HashSet is apparently less efficient than a TreeSet in this case.
•  » » » » 7 years ago, # ^ |   0
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   -6 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.
•  » » » » » » 7 years ago, # ^ |   -9 I love C++ <3 :)
•  » » » » 7 years ago, # ^ |   +2 Try not using modulo and division. Those are REALLY slow.
•  » » » 7 years ago, # ^ |   -10 lol C++ (FTW) :p
•  » » 7 years ago, # ^ |   +3 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?
•  » » » 7 years ago, # ^ |   +18 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.
•  » » » » 7 years ago, # ^ |   +8 Now I understand why such anti-quicksort test cases can not be made for C++ sort. Thanks for replying.
•  » » 7 years ago, # ^ |   0 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.
•  » » » 7 years ago, # ^ |   0 double pivot quick sort its used for primitives
•  » » » » 7 years ago, # ^ |   0 But I also see on the code that they use merge-sort sometimes, at least it seems not too easy to hack...
 » 7 years ago, # |   -10 Авторам спасибо. норм контест)
 » 7 years ago, # |   -10 I got WA in problem B Div. 2 because I've mistyped M with N ... :((
 » 7 years ago, # | ← Rev. 2 →   +7 OH GOD WHY?i'm from 1534 to 1699 points :(can somebody give me one point :(
•  » » 7 years ago, # ^ |   +7 Bad luck, bro :D. Look at my first contest :D http://codeforces.com/profile/Swistakk
•  » » 7 years ago, # ^ |   0 Me to Stuck at 1699 :P
 » 7 years ago, # |   0 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?
•  » » 7 years ago, # ^ |   0 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
•  » » 7 years ago, # ^ |   0 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...
•  » » 7 years ago, # ^ |   0 My solution failed for test 26. Anyone knows what's the complete test case ?
 » 7 years ago, # |   +12 I cannot wait to see the rating to be updated!
 » 7 years ago, # |   +5 Thank you very much for contest.I am very happy right now because my raiting has grown.
 » 7 years ago, # |   0 Is there any one who got accepted problem B-div2 with O(n^5) algorithm?
•  » » 7 years ago, # ^ |   +1 There are solutions with O(n^4) complexity, but i don't think there is any solution with O(n^5) algorithm at all
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 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! :(
•  » » » » 7 years ago, # ^ |   0 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 :)
•  » » » » » 7 years ago, # ^ |   0 O(n+m) can become O(1) if you pre-calculate itso total complexity is O(n^4)
•  » » » 7 years ago, # ^ |   0 My solution is O(n^5) :D
•  » » 7 years ago, # ^ |   +5 Mine is O(n^5) too. Horrible complexity but no-brain to code :)
 » 7 years ago, # | ← Rev. 3 →   0 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?
•  » » 7 years ago, # ^ |   0 Yes.
•  » » 7 years ago, # ^ |   +3 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.
•  » » » 7 years ago, # ^ |   0 Thanks.
 » 7 years ago, # | ← Rev. 2 →   +8 Thanks for the good contest! (at least for me) Looking forward to see official solutions
 » 7 years ago, # |   +11 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?
•  » » 7 years ago, # ^ |   0 "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.
 » 7 years ago, # |   0 Waiting for tutorial...
 » 7 years ago, # |   0 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."?
•  » » 7 years ago, # ^ |   +15 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 
•  » » » 7 years ago, # ^ |   0 I got it！thx
•  » » 7 years ago, # ^ |   0 "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.
•  » » » 7 years ago, # ^ |   0 where in sentence "Select the subtree of the given tree that includes the vertex with number 1." is the word "root"?
•  » » » » 7 years ago, # ^ |   +3 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).
 » 7 years ago, # |   0 Could you post tutorial for this round?
•  » » 7 years ago, # ^ |   +1 Sorry for annoying, I did not see that some guys have already asked.
 » 7 years ago, # |   +38 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??
•  » » 7 years ago, # ^ |   +31 Yes, even 100000 x 99999 empty board will produce a huge answer.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +37 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. :)
•  » » » 7 years ago, # ^ |   0 And another little problem is that previous submissions are still there without being rejudged. Would you please rejudge them?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +10 Gerald told me that it's impossible to do, because It would be unfair to those who've got AC. :)
•  » » » » » 7 years ago, # ^ |   +5 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...
•  » » » » » » 7 years ago, # ^ |   +10 I got the permission to rejudge it :) Thanks!
•  » » » » » » » 7 years ago, # ^ |   +2 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?
•  » » » » » » » » 7 years ago, # ^ |   +2 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. :)
•  » » » » » » » » » 7 years ago, # ^ |   +17 Thank you for your hard work！ You've made an excellent and enjoyable CF round！ I am looking forward to your next CF round！
•  » » » » » » » » » 7 years ago, # ^ |   0 Thanks! ^.^
 » 7 years ago, # |   -22 "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".
•  » » 7 years ago, # ^ |   +2 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.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -13 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.
•  » » » » 7 years ago, # ^ |   +3 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"
•  » » » » » 7 years ago, # ^ |   0 You are right, thank you! :)
 » 7 years ago, # |   +5 Editorials??
•  » » 7 years ago, # ^ |   +32 It should be uploaded in about 24 hours. Thanks for you patience. :)
 » 7 years ago, # |   +24 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.
 » 7 years ago, # |   +5 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.
 » 7 years ago, # |   +3 I am stuck on http://codeforces.com/contest/275/problem/D . Can anyone help me .??
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 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 -= welseb_i += wproof of this algorithm is very simple . sorry for my poor English, I hope this help you.
•  » » 7 years ago, # ^ |   +2 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).
 » 7 years ago, # |   0 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" :(
 » 7 years ago, # |   +16 I have a question.(maybe silly)Is the word "editorial" correct? shouldn't it be the "tutorial"?Sorry for my poor English.
•  » » 7 years ago, # ^ |   0 Both of them are correct! ;)
 » 7 years ago, # | ← Rev. 2 →   0 Testing speed is amazing. Thank you. That was related to Round 170.
•  » » 7 years ago, # ^ |   0 Anyway, thank you! :D