wanbo's blog

HackerRank 101Hack 31st Edition
By wanbo, history, 9 years ago, In English

Hello Codeforces community!

I am glad to announce that HackerRank 101 Hack 31st edition will be held on 19th Nov 2015 at 16:30 UTC. You can sign up for the contest here. Though what's priceless is solving interesting problems and the thrill of competition, prizes make the competition fierce. Top 10 performers will get a HackerRank T-shirt.

Problems have been set by shangjingbo and tested by wanbo. The contest will consist of 5 problems with variable scoring distribution. We have tried our best to prepare a nice problem set. Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.

If anyone are interested in sharing their knowledge, you can comment in this post or send message to me directly. We eagerly need bunch of good problems.

Good luck and have fun!

update 1: The editorial has been added, please upsolving the harder problems which you haven't solved in the contest.

update 2: The contest has been unrated because of the bad/misleading statement for the 3rd problem. We are apologize for that. We will show you more high quality contests in the future.

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

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

You said 17:00 UTC but the contest page shows 16:30 UTC.

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

How to solve falling rocks?

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

    It is very similar to this problem 585B - Phillip and Trains, have a look at its editorial. You may solve it using BFS, DFS or Dynamic Programming.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +2 Vote: I do not like it
    We can simulate the rocks moving a step upwards by moving a step downwards every second.

    You can maintain a boolean function f[i][j] which denotes whether the cell (i, j) is a safe starting position for the current grid with A rows and H columns.
    At Row x, we consider only the last (W - x + 1) rows of the grid in the current grid.
    This is pretty obvious because the other rocks are of no use now.

    Therefore A = (W - x + 1)
    The columns that we consider, however, remain the same i.e. H for all x.

    Initally, x = 1, so we consider the Whole Grid.
    We need to compute f(x)(y) where (x, y) is the place where we start.

    The recurrence is as follows:
    f(i)(j) = f(i + 1)(j + 1) || f(i + 1)(j) || f(i + 1)(j - 1)

    We can go from cell (i, j) to cell (i + 1, j + 1) only if S[i][j + 1] and S[i + 1][j + 1] aren't rocks.
    Same for (i + 1, j) and (i + 1, j - 1).

    Complexity :

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

Tandems Repeat was really confusing!! I only realized that the string has to start from the given position literally in the last 5 minutes!!

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

How to solve the last problem? Is it some smart bruteforce?

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

    I noticed that a card is an edge in a bipartite graph; we want to know the number of Eulerian subgraphs with some number of edges. The number of vertices is 14, so probably DP with 314 states for degrees of vertices (0, odd, positive even) and taking care of connectedness and the number of edges separately.

    The limits are crazy, though — 76·314 is way too much in whatever implementation I managed.

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

      Answer is less than 276, so you can precalculate all answers locally.

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

        Good point. With this, even a DP that counts subgraphs with a given bitmask of degrees and number of edges would run in... minutes at most.

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

      My solution is dp[current number-vertex(0~9)][connectivity of color-vetices(15 patterns)][parities of degree of each color-vertex(2^4)][the number of odd vertex in number-vertices(0~2)][isolation of each color-vertex(2^4)]. My source code

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

The test cases of Tandem Repeats were weak as my o(n*m) solution passed all the test cases.

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

I am quite disappointed by how this O(N*M) gives 80 pts on D — http://ideone.com/yPzX0r and after adding memoization it becomes 100 pts although it's still O(N*M) — http://ideone.com/7ZerOb.

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

I'm not particularly fond of partial scoring but I liked the contest, the problems were interesting.

I tried to solve problem D but wasn't able to, what do I need to know to solve it?

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

Can anyone share the approach for solving problem 3, Subsets Counting ?

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

    it will be (3^n+1)/2 for unordered pair and to find ordered pair,u need a little bit dinamic to find A,B where xors are equal,as answer is (3^n-x)/2+x where x is that amount

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

      I am not sure how this formula got derived ? Can you share some insight ?

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

3rd problem have a mistype on description. I think you can remove it from contest.

You can look at https://www.hackerrank.com/contests/101hack31/challenges/subsets-counting/forum

→ Reply