### fchirica's blog

By fchirica, 5 years ago, ,

Hello everyone!

We invite you to participate in Codeforces Round #245, scheduled for Sunday, 11th May at 7:30 MSK. This is the fourth round I write for Codeforces. After the last round your upvotes helped me get into the Contributors Top 10. Thanks for all your good remarks; I'll try and do my best in order for this round to be at least as good as the previous one.

This round is prepared by my friend Ioan Petcu (author of D1 E) and I (all problems, except D1 E). We've chosen the problems to be as diverse as possible — no two problems will share the same programming technique. As the problems are varied, we hope you'll find at least one problem of your taste. The main character is Iahub, currently the number one ranked contestant in the Romanian selection camps for IOI. After reading the problem statements, you'll see what the life of a very good Romanian competitive programmer is like (just kidding, it's just my evil imagination).

This round wouldn't have been possible without the people that helped me test it: Gerald Agapov (Gerald), Damian Straszak (DamianS), Dan Alexandru (danalex97) and Vlad Badelita (vladb). As always, we’d like to thank Mike Mirzayanov for creating the Polygon system and Codeforces plaftorm and to Delinur for translating the problems in Russian.

We wish high ratings to everyone and, above all, have fun!

UPD Score Distribution

Division 1: 500 1000 1500 2000 2000

Division 2: 500 1000 1500 2000 2500

I apologize for all technical issues during the round, from the ambiguous problem statements to very easy problem D1 D. In my trial to invent a nice task, I didn't see that straight forward solution for it and I have no excuse for this.

UPD Winners

Division 1:

Division 2:

UPD Editorial

UPD Statistics

•
• +313
•

 » 5 years ago, # |   +7 Thanks for taking the time to prepare the problems. Feeling excited! Good luck contestants.
 » 5 years ago, # |   +13 Good to see another Romanian made round. And it's even 1/3 Mures (my home region)
 » 5 years ago, # | ← Rev. 2 →   +8 Thanks for the contest! Long time no see:) And tonight I' ll try my best to reach purple( well, not pupil) God bless me:p UPD: I' m so surprised to realize that tomorrow is my birthday too, what a coincidence!
•  » » 5 years ago, # ^ |   +11 Happy birthdays ..
 » 5 years ago, # |   +1 A contest after 9 days. :) GL HF!!
 » 5 years ago, # |   +6 We really expect to see what the life of a very good Romanian competitive programmer is like :)
 » 5 years ago, # |   -15 I think the problem statements about programmer will be very different && interesting. May be 's counting girlfriends, scheduling for date with girls or some games with girls... haha, just kidding.
 » 5 years ago, # |   -10 Im bored Why there arent so much comment?
 » 5 years ago, # | ← Rev. 2 →   +23 A rare occasion: the points' distribution appeared more than 1 minute before the contest :DAnd yet another: there are exactly 1000 registrants in div1!
 » 5 years ago, # |   -19 It seems E question will be easy I dont want to be first again man
•  » » 5 years ago, # ^ |   +10 Easier it E(Div1)
•  » » » 5 years ago, # ^ |   -15 Ok ,i'll solve As you know no problem for me :)
 » 5 years ago, # | ← Rev. 3 →   +5 Div 1 начало в 19:40 Div 2 начало в 19:30UPD. исправили
 » 5 years ago, # |   +1 As usual, delayed :D
•  » » 5 years ago, # ^ |   +8 why the 10 minutes delay?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +72 Because I had to do my dinner.Although it was not official, still thanks for consideration Codeforces.
•  » » » » 5 years ago, # ^ |   0 And I needed some time to wash off the sand, running back from the beach :)
•  » » » 5 years ago, # ^ |   0 I think, server is busy.
 » 5 years ago, # |   +6 Delayed?
•  » » 5 years ago, # ^ |   +2 Like other contests its delayed
 » 5 years ago, # |   +4 Delayed :(
 » 5 years ago, # |   +7 Good start!
•  » » 5 years ago, # ^ |   0 Same as usual
 » 5 years ago, # |   +18 delay delay delay
 » 5 years ago, # |   +43 I think the "usual time of CF Round" should be 7:40 instead of 7:30
