### Блог пользователя lewin

Автор lewin, история, 12 месяцев назад, ,

On Sunday, August 6th, 22:00 IST, we will hold the 2nd elimination for IndiaHacks (some more details here). The top 900 individuals who qualified through previous rounds will have the opportunity to participate in this round. The top 25 global participants and top 25 Indian participants will advance to the final round. The link to the contest is here.

After the official round is over, the next morning, on Monday, August 7th, 11:35 IST, we'll hold an unofficial unrated mirror here on Codeforces. This mirror will have ICPC rules. For participants of the official round, please hold off on discussing the problems publicly until after this mirror is over.

I was the author of the problems in this set, and I hope you will enjoy the problems. I would like to thank zemen for testing the set, Arpa for writing editorials, r3gz3n for his help on the HackerEarth side, KAN for helping us set up the mirror contest, and of course MikeMirzayanov for the great Polygon/Codeforces platform.

The round will consist of 6 problems and you will have 3 hours to complete them. Please note that the problems will be randomly arranged in both rounds, since I couldn't figure out how to sort them by difficulty. Be sure to read all the problems.

UPD1: Updated time of official round and posted link to contest.

UPD2: We should have updated the leaderboard to accept solutions that followed the first version of the first problem. We have also increased the number of finalists to 60 total (30 global + 30 indian) based on this new leaderboard.

UPD3: Here is the list of qualifiers. Congratulations to everyone.

global
indian

•
• +135
•

 » 12 месяцев назад, # |   0 Auto comment: topic has been updated by lewin (previous revision, new revision, compare).
 » 11 месяцев назад, # |   +9 6 problems, 3 hours, looks much similar to Codeforces rounds style, why not making it rated???
•  » » 11 месяцев назад, # ^ |   +84 For this round, it's almost impossible for us to prevent leaking problems since there's 900 official participants. We should be able to have a rated version for the final round where leaking is less likely.
•  » » » 11 месяцев назад, # ^ |   +2 100 % right :D
 » 11 месяцев назад, # |   +23 what about the difficulty of the problems ?
•  » » 11 месяцев назад, # ^ |   +24 It should be around div2b/c to div1d/e.
•  » » » 11 месяцев назад, # ^ | ← Rev. 2 →   +29 ok thanks
•  » » » 11 месяцев назад, # ^ | ← Rev. 8 →   -15 That should be a hard contest for us -us mean the people like me(noob's)-
 » 11 месяцев назад, # |   0 I have not participated in the previous rounds. Am I able to participate in this round?
•  » » 11 месяцев назад, # ^ |   -21 nope. Same as me xD
•  » » 11 месяцев назад, # ^ |   +5 yes you can participated in this round
 » 11 месяцев назад, # |   -40 is it rated ?
 » 11 месяцев назад, # |   -18 Second elimination is live. Here is the link of the contest.  https://www.hackerearth.com/challenge/competitive/indiahacks-2017-programming-wave-20-eliminator/problems/
 » 11 месяцев назад, # |   +27 was contest extended? why there's no info about that?
 » 11 месяцев назад, # |   +55 Was it possible to understand that there's no partial scoring in this round without actually submitting the solution?
•  » » 11 месяцев назад, # ^ |   0 It turns out that there's line Marking Scheme: Marks are awarded when all the testcases pass.in the same block with TL and ML
•  » » » 11 месяцев назад, # ^ |   +33 This line is also presented in P5, but tourist got 74/100...?
•  » » » » 11 месяцев назад, # ^ |   +6 I'm pretty sure it's full score
 » 11 месяцев назад, # | ← Rev. 2 →   +46 lewin Problem Binary Blocks is gonna be rejudged, doesn't it? Cause this trick with changing the statement during the contest, when many people made submissions which were actually correct, is not a good way to handle the issue.
