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.
Auto comment: topic has been updated by Lewin (previous revision, new revision, compare).
6 problems, 3 hours, looks much similar to Codeforces rounds style, why not making it rated???
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.
100 % right :D
what about the difficulty of the problems ?
It should be around div2b/c to div1d/e.
ok thanks
That should be a hard contest for us -us mean the people like me(noob's)-
I have not participated in the previous rounds. Am I able to participate in this round?
yes you can participated in this round
is it rated ?
Second elimination is live. Here is the link of the contest. https://www.hackerearth.com/challenge/competitive/indiahacks-2017-programming-wave-20-eliminator/problems/
was contest extended? why there's no info about that?
Was it possible to understand that there's no partial scoring in this round without actually submitting the solution?
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
This line is also presented in P5, but tourist got 74/100...?
I'm pretty sure it's full score
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.
Good enough for HackerFuckingEarth. Silently change the statement, silently extend the contest.
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
Of course they should rejudge only WA submissions.
Solution for initial problem didn't work for sample, did it?
So rejudging wouldn't help much
It worked, at least mine. Why not?
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
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.
Yes, I'll see if we can get it rejudged.
It seems that you decided not to rejudge it. Right?
All WA submissions should have been rejudged.
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?
This should be fixed now.
The statement for first problem is bullshit. You must change model solution not change statement.
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.
I wish i hadn't not qualified :/
How does memory work at Hackerearth?
I was only using static memory and kept getting this verdict several times.
but 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.
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.
Edit: Nvm, I forgot problems were 0 indexed. Thanks rajat1603 for pointing that out.
Wish each problem is high-quality.good luck and have fun!
I want to explain what happened with the official round. I was on a plane for about 12 hours and I wasn't able to watch over the beginning of the contest, so I wasn't able to do some last minute proof-reading and I couldn't answer clarifications initially. I told Arpa to watch over the round while I was unavailable (and I'm sorry to Arpa for putting you in this situation).
Anyways, I was able to get some brief internet access after I landed about an hour and a half into the contest, and I saw that there was a lot of confusion about Binary Blocks, which Arpa tried his best to address. Unfortunately, the problem statement was incorrect, so some of his clarifications were also incorrect, which is entirely my fault. I tried my best to clarify the situation, but I had to leave again in order to continue on my journey and get some sleep. I had decided it was best to make an announcement that the statement has been corrected, and time will be extended (but it looks like the announcement didn't work for some reason). Now, looking back, that may not have been the best solution, but I didn't feel I had enough time to change the test data to the first version of the statement. Anyways, I'll see what we can do about it and think about fair solutions to this issue (it may take some time, but I hope to get this done by next week).
I apologize for these issues. I probably shouldn't have agreed to write an important round if I knew I couldn't watch over it, and I promise it won't happen again.
Thanks for your explanations.
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.
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?
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.
Alice always win if n is odd.
How to solve Airplane Arrangments?
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).
Am I the one who solved B without lazy segment tree? http://mirror.codeforces.com/contest/838/submission/29256987
So you call this function
for each query:
Weak test data? Or I am missing something? If the former, you didn't really solve the problem :P
But I got AC :P
I think your solution gets tle on test like this.
Yeah, test data is weak
How to solve D?
can someone tell me whats wrong with my solution for b ? 29256918
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.
thanks found my mistake
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!
Where is editorial?
They are on hackerearth contest page, but I believe it is available only to participants of IndiaHacks.
Would the editorials be uploaded on Codeforces for this round?
I could not find editorial on contest page although I participated in the contest. Can you give me the link?
There is a button 'editorial' on each problem page.
There ain't no button may be they removed it.
This problem is extremely similar to problem G from IPSC 2009, and the editorial is explained very well there.
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.
Deleted!
Is B heavy-light decomposition?
I think that it's possible to solve B with HLD but you can use normal max-seg-tree.
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.
You might need to walk by edge of convex. :) Its clearly DP.
What do you mean by greedy algorithm in Prob.E? How do you expect someone to answer your question?
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...
Can anyone provide counterexample for this solution?
What is the idea to solve problem A?
Editorial.
Auto comment: topic has been updated by Lewin (previous revision, new revision, compare).
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?
Somehow I wasn't notified of the contest through email and didn't remember till today when I read this post.
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?
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.