started with facebook hacker cup 2012 in great enthusiasm, but then in the very first online round they come in with problems, wither purely based on math or some other bullsh!t stuff added to it.
The problems can be solved, but require not just out of the box thinking, infact you will have to figure it out of the universe... Let me give you a bit more specific detail about each problem.
Problem 1: Checkpoint
You are racing on a 2D lattice grid starting from the origin (0,0) towards a goal (M,N) where M and N are positive integers such that 0 < M <= N. There is a checkpoint that's neither on the origin nor on the goal with coordinates (m,n) such that 0 <= m <= M and 0 <= n <= N. You must clear the checkpoint before you reach the goal. The shortest path takes T = M + N steps.
At each point, you can move to the four immediate neighbors at a fixed speed, but since you don't want to lose the race, you are only going to take either a step to the right or to the top.
Even though there are many ways to reach the goal while clearing the checkpoint, the race is completely pointless since it is relatively easy to figure out the shortest route. To make the race more interesting, we change the rules. Instead of racing to the same goal (M,N), the racers get to pick a goal (x,y) and place the checkpoint to their liking so that there are exactly S distinct shortest paths.
For example, given S = 4, consider the following two goal and checkpoint configurations
Placing the checkpoint at (1, 3) and the goal at (2,3). There are 4 ways to get from the origin to the checkpoint depending on when you move to the right. Once you are at the checkpoint, there is only one way to reach the goal with minimal number of steps. This gives a total of 4 distinct shortest paths, and takes T = 2 + 3 = 5 steps. However, you can do better.
Placing the checkpoint at (1, 1) and the goal at (2,2). There are two ways to get from the origin to the checkpoint depending on whether you move to the right first or later. Similarly, there are two ways to get to the goal, which gives a total of 4 distinct shortest paths. This time, you only need T = 2 + 2 = 4 steps.
As a Hacker Cup racer, you want to figure out how to place the checkpoint and the goal so that you cannot possibly lose. Given S, find the smallest possible T, over all possible checkpoint and goal configurations, such that there are exactly S distinct shortest paths clearing the checkpoint.
Input
As input for the race you will receive a text file containing an integer R, the number of races you will participate in. This will be followed by R lines, each describing a race by a single number S. Lines are separated using Unix-style ("\n") line endings.
Output
Your submission should contain the smallest possible length of the shortest path, T for each corresponding race, one per line and in order.
Constraints
5 <= R <= 20 1 <= S <= 10000000
Example Input:
5
4
5
12
14
1
Example Output:
Case #1: 4
Case #2: 6
Case #3: 6
Case #4: 9
Case #5: 2
The Issues:
The problem is not that easy as it seems, it requires a lot more imagination than can be visualized by a simple person. The problem says about S the number of unique ways, but you will have to see that:
Consider two graphs different from one another, one graphs takes you from start to checkpoint (so it will generate, S(start -> checkpoint) and T(start -> checkpoint) ), and the other takes you from checkpoint to the destination.
You can visualize the following way (I just borrowed it from some forum and rotated it):
Now to locate that at what coordinate is the value some number, you need to look at the binomial theorem, even better, look at the Pascal's Tree created by pascal using Binomial Theorem. Co-relate it to the points on your graph. you get:
1,1 = 2 or 2,2 = 6 or 1,2 = 3
Now I wrote a very simple function to return you an array for a particular diagonal, this function will originall return the maximum values in a diagonal, like, 2, 6, 10, 20... so on... but can be modified as per your needs:
But yet again I failed to write the complete program as the values varied too much, and could not figure out an exact approach, many believe that sqrt($num) will give them the ideal case then I can prove that there is a probability that your answer is more than wrong. the correct solution will be to track the factors of the number on the pascal's triangle and then proceding, Another thing was, many believed that the sample I/O was wrong, for that, I must tell that it is perfectly fine, and my program works for all $n< 100; in case of bigger number it does just gets enough time and memory.
Problem 2: Recover The Sequence
Merge sort is one of the classic sorting algorithms. It divides the input array into two halves, recursively sorts each half, then merges the two sorted halves.
In this problem merge sort is used to sort an array of integers in ascending order. The exact behavior is given by the following pseudo-code:
function merge_sort(arr):
n = arr.length()
if n <=1:returnarr//arrisindexed0throughn-1,inclusivemid = floor(n/2)first_half = merge_sort(arr[0..mid-1])second_half = merge_sort(arr[mid..n-1])returnmerge(first_half,second_half)functionmerge(arr1,arr2):result = []whilearr1.length()> 0 and arr2.length() > 0:
if arr1[0] <arr2[0]:print'1'//fordebuggingresult.append(arr1[0])arr1.remove_first()else:print'2'//fordebuggingresult.append(arr2[0])arr2.remove_first()result.append(arr1)result.append(arr2)returnresult
A very important permutation of the integers 1 through N was lost to a hard drive failure. Luckily, that sequence had been sorted by the above algorithm and the debug sequence of 1s and 2s was recorded on a different disk. You will be given the length N of the original sequence, and the debug sequence. Recover the original sequence of integers.
Input
The first line of the input file contains an integer T. This is followed by T test cases, each of which has two lines. The first line of each test case contains the length of the original sequence, N. The second line contains a string of 1s and 2s, the debug sequence produced by merge sort while sorting the original sequence. Lines are separated using Unix-style ("\n") line endings.
Output
To avoid having to upload the entire original sequence, output an integer checksum of the original sequence, calculated by the following algorithm:
function checksum(arr):
result = 1
for i=0 to arr.length()-1:
result = (31 * result + arr[i]) mod 1000003
return result
Constraints
5 ≤ T ≤ 20
2 ≤ N ≤ 10000
Examples
In the first example, N is 2 and the debug sequence is 1. The original sequence was 1 2 or 2 1. The debug sequence tells us that the first number was smaller than the second so we know the sequence was 1 2. The checksum is 994.
In the second example, N is 2 and the debug sequence is 2. This time the original sequence is 2 1.
In the third example, N is 4 and the debug sequence is 12212. The original sequence is 2 4 3 1.
Case #1: 994
Case #2: 1024
Case #3: 987041
Case #4: 570316
Case #5: 940812
The Issues:
Some say its the most difficult, I say would just require more time, the thing looks simple, but actually is not that simple. the first solution you might think off is, calculating all permutations of N and the solve each one to match criterion, but that actually wont happen that easily since the N<=10000 that might just take ages for even a super computer to solve easily.
My Take:
I tried to reverse the algorithm, which was time consuming but it works, at least on pen and paper, its a simple one:
Just reverse the input and debug code as an array.
get the first element from both, and initialize two empty arrays Arr1 and Arr2.
if the debug val is 2 it means that the second last number was belonging to the 2nd array then so place the first element in the Arr1.
the second element thus goes in Arr2
third will be checked on the basis of debug val, if it is 2, then put it in 2, else put it in 1
continue till we have placed all the inputs.
now initialize the Arr1 and Arr2 as two new input elements, meaning use these 2 elements and place it in array using debug code.
rinse and repeat
Fact:
I could not solve this, programmatically because first the algo is buggy for odd number of elements, secondly its poorly inefficient, third it is designed considering a small set of numbers and might fail for the long set.
Problem 3: Squished Status:
Some engineers got tired of dealing with all the different ways of encoding status messages, so they decided to invent their own. In their new scheme, an encoded status message consists of a sequence of integers representing the characters in the message, separated by spaces. Each integer is between 1 and M, inclusive. The integers do not have leading zeroes. Unfortunately they decided to compress the encoded status messages by removing all the spaces!
Your task is to figure out how many different encoded status messages a given compressed status message could have originally been. Because this number can be very large, you should return the answer modulo 4207849484 (0xfaceb00c in hex).
For example, if the compressed status message is "12" it might have originally been "1 2", or it might have originally been "12". The compressed status messages are between 1 and 1000 characters long, inclusive. Due to database corruption, a compressed status may contain sequences of digits that could not result from removing the spaces in an encoded status message.
Input
The input begins with a single integer, N, the number of compressed status messages you must analyze. This will be followed by N compressed status messages, each consisting of an integer M, the highest character code for that database, then the compressed status message, which will be a string of digits each in the range '0' to '9', inclusive. All tokens in the input will be separated by some whitespace.
Output
For each of the test cases numbered in order from 1 to N, output "Case #i: " followed by a single integer containing the number of different encoded status messages that could be represented by the corresponding compressed sequence modulo 4207849484. If none are possible, output a 0.
Constraints
5 <= N <= 25 2 <= M <= 255 1 <= length of encoded status <= 1000
Example Input:
5
12
12
255
219
30
1234321
2
101
70 8675309
Example Output:
Case #1: 2
Case #2: 4
Case #3: 6
Case #4: 0
Case #5: 2
The Issues:
People Claimed that this was the easiest, but I say this was the most prone to errors, first it says the input is separated by some spaces and later they clarified that the these spaces can be anything from a new line to a tab, means my code had to be tolerant towards:
\n | \r | \t | " " | etc.
People who had submitted the solution said that the input file was full of garbage values instead of white spaces.
My Take:
I think most of you can think how to solve it, since everyone said it was the easiest.
Fact:
I did not gave it much of try because the template which I use, uses the new line as the base to scan input file, designing a new template just for this sill problem seemed so tiring... the truth is... I even tried once.... but failed to check all the garbage stuff.
Finally, I have not submitted even a single problem, though had solved many algorithmically and believe that if I work more can get this done, but I do not want to right now. It was a nice experience and will be better prepared by next year, the people whom we are competing are PhD students with advance researches in just algorithms... So there is no point comparing a pr0-n00b to sup4-pr0s.
Cheers Guys!
Happy Fucking Hacking!
PS: I am desperately waiting for the score board to be dotted red, because most of you scrip-kiddies made a hush to submit your solutions (maybe staying on top of the score board for just 24-hours makes you feel... h4ppy!)
visualizing pascal triangle[/caption]
