CherryTree's blog

HackerRank 101Hack 30th Edition
By CherryTree, history, 11 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

»
11 years ago, hide # |
← 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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Ideas for 3rd??

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

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

→ Reply
»
11 years ago, hide # |
 
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
»
11 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, hide # ^ |
    ← 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
»
11 years ago, hide # |
← 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
  • »
    »
    11 years ago, hide # ^ |
     
    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
    • »
      »
      »
      11 years ago, hide # ^ |
       
      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
»
11 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Screencast with music

→ Reply
»
11 years ago, hide # |
← 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
  • »
    »
    11 years ago, hide # ^ |
     
    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
    • »
      »
      »
      11 years ago, hide # ^ |
       
      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
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

When will the editorials be available?

→ Reply
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    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
»
11 years ago, hide # |
 
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