Hello Coders!
I invite you to participate in HackerRank's weekly contest.
Link http://hackerrank.com/w9
Starting today 25th August 16:00 UTC there will be 1 challenge posted daily in increasing order of difficulty.
Penalty will be (Submit — View) time, which allows you to start late. But if you delay by 24 hours 10% score gets decayed per day. More rules can be seen here
With new addition to our leaderboard you can see the time penalty on the leaderboard itself Example
Contributors
Day 1 & 2: amitp08
Day 3: shaka_shadows
Day 4: viv001
Day 5: CherryTree
P.S. For contribution you can contact me or mail to: hackers [at] hackerrank [dot] com
1 shubhamutwal 30.00 0:07 India
2 nishit 30.00 0:20 India
Well, I'm quite sure that it's impossible to read the statement and type sufficient number of characters in 20 seconds. This penalty system (submit — view) is nice, because it allows people to participate when they have some free time, but I hope that organizers will disqualify people who definitely do not play fair.
You know, the so-called Internet superheroes...
I think the most probable cause is they spent time writing a script that can parse HTML, read the problem statement and write code that solves it according to a builtin database of algorithms. In fact, given how heroic this task is, they should be just awarded the contest win right away for their accomplishments and contribution to artificial intelligence.
Or they used 2 accounts?
No... definitely not. That would be impossible.
Why do you think we took all the pain to display penalty? :)
Right now all these are looking funny/fools and will be scrutinised for copy and other things and eventually disappear from leaderboard.
Cleaned Day 1 and Day 2 :)
Very effort, much appreciate.
Wow.
Lol, it's awesome how the number of participants is roughly halved for each problem after its day has passed :D
And time penalties for each problem are roughly doubled.
Nice problems. Nice week. Nice contest.=)
How to solve "Alex vs Fedor"?
For finding count of spanning trees we can use Kirchhoff theorem.
But how finding count of MINIMAL spanning trees?
This is a classic problem, see http://apps.topcoder.com/forums/?module=Thread&threadID=626113
What I could not do was calculate a determinant with these big numbers, so I can't help you with that.
You just need to do gauss using 2 prime modulos and then combine them using Chinnesse reminder theorem
We can even take modulo big prime greater than 10^18. modular multiplication or inverse of number fitting long can be done easily.
@ffao the link is broken, can you please update the link ?
Fixed, thanks.
There's also a neat algorithm which doesn't use modular arithmetic at all and works similar to Euclidean algorithm. See for example riadwaw's code — https://www.hackerrank.com/rest/contests/w9/challenges/alex-vs-fedor/hackers/AlexDmitriev/download_solution
I used the approach presented in this paper: http://www14.informatik.tu-muenchen.de/konferenzen/Jass08/courses/1/pieper/Pieper_Paper.pdf
But I didn't realize I could simply compute determinants modulo something, so I implemented my own class of fractions where the numerator and the denominator are big numbers (the worst parts were the need to do division and compute GCD for big numbers). I got TLEs with this approach and after several rounds of optimization, in the last day of the contest, I was able to pass all the tests except 4 of them (where I still got TLE, though probably not by much). The only benefit is that I now have these fractions implemented and ready for future contests :)
You can refer this editorial
https://www.hackerrank.com/contests/w9/challenges/alex-vs-fedor/editorial
It looks ugly as of now, but we'll format it soon