•  » » 5 years ago, # ^ |   +41 Then all of the contests start at 7:50 :D
•  » » » 5 years ago, # ^ |   +11 If so, I think the "usual time of CF Round" should be 7:50 instead of 7:40
•  » » » » 5 years ago, # ^ |   +10 Then all of the contests start at 8:00 :D
•  » » 5 years ago, # ^ |   0 Just a few recent contest.
 » 5 years ago, # |   +5 Another time... 10 minutes delayed...
 » 5 years ago, # |   0 For me it showed that it has started.
•  » » 5 years ago, # ^ |   +6 So, do it!
 » 5 years ago, # |   0 delay :'(
 » 5 years ago, # |   +5 Looks like somebody important rang and said he was late to register.
•  » » 5 years ago, # ^ |   0 maybe tourist ?
•  » » » 5 years ago, # ^ |   0 nope.
 » 5 years ago, # |   +14 Exacly 1000 participants in div1 :O
•  » » 5 years ago, # ^ |   +8 Wow, at the same second! :D
•  » » » 5 years ago, # ^ |   0 What, 999?! I thought it was final..?
 » 5 years ago, # |   +15 Exactly 1000 div1 registrants! :D
•  » » 5 years ago, # ^ |   0 It shows 999 to me.
•  » » 5 years ago, # ^ |   0 now it is 999 registrants in div1...... I think someone cancel it....
 » 5 years ago, # |   +3 1000 coders for div1 !!!! what an amazing contest~!!!! thanks for the delay!
 » 5 years ago, # |   0 Exactly 1000 people registered for div1.
 » 5 years ago, # | ← Rev. 2 →   0 exactly exactly exactly
 » 5 years ago, # |   +5 It's contest? :)
•  » » 5 years ago, # ^ |   +5 I don't know
•  » » 5 years ago, # ^ |   0 "As the problems are varied, we hope you'll find at least one problem of your taste."- are you kidding, elfus0?leaving contest arena, this contest is not for me. :(
 » 5 years ago, # |   0 what the heck ? >.<
 » 5 years ago, # |   +9 Is Div.2 really Div.2...?
•  » » 5 years ago, # ^ |   0 I agree...
 » 5 years ago, # |   +1 I dont understand the problem A div2. Who are the red and blue balls??. I am crazy with this problem. Please, for the next competitions that you should better the content of problem. Now, I see the clarifications of problem A, is very late and I lost many points, WDF!!!!
 » 5 years ago, # | ← Rev. 2 →   -28 a
 » 5 years ago, # | ← Rev. 2 →   +22 Wrong answer on pretest 2Wrong answer on pretest 2Wrong answer on pretest 2 . . .:|:|:|
 » 5 years ago, # |   +6 What is the solution for problem A Div.2??? A is the hardest problem today:)
•  » » 5 years ago, # ^ |   0 sort
•  » » » 5 years ago, # ^ |   0 Oh, No. It's a very stupid bag :(
•  » » 5 years ago, # ^ |   +1 Sort point by coordinate and 0 1 0 1 0 1 0
•  » » 5 years ago, # ^ |   +1 1) Sort points by coordinate. 2) Simply put 1 0 1 0 1 0 1 ... 3) Sort points by order in input 4) Write them to output
•  » » » 5 years ago, # ^ |   0 I wrote only 1 0 1 0 1 0 1... without sort :(
•  » » » » 5 years ago, # ^ |   0 I did it and got Wrong answer on test 3. But when I sort, I get Accepted.
•  » » » 5 years ago, # ^ |   0 why sort?
•  » » » » 5 years ago, # ^ |   0 Counterexample (without sorting gives the wrong answer): 3 0 3 1 2
•  » » » 5 years ago, # ^ |   0 Omg it seems so obvious now...
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 Hint[1]: you can totally ignore the segments...Hint[2]: sort
 » 5 years ago, # |   +1 What the heck is A? Could not come up with any idea :-s
•  » » 5 years ago, # ^ |   0 0101010101 And sort them by id afterwards
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +1 why can't we use all balls of the same color?
•  » » » » 5 years ago, # ^ |   0 Because for example if interval is 1..3, and balls are at 1,2,3 and all of them are black, and no red, then inequality |3-0|<=1 is incorrect.
•  » » » » » 5 years ago, # ^ |   0 thanks, I misunderstood the task, I thought ri, bi are coordinates of the balls (facepalm)
•  » » » » » » 5 years ago, # ^ |   0 So I was not the only one to think on the same lines :)Though I made the correction but could not get an AC because of the sort thing.
 » 5 years ago, # |   +39 I think D should've been B. (div1) Or A. Ok, not A, but it's seriously easy to solve. I saw several solutions that made use of the fact that |A[i]| ≤ 104 — solutions, which pass maxtests (easy to make here) in slightly under 2 seconds. Really? >_>
