Facebook Hacker Cup 2012 Round 1 Solutions: Checkpoint

Problem:

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

Solution:
Note that the racer will only take steps to the right or top. This leads us to a number of conclusions about the number of possible paths to a point in the lattice grid:

• the number of distinct shortest paths for every point situated on (x, 0) and (0, y) is 1;
• the number of distinct shortest paths for every target point on the lattice grid is exactly the sum of the number of distinct shortest paths leading to point at the target's immediate left, and point at the target's bottom.  This arrangement is very similar to the way binomial coefficients are calculated.

For each arrangement of the goal and checkpoint, the number S of distinct shortest paths leading to the goal through the checkpoint is number of shortest paths to the checkpoint Sc multiplied by the number of shortest paths from the checkpoint to the target St. Note that both these numbers can be found independently - for the number of paths to the checkpoint, the bottom left corner of the lattice grid represents the starting position; for the number of paths from the checkpoint to the target, the bottom left corner of the lattice grid represents the checkpoint.

The minimum number of steps needed to reach a point with coordinates [X, Y] in the lattice grid is obviously X+Y.

So, my algorithm has the following steps:

1. Pre-calculate the number of paths leading to each point in the lattice grid. The values are used to fill a vector P that maps number of distinct shortest paths to least possible amount of steps needed to reach a point in a lattice grid that has this exact number of distinct shortest paths leading to it from the starting corner. With a decent amount of constraints, this pre-calculation takes approximately ~500ms.
2. Set T to some large number (+inf)
3. Find all the possible pairs of factors F1, F2 for S (F1*F2=S). For each pair, check the sum P[F1]+P[F2], and, if the sum is less than T, store this sum as T.
4. Output T.

Facebook Hacker Cup 2012 Round 1 Solutions: Recover the Sequence

Problem:

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:

        return arr

    // arr is indexed 0 through n-1, inclusive

    mid = floor(n/2)

    

    first_half = merge_sort(arr[0..mid-1])

    second_half = merge_sort(arr[mid..n-1])

    return merge(first_half, second_half)

function merge(arr1, arr2):

    result = []

    while arr1.length() > 0 and arr2.length() > 0:

        if arr1[0] < arr2[0]:

            print '1' // for debugging

            result.append(arr1[0])

            arr1.remove_first()

        else:

            print '2' // for debugging

            result.append(arr2[0])

            arr2.remove_first()

            

    result.append(arr1)

    result.append(arr2)

    return result

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.

Solution:
Solution is easy. You just have to re-implement the provided algorithm in the language of your choice, with the only exception: instead of comparing arr1[0] to arr2[0] and outputting '1' or '2' depending on the result of the comparison, we append the result with the arr1[0] if the debug sequence [0] is '1', and arr2[0] otherwise. Just do not forget to strip the debug sequence of the 0th element afterwards.

Feed the sorted sequence of 1..N to the re-implemented algorithm. The algorithm will produce a permutation of the input. In this permutation, for i from 0 to N-1, permutation[i] is the position of element with the value of i+1 in the original sequence.

Having the original sequence, we only have to apply the checksum function to it, and output the result.

Facebook Hacker Cup 2012 Round 1 Solutions: Squished Status

Problem:

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

To solve the Squished Status problem, I wrote a following function:

Paths(string, depth) - function calculating the number of possible statuses encoded by a string in the given BASE.

1. If length of string is 0 return 1;
2. If cached number is available for the given depth, return the cached value (that was previously calculated by this function for the current depth);
3. If string starts with 0, return 0; 
4. If length of the string is 1: return 1 if value of the single element of the string is less then BASE, otherwise, return 0;
5. Set l=1; res=0;
6. While the integer value of substring(string, 0, l) is less than BASE: res += paths(t.substring(l, t.length()));

As a means of optimization, I also converted the input string into an array of integers on char-by-char basis, but, probably, the solution.

Code of this function in Java:

        private long paths(int a[], int length, int X){

        if (length == 0) return 1;

        if (a[0] == 0) return 0;

        if (length == 1)

        if (a[0] <= base)

          return 1;

        else 

           return 0;

        if (P[X] > -1) return P[X];

       

        long res = 0;

        int l = 1;

        int n = a[0];

       

        while (l<=length && n <= base){

        res += paths(Arrays.copyOfRange(a, l, length), length-l, X+l);

       

        if (l

        l++;        

        }

        P[X] = res % 4207849484L;

        return P[X];

        }

Ruby: Forward new email using IMAP and SMTP

Ever wondered how to forward email in Ruby?


#!/usr/bin/env ruby
require 'net/imap'
require 'net/smtp'


# Author: Sergei Velhas, sergei@velhas.net


FORWARD_TO = ["users@example.com","mail2@example.com"]
MAILBOX_LOGIN = "user"
MAILBOX_PASSWORD = "password"
FROM = 'user@example.com'
MAILSERVER = 'mbox.example.com'


imap = Net::IMAP.new(MAILSERVER)
  imap.authenticate('LOGIN', MAILBOX_LOGIN, MAILBOX_PASSWORD)
  imap.examine('INBOX')


  imap.search(["UNSEEN"]).each do |message_id|
    envelope = imap.fetch(message_id, "ENVELOPE")[0].attr["ENVELOPE"]


    # Adjust the if clause to suit the needed automation level
    if envelope.from[0].name =~ /John Doe/ then
      puts "\n\n Going to forward the message from #{envelope.from[0].name}: \t#{envelope.subject} \n\n"


      email = <<END_OF_MESSAGE
Subject: #{envelope.subject}


#{imap.fetch(message_id, "BODY[TEXT]")[0].attr["BODY[TEXT]"]}
END_OF_MESSAGE


      Net::SMTP.start('mboxld.ericpol.int') do |smtp|
        smtp.sendmail(email, FROM,FORWARD_TO)
      end


      imap.store(message_id, "+FLAGS", [:Seen])
    end
  end

Can You Confirm You Understood that Message?

Happy New Year!

The postcard by generation.by is dedicated to Dec. 19th events in Minsk. Over 640 innocent people plus 7 presidential candidates were detained, and thousands were beaten by riot police when well over 50000 people gathered in Minsk to protest against rigged elections.

It is not funny anymore