Good morning everybody.
January Clash '16 will start tomorrow (check your time zone). Duration is 24 hours and submitting time doesn't matter so you can join whenever you want.
Note the unusual starting time (compared to previous Clashes). We moved it a bit because of colliding with Facebook Hacker Cup.
You will be given 5 algorithmic problems and one approximate (optimization) one. All problems will have partial scoring (points for each test passed) and easier subtasks. Thus, everybody should find something for themselves. Getting full points on all 5 problems should be hard for everyone. Remember to solve as many subtasks as possible if you want to get to the top.
Problems were prepared by Lewin. He is an author of numerous contests, including many SRM's on TopCoder (link) so you don't have to worry about the quality of the problem set. I am a tester and an editorialist.
Problems are interesting and so do smaller subtasks. Don't expect them to be very easy though — some of them are far from being straightforward. Anyway, solve them first if you don't see a 100-points-solution.
There are prizes — t-shirts and Amazon gift cards. And the eternal glory of course.
Enjoy a contest.
WINNERS
Congratulations:
I want to congratulate anta for solving the hardest problem and Egor for almost solving it — but well, he won anyway. Kostroma had the best score in an approximate problem and HellKitsune was very close to that.
What was your approach to an approximate problem?
GL & HF
Bump. This is starting in about half an hour.
4 hours left and only one person has solved all 5 standard problems, though he is not on the lead. How will it end?
Nice problems (y) !
Seems like I'm missing well known technic to compute function over all permutations in Retract. Can someone enlighten me?
You have a sum that's like (-1)^(sign of permutation) * a_(1,p_1) * .. * a_(n,p_n) over all permutations p. You can compute this using a determinant.
Yes, I am stupid :) Thanks
That problem was in October Clash :D
@Egor, I didn't realize it too as a tester. Lewin had to tell me that I'm looking at a formula for determinant.
@Xellos, exactly the same problem?
Not exactly, but Lewin's comment summarises the solution of it.
By the way, it would be nice if Java would be upgraded to Java 8
Editorials are ready but we must wait a bit for a system to refresh. By the way, it was very interesting to watch the leaderboard in the final hours. EDIT — you can see editorials.
Where I can find editorial? Please post a link.
Open any problem, for instance, Remains and click on the editorial tab.
The general URL is: https://www.hackerearth.com/nameofthecontest/typeofthecontest/problemname/editorial/
I am wondering how this O(n) code got 100 points for problem remains. It would easily TLE for a case where x = 1,y = 10^9 and n = 10^9 .
what is wrong with my solution from "Rebuild" (2nd problem) :- solution
just a small mistake was there ,,, you should push the edges like this " v.pb({c, {min(a, b), max(a, b)}}); " http://ideone.com/t2xGpO (this code gets AC)
still don't get it, what is the difference ??
thanx for the help, got it :).