Hello Codeforces,
I invite you all to participate in HackerEarth's October Easy on the 1st of October at 10:00 PM IST.
You will be given 6 problems to solve in 3 hours. The problem difficulty will be similar to that of a Div. 2 round on Codeforces. Each problem will be worth 100 points, but partial scoring is allowed so you can try to pass as many tests as you can.
The contest will be rated and will have prizes for the top 5 beginners.
The problems have been set by Himanshu Jaju(himanshujaju) and me(rivudas) and tested by Yury Bandarchuk(Yury_Bandarchuk). I would also like to thank all the Hackerearth admins for their help.
Good luck and have fun.
Edit 1 — The contest has started. Good luck to all.
Edit 2 — The contest is over now.
The top five winners are -
1. Trumen
2. -Morass-
3. 1100011101
4. felix
5. hellman_
Thanks to everyone for participating. Hope you liked the problems. The editorials will be out soon.
Auto comment: topic has been updated by rivudas (previous revision, new revision, compare).
Oh, a time clash again! I hope it gets resolved before the Codeforces Round starts, I wanted to do both :) Since the intersection this time is minor (5 or 15 minutes, depends on Codeforces), I wonder if the October Easy can be moved forwards with like 20-30 minutes, it would be quite unfair to move the Codeforces round backwards.
The contest has been postponed by half an hour. Good luck. :)
What's the new time now?
10:00 PM IST. The timing has been updated in the blog.
Auto comment: topic has been updated by rivudas (previous revision, new revision, compare).
Thanks a lot to everyone who took part in the contest. I was the setter of the first three questions "The Best Player", "Gold at lolympics" and "Closing ceremony". Any feedbacks on these questions is welcome :)
People openly discuss solution in comments and no one takes any action. Also the problem statement of "Boring Marathon " was not clear earlier and a change was made between the contest without any notification.
Wasted my 3 hrs. Last contest on hackerearth
Here is one such comment.
Well I was in charge of my questions, and kept deleting unnecessary comments as and when I saw them. Regret any inconvenience caused. We will definitely try to improve on the statements and overall quality. Thanks!
I liked Gold at lolympics. Though it was more or less straightforward.
Also I suspect the test cases were very weak. I was getting 1 test WA (and others AC), and I fixed 4 different bugs until I got it. Probably all that bugs were not covered..
I suspect the same about other challenges. Byteland Trip — a graph problem with 5 tests? Seriously?
Thanks for the feedback. Yes, after seeing some solutions pass I figured out that the tests were weak. I will try to improve my test generation skills. :)
Could you explain author's solution for the problem "Gold at lolympics"? My solution got 100, but I suppose that it's not completely right.
The author solution involves finding prime factorisation in O(N^{1/3}). Once that's done, its a simple dp to find the answer.
Your solution is almost fine.
If N has smallest prime factor p > cuberoot(N), then either N = p2 or N = pq in which cases the Sprague-Grundy function f(N) is equal to 2. Thus if you can't find a prime factor less than 105, you have to check if N is prime (f(N) = 1) or not (f(N) = 2), with a primality test.
A tricky point is that even if you have found a small factor (e.g. N=2*d), you still have to check that d = N / 2 is prime or not.
I didn't notice the fact "If N has smallest prime factor p > cuberoot(N), then the Sprague-Grundy function f(N) is equal to 2.".
Thank you for the explanation!
Can you please :
Make the solution public
provide short editorial
Make the problem available for practise
Can anyone tell the correct approach of Closing Ceremony at Lolympics because the editorials are not available and the solutions of other programmers are also not visible.
Good day to you.
It can be solved with "Nimbers" {some dynamic programming [Number X maxXor] }.
The nimbers are +/- prime_factors_counts (since this allows you to move on "some lesser divisors")
You also have to use some faster factorization (such as Pollard Rho) :)
Good Luck!
I think you are telling about the Gold at lolympics question but I'm asking about the 3rd question which is Closing Ceremony at the lolympics.
Count the number of bad answers and subtract it from 2^n.
For the number of bad answers, count the number of subsets with sum < K and multiply by 2 (because it can belong to either bag A or bag B).
Counting the number subsets with sum < k can be done in O(n*k) time using knapsack dp.
Thank You :) Didn't thought the main trick of taking the problem in the opposite manner. Nice One !!!
Oh ye,
I'm so sorry for the inconvenience! :P
So as abisheka said, Knapsbag ^_^
How to solve "Boring Marathon" ?
What i felt this problem had a quite confusing and unclear problem statement, from what i had inferred and solved using the same logic. The problem basically gives you a string and this same string is given to both the players. Now we have to find the expected number of times both pick the same character, as there can be atmost 26 distinct characters this is what i did..
1.Traversed the string and stored the count of each character in an array. 2.Iterate over all the characters and now we basically have to calculate the number of ways this character would be picked up simultaneously by both players ie (number of ways player1 picks up this character)*(number of ways player2 picks up this character). As the string is same this is equal to count(character)^2. 3. Add all these squares and finally divide them by the length of the string.
This gave me AC. I hope this helps :)
Thank you. I think I got it.