Hello Codeforces community!
I am glad to announce that HackerRank 101 Hack 33rd edition will be held on 20th Jan 2016 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 Sundar 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.
Good luck and have fun!
The judging system is very slow UPD : It's working fine now
How to solve 4th problem(Intersecting Paths)?
For "Intersecting Paths" problem, my solution was passed on "Test Case #0" (sample) and on "Test Case #8", but it still gives 0.00 points.. It was suprise, because for another problem with the only one passed not-sample test case i've got positive score.
Is there any way to figure out scoring rules applied to particular problem without actually trying to solve this problem? :) Once again today we had different rules for different problems...
And I got AC for 4th problem with simulation; it shouldn't give me AC, right? I have no idea if doing "pick path at which you are further from the end and move to the right over this path" is actually somehow better than N^2.
Suppose you've got AC for simulation because of test case weakness, not because of it was planned by authors :)
It was difficult to have set testcases for all brute force solution. Most of it failed the testcases. So, you moved one vertex at a time and it passed ?
If you are going to do like this — it passes all tests except one (or maye it can still give AC, but I got TL on one test :) ). In order to get AC I was moving left vertex to the right by multiple steps in a single iteration, i.e. if it will reach right vertex in X moves — we can find this X in log(N) and make X moves at once, instead of doing a single move X times.
Nice :) . This is somewhat similar to the correct solution. Yeah, the testcases should have been stronger maybe.
Shouldn't be better than N^2. If the testcase is 4 3 1 2 4 3 1 2 4 3 1 2... and you start at one 4 and one 2, your code will have to walk the whole path to check, right?
Thanks, that's exactly what I was looking for :) You are right, on such test my solution does O(N) operations per query.
The fourth problem's score is changed to binary before the contest, it means you will get score iff you passed all test cases. Sorry we haven't told in the statement. Hope it doesn't effect much.
There wasn't a significant impact on my result, but information about "nonzero score only for a complete solution" in the statement would be extremely useful.
Is it right, that usually on HackerRank contests partial score is given for partial solution?
My solution for 4th. My code doesn't find is there any intersection, it finds the number of intersections.
http://ideone.com/rORDJc
We make a tree with 2 * n vertices. Our edges are (i, nextSmall[i] + n) and (i + n, nextBig[i]). For any query we need to count how many vertices k such that, x is in subtree of k or k + n, and same thing for y. Dfs in our tree, when we traverse increase subtree of x and subtree of x + n. When we finish this node, we will decrease them. When our node equals x we will answer queries (x, y). Answer of the query is the value of y in our data structure.
Fine tasks. I didn't read editorial, but I suppose you solved the third by set. Standard I had problem with set functions and spending on it a half hour :(
Also, for my opinion the first task is harder than it should be.
I always compete in 101 Hack hoping for cool problems, but it always relies extremely heavily on standard algorithms rather than elegant solutions (the third problem is the exception in this case).
For example, can literally take the statement of the first problem, put it into Google and the first result is the solution (except for the trivial "no zero").
The fourth problem was quite nice too, it took me a long time to see the simple solution.
The fifth problem is amazingly standard, though, as the hardest problems in HackerRank almost always are.
It is a nice dp problem, it may not too easy to come up with the dp state. Find the max value then can be solved by smaller subproblem. Even finding this, solving this problem is not super easy for most contestants. There are many ways to build the state, finding the above one is not that easy. BTW, do you have any interest in sharing nice ideas to us?
Aren't the last 3 problems cool? You need nice observation to find the solution. The first challenge is easy, we need almost everyone to solve it. So we change it from a classic problem. Can you find them by google?
How to do "Longest Path" ?
With DFS. You need to make the tree graph. I used adjacency list. Then, you can traverse the graph, only going deep when the next node is black. You must traverse all the subtrees, not only the one rooted in the root (well, you know). Hope this hint help you. Feel free to ask!
Hi Gaston, I tried solving the problem using DFS. https://www.hackerrank.com/contests/101hack33/challenges/longest-path/submissions/code/5459217
However, it didn't pass all the test-cases. Can you please help me out?
Hi! Surprisingly, I scored the same 23.33 points: https://www.hackerrank.com/contests/101hack33/challenges/longest-path/submissions/code/4722672
It seems I'm missing something. Maybe you can find something more interesting in the forum:
https://www.hackerrank.com/contests/101hack33/challenges/longest-path/forum
If you have a fully-working approach, please tell me!