Scribd
Upload
195 views2 pages

Facebook Hacker Cup 2012 Solutions

This document summarizes three problems from the Facebook Hacker Cup 2012 competition: 1) The "Checkpoint" problem involves finding the minimum value of T, given S, such that S can be expressed as the sum of four numbers meeting certain criteria. 2) The "Recover the Sequence" problem requires determining the original sequence before sorting, given the length of the sequence and output from a merge sort algorithm. 3) The "Squished Status" problem involves calculating the number of possible separations of a string into decimal numbers between 1 and a given value M, using a dynamic programming approach.

Uploaded by

Panot Chaimongkol
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
195 views2 pages

Facebook Hacker Cup 2012 Solutions

This document summarizes three problems from the Facebook Hacker Cup 2012 competition: 1) The "Checkpoint" problem involves finding the minimum value of T, given S, such that S can be expressed as the sum of four numbers meeting certain criteria. 2) The "Recover the Sequence" problem requires determining the original sequence before sorting, given the length of the sequence and output from a merge sort algorithm. 3) The "Squished Status" problem involves calculating the number of possible separations of a string into decimal numbers between 1 and a given value M, using a dynamic programming approach.

Uploaded by

Panot Chaimongkol
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 2

Facebook Hacker Cup 2012 - Round 1

Panot Chaimongkol

Problem 1: Checkpoint

For each S, nd minimum T such that S = xy x = p+q p x, y, p, q, r, s y = r+s r T =p+q+r+s where there are R cases (5 R 20) and 1 S 107 . The intuitive algorithm is to list all possible pairs of x and y and then nd p, q, r, s. But the search space for each pair (p, q) and (r, s) is too large; the search space is roughly the square of x or y which can be as large as S itself. The main point of my algorithm is to approximate p + q for each q (and also r + s for eachs). Suppose x = p+q , we have p x= p+q p (p + q)! p!q! (p + 1)(p + 2) (p + q) = q! q!x = (p + 1)(p + 2) (p + q) =

q!x > pq . So, for each q, we have


q

q!x > p. q q!x

The algorithm I used is to search from q = 1 and nd p starting from descending, until q > p.

Problem 2: Recover the Sequence

Given the length N of a sequence from 1 to N and the string emitted from the given merge sort algorithm, nd the original sequence before sorting. Solving this problem is not dicult. Reverse the merging algorithm by changing the condition for emitting the checking character to nd backward permutation for the sequence. 1

Problem 3: Squished Status

Given M and a string s, nd the number of possible separation such that each separation is a non-zero-leading decimal number n where 1 n M . Constraints: 2 M 255 and 1 len(s) 1000. This problem is solvable by a simple dynamic programming technique. Let l = len(s). for i = 1 l do dp[i] 0 if i 1and1 dp[i] M then if i = 1 then dp[i] dp[i] + 1 else dp[i] dp[i] + dp[i 1] end if end if if i 2and1 dp[i 1 : i] M then if i = 2 then dp[i] dp[i] + 1 else dp[i] dp[i] + dp[i 2] end if end if if i 3and1 dp[i 2 : i] M then if i = 3 then dp[i] dp[i] + 1 else dp[i] dp[i] + dp[i 3] end if end if end for return dp[l]

You might also like