My Facebook Hacker Cup 2012 Round 1 - Squished Status answer (Java)

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Scanner;


public class C {


    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("input.txt"));
        PrintWriter out = new PrintWriter(new File("output.txt"));
        int T = in.nextInt();
        for (int i = 0; i < T; i++) {
            String s = new C().solve(in,i+1);
            out.println(s);
            System.out.println(s);
        }
        out.close();
    }


    HashMap<Integer,Long> hash1=new HashMap<Integer,Long>();
    HashMap<Integer,Long> hash2=new HashMap<Integer,Long>();
    
    private void printDebug(HashMap<Integer,Long> hash1)
    {
    for(Entry<Integer,Long> e:hash1.entrySet())
    {
    System.err.println(e.getKey()+","+e.getValue());
    }
    }
    
    synchronized private String solve(Scanner in, int caseid) {
        int m = in.nextInt();
        String s = in.next();
    int i=0;
   
//        System.err.println("m="+m+",s="+s);
   
    hash1.clear();
    int c=(int)s.charAt(0)-48;
    if(c>0)
    hash1.put(c, 1l);
   
        for(i=1;i<s.length();i++)
        {
        c=(int)s.charAt(i)-48;
//            System.err.println("c="+c);


            hash2.clear();


            for(Entry<Integer,Long> e:hash1.entrySet())
            {
            int s0=e.getKey();
            int s1=s0*10+c;
            int s2=c;            
            long c0=(hash1.get(s0)!=null)?hash1.get(s0).intValue():0;
            long c1=(hash2.get(s1)!=null)?hash2.get(s1).intValue():0;
            long c2=(hash2.get(s2)!=null)?hash2.get(s2).intValue():0;
            hash2.put(s1,(c1+c0)%0xfaceb00c);            
            hash2.put(s2,(c2+c0)%0xfaceb00c);            
            if(s1<=0||s1>m)
                hash2.put(s1,0l);
            if(s2<=0||s2>m)
                hash2.put(s2,0l);
            }
            
            hash1.clear();
            for(Entry<Integer,Long> e:hash2.entrySet())
            {
            if(e.getValue()>0)
            {
            hash1.put(e.getKey(), e.getValue());
            }
            }
            
//            printDebug(hash1);
        }        
        long res=0;
        for(Entry<Integer,Long> e:hash1.entrySet())
        {
        res=(res+e.getValue())%0xfaceb00c;
        }
        
    return "Case #"+caseid+": "+res;
    }


}

My Facebook Hacker Cup 2012 Round 1 - Checkpoint answer (Java)

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;


public class C {

    static int nCrMax=10000000;
    static long _nCr[]=new long[nCrMax+1];
    static long _tmpnCr[]=new long[nCrMax+1];
    static int _n[]=new int[nCrMax+1];
    static int _r[]=new int[nCrMax+1];


    private static void init()
    {
    for(int i=1;i<=nCrMax;i++)
    {
    _n[i]=i;
    _r[i]=1;
    }
   
    _n[0]=0;_r[0]=0; //Not use    
    _nCr[0]=1;
    _nCr[1]=1;
    int thisRowEnd=0,r=0;
    for(int n=2;n<=nCrMax;n++)
    {
    for(r=1;r<=((int)(n/2));r++)
    {
    if(r==((int)(n/2))&&n%2==0)
    _tmpnCr[r]=(_nCr[r-1]*2);    
    else
    _tmpnCr[r]=(_nCr[r]+_nCr[(r-1)]);
   
    if(_tmpnCr[r]>nCrMax)
    {
    break;
    }
    }
    thisRowEnd=r-1;
    for(r=1;r<=thisRowEnd;r++)
    {
    _nCr[r]=_tmpnCr[r];
        int ncr=(int)_nCr[r];
        if((_n[ncr]+_r[ncr])>(n+r))
        {
        _n[ncr]=n;
        _r[ncr]=r;
        }
    }
    }
    }


    public static void main(String[] args) throws FileNotFoundException {
    init();
        Scanner in = new Scanner(new File("input.txt"));
        PrintWriter out = new PrintWriter(new File("output.txt"));
        int T = in.nextInt();
        for (int i = 0; i < T; i++) {
            String s = new C().solve(in,i+1);
            out.println(s);
            System.out.println(s);
        }
        out.close();
    }
             
    synchronized private String solve(Scanner in, int caseid) {
        int s = in.nextInt();
    int i;
    int res=Integer.MAX_VALUE;
        
    if(s==1)
    {
    res=_n[1]+_n[1];
    }
    else
    {
    for(i=1;i*i<=s;i++)
    {
    if(s%i==0)
      {
    int s1=i;
        int s2=s/i;
if(res>(_n[s1]+_n[s2]))
res=_n[s1]+_n[s2];
      }
    }
    }


    return "Case #"+caseid+": "+res;
    }


}

