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!
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
I have this — https://www.hackerrank.com/contests/101hack30/challenges/sergey-and-homework
Please, somebody post forth and fifth tasks :)
https://www.hackerrank.com/contests/101hack30/challenges/solving-the-puzzle-1 https://www.hackerrank.com/contests/101hack30/challenges/shortest-path-revisited
Thanks! :)
Ideas for 3rd??
Binary search on how big A[i]*B[i] will be almost before the end
Can you be a little more specific?
Maybe a piece of code.. #tdG8Iv
Thanks!!!
Was 5th some standard stuff or did I miss some key observation?
Just a suffix automaton + Dijkstra...
LOL.. thought of this but gave up just because it was 5th .....
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?
GOT AC.
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.
Hey adamant, why don't you sort according to the number of problems while computing the final result?
It was easier for me to use set :)
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
How to solve "How Many Solvable Puzzles" I always get TLE
Care to elaborate? :P
You can store the xor of last two. 2 is interchangeable with 0.
Was anyone able to use the criteria of solvability on wikipedia for a solution that does not TLE?
Yep, look at my comment above
Any idea on how to solve Four Primes(2nd Question) ?
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 iso, if
d[j] > 0 and d[j] < 4(if we can find j, and we can find it with less than 4 primes) thend[j | prime[i]] = d[j] + 1if this is a better solution.my code
Thanks Bayan!
My code for B: http://ideone.com/NPSnTu :D (it got full score)
Okay. I am not able to figure out what rng.next(v.size()) does ?
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
Got it! Thanks!
Screencast with music
This video contains content from wtofficial, who has blocked it in your country on copyright grounds.
Nice music!
Ok, hence now without some music
This video is private.
Sorry about that.
Must work now
yep now it works fine thanks :)
How do you solve E with the maximum score? I could only get 85.72 by using Djikstra's algorithm.
I have used the Suffix Automaton,then use Djikstra Dp(a,b) a-vertex,b-Automaton state.
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.
When will the editorials be available?
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.
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 -_-
Why doesn't hashing work in Shortest-path problem(Problem Link) ?Or it does and I did it wrong.
Here's what I did.
Stored count of all pairs of (hash, substring_length) for all possible substrings of s.
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.
Applied Dijkstra.
But I'm getting only 85.71 points and wrong answer on many test cases.Here's my code.