Week of Code 21 at HackerRank

shef_2318's blog

By shef_2318, history, 8 years ago, In English

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

hackerrank, weekly

shef_2318
8 years ago
31

Comments (31)

Write comment?

Sawako

8 years ago, # |

+46

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 ~~cheaters~~ true professionals! :P

→ Reply

Errichto

8 years ago, # ^ |

+41

No matter how good you are, there's always an ~~Asian~~ Indian better than you.

→ Reply

Sawako

8 years ago, # ^ |

+11

LOL this leaderboard is getting too good

→ Reply

animeshf

8 years ago, # ^ |

Wait for three more days, maybe? Balance will definitely be restored xD!

→ Reply

dush1729

8 years ago, # ^ |

+32

And the moral of the story is

FuckYouCatman12 has better internet connection than catman12.

→ Reply

pranet

8 years ago, # ^ |

+30

"Catman"

→ Reply

himanshujaju

8 years ago, # ^ |

+12

Well, it was you who came to India to promote competitive programming! Now suffer the consequences :P

→ Reply

anh1l1ator

8 years ago, # ^ |

+21

Well, If it makes any better I think I know why do these people cheat.

A part of the Indian community wants to make their CV better rather than making themselves better. So , they rather take it as it is and do it in moderation just to add things. It might be a consequence of this that some might cheat.
Maybe sometimes making themselves better than their friend X or boasting about their skill(Not possible here but it still might be a cause). I think some people don't really care what their rank is , but all they care is where are all his friends/his school etc. These people can do anything. I had an acquaintance, who left CP just after he was unable to boast of his knowledge . There are many other who feel bad if I get a better Rank or something(even if they have a good rank in a contest). They want to make everything a rat race and be the leader in that(These are the worst people).

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.

→ Reply

himanshujaju

8 years ago, # ^ |

+18

→ Reply

bharsi

8 years ago, # |

← Rev. 2 →

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.

→ Reply

Single_Ready_To_Mingle

8 years ago, # |

← Rev. 3 →

-8

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

→ Reply

himanshujaju

8 years ago, # |

← Rev. 2 →

+27

My experience in this contest :

First two were really easy, but still interesting enough!
Third problem: wrote up a bruteforce. Check pattern and ac'd. Did proof after submission!
Fourth problem: Constraints made me feel meet in the middle is necessary. First wrote a brute solution(so that i can use it as a testing solution). I wasnt very comfortable with meet in the middle, but solving this question did give me a lot of confidence. Also, its possible to do in O(2^(N/2) * N * N) which is tad faster than O(3^(N/2)).
Fifth problem: Started with O(N^4) and managed to come to O(N^2logN). The mistake? Using atan2 to sort! DAMN! But then, I had always feared geometry problems, and I felt really good after solving this :) AC'd in practice by changing the sort function.
Sixth problem: Still no idea! Submitted a brute. Can anyone help with this?

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 :)

→ Reply

chemthan

8 years ago, # ^ |

Let f[k] be the number of ways. g_r(x) = f[a₁a₂...a_n * x + r], then for each r = 0, 1, ..., a₁a₂...a_n - 1, g_r(x) is a polynomial with degree ≤ n.

→ Reply

himanshujaju

8 years ago, # ^ |

A bit detailed? I have never come across these kind of questions! How does the generator help?

→ Reply

jtnydv25

8 years ago, # ^ |

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 $\text{[math]}$ different remainders, and hence polynomials.

Below is a problem based on similar idea:

622F - The Sum of the k-th Powers

→ Reply

Xellos

8 years ago, # ^ |

My solution is completely different and makes use of the constraint on $\text{[math]}$ in a different way.

Let S be the sum of all a_i and S' the sum of all but the largest a_i.

Using some inclusion-exclusion or rewriting the generating function as $\text{[math]}$ , we arrive at a linear recurrence in a general form $\text{[math]}$ . Let's introduce prefix sums F_k: F_k + 1 - F_k = f_k, which is what we want to compute. Plugging it into the recurrence, we get a different linear recurrence.

That gives us the answer in $\text{[math]}$ time by matrix multiplication; if v = (1, 0, ..., 0), then there's a matrix M such that (F_k, F_k - 1, ..., F_k - S) = M^k·v.

If one of the a_i 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 a_i = a_m, then $\text{[math]}$ , which is the first element of the vector $\text{[math]}$ 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: $\text{[math]}$ .

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.

→ Reply

guru2691

8 years ago, # ^ |

← Rev. 2 →

For the sixth problem, the answer is the coefficient of x^R in $\text{[math]}$ . Let l = lcm(a₁, ..., a_N). Multiply numerator and denomenator by (1 - x^l)^N. We end up with $\text{[math]}$ . The numerator polynomial can be computed in O(LN²). Using this the number of ways for the range can be calculated.

→ Reply

Na2a

8 years ago, # |

← Rev. 3 →

+10

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?

→ Reply

himanshujaju

8 years ago, # ^ |

With atan2, I got TLE. By changing it to avoid double comparisons, I got AC :)

→ Reply

satyaki3794

8 years ago, # ^ |

How did you compare without using double?

→ Reply

himanshujaju

8 years ago, # ^ |

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.

→ Reply

allllekssssa

8 years ago, # |

← Rev. 3 →

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:

Calculate some kind of dp called max[mask], where mask is the set of vertices which are allowed to be used. We cannot include vertices in the independent set having a 0-bit in mask , so we must iterate over all the possible submasks (sub of mask) and find the maximal val[mask] as well as the number of such submasks we met. This part of iterating over all the submasks of each possible mask works in total time O(3^K).

Why is this complexity, for me it looks as complexity O(4^K) ?

→ Reply

riadwaw

8 years ago, # ^ |

← Rev. 2 →

Consider some (i-th) bit in pair (mask, sub). It's either (1, 1), (1, 0), (0, 0) but not (0, 1)

→ Reply

allllekssssa

8 years ago, # ^ |

Thanks, I got it :)

→ Reply

knightL

8 years ago, # ^ |

The fourth passed because it is actually $\text{[math]}$ 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 $\text{[math]}$ ways. Thus there will be only $\text{[math]}$ 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 $\text{[math]}$ masks also.

So we will store in map at most $\text{[math]}$ masks. And total complexity because of map is as stated.

→ Reply

allllekssssa

8 years ago, # ^ |

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).

→ Reply

knightL

8 years ago, # ^ |

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.

→ Reply

allllekssssa

8 years ago, # ^ |

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

→ Reply

xyz.abc

8 years ago, # |

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

→ Reply

alibaba

8 years ago, # |

← Rev. 3 →

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!

→ Reply