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.
You said 17:00 UTC but the contest page shows 16:30 UTC.
How to solve falling rocks?
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.
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 :
Tandems Repeat was really confusing!! I only realized that the string has to start from the given position literally in the last 5 minutes!!
How to solve the last problem? Is it some smart bruteforce?
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.
Answer is less than 276, so you can precalculate all answers locally.
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.
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
The test cases of Tandem Repeats were weak as my o(n*m) solution passed all the test cases.
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.
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?
hash+binary search
Can anyone share the approach for solving problem 3, Subsets Counting ?
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
I am not sure how this formula got derived ? Can you share some insight ?
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
we are marking this contest unrated.
What about prizes?