•  » » 5 years ago, # ^ |   0 Really :(Unfortunatelly, I've tested this approach during challenges only — it passes in 1.3s in my implementation.
•  » » » 5 years ago, # ^ |   +5 I rewrote Snusmumriken's 6595981, ran it on "40000 40000x10000" and got 686 ms using the CF Custom invocation. On my computer, it takes 1200 ms on that test and 3200 ms on "100000 100000x10000", so it should be 1830 ms on CF, +- something in the order of 10 ms.
•  » » » 5 years ago, # ^ |   +13 Unbelievable if O(N*max(A)) solutions could be passed systest.
•  » » » » 5 years ago, # ^ |   0 not max(A) but min(A) (although it's not key ...
•  » » » » » 5 years ago, # ^ |   +3 min(A) = -10000 => O(-1e9) ??? Faster than every algorithms?
•  » » » » » » 5 years ago, # ^ |   0 min(abs(A)) ......
•  » » 5 years ago, # ^ |   +28 At the beginning, I was expecting it might be something related to dp convex hull (yeah, it's problem D) and tried to play around with the formula to solve it. And you probably know how it feels when I finally got the solution...
•  » » 5 years ago, # ^ |   +20 Really sorry for that. Didn't notice such a solution. =(
•  » » » 5 years ago, # ^ |   +8 Why have O(nlogn) solutions timed out?
•  » » » » 5 years ago, # ^ |   +8 Right O(n * logn) solutions haven't timed out ;)I mean that as someone has already noticed it's easy to make a mistake in this algorithm in this problem by writing somewhere dist2 instead of dist or vice versa.
•  » » » » » 5 years ago, # ^ |   0 Yeah you are correct!
•  » » 5 years ago, # ^ |   +14 Even if we suppose that simple solutions (such as O(N|A|max) solution with some heuristics) doesn't work, I think D was too well-known for a D. It was just the classic closest pair of points problem. Some participants might have copied the implementation of this problem and submitted..
 » 5 years ago, # |   0 I try to hacking a submission when the countdown show 15sec, then when the hacking is running contest going to be ended, what happen with my hacking? It show "Status: challenge-other"
 » 5 years ago, # |   0 Why doesnt this work for A?If we alternate the points 0 1 0 1 0 1 then no segments can have the difference more than 1.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 That's right. Sort them by id(input order) then
•  » » 5 years ago, # ^ |   0 Ah.....crap assumed points were in order : D
•  » » 5 years ago, # ^ |   0 A / Div. 2 sucks.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Looks very hard for A, knowing that the same problem was used for Div1-E just with a little restriction change.Edit: My excuses, the problem is actually different, I misunderstood.
 » 5 years ago, # | ← Rev. 5 →   -27 Nice contest, A was an exemplary A problem, not too hard, not too easy. Speaking about B, things change, a little bit hardcore to implement, otherwise a classical DP problem. C was way easier than D (look at the number of submitted codes for C, it's pretty low). C probably is some backtracking and for D I'm really curious about the solution. At E I smell an idea similar to http://acm.timus.ru/problem.aspx?space=1&num=1129, but much more elaborated. Clearly, the score distribution was a little bit wrong. Hope my rating won't decrease by too much. Overall, I liked this contest a lot. This should be taken as constructive criticism. Everybody makes mistakes. ;)
•  » » 5 years ago, # ^ |   +8 You mean C was harder than D*
 » 5 years ago, # |   +2 Couldn't understand problem A (Div. 2). I think an example would have been great in the problem statement...
•  » » 5 years ago, # ^ |   0 read my comment above.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 5 1 3 1 2 2 3 Look at this from left to right, in case you print 1 0 1: 0 1 1 so segment [2,3] will have |2 — 0| = 0, which violates.So, the problem is just with the problem text. If he had taken the time to write it properly, there wouldn't have been so many WAs for such a trivial problem.
 » 5 years ago, # |   0 Thank you Chirica! Really nice poblemset ;) I just needed 2 more minutes to submit C :(
 » 5 years ago, # |   +24 System test!!!!!!!!!!!!!!!!
