Facebook Hacker Cup Qualification Round

Last weekend i’m participating on Facebook Hacker Cup, and the first stage is qualification round. If you managed to answer one of the problem you can pass to next round.

In Qualification round there is 3 problems :

1. Cooking Books (https://www.facebook.com/hackercup/problems.php?pid=582062045257424&round=742632349177460)
   Every business can make use of a good accountant and, if they’re not big on following the law, sometimes a bad one. Bad accountants try to make more money for their employers by fudging numbers without getting caught.

   Sometimes a bad accountant wants to make a number larger, and sometimes smaller. It is widely known that tax auditors will fail to notice two digits being swapped in any given number, but any discrepancy more egregious will certainly be caught. It’s also painfully obvious when a number has fewer digits than it ought to, so a bad accountant will never swap the first digit of a number with a 0.

   Given a number, how small or large can it be made without being found out?

   Input
   Input begins with an integer T, the number of numbers that need tweaking. Each of the next T lines contains a integer N.

   Output
   For the ith number, print a line containing “Case #i: ” followed by the smallest and largest numbers that can be made from the original number N, using at most a single swap and following the rules above.

   Constraints
   1 ≤ T ≤ 100
   0 ≤ N ≤ 999999999
   N will never begin with a leading 0 unless N = 0

   Input :
   5
   31524
   897
   123
   10
   5

   Output :
   Case #1: 13524 51324
   Case #2: 798 987
   Case #3: 123 321
   Case #4: 10 10
   Case #5: 5 5

And this is my answer source code :

import java.util.Scanner;


public class Cooking {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            int number = sc.nextInt();
            char [] a = (""+number).toCharArray();
            int max = from_char(a[0]);
            int max_p = 0;
            int min = from_char(a[0]);
            int min_p = 0;
            for (int j = 1; j < a.length; j++) {
                int temp = from_char(a[j]);
                if (min > temp){
                    min = temp;
                    min_p = j;
                }
                if (max < temp){
                    max = temp;
                    max_p = j;
                }
            }

            if (min == max ){
                System.out.println("Case #"+i+": "+number+" " + number);
            }
            else if (min == 0){
                String max1 = swap(a, max_p);
                System.out.println("Case #"+i+": "+number+" " + max1);
            }
            else{
                String min1 = swap(a, min_p);
                String max1 = swap(a, max_p);

                System.out.println("Case #"+i+": "+min1+" " + max1);

            }


        }

    }

    static String swap(char [] a, int pos2){
        char b[] = a.clone();
        char temp = b[0];
        b[0] = b[pos2];
        b[pos2] = temp;
        return new String(b);
    }

    static int from_char(char a){
        return ((int)a) - 48;
    }
}

Unfortunately my answer is wrong. After discussed with my friend we miss the tricky thing :
when the input is : 12340567
our minimum answer is : 12340567 but the right answer is 10342567

1. New Year’s Resolution (https://www.facebook.com/hackercup/problems.php?pid=1036037553088752&round=742632349177460)

   Alex’s New Year’s resolution for 2015 is to eat healthier foods. He’s done some research and has found out that calories come from three main sources, called macronutrients: protein, carbohydrates, and fat. Alex wants to get the right balance of protein, carbohydrates, and fat to have a balanced diet. For each available food, Alex can only choose to eat it or not eat it. He can’t eat a certain food more than once, and he can’t eat a fractional amount of a food.

   Input
   Input begins with an integer T, the number of test cases. For each test case, the first line consists of three space-separated integers: GP, GC, and GF, which represent the amount of protein, carbohydrates, and fat that Alex wants to eat. The next line has the number of foods for that test case, an integer N. The next N lines each consist of three space-separated integers: P, C, and F, which represent the amount of protein, carbohydrates, and fat in that food, respectively.

   Output
   For each test case i, print a line containing “Case #i: ” followed by either “yes” if it is possible for Alex to eat the exact amount of each macronutrient, or “no” if it is not possible.

   Constraints
   1 ≤ T ≤ 20
   1 ≤ N ≤ 20
   10 ≤ GP, GC, GF ≤ 1000
   10 ≤ P, C, F ≤ 1000

   Input :
   5
   100 100 100
   1
   100 100 100
   100 100 100
   3
   10 10 40
   10 30 10
   10 60 50
   100 100 100
   5
   40 70 30
   30 10 40
   20 20 50
   10 50 90
   40 10 20
   292 264 512
   20
   909 302 261
   705 597 823
   291 51 126
   28 697 57
   593 31 826
   311 256 57
   292 14 47
   29 730 716
   12 529 146
   768 16 439
   37 472 15
   350 192 34
   163 468 238
   69 173 10
   203 72 690
   424 875 213
   223 593 292
   151 46 10
   88 90 16
   773 653 711
   991 827 352
   20
   29 560 929
   139 681 102
   144 853 10
   84 729 80
   218 20 67
   140 80 901
   428 20 500
   520 970 128
   422 419 30
   413 101 192
   467 448 501
   32 939 684
   34 20 38
   251 317 132
   588 437 10
   648 21 79
   391 25 14
   499 22 24
   854 77 361
   405 25 20

   Output :

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

My solution for this case is Dynamic Programming, i combine the food and the combination result will save in an ArrayList. This is my Solution :

import java.util.ArrayList;
import java.util.Scanner;


public class Macronutrient {

    static int gp, gc, gf, n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String text = "";
        int T = sc.nextInt();
        for (int i = 1; i <= T; i++) {
            gp = sc.nextInt();
            gc = sc.nextInt();
            gf = sc.nextInt();

            n = sc.nextInt();

            int [] arrp = new int[n];
            int [] arrc = new int[n];
            int [] arrf = new int[n];

            for (int j = 0; j < n; j++) {
                int p = sc.nextInt();
                int c = sc.nextInt();
                int f = sc.nextInt();

                arrp[j] = p;
                arrc[j] = c;
                arrf[j] = f;



            }

            System.out.println("Case #"+i+": " + (process(arrp, arrc, arrf)?"yes" : "no"));
        }
    }

    static boolean process(int [] arrp, int [] arrc, int [] arrf){
        ArrayList<Integer> lp = new ArrayList<Integer>();
        ArrayList<Integer> lc = new ArrayList<Integer>();
        ArrayList<Integer> lf = new ArrayList<Integer>();

        boolean fp = false;
        boolean fc = false;
        boolean ff = false;
        for (int j = 0; j < n; j++) {
            lp.add(arrp[j]);
            lc.add(arrc[j]);
            lf.add(arrf[j]);
            int s = lp.size();
            int sump = 0;
            int sumc = 0;
            int sumf = 0;
            if (lp.size() == 1){
                if (arrp[0] == gp && arrc[0] == gc && arrf[0] == gf){
                    return true;
                }
            }
            for (int j2 = 0; j2 < s-1; j2++) {
                sump = lp.get(j2) + arrp[j];
                lp.add(sump);
                sumc = lc.get(j2) + arrc[j];
                lc.add(sumc);
                sumf = lf.get(j2) + arrf[j];
                lf.add(sumf);
                if (sump == gp && sumc == gc && sumf == gf){
                    return true;
                }
            }



            lp.add(arrp[j]);
            lc.add(arrc[j]);
            lf.add(arrf[j]);
        }
        return false;
    }
}

And for number 3, i’m not solve it yet but my guess is solve it using BFS or DFS.