### Errichto's blog

By Errichto, 4 years ago, ,

Hi everybody.

The IndiaHacks finals will take place tomorrow (on Saturday). The contest is being organized by HackerEarth. Just after the official finals, the CF round will start (check-your-time) with almost the same problems. You can treat it as a standard CF round — there will be 5 problems in each of 2 divisions, and 2 hours to solve them. Two divisions will compete together on the problem set with 7 problems, with 2 hours to solve them.

I want to especially thank I_love_Tanya_Romanova for testing the problems, GlebsHP for help with making the CF round possible, and MikeMirzayanov for his awesome attitude and for the Polygon system. Setters: lewin, k790alex, Sokolov, Errichto. Testers: I_love_Tanya_Romanova, Errichto. Small help: belowthebelt, raviojha2105, johnasselta, Stonefeang. And my big thanks to HackerEarth for inviting me to Bangalore, it's truly a vibrant city.

Some info only for 40 official finalists — Remember not to discuss anything until the CF round ends (so, at least 2 hours after the official contest ends). You will find all important information at link-to-the-contest. You can ask me questions by PM on CF or on HE, and I will put answers in the "Challenge Details" at the link provided. Do not use comments here because it can only confuse others. You can use some old blog about the IndiaHacks semifinals if you want to discuss something.

I wish you great fun and no frustrating bugs. Enjoy the contest.

Scoring: 500-1000-1500-2000-2500-3500-3500.

WINNERS

1. TooDifficuIt, the only one to solve all 7 problems!
2. izrak
3. jcvb
4. andrew.volchek
5. ikatanic

