The Clocks on USACO

I submitted my code for a question on USACO titled "The Clocks".

This is the link to the question: http://ace.delos.com/usacoprob2?a=wj7UqN4l7zk&S=clocks

This is the output:

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.173 secs, 13928 KB]
   Test 2: TEST OK [0.130 secs, 13928 KB]
   Test 3: TEST OK [0.583 secs, 13928 KB]
   Test 4: TEST OK [0.965 secs, 13928 KB]

  > Run 5: Execution error: Your program (`clocks') used more than the
        allotted runtime of 1 seconds (it ended or was stopped at 1.584
        seconds) when presented with test case 5. It used 13928 KB of
        memory. 

        ------ Data for Run 5 ------
        6 12 12 
        12 12 12 
        12 12 12 
        ----------------------------

        Your program printed data to stdout.  Here is the data:
        -------------------
        time:_0.40928452
        -------------------

    Test 5: RUNTIME 1.584>1 (13928 KB)

I wrote my program so that it will print out the time taken (in seconds) for the program to complete before it exits.

As can be seen, it took 0.40928452 seconds before exiting. So how the heck did the runtime end up to be 1.584 seconds? What should I do about it?

This is the code if it helps:

import java.io.*;<br>
import java.util.*;

class clocks {

    public static void main(String[] args) throws IOException {

        long start = System.nanoTime();
        // Use BufferedReader rather than RandomAccessFile; it's much faster
        BufferedReader f = new BufferedReader(new FileReader("clocks.in"));
        // input file name goes above
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("clocks.out")));
        // Use StringTokenizer vs. readLine/split -- lots faster

        int[] clock = new int[9];

        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(f.readLine());
            // Get line, break into tokens
            clock[i * 3] = Integer.parseInt(st.nextToken());
            clock[i * 3 + 1] = Integer.parseInt(st.nextToken());
            clock[i * 3 + 2] = Integer.parseInt(st.nextToken());
        }

        ArrayList validCombination = new ArrayList();;
        for (int i = 1; true; i++) {
            ArrayList combination = getPossibleCombinations(i);
            for (int j = 0; j < combination.size(); j++) {
                if (tryCombination(clock, (int[]) combination.get(j))) {
                    validCombination.add(combination.get(j));
                }
            }
            if (validCombination.size() > 0) {
                break;
            }
        }

        int [] min = (int[])validCombination.get(0);
        if (validCombination.size() > 1){
            String minS = "";
            for (int i=0; i<min.length; i++)
                minS += min[i];

            for (int i=1; i<validCombination.size(); i++){
                String tempS = "";
                int [] temp = (int[])validCombination.get(i);
                for (int j=0; j<temp.length; j++)
                    tempS += temp[j];
                if (tempS.compareTo(minS) < 0){
                    minS = tempS;
                    min = temp;
                }
            }
        }

        for (int i=0; i<min.length-1; i++)
            out.print(min[i] + " ");
        out.println(min[min.length-1]);

        out.close();                                  // close the output file

        long end = System.nanoTime();
        System.out.println("time: " + (end-start)/1000000000.0);
        System.exit(0);                               // don't omit this!
    }

    static boolean tryCombination(int[] clock, int[] steps) {
        int[] temp = Arrays.copyOf(clock, clock.length);

        for (int i = 0; i < steps.length; i++) 
            transform(temp, steps[i]);

        for (int i=0; i<temp.length; i++)
            if (temp[i] != 12)
                return false;
        return true;
    }

    static void transform(int[] clock, int n) {
        if (n == 1) {
            int[] clocksToChange = {0, 1, 3, 4};
            add3(clock, clocksToChange);
        } else if (n == 2) {
            int[] clocksToChange = {0, 1, 2};
            add3(clock, clocksToChange);
        } else if (n == 3) {
            int[] clocksToChange = {1, 2, 4, 5};
            add3(clock, clocksToChange);
        } else if (n == 4) {
            int[] clocksToChange = {0, 3, 6};
            add3(clock, clocksToChange);
        } else if (n == 5) {
            int[] clocksToChange = {1, 3, 4, 5, 7};
            add3(clock, clocksToChange);
        } else if (n == 6) {
            int[] clocksToChange = {2, 5, 8};
            add3(clock, clocksToChange);
        } else if (n == 7) {
            int[] clocksToChange = {3, 4, 6, 7};开发者_Python百科
            add3(clock, clocksToChange);
        } else if (n == 8) {
            int[] clocksToChange = {6, 7, 8};
            add3(clock, clocksToChange);
        } else if (n == 9) {
            int[] clocksToChange = {4, 5, 7, 8};
            add3(clock, clocksToChange);
        }
    }

    static void add3(int[] clock, int[] position) {
        for (int i = 0; i < position.length; i++) {
            if (clock[position[i]] != 12) {
                clock[position[i]] += 3;
            } else {
                clock[position[i]] = 3;
            }
        }
    }

    static ArrayList getPossibleCombinations(int size) {
        ArrayList l = new ArrayList();

        int[] current = new int[size];
        for (int i = 0; i < current.length; i++) {
            current[i] = 1;
        }

        int[] end = new int[size];
        for (int i = 0; i < end.length; i++) {
            end[i] = 9;
        }

        l.add(Arrays.copyOf(current, size));

        while (!Arrays.equals(current, end)) {
            incrementWithoutRepetition(current, current.length - 1);
            l.add(Arrays.copyOf(current, size));
        }

        int [][] combination = new int[l.size()][size];
        for (int i=0; i<l.size(); i++)
            combination[i] = (int[])l.get(i);

        return l;
    }

    static int incrementWithoutRepetition(int[] n, int index) {
        if (n[index] != 9) {
            n[index]++;
            return n[index];
        } else {
            n[index] = incrementWithoutRepetition(n, index - 1);
            return n[index];
        }
    }

    static void p(int[] n) {
        for (int i = 0; i < n.length; i++) {
            System.out.print(n[i] + " ");
        }
        System.out.println("");
    }
}

---

maybe they counting run time as a whole with a Java Virtual Machine startup/warmup

---

I have test your code. In my computer, it costs 6 seconds to calculate the sixth data. I also do a code for this problem, but I was failed at the sixth data. My solution costs 1.4 seconds. I don't know how to deal with it. Two possible cases to me is that my solution is not fast enough, or the solution code in Java can't run fast enough. So if you think your solution is fast enough, I suggest you to code it in C++ or C.

Good luck with you.

I just fond a better solution on topcoder this is the URL: enter link description here