Hello CodeForces Community!
I am glad to share that HackerRank's CodeStorm (CodeSprint on Algorithmic Programming Challenges) is scheduled on 29-October-2015 at 16:00 UTC. Contest duration is 24 hours.
Go ahead and register now to show off your coding chops, and win amazing prizes like GoPro HERO4 camera, Bose Speakers, FitBit Charge, HackerRank hoodies and t-shirts. All participants who completely solve one challenge will get $100 of AWS credits.
Also, you'll get an opportunity to connect for a career opportunity with CodeStorm contest sponsors — like ErosDigital, Indeed Prime, Slice, Steelhouse, Sightline Systems, SWATT etc. Contest site will be continually updated to reflect upcoming sponsors.
The problems were created by malcolm, svanidz1, Timur_Sitdikov and Shafaet. Thanks to wanbo and allllekssssa for testing the problems.
The contest will be rated. If two person gets same score, the person who reached the score first will be ranked higher.
Editorials will be live soon after the contest ends, I invite everyone from experts to beginners to participate and solve challenges. I hope everyone will enjoy the contest.
Update: The max scores of the problems will be 15-30-50-70-90-90-125. The problems will have partial scoring unless we mention about binary-scoring explicitly in problem-statement.
Update: Some users got automated emails after the contest about prizes. Everyone with rank 11 to 100 will surely get the tshirt as mentioned here, we are investigating why that email went out.
GL&HF
Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
So,
time does not matter at all (and the answer to this question won't just suddenly change after the contest)?
will there be some kind of partial scoring; if so, what kind and on which problems (in particular: on the hardest one)?
will there be a problem with non-binary scoring per test?
(questions 2. and 3. can be summed up and "will there be a lot of ties?")
UPD: I feel silly for not asking 0. will the problems have sufficient difficulty for a 24-hour contest?
Yes time matters, it will be the tiebreaker.
There will be partial scoring (probably in most of the problems). If some of the problems are binary, we will mention it in the problem statement. I know we didn't mention it clearly in some contests in past, but that won't happen it in this contest. I will update the post with details about score of each problems before the contest. So to sum up, there won't be lots of ties.
Any suggestion is most welcome :).
(Btw, I edited the line you mentioned to make it more clear)
In some recent contests, there were cases of hardest problems without partial scoring. That makes partial scoring on the rest of the problems useless, since the top of the scoreboard is what actually matters. And when there are ties at the top, it's about timezones or free time that day.
The optimal solution is really introducing a challenge problem.
Also partial scoring challenges should have at least good number of strong test cases. Otherwise sometimes it happens wrong solution get full points or 70% points.
Why can't you do subtasks system(similar to ioi system) to prevent it?
I really don't know that. When I was preparing 101 Hack and HourRank, I had big problems to make fair and correct scoring. Even I like binary score more than partial.
Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
Auto comment: topic has been updated by Shafaet (previous revision, new revision, compare).
Please keep partial scoring for last 4 challenges.
is so difficult to post the exact time using http://www.timeanddate.com/?
I forgot. Added it, thanks.
@Shafaet/Organizers — Sorry if I sound ignorant, but can you explain how are RATED contests different from UN-RATED at HackerRANK? I understand the meaning, but on what basis you decide which ones will be rated. I am good at python, but see that your contest named "Pythonist 3" is not rated, why?
First HackerRank now has several RATED competitions prepared by one author:
-101 Hack
-HourRank
-Week of Code
We have this contests 3-4 times in the month. Now you have CodeStorm- 24h long. Duration of contests are different, so everybody can find something interesting and good. I think that contests are pretty good (I was doing and watching task in last 3-4 months, before I didn't know a lot of about HackerRank). Now, I like at most CF problems(they have hacks, many users, platform is good...), but after it for me the best platform is HackerRank, after than CodeChef... SRM has good tasks, but platform (topcoder arena) is very bad and I lost 2-3 years of my life during one contest.
Why other contests aren't rated. HackerRank has several better coders than me, probably than you. If they think the tasks aren't enough good for rating you must respect it. I saw several good and interesting task on that contests, but also I saw some unclear with strange solutions. Some companies organize contest for job, so they want harder level than usual round, or maybe they need more similar challenges (something important for them). The last type of contests like Java, Python... That can not be for rating. Many users don't know Java and Python, so results aren't real and correct for whole platform. You should get rating for solving programming challenges, not for the knowledge of a language. The main thing — rated contests must have something for every kind of programmers ( from newbie to legendary grandmaster).
Good question.
If a contest is language specific, company specific, restricted to regions or a new non-standard format like magic-lines contest, than the contests are not rated. Usually global contests with standard algorithm problems are rated.
I hope all the problems will be new, not like in the last contest.
I tested one problem and it was new and nice for me. I beleive that our tastes don't differ much :) I saw many tasks of this authors till now and they were good. I can not participe official on this contest, but I am planning to do other tasks this afternoon.
Our hopes are the same :)
I really hope you will like the problems :). Please let us know what you think after the contest too.
Questions are interesting. This is my first contest at hackerrank. I solved 1st, 2nd and 3rd completely. Stuck on 4th. Wont even attempt 5th, 6th and 7th as they are beyond my level currently :( Will editorial be given immediately after contest ends or after 2-3 days?
Thanks. Editorials will be available instantly.
Does it matter that a participant start the contest late i.e. will my time start when i enter the contest or everyone's time will start right when the contest started ??
It DOES matter, so start early. I know you may say some timezone will get advantage, but we don't have better option at this moment. If we start the time when someone enter the contest, cheaters will take advantage.
Were 19 full scores after 10 hours part of your plan?
The problems are quite interesting IMO, but this would've done better as a... 5-hour contest, for example. I don't have much of a motivation to submit my solutions at this point.
Sorry, but I think no man on the world who can start with 24h-contest 10 hours later and beat some of top 20 guys on leaderboard.
You're missing my point. I'm saying there are too many full scores. (28 now btw)
Than I can not understand why you don't have motivation to submit code.
I am not organizator of contest, so I can not tell you what is expected number of full scores. I think the tasks are enough hard to make difference between the best competitiors.
My motivation isn't an objective factor of contest balanced-ness. It's the second least important part of my OP (after the banepost), don't bother with it.
Continued by PM.
could you add a picture of the HackerRank t-shirts to your blog?
Anyone can give me an idea how to solve "A Game of Reduction" ?
If you have the final list L, you can find the winner using grundy value, right? Now notice that grundy value for any integer between 1 to N is very low, the numbers reach single digit very quickly.
So after getting the list L1, calculate xor of grundy values of every numbers, let the number be sxor. Now bob have to chose sum numbers whose xor of grundy values is also sxor, because sxor^sxor=0. If you know how many times a particular grundy value occurs before N, you can calculate it using simple dp. So the solution is precalculation+dynamic programming. Please see the editorial for the code.
Calculate Sprague-Grundy function for each number from 1 to 1000000. Then calculate number of non-empty subsets with xor equal to xor of Sprague-Grundy values for given numbers. Observation: SG values won't exceed 3.
SG vaule won't exceed 6 not 3. I hope you like this problem. For me it was very interesting.
And 3 is a better bound than 6, which can be found just by finding them all and checking.
Also with just 0,1,2,3 manually doing the cases was easier for me than dp (only a few cases).
There were 2 cases for me: xor == 0 and xor != 0.
I had additional cases with number of nimbers left (Alice didn't take all of them) from 1,2,3.
This seems necessary, but it looks like your code also includes this? I see more than 2 cases.
Nope. Xor != 0 cases pretty similar. One "for" for these cases.
This code?
I see 2 "if"s in each call to get() and 3 if's in the Xor>0 case. Am I missing something? Maybe not the latest code?
I meant that I don't distinguish cases 1, 2, 3. I don't have to write "if" for each of them
Ah okay, same with me. I just have 3 cases — all zero, one nonzero, and >one nonzero.
Well, my solution considered values up to 3, not 6. I got full score. P.S. Nice problem :)
Yes it is 3. I was testing that problem and I know that I get same grundy numbers as Shafaet, but I didn't print maximum value. Obvious it can't be more than number of digits.
I got the following message (rank 68):
"Prizes were awarded to the top 10. So close, yet so far. You could have made it if you had done better at Emma's Notebook."
Does this mean that I don't get a t-shirt?
Rank 87 got the same message.
Don't know who sent you the message, rank 11 — 100 will get Tshirts.
upd: may be the message means you are not getting top-10 prizes.
I love part about Emma's Notebook most of all :)
They also suggested a problem Library Fine for me in order to improve my skills, that's so cute :)
Problem 7 (Little Alexey's Tree) could be solved on O(n log n), don't understand how author could miss it (solution almost the same as in editorial). Number of vertices should be at least 10^5 to avoid n^2 solutions (and there were a lot of them).
And imho it is strange to add antihash tests, but accept quadratic solutions
The testers couldn't pass any n^2 solution. Can you please show me any n^2 solution that passed?
Let's start a comment chain with increasing scores for O(n^2) solutions. I'll start with 62.5 points here
Hi, I'm the author of this problem.
Of course, we knew that there's a solution on O(N × log(N)). We intentionally allowed all the subquadratic solutions to pass.
If any quadratic solution passed, that's fully my fault, I'm deeply sorry about that. Could you give me a link with any such solution getting AC?
Here's mine for instance: https://www.hackerrank.com/contests/codestorm/challenges/little-alexeys-tree/submissions/code/4115547. It runs in 1.39s in the worst case.
Mine might goes to n^2 with string operattions
here
Here is my piece of shit, runs in 0.14s.
That's a total fuckup with task, sorry :(
I'm quite satisfied with it :)
I hope hackerrank admins will not exclude my solution from the leaderboard... =)
Is it just dfs with memoization?
My implementation is quite straight-forward (but I needed to add hacks to avoid RE-ML).
https://www.hackerrank.com/contests/codestorm/challenges/little-alexeys-tree/submissions/code/4103675
(actual code is in the bottom) Time is 0.28
Didn't have an idea that quadratic solution may not pass when constraints are 2e4
BTW, isn't it too risky usign 20000 as N? Even testers couldn't pass their O(n2) solutions? And O(n * log3(n)) is a very bad complextiy when there is a O(n * log(n)) solutions. Why do you allowed them? I'm just sad about, the problem is very nice but so much not very good solutions passed it.
The most fun for me was, when I decided to stress some part of my solution by some stupid O(n^2) function and didn't got TL on any test.
Another O(n^2) solution: Link
Passes in 0.63 seconds
I understand the O(NlogN^3) solution from the editorial, but cannot come up with a O(NlogN) solution. Can anyone give me a hint ?
Comparing two power-of-two linked strings could be done in log n operations (like in lca). Then count dfs-dynamics simple bottom to up, count best child-string for each vertex, using the same dynamics for children. State of this dynamics is length of best string and power-of-two links to prefixes of this string and its hashes. Result of this calculation could be interpreted as correct state despite of some oriented edges forbidden (actually forbidden half of edges, all from down to up). Then goes the most tricky part, count it from up to bottom, in each moment you have some state for the initial dynamics, where some new edges added and some edges become forbidden. In single moment still will be invariant that for every edge exactly one of its orientation will be forbidden. For every vertex A and each of its child B we will recalculate state of dynamics and forbid edge from A to B, then push dfs to B. In B we will add edge B->A, calculate answer for B, then do the same for B and its children. When dfs comes to some vertex X, state of dynamics is correct, because for all vertices except ancestors of X edges oriented from up to down (it is what exactly we need to calculate result for X).
Thanks for your attention, but it's seems really hard to understand. Did you use divide and conquer like in the editorial ?
No, instead of this I have two dfs.
Could you please share a link to the editorial?
Each problem has it's editorial in HackerRank
rank 11, dammit.
It's been about two months since the contest has ended and I haven't received the t-shirt yet.