In the official finals there were technical issues with the stack size (it was again only 8MB) and constraints in E weren't correct at the beginning. We want to fix it as much as possible, without any guessing though — we can't say how much time did you waste because of something. If you were affected then write to me PM with the description of the situation. Your time penalties will be canceled (and maybe some earlier submission will be accepted, if only the stack size didn't allow you to get AC).

Editorial is being created here.

• +197

 » 4 years ago, # |   +6 So the official finalists lose a rated contest? Or is there a way to add ppl to the standings afterwards and let them be rated?
•  » » 4 years ago, # ^ |   +21 Yes, they do lose a rated contest. It's impossible to add them to the leaderboard, too many differences in the problem set.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 most of them will probably lose two rated contests if they are competing on-site
•  » » » 4 years ago, # ^ |   -49 The top 19 or so won't be competing onsite. World level vs country level...
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   -18 why my comment was removed? "because of codeforces rules violation" — i only showed how xellos was offending the honorable authors.
 » 4 years ago, # |   0 We always expect some photographs in these onsite contests :)
•  » » 4 years ago, # ^ |   0 You'll get all the photo updates tomorrow during the live contest. :)
•  » » » 4 years ago, # ^ |   +1 Where is the blog?
 » 4 years ago, # |   -17 A rated div2 contest after a long time.
 » 4 years ago, # |   +67 Welcome to India Errichto! :)
 » 4 years ago, # | ← Rev. 2 →   0 Idk why, but March is so adored by different cups and competitions. It's hard to take a part in all of them, especially (speaking about me) because there is some All-ukrainian competition in this time too (I'm talking about Math and Informatics). So, can someone explain me why March is so adorable?
 » 4 years ago, # |   +15 Note changes in the blog — the contest will be combined for two divisions. Make sure to register again.
•  » » 4 years ago, # ^ |   +8 And the contest will last for 2 hours.
 » 4 years ago, # | ← Rev. 2 →   +75 It's goodbye 1394(in Iran) Happy new year(1395) :)))
•  » » 4 years ago, # ^ |   +25 Happy New Year !!!
 » 4 years ago, # |   +6 I think these 2 contests (CROC & IndiaHacks) are closer time-wise in history of codeforces.
•  » » 4 years ago, # ^ |   0 It's probably the technical issue that caused the divisions to be combined :P http://codeforces.com/blog/entry/43838
 » 4 years ago, # |   0 Thanks for Announcement .
 » 4 years ago, # |   +6 The name of this contest is "IndiaHacks" and none of the writers or the testers of this contest are Indian. Not that I am saying it's a problem but it feels a little weird.
 » 4 years ago, # | ← Rev. 2 →   +47 Still decreasing in Div 1 after 6 months :(
•  » » 4 years ago, # ^ |   +6 finally positive rating changes :))))
 » 4 years ago, # |   +33 "The duration is 2 hours. I will try to inform you about the duration in a few hours."Just in case the duration will change again.
 » 4 years ago, # |   -10 Will the format be ACM or standard CF?
•  » » 4 years ago, # ^ |   +5 It's never written about ACM, so I think it will be standart CF
 » 4 years ago, # |   +16 I submit a hack but get Unexpected verdict.I want to know what happened.
•  » » 4 years ago, # ^ |   +44 Oh god, not again.
 » 4 years ago, # | ← Rev. 5 →   +6 I feel many submissions will fail in B. Will generating all strings give time out? And can it result in int overflow?PSMy submission was running too slow for this test case6 26aa aab aac a.. .. till az aPPS — I was wrong. I forgot that we can only use a,b,c,d,e and f.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 6*6*6*6*6 = 7776 won't time out and neither will 6^6 = 46656
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 You mean: 6^6 or 6^5?
•  » » 4 years ago, # ^ |   0 Considering that the length must be between 2 and 6 inclusive, I really don't think that generating all the possible strings will be a problem
•  » » 4 years ago, # ^ |   +5 46656 total strings possible in worst case and O(n) operation per string. Why should it tle? And no chance of overflow as total possible strings are 46656
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 You can only use 'a', 'b', 'c', 'd', 'e' and'f', the test case you provided is invalid
•  » » » 4 years ago, # ^ |   +1 I forgot that. My bad.
•  » » » » 4 years ago, # ^ |   0 I think the test case is fine. You just have to put a check and skip the ones with 'g' and all. A possible hack case?
•  » » » » » 4 years ago, # ^ |   0 "It's guaranteed that... all ai and bi consist of only first six lowercase English letters."
•  » » 4 years ago, # ^ |   0 I was generating all possible strings but somehow i am failing test 6. Is answer to this 26 btw?
 » 4 years ago, # |   +5 Such a difference between B and C. I think in B condition "a.i!=a.i for all i!=j" makes the problem much more easy
 » 4 years ago, # |   0 Anyone can share his idea about D/E?
•  » » 4 years ago, # ^ | ← Rev. 4 →   +5 D. Max-flow with some tricks: Binary search on the answer. For answer being tested edge capacity equals maximum number of bears that can go through it. Calculate max flow. If it's more or equal than number of bears — such answer is achievable.E. Let's consider graph with all non-forbidden edges (G). G' = G with vertex 1 removed. Proposal: Answer is possible if and only if following conditions are met: Degree of vertex 1 in G more or equal than k. Number of connected components in G' is less or equal k. Each connected component in G' is connected to vertex 1 in G.
•  » » » 4 years ago, # ^ |   0 for E, I deduced this much, but how do we check the condition that number of connected components in G' <=k ?
•  » » » » 4 years ago, # ^ |   0 Basically we do dfs. We need to do in some "trickier" way to fit in time. You can take a look on my solution: https://github.com/aeremin/Codeforces/blob/master/alexey/Solvers/6xx/653/Solver653E.cpp
•  » » » » 4 years ago, # ^ |   +10 You can check problem E from cf120 and it's tutorial
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 In D, I did the following:1). I used binary search on the answer.2). How can we check if we can use this weight? 2. 1). Calculate the weight that one bear carry. It will be totalWeight / x. 2. 2). Now, for each edge, we can count how many bears can go through this edge. 2. 3). Count maximum flow. The weight capacity of the edges in the graph will be the values we've counted in 2. 2). 2. 4). When we've counted maximum flow, it will be maximum count of bears. If this value will be more or equal than x, then the bears can carry this weight.
•  » » » 4 years ago, # ^ |   0 I used the same approach but I am getting WA on test 44. Its because of precision issue, but I do not know how to handle this. LINK Correct answer: 1.000000 Output: 0.99991126
•  » » » » 4 years ago, # ^ |   0 You should change condition in binary search. Now you EPS = 10^(-9) * x Correct condition is (Math.abs(r — l)*x / (Math.max(r,1)) > E)
•  » » 4 years ago, # ^ |   +5 D: Binary search on doubles the check with maxflow if you can travel to the end with each bear's weight equal to the current middle in the binary search.
 » 4 years ago, # |   +3 There is a strange bug(?) happening during contests. Whenever I'm seeing someone's solution, and this solution is hacked or resubmitted, a message pops up and I automatically log out.This happened in yesterday's contest too.
 » 4 years ago, # |   +8 When will start system tests?
•  » » 4 years ago, # ^ |   -13 soon
 » 4 years ago, # |   +17 How we can solve C simply?
