shashank21j's blog

[HackerRank] Weekly 13th edition
By shashank21j, 9 years ago, In English

HackerRank presents 13th week of Weekly Contest.
The week long contest will begin on on 5th January 16:00 UTC. We’ll put your coding skills to the test with 5 interesting challenges.

Each day you get to solve a challenge whose difficulty level increases as the week progresses. Challenge score will decrease by 10% every 24 hours. To solve the final challenge, you're given an entire weekend.

The problem statements will be available in English, Russian, Chinese and Ukrainian

Contributers

Tie-breaking rule: For each challenge, we calculate your solved time, t. [t = submit — open] where submit is the time you submitted the solution, and open is the time you opened the challenge. This way, you do not have to worry about solving the challenge as soon as it becomes available.

Top 10 on leaderboard will get a cool HackerRank T shirt.

You can visit the contest page in order to register.

Week 13

https://www.hackerrank.com/w13

Happy Coding!

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

Comments Comments (35)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you are late

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

    One should note shashank21j is the organizer of this event, not the person you linked to.

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

    Please note, that person is not related to hackerrank. If there are issues reply on this blog so I can track it.

    I hope you understand.

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

I have a problem — I can't open the first problem and when I click on a link to the leaderboard I get the message "Error Ocurred". I guess something is wrong.

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

Could you make it possible to see the time it took people to solve a particular question. I remember it was done for one of the previous weekly challenges and I think it is a rather effective tool against cheaters using 2 accounts.

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

    I will enable that after contest ends and will take them down by surprise.

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

      Why did you removed this feature? Is it just because of some technical problems, for this contest only? Or you did it intentionally for some reasons?

      It looks like a step back for me. Now I don't even know my current place in standings. I am just one of 600+ guys who see Current Rank: 1 at contest page, and i have to count my actual place manually.

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

        It's intentional. I have a lot of people to remove, so your position will improve. Moreover comparing rank after day 2 is premature ;)

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