•  » » 11 месяцев назад, # ^ |   +58 Good enough for HackerFuckingEarth. Silently change the statement, silently extend the contest.
•  » » 11 месяцев назад, # ^ |   +26 I dont understand the issue because I started from another problem, and when I solved Binary Blocks the statement was already updated. However I think that if they rejudge and I get WA, then it will be unfair for me
•  » » » 11 месяцев назад, # ^ |   +24 Of course they should rejudge only WA submissions.
•  » » 11 месяцев назад, # ^ |   0 Solution for initial problem didn't work for sample, did it?So rejudging wouldn't help much
•  » » » 11 месяцев назад, # ^ |   0 It worked, at least mine. Why not?
•  » » » » 11 месяцев назад, # ^ | ← Rev. 2 →   0 Hm, maybe I didn't read the first version of the statement and just didn't understand the statement(or may be there were several incorrect versions) but my solution to what I read first gave answer that is less then expected
•  » » » » » 11 месяцев назад, # ^ |   +5 The version I was solving was that the table is padded with zeroes, and it was confirmed in discussions. Than the answer on sample is the same.
•  » » 11 месяцев назад, # ^ |   0 Yes, I'll see if we can get it rejudged.
•  » » » 11 месяцев назад, # ^ |   +3 It seems that you decided not to rejudge it. Right?
•  » » » » 11 месяцев назад, # ^ |   0 All WA submissions should have been rejudged.
•  » » » » » 11 месяцев назад, # ^ |   +10 I think my first submission hasn't.https://www.hackerearth.com/submission/10444755/This 3rd submission got AC after rejudged, and these two code outputs the same answer for all WA testcases of the first submission (number 2, 21, and 35). https://www.hackerearth.com/submission/10449302/Can you check if this submission has been rejudged?
•  » » » » » » 11 месяцев назад, # ^ |   +10 This should be fixed now.
 » 11 месяцев назад, # |   +55 The statement for first problem is bullshit. You must change model solution not change statement.
 » 11 месяцев назад, # |   +22 It seems that kut_msm1993 was trying to solve many hard problems simultaneously lol.You can check his submission log here by clicking "All Submissions" and enter the username in the "Search User" box.
 » 11 месяцев назад, # |   -11 I wish i hadn't not qualified :/
 » 11 месяцев назад, # |   +14 How does memory work at Hackerearth? I was only using static memory and kept getting this verdict several times.
 » 11 месяцев назад, # |   +52 problems will be randomly arrangedbut p0 was the easiest. so to me seems like a notorious shuffling.p4: when you need an extra problem for tomorrow's contest but it's hackerearth where nobody cares about quality, so you're fine.
 » 11 месяцев назад, # |   +28 Was it intentional that a brute force solution passes in P1? I coded my solution but got WA and couldn't find a bug. I wrote a brute force solution for testing and to be sure of its correctness I decided to submit it. I was really surprised when it just passed all tests.
•  » » 11 месяцев назад, # ^ | ← Rev. 3 →   +5 Edit: Nvm, I forgot problems were 0 indexed. Thanks rajat1603 for pointing that out.
 » 11 месяцев назад, # |   -11 Wish each problem is high-quality.good luck and have fun!
 » 11 месяцев назад, # |   0 Кажется уже слили этот контест
•  » » 11 месяцев назад, # ^ |   +10 Thanks for your explanations.
•  » » 11 месяцев назад, # ^ |   -32 If possible please host the contest again. Just because of that problem many were not able to qualify as they wasted alot of time on that question.
 » 11 месяцев назад, # |   0 So sqrt-decomposition won't work in time for B? And the observation that Alice will always win if the initial string has an even number of ways to re-permute is wrong in C?
•  » » 11 месяцев назад, # ^ |   0 I don't think it's wrong, however it's not easy to find all the strings that have even number of ways to re-permute. I tried some recursion that finds all such strings, but I'm getting wa 6.
•  » » 11 месяцев назад, # ^ |   0 Alice always win if n is odd.
 » 11 месяцев назад, # |   0 How to solve Airplane Arrangments?
•  » » 11 месяцев назад, # ^ | ← Rev. 2 →   +25 Let's reformulate the problem. Suppose we have n + 1 seats arranged in a circle and every passenger chooses a seat and a direction. We have (2(n + 1))m ways to do this. Now, since it's a circle every passenger will find a seat. Some seats will remain empty. An arrangement is good if the last seat is empty. In this situation, the same arrangement works for the original problem. Since exactly n + 1 - m seats will be empty, and every seat has an equal probability of being empty through all possible arrangements, the answer is (2(n + 1))m * (n + 1 - m) / (n + 1).
 » 11 месяцев назад, # | ← Rev. 2 →   -10 Am I the one who solved B without lazy segment tree? http://codeforces.com/contest/838/submission/29256987