•  » » 5 years ago, # ^ |   0 I missed to watch systest.
 » 5 years ago, # | ← Rev. 3 →   +38 ()
•  » » 5 years ago, # ^ |   0 Translation please. Thanks.
•  » » » 5 years ago, # ^ |   +9 How fast have you submitted the A problem?
•  » » » » 5 years ago, # ^ |   +27 Just that three words means this long sentence?? Russian language!!
•  » » » » » 5 years ago, # ^ |   +6 Not really unexpected, considering Slavic languages have something called conjugation and declension (note that I just googled the english words :D).
•  » » » » » 5 years ago, # ^ |   +5 It's just one example... If you compare the today's problem statements, the Russian versions are longer than English, less words, but more characters and syllables.In Hungarian, "I love you" is one word, 'szeretlek', but its length in syllables (3) is same as in English. Does that really makes Hungarian more concise than English?
•  » » » 5 years ago, # ^ |   +20 "Did you solve the first one quickly"?
 » 5 years ago, # |   0 на чем у всех падает div1 B? на том, что не учли, что они не могут встретится в 1 или последней строчке и в 1 или последнем столбце?
•  » » 5 years ago, # ^ |   +9 Ага(
 » 5 years ago, # | ← Rev. 3 →   +6 spent over thirty minutes finding a test case that gives  - 1 on problem A Div 2. Gave up and submitted and it got accepted. I guess there was no such test case.
•  » » 5 years ago, # ^ |   0 Is there any such test case? Please mention it.
•  » » 5 years ago, # ^ |   +1 There's no such case. If you color the points 01010..01, any interval will end up with the same quantity of 0s and 1s (size of interval is even) or |#0 — #1| == 1 (size of interval is odd).
 » 5 years ago, # | ← Rev. 2 →   +62 Just adjacent xs and ys enough for D. Such a tests... Take look to this.6597823I think tester should explain this.
•  » » 5 years ago, # ^ |   +64
 » 5 years ago, # | ← Rev. 2 →   +21 WA7 в D на решении с перебором
•  » » 5 years ago, # ^ |   +16 I also had WA7; now I fixed it, and now I have WA8
•  » » » 5 years ago, # ^ |   0 And what does WA7 mean?
•  » » » » 5 years ago, # ^ |   0 I hadn't checked right border of array
 » 5 years ago, # |   +15 Why the test cases hasn't been visible yet?
 » 5 years ago, # |   +3 How do I check on which test case my submission is failing? Once I click the solution link, its showing test case number "Runtime error on test 34" but not the test case.
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 Click the solution number, and click the "#" sign above, and you'll get this: 6595417UPD: Sorry, it used to be there. I don't know where it is now.UPD2: It is shown now.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +8 ...where you also wouldn't be able to see tests :)
 » 5 years ago, # |   +2 the tests for problem D are very weak6592992 should get WA with this test case n = 1003501 elements with value 10000 , 1 element with value 5000, 500 elements with value -10000, 1 element with value -5000(my generator code : http://paste.ubuntu.com/7448665/ )
 » 5 years ago, # |   +14 Unfortunately, the announcement for problem B modified what was asked in the original statement. Instead of requiring that the two characters meet at a single cell, their paths should have only a common cell after the clarification, which is a stronger requirement (since their speed may be different).This was surely troublesome for those who started the contest with problem B (like me)...
•  » » 5 years ago, # ^ | ← Rev. 4 →   +32 After the contest, xhae had told me that the following paths are feasible to the problem description, but not to what the problem author requires.A: [1,1] -> [1,2] -> [2,2] -> [2,3] -> [3,3]B: [3,1] -> [3,2] -> [2,2] -> [1,2] -> [1,1] (edited, Thanks to marspeople! It was previously [2,3] instead of [3,2])(spent exactly same time on all cells)In this case, they only meet in [2,2], but this was not included in the solution (since the intersection of both paths is {[2,2], [1,2]}). The problem description is not clear enough. actually wrong.
•  » » » 5 years ago, # ^ |   +11 I think you meant B: [3,1] -> [3,2] ...Yes, the problem becomes totally different with the added clarification
 » 5 years ago, # |   +11 What are tests 18 and 14 in Div1.D? I have two solutions (6592810 and 6597945) and they both got TLE on corresponding tests, while running the latter on the 'Custom run' page shows me stable 900ms running time.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 I think in the following line the difference should be squared:if (p1 >= 0 && pts[i].proj — pts[p1].proj < ans — eps) {I had a TL18 with a similar bug.