2012 Facebook Hacker Cup Auction Question

You have encountered a new fancy online auction that offers lots of products. You are only interested in their price and weight. We shall say that product A is strictly preferred over product B if A costs less than B and is not heavier (they may be of equal weight) or if A weighs less and is not more expensive (they can have equal price).

We shall call a product A a bargain if there is no product B such that B is better than A. Similarly, we shall call a product C a terrible deal if there exists no product D such that C is better than D. Note that according to our definitions, the same product may be both a bargain and a terrible deal! Only wacky auctioneers sell such products though.

One day you wonder how many terrible deals and bargains are offered. The number of products, N, is too large for your human-sized brain though. Fortunately, you discovered that the auction manager is terribly lazy and decided to sell the products based on a very simple pseudo-random number generator.

If product i has price P_i and weight W_i, then the following holds for product i+1:

• P_i = ((A*P_i-1 + B) mod M) + 1 (for all i = 2..N)
• W_i = ((C*W_i-1 + D) mod K) + 1 (for all i = 2..N)

You carefully calculated the parameters for the generator (P₁, W₁, M, K, A, B, C and D). Now you want to calculate the number of terrible deals and bargains on the site.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with 9 space-separated integers: N, P₁, W₁, M, K, A, B, C and D.

Output

Output T lines, one for each test case. For each case, output "Case #t: a b", where t is the test case number (starting from 1), a is the number of terrible deals and b is the number of bargains.

Constraints

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 10¹⁸
• 1 ≤ M, K ≤ 10⁷
• 1 ≤ P₁ ≤ M
• 1 ≤ W_1 ≤ K
• 0 ≤ A,B,C,D ≤ 10⁹

Example Input

5
5 1 4 5 7 1 0 1 2
3 1 3 3 3 1 0 1 1
8 1 3 3 3 1 0 1 2
13 5 7 5 9 1 3 2 5
11 2 3 5 7 11 13 17 19

Example Output

Case #1: 3 3
Case #2: 3 3
Case #3: 2 3
Case #4: 2 2
Case #5: 3 1

https://www.facebook.com/hackercup/problems.php?pid=268598303201105&round=146094915502528 

My Alphabet Soup Solution

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;

public class C {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("input.txt"));
        PrintWriter out = new PrintWriter(new File("output.txt"));
        int T = in.nextInt();
        for (int i = 0; i < T; i++) {
            String s = new C().solve(in,i+1);
            out.println(s);
            System.out.println(s);
        }
        out.close();
    }

    private String solve(Scanner in,int caseid) {
//        long n = in.nextLong();
//        long k = in.nextLong();
     int h=0,a=0,c=0,k=0,e=0,r=0,u=0,p=0;
     int stats[]={0,0,0,0,0,0,0,0};
     String s;
     do{
     s = in.nextLine();
     }while(s.length()<=0);
   
     for(int ii=0;ii<s.length();ii++)
     {
     char cc=s.charAt(ii);
     if(cc=='H'){ h++;stats[0]++;}
     if(cc=='A'){ a++;stats[1]++;}
     if(cc=='C'){ c++;stats[2]++;}
     if(cc=='K'){ k++;stats[3]++;}
     if(cc=='E'){ e++;stats[4]++;}
     if(cc=='R'){ r++;stats[5]++;}
     if(cc=='U'){ u++;stats[6]++;}
     if(cc=='P'){ p++;stats[7]++;}
     }
     stats[2]=(int)(stats[2]/2);
   
   
     int res=stats[0];
     int ri=0;
     for(int i=1;i<8;i++)
     {
     if(stats[i]<res)
     {
     res=stats[i];
     ri=i;
     }
     }
   
     return "Case #"+(caseid)+": "+res;
    }

}

Hacker Cup 2012 - 3 problems solved.

I just solved 3 questions. Here are some of my comments:

1. Alphabet Soup

Just use 8 counters to count the numbers of the key letters. The solution can be easily deduced by those values.

2. Auction

My approach is trying to construct a directed graph based on the 'better' relation. This graph constructed should be acyclic. Every root you found should be Bargain product. And every leaves should be Terrible Deal product. To save the computation time, I just used an ArrayList to model the computation mentioned above.

3. Billboards 

I just use brute force method for this problem. The fontsize are reducing during the iteration.

To make the verification easier, I assume there is a cursor in the billboard. When I insert a word to the billboard, the cursor move. If the cursor goes outside of the billboard, I reset and try another iteration with a smaller fontsize.