•  » » 11 месяцев назад, # ^ |   +3 So you call this function intt dfs_dis (intt v) { intt res = rootweight[v]; for (int i = 0; i < g[v].size(); i++) { int to = g[v][i]; intt tmp = dfs_dis (to) + parweight[to]; res = min (res, tmp); } return res; } for each query: printf("%lld\n", distoroot (u) + dis (v)); Weak test data? Or I am missing something? If the former, you didn't really solve the problem :P
•  » » » 11 месяцев назад, # ^ |   -8 But I got AC :P
•  » » » » 11 месяцев назад, # ^ |   +11 I think your solution gets tle on test like this.
•  » » » » » 11 месяцев назад, # ^ |   +3 Yeah, test data is weak
 » 11 месяцев назад, # |   +6 How to solve D?
 » 11 месяцев назад, # |   0 can someone tell me whats wrong with my solution for b ? 29256918
•  » » 11 месяцев назад, # ^ |   +3 My approach is using Lazy propagation on the array of depth (+return edge) in euler tour order. Which works well in time. Your approach seems different. If you clarify it then it will be easier to debug.
•  » » » 11 месяцев назад, # ^ |   0 thanks found my mistake
 » 11 месяцев назад, # |   0 Btw editorials for Airplanes and Earnings problems suck :( Hope they will be updated or at least explained in more details here, because the most interesting parts are skipped. Yes maybe I can understand them after some thinking reading the code, but I thought that editorial should explain the ideas by itself too.On the other side, I must say that problems were interesting to solve, except the issue in the easiest problem and yet another standard problem to write segment tree on Euler tour. So thank you for the contest!
•  » » 11 месяцев назад, # ^ |   +11 Where is editorial?
•  » » » 11 месяцев назад, # ^ |   0 They are on hackerearth contest page, but I believe it is available only to participants of IndiaHacks.
•  » » » » 11 месяцев назад, # ^ |   +4 Would the editorials be uploaded on Codeforces for this round?
•  » » » » 11 месяцев назад, # ^ |   0 I could not find editorial on contest page although I participated in the contest. Can you give me the link?
•  » » » » » 11 месяцев назад, # ^ |   0 There is a button 'editorial' on each problem page.
•  » » » » » » 11 месяцев назад, # ^ |   0 There ain't no button may be they removed it.
•  » » 11 месяцев назад, # ^ | ← Rev. 3 →   +5 This problem is extremely similar to problem G from IPSC 2009, and the editorial is explained very well there.
•  » » » 11 месяцев назад, # ^ |   0 Yeah thank you, it turned out that the problem statement of Airplanes was too hard for me to understand correctly, now everything is clear, cool solution.
 » 11 месяцев назад, # |   0 Будет ли разбор?
 » 11 месяцев назад, # | ← Rev. 2 →   +5 Deleted!
 » 11 месяцев назад, # |   0 Is B heavy-light decomposition?
•  » » 11 месяцев назад, # ^ |   0 I think that it's possible to solve B with HLD but you can use normal max-seg-tree.
 » 11 месяцев назад, # | ← Rev. 2 →   -17 Why greedy algorithm in Prob.E is not right? For a start point A, there are left side and right side, for example, first go to the right side, then to the left side, then right side... Then you enumerate all the point as start point, enumerate both side as a start direction.
•  » » 11 месяцев назад, # ^ |   +3 You might need to walk by edge of convex. :) Its clearly DP.
•  » » 11 месяцев назад, # ^ |   +40 What do you mean by greedy algorithm in Prob.E? How do you expect someone to answer your question?
•  » » » 11 месяцев назад, # ^ |   +18 For a start point A, there are left side and right side, for example, first go to the right side, then to the left side, then right side...
•  » » » » 11 месяцев назад, # ^ |   0 Can anyone provide counterexample for this solution?
 » 11 месяцев назад, # |   0 What is the idea to solve problem A?
•  » » 11 месяцев назад, # ^ |   +3
 » 11 месяцев назад, # |   -11 Cause this trick with changing the statement during the contest, Pembesar Payudara when many people made submissions which were actually correct
 » 11 месяцев назад, # |   -11 LOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOL
 » 11 месяцев назад, # |   0 Auto comment: topic has been updated by lewin (previous revision, new revision, compare).
•  » » 11 месяцев назад, # ^ | ← Rev. 2 →   0 How to see only Indian Rankings ?Or could you say what is the rank of the 30th Indian on the ranklist?Also do Indians in top 30 count under global or Indians?
 » 11 месяцев назад, # |   0 Somehow I wasn't notified of the contest through email and didn't remember till today when I read this post.
 » 11 месяцев назад, # |   +43 Am I the only one who read information on the contest page and aimed at top 50 because there was nothing about top 25 global and top 25 Indian?
•  » » 11 месяцев назад, # ^ |   +10 I have updated the details. We have increased the number of finalists to 60 total (30 global + 30 Indian) based on this new leaderboard. Sorry for the inconvenience.