shef_2318's blog

Week of Code 21 at HackerRank
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

  • Vote: I like it
  • +25
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      LOL this leaderboard is getting too good

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

        And the moral of the story is

        FuckYouCatman12 has better internet connection than catman12.

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

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

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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
»
8 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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
»
8 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

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
»
8 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like 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.

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you compare without using double?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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:

  1. 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(3K).

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like 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:

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

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the fourth question ?

→ Reply