What's going on? I had 280 points (4 task solved 100%) few hours ago, but now my score decreased to 208. PS it's my first contest on hackerrank

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

    "solved 100%" on a day when you submit a solution don't actually mean full solution. Your solution is tested only on pretests when you submit it; at the end of the day it is tested on full dataset, and you know your actual score. If you open detailed results of judge, you'll see that some testcases are marked as "additional". Maybe your solution failed some of these "additional" cases for last problem, and this is the reason why your score decreased.

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

    If things are still as they used to be, your problems go through a final test every day with additional test cases. So when you submit a problem and get 100% on the available instant test cases, this doesn`t mean your program will get 100% on the daily recorrection. You should probably check the problem you submitted yesterday to see if this happened.

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

Confusing thing with leaderboard — i have 112/120 on full dataset for Swaps and Sum, today i submitted it again for 108/108 on pretests, and after that leaderboard don't say anything about my 112 points, it just shows that i have 108. A bit tricky way to hide my score)

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

    So... the last submit counts, not the best one?

    I sense a disturbance in the Force contest rules...

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

      Don't worry, best one should be counted.

      I tried same trick on Taum and B'day — and my score did not decreased:)

      Maybe system decided that 108/108 is AC while 112/120 isn't, and AC is always better than something else:)

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

    Bug? Will fix it. Also I'm thinking i will reveal time. It'll be exciting for last challenge.

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

      What's the time based on? First AC? In that case, is it recalculated if the final testing gives WAs?

      Also, if many people get full scores, is there no tiebreaker?

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

        It's based on first submission of maximum points.

        Same score = Same rank

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

          This rule works both for rating calculation and prize distribution?

          In case next time problemset will be very easy and we'll have 50 users with full scores — competitor #50 (by penalty time) will receive t-shirt (as his score is same as a score of winner) and his rating will be recalculated in the same way as rating of winner?

          → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Blood for the Blood God!

Skulls for the Skull Throne!

Small pretests for the Small Pretest Contest!

Seriously, couldn't there have been at least one serious pretest for the last problem? The current ones are completely bruteforceable...

→ Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve the last problem from the contest?

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

    This problem is solvable using dynamic programming.

    Let dp[i][j] be the number of good arrays, built from the first i elements with last element equal to j.We can easily calculate our dp in O(N^3) time:

    From this formula we can get another one:

    dp[i][j] = dp[i][j - 1] - dp[i - 1][j - 2]

    This formula is almost good, but we don't know, how to calculate the base of our recurrent formula (case with j==2 or j==1). We can generate this values by hand and just google them :) It turns out, that answers for j==1 and j==2 (they are equal in the most of cases) can be expressed as the members of the Catalan's triangle, and there is a formula for calculating them. Specifically, this values depend from the value of the last fixed number in the array and from it's position.

    Using this observations, we can solve our problem in O(n * maxA) time

    Code

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

    The first thing to do is to determine what a valid height sequence looks like. Let us think about it in terms of the dfs. Lets say at the current point in the dfs, we are at height h. The next entry in the array is either h + 1 (which corresponds to us moving to a child), or some value x, 0 < x ≤ h which corresponds to going back up the dfs callstack. Hence, a valid sequence will be composed of a series arithmetic progressions (of difference 1), where each arithmetic progression starts at a value less than or equal to the previous term. In other words, it will look like 0, 1, ... , e1, b2, b2 + 1, ... , e2 - 1, e2, b3, ... , e3, b4, ... where 0 < bi ≤ ei and bi + 1 ≤ ei.

    Now the problem boils down to counting these sequences with some values already set. In order to do this, notice that the set numbers create a series of ranges which we can evaluate independently. A range is simply [i, j] where A[i] ≠ ? and A[j] ≠ ? and . To count the number valid sequences range, we convert it to a question on the cartesian plane. We are essentially counting the number of grid paths from (0, 0) to (A[j] - A[i] + j - i, j - i - 1) that do not go past the line y = x - A[i]. To see why this is true, think of each upwards step as moving down in the dfs tree, and each rightwards step as moving back up the callstack in the dfs. To solve this problem, we can use a trick called Andre's Reflection Method, which states than the number of paths from (0, 0) to (a, b) not going beyond y = x - k to be . The Wikipedia explanation of the method gives you a sense of how it works. Basically, it relies on the fact that the number of paths that are invalid is , because there is bijection between each invalid path from (0, 0) to (a, b) and every path from (0, 0) to (b + k + 1, a - k - 1), the later point being (a, b) reflected over y = x - k - 1.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Great contest, it was a pleasure to solve problems.
However, I'm sad that my sqrt-decomposition TL'ed on 'Swap and sum' problem — way to improve myself in future!

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

My solution for last problem failed on 37th testcase with segmentation fault during the contest. Now absolutely same solution gets AC. It can be either an undefined behaviour somewhere in my code or technical problems on server. I haven't managed to find any places in which UB can appear. Can somebody help me to find it?

My code: http://pastebin.com/fqcgYL81

37th test: http://pastebin.com/4jbmcW38

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

How can the Swaps and Sums problem be solved efficiently?

I attempted a brute-force algorithm first (I optimized where I could) but it reached the time limit for some cases, unsurprisingly.

My second attempt just stored all swaps in a list, and each sum query was transformed by the swaps into a series of ranges of where the elements originally were. However it also reached time limit in some cases (especially ones that had many queries).

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

    You can do an sqrt-decomposition.

    Split the array into blocks of even size, approximately . Each block can be viewed as 2 arrays, formed by even and odd elements respectively. If you apply a swap operation to a whole block, we can view it as moving these 2 arrays, one to the right and the other to the left (that can mean that an element has to be erased from one end and an element added to the other end); if we only apply it to a part of the block, we can process that block (depending on how it's been moving so far — essentially transform a deque into an array) and bruteforce the swaps made on it.

    There are at most blocks to process in each query, at most 2 blocks to bruteforce (in time), so the time complexity is .

    It sounds simple in theory, but (at least to me) it was long hours of debugging an ugly long code.

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

      Wow. I actually thought about splitting it into sub-arrays, but I didn't really understand what I could gain from it. Your explanation really helped enlighten me! Thank you very much =)

      The only thing I didn't understand was the part you said that it would be "essentially transform a deque into an array". From what I understood, there would be these cases:

      1. Swap range that's exactly one block (just "swap" the arrays)
      2. Swap range that's inside a block (bruteforce, at most block size — 2 swaps)
      3. Sway range that's exactly M blocks ("swap" arrays on the M affected blocks)
      4. Swap range that starts on a block edge and ends in the middle of another block (swap arrays in all full blocks, bruteforce like case 2 for the last block)
      5. Swap range that ends on a block edge and starts in the middle of another block (almost same case as 4)
      6. Swap range that starts and ends in the middle of different blocks, and that start is odd ("swap" arrays in full blocks, bruteforce in the first and last blocks)
      7. Swap range that starts and ends in the middle of different blocks, and that start is even (this is the one I think I didn't really understand. I think you'd have to do the bruteforce first in the first and last blocks, then "swap" arrays of all fully affected blocks, but also exchange elements between all the blocks, exchanging the highest element with the lowest element of the next block. Is this correct).

      The suggestion you made, would it replace or complement the bruteforce used for partial blocks? How would it be used?

      Thanks,

      Janito

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

        Well, as it was already discussed in Russian thread, the possibly best solution is to use 2 Cartesian trees — one for even indices and one for odd. Then swap operation is exchanging some subtrees in two trees, sum is sum in two of them. Code:http://pastebin.com/2HScnAJQ

        And it turned out to be an old problem from Russian online judges.

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

          I thought it would require Treap, so gave up. I don't know how to use/code Treap. Need to learn that, but seems too tough :(

          → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 6   Vote: I like it 0 Vote: I do not like it

        For simplicity (to eliminate some cases), I did the following:

        1. Set block size to be an even number. Thus, if swap query starts in even number (0-based), there will be no transitions from one block to other.

        2. If the query starts with odd number (0-based), one can notice that in "middle" blocks (all excluding first and last) the leftmost element changes places with the rightmost element of block on the left, and the rightmost element changes places with the leftmost element of block on the right.
          So I constructed arrays to_left and to_right, which hold elements that must be exchanged to named direction, and that elements are removed from corresponding blocks.

        3. Perform swaps on each block: by bruteforce on first and last block, and by swapping two deques on "middle" blocks. By bruteforce here I mean either:
          a) Remove every element from both deques and push them into vector. Then swap what you need in that vector. At last, push everything back into deques. Firstly, I wrote this, but then realised that it could be too slow to push into vector each time.
          b) Deques have random-access in constant time, so you can swap elements directly from one deque to other.

        4. Then add elements from to_left and to_right into needed blocks.

        My solution got TL on every (except last two) additional test, though the random testcases I generated (with maximal n and q) were working in 1-1.5 seconds locally.
        Here is my code.

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

      That's exactly what I was thinking about during the contest. But I find it hard to implement!At that time my code went up to 280 lines.

      But today I rewrite it. And only 180 lines. But as you pointed out, I spent the whole afternoon debugging, Here's my code.

      → Reply