•  » » » 5 years ago, # ^ |   0 Thank you, that's definitely a bug.However, I'm still wondering about the latter submission (and that's my main concern), which was tested via 'Custom run' on several test cases and still got TLE. Do you have any cool ideas about it too?
•  » » » » 5 years ago, # ^ |   0 Nope.
 » 5 years ago, # | ← Rev. 2 →   +85 So, I decided to write something stupid in Div 1 D since I haven't thought of solution.Seemingly, I couldn't construct an example with large length, so I tried to stop my search after something bigger than sqrt(100K). As I like round numbers, I only checked length up to and including 400. Which, unsurprisingly, got WA.After the contest, I tried using binary search to determine what the actual maximum length was on the test data. Imagine my joy when I gradually found out that the answer to that question was 401.But, seriously, I am disappointed that this task was included in the contest if the authors were unable to find a case large enough to fail these naive solutions. Even though I liked the task intended solution with conversion to geometry.
•  » » 5 years ago, # ^ |   +3 I have a standard solution to "closest pair of points": sort the points and sweepline, keep the ones already sweeped in a map<>; when processing a point, try all points with close y-coordinates, up to the K-th closest in both directions, then add the processed point into the map<>. Time complexity: . I know that if K = 50, this approach hasn't ever failed me, so I use it :D
•  » » » 5 years ago, # ^ |   0 What's wrong with the standard divide and conquer?
•  » » » » 5 years ago, # ^ |   +9 It's a bit harder. What I'm talking about is basically a bruteforce+smart condition.
•  » » » » » 5 years ago, # ^ |   +5 Your bruteforce can be turned into a simple correct solution: Sweep points by x and maintain a set of points that have already been processed sorted by y Maintain bestAnswer — closest distance among pairs of processed points When processing a point, scan the set for all points with currentPoint.y - bestAnswer < y < currentPoint.y + bestAnswer, delete points with x < currentPoint.x - bestAnswer and update bestAnswer Even though you might scan through a lot of points in one iteration, all of them except O(1) will get deleted, so the complexity is
•  » » » » » » 5 years ago, # ^ |   0 I just need to remember something like "an solution similarly relies on there being few numbers close to the processed one, so there shouldn't be evil test data for my approach either" :D
•  » » » 5 years ago, # ^ |   0 This worked for me too for a long period now. ( even with K smaller ) It is very usefull in a Olympiad fromat as you always make many points in short time. :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 never mind!
•  » » 5 years ago, # ^ |   +5 401? I also binary searched and got 1002... Look at those solutions: http://codeforces.com/contest/429/submission/6598773 (1001 fails) http://codeforces.com/contest/429/submission/6598792 (1002 passes)
•  » » » 5 years ago, # ^ |   0 I would guess that you're getting WA because your initial value of best is too low.
•  » » » » 5 years ago, # ^ |   0 This is not the case: http://codeforces.com/contest/429/submission/6599177 g(i, i+1) <= 10^8 + 1, so 10^9 is not too low.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Agreed. Hmm, that's interesting...Here's 400 failing and 401 passing from me. I cannot yet spot the difference in our codes.UPD: Oh, OK. There were some extra cases added afterwards (from community, I guess). But 401 was enough during the competition then.
•  » » » » » » 5 years ago, # ^ |   0 Ah, I understand. You're really unlucky :P. But my case is similar, I set bound to 320 :P. I thought about making it larger, but on my computer it took 1s to process maxtest, so I have left it on 320. But cf servers are much faster than my laptop, for 1000 it took 0,3ms to process maxtest using my solution, if I would have known that before, I would enlarge my bound and got AC xd. But we shouldn't complain, in fact we were "cheating" and we don't deserve AC :P.
•  » » 5 years ago, # ^ |   0 I only checked up to 100 numbers back + 100 closest positions (larger and smaller) in terms of prefix sums. I didn't know how fast the CF servers were, so I wanted to avoid TLE. Sadly, this got WA on test 39, with < 500 msec. When I increased the limit to 500 I got AC (with a running time of about 1.8 sec). Anyway, I don't think it's easy to create test cases to fail something like this.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 "Anyway, I don't think it's easy to create test cases to fail something like this." — it is.5000 (k x 10000) -5000 (k x -10000)for some big k.
 » 5 years ago, # |   +3 Div.2 B. I used easy solution with regexps, because there were no big data. Insert x in every possible position, and While (find 3+ equal numbers){delete them}, Calc what is left. Solution with Perl 6597887.
 » 5 years ago, # | ← Rev. 3 →   +3 This guy is lucky as hell: http://codeforces.com/contest/429/submission/6591828 He set max difference j-i to 1005 and got accepted but if it will be changed to 1001 it will fail (smallest number which can be set is 1002).EDIT: I don't know why, but I can't reply to those posts below :( Compare those solutions: http://codeforces.com/contest/429/submission/6599177 (my solution, 1001 fails) http://codeforces.com/contest/429/submission/6598792 (my solution, 1002 passes) http://codeforces.ru/contest/429/submission/6598182?locale=en (eduardische solution, 401 passes)EDIT2: Explanation of that phenomenon is here: http://codeforces.ru/blog/entry/12254#comment-169126