•  » » 4 years ago, # ^ |   +8 Iterate through the array if you found a bad index i then you must swap i or i + 1. So try swapping i and i + 1 with the rest of the array and check if each swap will fix all the bad indices.
•  » » » 4 years ago, # ^ |   +19 OH MY GOD , thanks!!! My brain stopped in the contest. How stupid am I !!!
 » 4 years ago, # |   0 How to solve C? :)
•  » » 4 years ago, # ^ |   +12 I think that you can find all "invalid" positions (d[i] <= d[i+1] or >=, whatever), and brute force to "fix" it with swapping with any other position. It's not hard to see that invalid positions cannot be too many (i set limit = 9, but should be <= 6 or smth), and you need a O(1) checking then.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +14 Ohh sh*t, that is actually too easy, thanks!
•  » » » 4 years ago, # ^ |   0 I timed-out when trying all swap combinations, I never thought to only check bad indexes! :(
•  » » » 4 years ago, # ^ |   0 How did you deduce that the number of invalid positions would be less than 6?
•  » » » » 4 years ago, # ^ |   +3 We touch only two numbers. Let indices be i and j. Proposal: swapping them can fix only positions {i — 1, i, i + 1, j — 1, j, j + 1}. So if we have more than 6 "bad" positions, some of them will still be unfixed.
•  » » » » » 4 years ago, # ^ |   0 Ohh, thanks. :)
•  » » » » » 4 years ago, # ^ |   0 oh, thank yo for your explanation.
•  » » » 4 years ago, # ^ |   0 Hello can you suggest similar problems! I fail on such easy to "see" problems.I knew that 4th was binary search with max flows but I don't know much about any algorithm of Max Flow so couldn't solve it! I was solving C yesterday using ternary search( I didn't knew much theory about it ) and couldn't debug (although I had that sliding window in my mind) I switched to D but was unable to deduce the fact! So Probably I am having very bad contests these days! I think I should take a break :/
•  » » » » 4 years ago, # ^ |   0 CantGetAnyACWhyAmISoWeak
•  » » » » » 4 years ago, # ^ |   0 I feel very stupid for not solving C.CantGetAnyACWhyAmISoWeak
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   0 You just need more practice to improve your intuition! :)BONUS: Thank you guys for C explanation!! I managed to code it :) I needed only to add a set to avoid counting two times swaps. Is there a way to avoid it? 16822666
•  » » » » » 4 years ago, # ^ |   0 Yes, see TooDifficuIt's code: http://codeforces.com/contest/653/submission/16814329
•  » » 4 years ago, # ^ |   +6 Considering positions i and i+1 as invalid if sequence[i] >= sequence[i+1], for odd i, or if sequence[i] <= sequence[i+1], for even i.You must notice that if there are more than 6 invalid positions then a single swap won't fix it, so you output 0.When there are 6 or less invalid positions just test all possible changes with them.The complexity is O(6*N) if you check if one change makes the sequence nice in O(1).
•  » » » 4 years ago, # ^ |   0 A really nice implementation of the above idea by TooDifficuIt : http://codeforces.com/contest/653/submission/16814329
 » 4 years ago, # | ← Rev. 2 →   +51 Looks like problems in the Codeforces round are significantly easier than those in the HackerEarth round.
•  » » 4 years ago, # ^ |   +8 is it bad?
•  » » » 4 years ago, # ^ |   +7 Well, this round was initially announced as an online mirror of IndiaHacks Algorithm Finals, but now it looks more like a different contest. Also, because the problems are different, it is not possible to easily compare results of this round with those of the official participants, and discussing problems is also more difficult because some problems are different, and all the problems are in a different order.Not to mention that I spent some time solving problem E with a wrong constraint.
 » 4 years ago, # |   +9 The period of waiting for systest to begin, is painful. They lock problemset and all. Maybe next time I'll contribute too so they can get more servers and keep them open for generic solving >.>
 » 4 years ago, # |   0 What is the idea for problem D ?, I tried to solve using binary search the maximum amount of weight one bear can deliver and check if it's possible using fordFulkerson. But I am getting WA in pretest 6. Am I missing anything ?
•  » » 4 years ago, # ^ |   0 Did you copy-pasted Ford-Fulkerson from some site? I got WA when used some apparently broken max-flow algorithm from e-maxx.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yes, I copied it from geeks for geeks.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I have copy-pasted one from https://web.stanford.edu/~liszt90/acm/notebook.html#file3 (called PushRelabel) and got AC. You can try to use it instead and check if it will got you AC.
•  » » » » » 4 years ago, # ^ |   0 Yeah I will try, thank you.
 » 4 years ago, # |   +24 Damn it, integer overflow in D!!!. T^T
