The 21-st edition of Week of Code https://www.hackerrank.com/w21 starts soon: 27 June 16:00 UTC.
Monday to Friday, every day one challenge will go live, easy to hard. The maximal score decreases by 10% at the end of every 24 hours. Your submissions will run on hidden test cases at the end of every 24 hours.
The time of each challenge will be counted since it's open. It allows you to start late.
The contest is prepared by shef_2318 and tested by CherryTree
The contest is rated and top 10 get T-shirts.
GL & HF
Wow!
These guys are really getting good at competitive programming, just look- people have solved the first two questions in less than a minute already!
Errichto, looks like you've met your matches, better step up your game against the
cheaterstrue professionals! :PNo matter how good you are, there's always an
AsianIndian better than you.LOL this leaderboard is getting too good
Wait for three more days, maybe? Balance will definitely be restored xD!
And the moral of the story is
FuckYouCatman12 has better internet connection than catman12.
"Catman"
Well, it was you who came to India to promote competitive programming! Now suffer the consequences :P
Well, If it makes any better I think I know why do these people cheat.
This are 2 reasons I think Indian community on CP is too big even if they don't perform. Many times these things make me sad .
But there are some guys who rise from newbie to purple/yellow in their college life and continue after that too. They never cheat, they always learn. If you remove that CV and boasting people ,these are the people who are left and this is actually the real community of CP from India.
Moreover nothing can be done to stop these people except banning them. I don't think talking to each individual is a feasible idea.
Unless all the competitors for the contest come from codeforces blog, its better to mention the scoring rules in the official contest page https://www.hackerrank.com/w21#scoring.
Major disadvantages of this feature "The time of each challenge will be counted since it's open. It allows you to start late" are seen in the leaderboard. Seriously in 12 seconds, the rank 1 in leaderboard read two questions and coded them. Hope the hackerrank admins review this feature again :P
My experience in this contest :
All in all, this contest actually made me work towards my weak points and that too in the form of tougher questions! Thanks for this problemset :)
Let f[k] be the number of ways. gr(x) = f[a1a2...an * x + r], then for each r = 0, 1, ..., a1a2...an - 1, gr(x) is a polynomial with degree ≤ n.
A bit detailed? I have never come across these kind of questions! How does the generator help?
Knowing that the answer for a particular remainder is a polynomial of degree at max N in x, the remaining part is Lagrange Interpolation for
different remainders, and hence polynomials.
Below is a problem based on similar idea:
622F - The Sum of the k-th Powers
My solution is completely different and makes use of the constraint on
in a different way.
Let S be the sum of all ai and S' the sum of all but the largest ai.
Using some inclusion-exclusion or rewriting the generating function as
, we arrive at a linear recurrence in a general form 
. Let's introduce prefix sums Fk: Fk + 1 - Fk = fk, which is what we want to compute. Plugging it into the recurrence, we get a different linear recurrence.
That gives us the answer in
time by matrix multiplication; if v = (1, 0, ..., 0), then there's a matrix M such that (Fk, Fk - 1, ..., Fk - S) = Mk·v.
If one of the ai is too large, S can be large, but S' will always be small enough — specifically, up to ~300,2016-07-05. If we use the same notation f'k, F'k for the number of ways if we remove the largest ai = am, then
, which is the first element of the vector 
for a corresponding matrix M'. This matrix has size O(S' × S') and we can compute geometric series of matrices with the same time complexity as their powers: 
.
I thought this wouldn't get full score, so I tried to optimise through loop unrolling and other shit, and it did get a very comfortable full score. Maybe there weren't tests to break it.
For the sixth problem, the answer is the coefficient of xR in
. Let l = lcm(a1, ..., aN). Multiply numerator and denomenator by (1 - xl)N. We end up with 
. The numerator polynomial can be computed in O(LN2). Using this the number of ways for the range can be calculated.
After getting TLE with my O(N^2 * log(N)) solution on fifth task, I gave up on optimizing it. Suprised to know that intended solution is also O(N^2 * log(N))...
Btw, why my code is TLE?
With atan2, I got TLE. By changing it to avoid double comparisons, I got AC :)
How did you compare without using double?
First, I find out the quadrant the points lie in. If they are in two separate quadrants, we can easily identify the sorting. Now if they are in the same quadrant, I use cross product to identify which one has a smaller polar angle.
Contest was fine :) Generally, I like this kind of contests and tasks were enoguh interesting to spend nice time for thinking about it.
My opinion:
First three tasks were nice, with some special cases. For me they are very good for that places.
Fourth task is a little strange. I solved it by recursion and got full score. My first submission got full score too, but it is obviosly slow — it gives TLE for graph with all zeroes like a star. I can not believe you didn't have some graph like it for maximum possible answer.
Fifth task is ok, but honestly I don't love this kind of geometry. it wasn't hard, I solved it on paper, but when I saw implementation and real numbers I decided to write code in O(n^3) in Pascal and be happy with non zero points :P
Sixth task looks interesting, current it is above my level. I supposed solution is something like it, but I can not solve it for now.
I have one thing which is not clear for me in editorial for third task, if someone want to explane I will be grateful:
Why is this complexity, for me it looks as complexity O(4K) ?
Consider some (i-th) bit in pair (mask, sub). It's either (1, 1), (1, 0), (0, 0) but not (0, 1)
Thanks, I got it :)
The fourth passed because it is actually
if you consider houses in ascending order of numbers and store everything in map. The proof is simple. Let's split masks into two types:
Have any houses with number <= n/2. This means we are still processing first houses. And we can process them in
ways. Thus there will be only 
masks of this type
Have no houses with number <=n/2. There are only n-n/2=n/2 of those. Thus there are only
masks also.
So we will store in map at most
masks. And total complexity because of map is as stated.
Good, now everything is clear :)
I would like to show my solution too. It is some kind of optimized recursion. It worked very fast for all testcases, but maybe someone can find counter — example or can estimated total complexity.
My solution, if someone wants to hack it :) Code
Basic idea: Process nodes from 1 to n. If you mark current node, than say for all nodes connected with current node that they can not be used(mark it too). Also consider case when current node doesn't have unmarked connected nodes, then for sure you will use current node (in case C[current_node]=0, ways=ways*2).
.
Ah... I thought you tried remembering answers in your solution. Everything I wrote has nothing to do with your then. :-) Maybe your work in Fib(n) or something similar since on each step when you have a non-isolated house you will either discard one or at least two nodes.
Never mind, I know what you are talking :)
It would be cool if it works in Fib (n) , that is faster than all other solutions :D
I am finding it difficult to determine the time complexity of SohelH solution for Demanding Money problem. I have provided the link to the solution below. It is not the meet in the middle approach. It seems to do memoization on certain states. Any idea what's the worst case time for this solution.
https://www.hackerrank.com/rest/contests/w21/challenges/borrowing-money/hackers/sohelH/download_solution
Being marked as plagiarism even though didn't do any thing, what should I do? I have contacted hackerrank support but they haven't replied back. Feeling so frustrated!
How to solve the fourth question ?