•  » » 5 years ago, # ^ |   0 Nope, 1000 is just fine. http://codeforces.ru/contest/429/submission/6597981
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 No, the difference of 401 passes, as I mentioned earlier.
•  » » 5 years ago, # ^ |   0 Hmmm, and what about http://codeforces.ru/blog/entry/12254#comment-169072
•  » » 5 years ago, # ^ |   0 Maybe some new tests were added? My solution also fails with 1000, but works with 1010...
 » 5 years ago, # |   +3 Hi,Does Codeforces usually allow users to see test cases after the contest ends?I see that test cases for problem B (DIV 2) are visible now, but not for problem A (DIV 2). Will it be a matter of time until test cases for problem A get released, or does Codeforces sometimes not release them?
 » 5 years ago, # |   +10
 » 5 years ago, # |   0 What's typically too deep for a recursive solution? I figured 10^5 would cause a stack overflow, so I wrote Div1 A non-recursively (and somehow wrote a bug into it that way).
•  » » 5 years ago, # ^ |   +2 Codeforces sets the stack to 256 MB, so it's not easy to overflow it with recursion. You'll likely hit a time limit before that.
•  » » » 5 years ago, # ^ |   0 Ahh, I wasn't aware it was that high! Thanks!
 » 5 years ago, # | ← Rev. 2 →   +8 j = 1001WA 47http://codeforces.ru/contest/429/submission/6599410j = 1002Accepted http://codeforces.ru/contest/429/submission/6599408Nice
 » 5 years ago, # |   +1 Why are the test cases not showing up till now ?? -_-
 » 5 years ago, # |   +13
 » 5 years ago, # | ← Rev. 2 →   0 About div1A/div2C How is this test case valid ? http://codeforces.com/contest/429/submission/6589121 test 35which is101 101 910 210 33 73 89 49 55 61 0 1 1 0 1 0 1 0 10 0 0 0 0 0 0 0 0 0But in the question it was given The root of the tree is node 1 But in the test case it states an edge from 10 --> 1 ???