•  » » 4 years ago, # ^ |   0 Feel the same...
•  » » » 4 years ago, # ^ |   +27 I think you're lying, because you get ACs.
•  » » » » 4 years ago, # ^ |   0 CantGetManiACWhyAmISoWeak?
 » 4 years ago, # |   -28
•  » » 4 years ago, # ^ |   +28 Thank you. I myself would not have found.
 » 4 years ago, # |   0 How to solve D. I figured out that if I obtain residual graph and after that find flow from each edge which is leaving source node than I have to distribute 'x' bears over them. But how to do it? Or I started wrong?
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # |   +62 Summary of HackerEarth problems: A: like Codeforces problem 653C - Bear and Up-Down. B: like Codeforces problem 653E - Bear and Forgotten Tree 2. C: like Codeforces problem 653G - Move by Prime. D: like Codeforces problem 653F - Paper task. E: like Codeforces problem 653B - Bear and Compressing, but with n ≤ 1000, q ≤ 216, operations with equal ai are possible. F: like Codeforces problem 653D - Delivery Bears, but need to compute the answer for x = x0, x0 + 1, ..., x0 + k - 1, with k ≤ 104.
•  » » 4 years ago, # ^ |   0 How to solve F from this problem set?
•  » » » 4 years ago, # ^ |   +8 If I'm not mistaken, if you already have a valid flow for x0, then the answer for x0 + 1 depends on the least amount of wood each bear needs to lose to create a new augmenting path from source to sink. If you compute, for each edge in the residual graph, how much wood each bear would need to lose to be able to send one extra bear through that edge (it can be 0 if the capacity is not full), then this is equivalent to finding a path from source to sink with the minimum maximum weight, which can be solved in O(E log V) by Prim or Kruskal.
•  » » » » 4 years ago, # ^ |   0 It seems to be true. Thank you!
•  » » » » 4 years ago, # ^ |   +18 Yeah, that's how I solved this problem. The algorithm looks more like Dijkstra though, with the sum replaced with maximum. I tried to find the initial flow in the same way, but it didn't pass TL, so I had to add binary search.
•  » » 4 years ago, # ^ |   0 my solution for B( codeforces) and E ( hackerearth) has a complexity n*26*q .code
•  » » » 4 years ago, # ^ |   0 Your program doesn't solve E from hackerearth.
•  » » » » 4 years ago, # ^ |   0 Is there any way to access the problemset from onsite ? I tried looking at hackerEarth recent contest but couldn't find anything.
•  » » » » » 4 years ago, # ^ |   0 I think it will become available in a couple of days, maybe tomorrow.
 » 4 years ago, # | ← Rev. 2 →   +177 Human stupidity at its finest: taking 50 minutes to notice a compilation error -.-'(I'm so happy I did it before the contest ended, though :P)
•  » » 4 years ago, # ^ |   0 I know that feel bro, same sh_t with MLE, so now I catched -27 to my rating
•  » » 4 years ago, # ^ |   +51 Wow so you just submit and don't wait to see whether you passed the pretests? #justgrandmasterthings
•  » » » 4 years ago, # ^ |   0 I usually think so:"Im not going to waste my time on waiting, see later"trying to solve next problemforgot about previous"OH WAIT WTF"
•  » » 4 years ago, # ^ |   +52 I had a similar issue.I've noticed that I actually got TL for C only after successful submission for D. I'm pretty sure that I've seen "Pretests passed" for C and I think that it is the issue of twitchy status line that can change from "Running on pretest 7" to "Running on pretest 3" and back several times before showing an actual verdict. That's pretty sad :(
 » 4 years ago, # |   0 Why didn't my submission fail?This line is wrong according to mez.pb(a[k]+c[j][i-3]);It should bez.pb(a[k]+c[j][0]);
 » 4 years ago, # |   +12 A total rating gain of 1 in last 24 hours
•  » » 4 years ago, # ^ | ← Rev. 2 →   +19 A total rating change of 0 in last 24 hours :P
•  » » » 4 years ago, # ^ |   +33 Same here because I didn't participate in any of the contests :D
 » 4 years ago, # |   +8 12 Legendary grandmasters! :D
 » 4 years ago, # |   +25 LolHashes with modulo = 264 passed :)16814596
•  » » 4 years ago, # ^ |   -15 Time limit for this problem was intended to be 1 second or 2 seconds for slow languages like Java to avoid these kind of solutions.
 » 4 years ago, # |   +161 TooDifficuIt rating looks like typical track in Gravity Defied now
 » 4 years ago, # |   0 I have got WA 2 for Problem C.But locally with gcc 4.9 and on ideone.com with C++ 14 this code on this test was executed correctly.http://codeforces.com/contest/653/submission/16816483What's wrong with this code?
