Hi!
Ad Infinitum is back with 9th Edition, a monthly contest restricted to mathematics domain, held on HackerRank.
Register at https://www.hackerrank.com/infinitum9
The contest commences on 12th December 15:30 UTC. You are allowed to enter the contest anytime, for tie breaking the timer will start when you view the first challenge, which allows you to start late at your convenience, but once started try to finish as fast as possible to be on top of the leaderboard :)
It's a 2 days contest with 8 problems (3 Easy, 3 Medium, 2 Hard)
Scoring Distribution: 20 20 20 40 60 80 100 120
Top 10 on leaderboard gets Cool HackerRank T shirt,
Contributers
kevinsogo
oversolver
bayleef
amitp08
minimario
Detailed editorials will be available by the end of contest :) I suggest you to try all challenges and at the end of contest understand the solutions.
GL&HF
Why in my submission WA was reported as timeout? Or was that caused by some other issue? I'm saying about my first submission to first problem. I also got timeout in 8th problem and I don't know whether my program runs too slow or is it just giving WA?
By the way in my opinion problems are much easier than they used to be in Ad Infinitum. Stating that "Merge list" problem is "Difficult" is pretty humiliating for contestants xd. But at least 7th and 8th problem are fun to solve and that's what really counts :).
Hi can you give me your suspected submission link/id? (Email me)
I have changed the difficulty tags, i think it was a bug as you notice everything had just 1 tag "difficult" sorry about that :)
I am not sure about "much easier". Ok, first 7 problems are easy (and even if one can't solve last 2 of them — it takes just a few minutes to Google both); but the last one is good enough:) 9 full scores is not too much — comparing to 6 full scores in Ad Infinitum 8.
It turned out that i made 147 wrong tries on the last problem before finally getting AC:) I think that this number would be larger in case there were no "your submission rate is too high" :D I am surprised that there are almost no partial solutions for it — it is enough to have solution which works 10-15 seconds on max.test in order to pass testcase #2 and get 12 points.
I agree that last problem was pretty tough, but I was talking mainly about earlier problems :P (I somehow emphasized that in my last sentence). I also tried last problem, but gave up after seeing that my baby-step giant-step got TLE even after modifying it to this specific task, so it ran in better complexity :<. And I agree about almost no partial solutions, that should be a room for improvement for next Ad Infinitums.
Btw I couldn't google 7th problem, though I wasn't that determined to do it and having fun from solving problem became stronger than being fast :P.
Jump between 7th and 8th problem is too big, i agree.
I guess that my solution for the last problem is not the same as in editorial (i am a bit scared by a lot of formulas there, so i haven't read it yet) — after making problem X1 * C1 = Y1 * C2(modC3) i am moving from it to a problem X2 * C4 = Y2 * C5(modC6) such that X2 and Y2 are both comprime with C6 and cost of X2 is larger than cost of Y2. Then i am just checking all possible values for C4 in increasing order — using the fact that now values of C5 should be either same small numbers (for X2 = = Y2) or random enough in other case, so we'll have to check just
values before finding the best one.
If I understood well, I got the same idea for the last part :). But TLE on BSGS blocked me from taking a proper care of it :P (in codes I've submitted I did it in wrong way, I think, but I knew how to fix this). Indeed those formulas are really scary :D.
By the way, 147 submissions :o!? With that annoying loading of codes with fleeing "Submit" button? That summed is something like 1h of watching Submit button escaping :P.
Oh, so i was not the only one with this problem:) It was not this way all the night:) Sometimes editor was working well, sometimes it was not displaying some characters; and at some point during a night i found a nice hack — if you try to drag editor's scrollbar while "Submit" button is still on it's way down — everything turns to be OK in the very same moment.
For the 7th problem Computer Virus, I came to a solution using combinatorics. I got WA though. Can anybody point out what is wrong with it?
IDEA: Suppose it has only 3D. Then it will have 3 axis, each with it's own positive and negative. (x+,x-,y+,y-,z+,z-). I will just find the answer for 1 quadrant (x+,y+,z+) and then multiply with 2^n to get all the quadrants.
How do I get integer points of 1 quadrant? Suppose I want all points with taxicab distance exactly T. So I will partition T into 3 parts. So using ball and urn theorem, that will be NCK(T+n-1,n-1). Now I have to find sum over 0<=T<=t(the t they gave). This is vertical sum of binomial coefficient, which is equal to NCK(t+n,n).
After that, I remove the boundary values ( points that lie on the axis ) and multiply with number of quadrant, and finally add back the boundary values appropriately.
Got only 4 test cases correct. Saw in the editorial that they used generating function. I am curious why my solution does not work? Cause it kinda make sense.
UPD1 Never mind. Found my mistake. UPD2 AC. Had to modify the idea a little bit, but it worked.