•  » » 5 years ago, # ^ |   0 Then node 10 is a child of node 1 (the root) !
•  » » » 5 years ago, # ^ |   0 No the test case assumes that the edges are bi-directional and the optimal answer is found assuming 1 to be a child of 10.Also the 1st test case has edges,2 1 and 3 1, which are opposite to 1 10.
•  » » » » 5 years ago, # ^ |   0 I solved the case by hand, assuming that node 1 is the root, and it is showing correct answer !
•  » » » » » 5 years ago, # ^ |   0 Hmm .. you maybe correct about what you are saying Let us assume that if the input contains a b then there is a directed edge from a->b , like in this case 1-10, which justifies 1 being the root.But see the sample test here,It has the following edges in the input:2 1 3 1which tells us that there are edges from 2->1, which contradicts of 1 being the root. I hope you understand what I am trying to say.
•  » » » » » » 5 years ago, # ^ | ← Rev. 4 →   +1 Actually this is how I've generated the tests , but some of them were added later. But it didn't came to my mind that this will make any difference or someone will get confused. Though , the statement was clear sorry for the inconvenience.
•  » » 5 years ago, # ^ |   0 My friend, why do you assume that the trees are directed?Typically trees are undirected (unless otherwise stated in the problem), and the input specification just states that a pair ui, vi means that there is an edge between those two nodes. It doesn't mention any particular direction.
•  » » » 5 years ago, # ^ |   +5 Problem statement states that 1 is the root of the tree.Doesn't that mean if the tree is rooted so it has to be directed ?? Because root of a undirected graph doesn't makes any sense.
•  » » » » 5 years ago, # ^ |   0 I frankly have no answer to your statement that "root of a undirected graph doesn't makes any sense".My recommendation, if you'd like to consider it, my friend, would be to invest a few moments studying the definition of a tree. Wikipedia's entry is fairly well-written and I think it will helpful.
•  » » » » 5 years ago, # ^ |   0 Yes, you're actually right in saying that since it has a root, it must be directed (by definition of rooted tree). However, naming the root isn't enough to uniquely determine the direction of each edge (since they can either be all towards or all away from the root), the edges they give you are just a list of the edges present in the tree (without direction), and it's up to you to assign them a direction that makes sense.
•  » » » » » 5 years ago, # ^ |   +5 Wonder why they can't simply give us parent index for each vertex. Would be a lot less trouble for everyone involved.
•  » » 5 years ago, # ^ |   0 The problem statement goes as follows:“Each of the next n  -  1 lines contains two integers ui and vi meaning there is an edge between nodes ui and vi.”Note that it mentions an undirected edge between two nodes, not a directed edge from one node to another. So, the statement does not imply the nodes will be given in any particular order (from the root, or lexicographical, or whatever).
 » 5 years ago, # |   +13 What were your solutions to C? First important observation is that there are at least n/2 leafs. I got AC with some weird backtracking, which tries to build (n/2)! different trees (but its search space is in fact lot smaller, but I can't come up with a better estimation). but after the contest I came up with a solution O*(2^n), but 4^(n/2) is in fact a better description of that :P. Consider a dp with array dp[n/2][3^(n/2)] (^ means power not xor ;) ). We divide non-leafs into 3 groups — nonactive and used, active and used, nonused and for given dp[k][mask] where mask denotes the division of nonleafs into 3 groups. This state is reachable iff we can build a forest where set of vertices are used vertices, set of roots are used and active vertices and where k leafs were used. But when checking if fixed state is reachable we have to search many states, possibly 2^(n/2). So whole algorithms runs in O*(6^(n/2)) ("*" means "*poly(n)", it is standard notation), which is in fact O(*(4^(n/2)) algorithm. Why? I will leave that to you as a nice exercise.
•  » » 5 years ago, # ^ |   0 As far as I got you, my solution was similar, but instead of having those 3-states I was attaching children to the nodes in some order, so instead of having 3rd state I had a variable in my DP solution which shows up to which non-leaf node I have already assigned childrent. DP[mask][assigningTo][remainingLeafs] in my solution is whether we can assign nodes denoted by mask to the nodes from [0 .. asssigningTo] interval using additional 'remainingLeafs' number of leafs. Internally when calculating this DP I was simply checking all the submasks of the given mask.Here is the solution: 6599572
•  » » 5 years ago, # ^ |   +10 My DFS solution runs in time. I built it based on simpler solution, that runs in: O(3n) time. Let's start with sorting nodes by number, given in input. We encode our state as pair i,j — means that we have considered first i nodes, some of them connected and mask j contains all nodes, that have no parents. First note that i is redundant, since the last one in mask is obviously the last node considered, so i equals last bit +1. Let's consider all subsets of this mask and pick each that have at least two bits set and required sum. It is known that total amount will be 3^n. And if we precalc all sums and bitcounts, we will be able to solve problem in O(3n)Now let's remove all leafs from mask. Then we will have state i,j — we considered some first nodes and now we have i leaves without parents and inner nodes described in mask j.
 » 5 years ago, # |   +35 All of those accepted solutions are a big shame for tests preparers:http://codeforces.com/contest/429/submission/6591828 checking pairs of points with small j-i in Dhttp://codeforces.com/contest/429/submission/6597823 — checking pairs of points with adjacent xs and ys in D :(
 » 5 years ago, # |   0 For (Div. 1) B, when brute forcing the meeting point after pre-computing the dp tables, my original solution (which got WA on test 23) checked every possible cell, including those on the border. Then, after contest, after viewing some of the accepted solutions, I changed it to only allow them to meet at interior points. So for this case:3 3 1 1 1 1 1000 1 1 1 1my new accepted solution gets 8, while my old solution got 1006 (corresponding to them meeting at the left middle cell and then one of them proceeding to the middle). I'm probably just missing some detail in the problem statement, but why is that invalid?
