Hi everyone!
I would like to invite you to participate in HourStorm #10. The contest will start at 16:00 UTC,April 13, 2019
It's a 1-hour competition with 3 traditional (but nice) algorithmic tasks. You will receive points for every test case your solution passes, so you can get some points with partial solutions as well. Check the contest page for more details about contest schedule and rules.
The problems have been prepared by me and FastestFinger, helped by anil9717 and tested by Arpa. There are prizes for top 3 contestants: $75, $50 and $25 Amazon gift cards respectively. In addition, the top 5 will win HackerEarth t-shirts.
Good Luck and High Ratings!
Upd: Round begins in less that 22 hours!
Upd2: Round has begun. All the best!
Upd3: Round has ended. It was very exciting to watch the leaderboard towards the end with 4 people securing perfect score of 300 at 58th minute :)
Winners:
Congratulations to all the winners!
Sample tests were bad and didn't help to understand statements. Especially in P1 with the answer -1.
We realized later and apologize for the inconvenience. We will ensure clear samples for our future contests.
It is more a "understand the language" than a programming contest. Skipped this one because I (and google translate) was not able to decypher any of the problem statements.
In 2nd one, do we use any properties of the graph. Or just m*sqrt(n) bipartite matching was intended. Obviously inside binary search
Since no more than 2 people like a cake, we can do a case analysis for both the people and then create the bipartite graph. If there are three or more people, several cases would arise, like any two people out of three can finish the cake alone but any one cannot do it alone.
I get till the bipartite part. I want to know what is the complexity of this bipartite matching. Is it m*sqrt(n). Or do we use that graph has extra properties of one side having atmost degree 2 and do a better analysis or maybe better algorithm.
No there is no further use of the property. I think we can come up with another algorithm but I did not do further analysis.
So the total intended complexity is m*sqrt(n)*log(n) and time limit was 1 sec because your solution ran in less than 1/2 sec maybe. Great job on this!
Also was there any slow solution like n*m or something?
You're right. It could have been about 3 seconds or so. Hopcroft matching runs quite fast in general so I decided to go with 1s TL. I've come across several problems involving matching with lower time limits so I thought that shouldn't be a problem.
But likely those problems asked to run bipartite matching only once, not $$$O(\log n)$$$ times. Are you sure your solution works in 1s for any test?
I guess this will help with how good the tests are.
We too, were surprised. We expected greedy's to earn partial. We tried designing tests to avoid greedy. But this clearly showed that indeed our test data were weak.
I also understand the point you and Errichto are trying to make regarding time limit, and true we should have been more calculative.
Apologies for the inconvenience.