CherryTree's blog

HackerRank 101Hack 30th Edition
By CherryTree, history, 9 years ago, In English

Hello Codeforces community!

I am glad to announce that HackerRank 101 Hack 30th edition will be held on 21th October 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 me 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 after the contest.

Good luck and have fun!

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

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

https://www.hackerrank.com/contests/101hack30/challenges leads to a blank https://www.hackerrank.com/domains/master. However one can still access the problems if he has the url?! EDIT: I have https://www.hackerrank.com/contests/101hack30/challenges/voting-1 and https://www.hackerrank.com/contests/101hack30/challenges/four-primes

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

Ideas for 3rd??

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

    Binary search on how big A[i]*B[i] will be almost before the end

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

      Can you be a little more specific?

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

        Maybe a piece of code.. #tdG8Iv

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

          Thanks!!!

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

          Was 5th some standard stuff or did I miss some key observation?

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

            Just a suffix automaton + Dijkstra...

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

              LOL.. thought of this but gave up just because it was 5th .....

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

              Can you please help me? I got 109 point with Trie & Dijsktra. Again got 106 with Suff. Automata (Here, 1 test case got TLE). Can't figure out why wrong answer. Please can you help regarding this problem?

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

              GOT AC.

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

          Is a priority queue really necessary in C? I think after finding 'max' in result array, the only a[i]'s that can be further decreased are the ones equal to that 'max' after decrease. So we can just process them serially from left to right in O(n) by a simple iteration keeping track whether further days are left or not.

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

          Hey adamant, why don't you sort according to the number of problems while computing the final result?

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

            It was easier for me to use set :)

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

    Binary search for maximum value in result array. After this you have done most of k opeprations so k is small. For small k you can solve it using heap

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

How to solve "How Many Solvable Puzzles" I always get TLE

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

Was anyone able to use the criteria of solvability on wikipedia for a solution that does not TLE?

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

Any idea on how to solve Four Primes(2nd Question) ?

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

    Just find all primes that are less or equal than 8000, and use knapsack algorithm for this:
    d[i] = how many primes needed to find i
    so, if d[j] > 0 and d[j] < 4 (if we can find j, and we can find it with less than 4 primes) then
    d[j | prime[i]] = d[j] + 1 if this is a better solution.
    my code

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

My code for B: http://ideone.com/NPSnTu :D (it got full score)

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

    Okay. I am not able to figure out what rng.next(v.size()) does ?

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

      Well, rng is just a pseudo random number generator and rng.next(K) generates a number in range [0;K-1]. So what I do in order to check if the current number can be expressed as the "OR" of at most 4 numbers is the following. Having the prime numbers in a vector "primes", we can take those which can possibly be in the at most 4 numbers. A number P can be in those at most 4 numbers if A==(P|A) where A is the current number to be checked. Now, let's 8000 times take some randomly chosen 4 indices (not necessarily the same) and check with them :D

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

Screencast with music

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

How do you solve E with the maximum score? I could only get 85.72 by using Djikstra's algorithm.

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

    I have used the Suffix Automaton,then use Djikstra Dp(a,b) a-vertex,b-Automaton state.

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

      Well can you please explain why DP(a,b) with state b as suffix automaton work ?? I was thinking of DP(a,b) where b was the hash of the string formed till now i.e shotest path from 1 to a with b as the string formed but that would give tle as there are total n square possibilities of b.

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

When will the editorials be available?

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

By the way, what does %pic related% button do? I thought that Shortest Path Revisited was the fourth problem since it's exactly what I saw after I followed this link from the 3rd task: look at the bottom-left corner of the picture.

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

    I couldn't open the challenges page, so clicked "try next challenge" after solving the second one & got the hardest problem(shortest path revisited) as third -_-

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

Why doesn't hashing work in Shortest-path problem(Problem Link) ?Or it does and I did it wrong.

Here's what I did.

  1. Stored count of all pairs of (hash, substring_length) for all possible substrings of s.

  2. Stored 4 items in heap — (cur_distance, cur_node, cur_hash, cur_length).cur_length denotes the length of substring formed on reaching node cur_node from node 1.

  3. Applied Dijkstra.

But I'm getting only 85.71 points and wrong answer on many test cases.Here's my code.

→ Reply