•  » » 5 years ago, # ^ |   +8 If by "left middle cell" you mean (row 2, column 1), it wouldn't be a valid meeting point because they can't get out of that cell without both moving to (row 2, col. 2), or stepping on a cell previously visited by the other person.There was a clarification stating something to the effect that both paths have to be completely disjoint, except for the cell in which they meet.So, in a 3 × 3 grid, the only valid meeting point is (2, 2).
•  » » » 5 years ago, # ^ |   0 Oh okay, I somehow missed that clarification, but I see it now. Thanks!
 » 5 years ago, # |   0 What's the solution to 1E problem. I read the code, I see what it does. However, I don't understand what is the idea behind the problem. How do I proof that doing it like this always scott_wu or SergeyRogulenko always returns a solution?
•  » » 5 years ago, # ^ |   +5 Consider a sorted list of all starting and ending points of every segment. It doesn't matter in which order we place points that have the same coordinate: see below why. Starting points of red segments and ending points of blue segments would be marked with +1, and starting points of blue/ending points of red will be -1. We need to make sure the sum in every prefix is between -1 and 1. This means the sum at all even points will be 0. This means points 2k and 2k+1 must have different signs. Also, obviously, two ends of the same edge must have different signs. We got a graph that we must color in two colors. Now note that the graph has two kinds of edges, and edges of the same kind can never share a vertex (by construction). This means that there are no odd cycles, so we will always find an answer.
 » 5 years ago, # |   0 The problem A div2 make me crazy!
 » 5 years ago, # |   +8 I used O(min(abs(a[i]))n) past the problem D ....
 » 5 years ago, # | ← Rev. 2 →   +21 The data for D is weak. My AC solution gets this case wrong:1 10000 ... (2000 times) ... 10000 -5000 -10000 ... (1999 times) -10000 -5000My AC solution: http://codeforces.com/contest/429/submission/6596958Generator code for this test case: https://gist.github.com/jonathanpaulson/1d5fb7825395185dcd5d
•  » » 5 years ago, # ^ |   0 It is difficult that make this problem's data. But my solution is ugly. In this case 100000 10000 10000…… (100000 times) my sulution will TLE.
 » 5 years ago, # |   0 I feel so stupid trying to solve E for an hour until the time ran out then doing C in 15 minutes after the contest =\
 » 5 years ago, # | ← Rev. 2 →   0 About problem 429A, a recursive version solution got RE while a iterative version passed.Is this a limitation of a interpreted language, so most people chose compiled languages to do the recursion?
•  » » 5 years ago, # ^ |   0 You seem to have set the stack to 100k, which seems to be enough at least for that particular test (but would probably fail on the maximum one). I would avoid python here. It barely works on topcoder, and they have WAY smaller datasets. If a correct solution to any problem takes half a second in C++, it would take like 5 seconds in python.
•  » » 5 years ago, # ^ |   0 Yes,it is a huge limitation. I don't prefer to use python for a recursive solution that has a depth of more than 1000(the default recursion limit in python) ... Though the stack size in codeforces is very large, but python requires more!
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 After some discussion, I think the root cause might be Python need larger stack frame so the stack just overflow. Thanks to tkcn.
•  » » 5 years ago, # ^ |   0 In my experience:sys.setrecursionlimit just sets "desirable" limit. If stack space ends before this setrecusionlimit is reached, python interpreter just dies silently. Also Python reserves a lot of stack space on each iteration. In one examples of mine I needed just 3,000 recursion limit and it died on my local machine at around 2,500. I didn't even receive any error messages — python just stopped execution and finished. 100K I think is impossible for Python even with very large stack space.
•  » » » 5 years ago, # ^ |   0 That's true. I also tried to set the stack size but still failed.http://codeforces.com/contest/429/submission/6609602