•  » » 4 years ago, # ^ |   0 Same thing with problem B.http://codeforces.com/contest/653/submission/16817781
 » 4 years ago, # |   -12 Great news! We have found another Legendary Grandmaster today! so there are 12 LGM's right now.
 » 4 years ago, # | ← Rev. 2 →   +46 Somehow, tests for D allow to search only for blocking flow, not for maximum. Compare this accepted solutions: 16816698, 16816675 on next test: 4 5 2 1 2 3 2 3 3 2 4 2 1 3 2 3 4 3 (outputs are about 3 and 4, second one is correct).
 » 4 years ago, # |   +89 There is a overflowing bug in my code of problem D.My code will fail on the following case: 4 3 100000 1 2 2 2 3 1000000 3 4 2 And some other participants also passed the system test using int to store the capacity of edges.
•  » » 4 years ago, # ^ |   0 I think such test should be added and then to rejudge all submissions. And calculate rating afterwards.
•  » » » 4 years ago, # ^ |   +6 Also a test like the one Kaban-5 mentioned should be added.
•  » » 4 years ago, # ^ |   +29 Like me... :)
 » 4 years ago, # |   +11 What are results of onsite(?) round?
 » 4 years ago, # |   +65 Remember, HackerEarth has different problems.
 » 4 years ago, # |   0 Can you guess or prove why does it work? Problem E solution. 16820873
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 I suppose the testset in E is pretty weak. My original solution was too slow... so I just done some hacks in order to pass pretests: 16814798. I was super surprised when it was accepted on the main tests, because I'm almost 100% sure it's wrong.
•  » » » 4 years ago, # ^ |   0 Have you tried to find some tests?I tried but has not found.
•  » » » » 4 years ago, # ^ |   +10 Yes, for my solution I can came up with simple test on ~50 vertices (constant that I use in the code) that will fail. Essentially, there will be one bridge that connects one separate vertex to the fully connected component, and all the edges except one from this component to this vertex will be prohibited. Then this edge won't be discovered and the vertices will be considered disconnected.
 » 4 years ago, # | ← Rev. 4 →   +76 Another suspicious North Korean code!http://codeforces.com/contest/653/submission/16815024http://codeforces.com/contest/653/submission/16811842I think those codes are really identical — simply some names are the difference (ex, 'doit' <-> 'foo', 'xvalue' <-> 'dat')I actually didn't really care about those stuffs before, but my 2599 rating makes me bit sensitive. MikeMirzayanov, can you investigate these deeper? My temptation grew bigger, and I finally wrote a blog post about it. http://codeforces.com/blog/entry/43880
•  » » 4 years ago, # ^ |   -46 Says the South Korean...
•  » » » 4 years ago, # ^ |   +81 Regardless of nationality, The fact remains :)(And the desire for IGM also remains..)
•  » » 4 years ago, # ^ |   0 Is it possible that this is some sort of template or part of an official solution to an earlier (North Korean) problem? Also, it's interesting that those nearly identical submissions still make a difference of 15 ms.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +10 It's not possible that this is some sort of template — problem E from this round wasn't that typical. Considering the huge simillarities between those two submission (they only replaced some name) maybe they were a part of an official solution, but then there is no way to punish cheaters (since the same logic belong to any cheated code). So this should be decided upon other reasoning like previous decisions.Also, "completely identical" submissions can easily make a difference of 15ms, so IMO it's not that interesting..
 » 4 years ago, # |   +6 Will be tutorial?
 » 4 years ago, # |   +5 Editorial Please!!!
 » 4 years ago, # |   +16 wrong answer 1st numbers differ - expected: '1.0000000', found: '0.9999918', error = '0.0000082'`What a sad story :((
 » 4 years ago, # |   0 What's the meaning of dsu? I can see it in Problem tags sometimes.
•  » » 4 years ago, # ^ |   +18 disjoint-set union. aka union find tree
 » 4 years ago, # |   +14 Why has the round been made unrated ?
•  » » 4 years ago, # ^ |   0 My rating is as low as it used to be. Nothing's unrated.
•  » » » 4 years ago, # ^ |   +6 It was made unrated for a while because they were recalculating the ratings to remove cheating cases etc. I think.
 » 4 years ago, # |   +38 Errichto And India Thanks for coming to India. I hope you had a great time. Image1 Image2 Image3 Image4 Image5