wanbo's blog

HackerRank 101Hack 33rd Edition
By wanbo, history, 8 years ago, In English

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!

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

The judging system is very slow UPD : It's working fine now

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

How to solve 4th problem(Intersecting Paths)?

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

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.

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

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.

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

    Suppose you've got AC for simulation because of test case weakness, not because of it was planned by authors :)

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

    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 ?

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

      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.

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

        Nice :) . This is somewhat similar to the correct solution. Yeah, the testcases should have been stronger maybe.

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

    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?

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

      Thanks, that's exactly what I was looking for :) You are right, on such test my solution does O(N) operations per query.

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

    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.

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

      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?

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

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.

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

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.

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

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").

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

    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.

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

      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?

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

    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?

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

How to do "Longest Path" ?

→ Reply