Блог пользователя wanbo

Автор wanbo, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve falling rocks?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +2 Проголосовать: не нравится
    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 :

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

      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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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