Teamwork TLE

Problems and Contests
#1

Hi,

I used Java to solve the USACO Teamwork problem. My solution uses dynamic programming to construct the teams from left to right. Given the index of the next cow and the number of cows in the rightmost team, a matrix stores the maximum skill of each cow. Each step, you can go from the DP state (Index, Num) to (Index + 1, 1) and (Index + 1, Num + 1).

My solution has O(NK) time complexity, but it times out on the last test case. I am wondering if there are any optimizations I can make on the code, or if this approach is not good enough to solve the problem.

import java.io.*;
import java.util.*;

public class Teamwork {
    public static void main(String[] args) throws IOException {
//        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//        PrintWriter out = new PrintWriter(System.out);
        BufferedReader in = new BufferedReader(new FileReader("teamwork.in"));
        PrintWriter out = new PrintWriter(new FileWriter("teamwork.out"));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int numCows = Integer.parseInt(st.nextToken());
        int maxTeam = Integer.parseInt(st.nextToken());
        int[] skill = new int[numCows];
        for (int i = 0; i < numCows; i++) {
            skill[i] = Integer.parseInt(in.readLine());
        }
        // Given the number of cows in rightmost team, and the index of the first cow to add,
        // Returns the max skill in rightmost team and max sum of skills NOT including team.
        State[][] teamSum = new State[maxTeam + 1][numCows + 1];
        for (int rIndex = 0; rIndex <= numCows; rIndex++) {
            for (int numMembers = 0; numMembers <= rIndex && numMembers <= maxTeam; numMembers++) {
                teamSum[numMembers][rIndex] = new State(0, Integer.MIN_VALUE);
            }
        }
        teamSum[0][0].maxSum = 0;

        for (int rIndex = 0; rIndex <= numCows; rIndex++) {
            for (int numMembers = 0; numMembers <= rIndex && numMembers <= maxTeam; numMembers++) {
                if (numMembers == 0 && rIndex != 0) continue;
                if (numMembers > 0) {
                    teamSum[numMembers][rIndex].maxSkill = Math.max(teamSum[numMembers - 1][rIndex].maxSkill, skill[rIndex - numMembers]);
                }
                if (rIndex < numCows) {
                    teamSum[1][rIndex + 1].maxSum = Math.max(teamSum[1][rIndex + 1].maxSum,
                        teamSum[numMembers][rIndex].maxSum + numMembers * teamSum[numMembers][rIndex].maxSkill);
                    if (numMembers < maxTeam) {
                        teamSum[numMembers + 1][rIndex + 1].maxSum = Math.max(teamSum[numMembers + 1][rIndex + 1].maxSum, teamSum[numMembers][rIndex].maxSum);
                    }
                }
            }
        }
        int maxTeamSum = -1;
        for (int numMembers = 1; numMembers <= maxTeam; numMembers++) {
            maxTeamSum = Math.max(maxTeamSum, teamSum[numMembers][numCows].maxSum + numMembers * teamSum[numMembers][numCows].maxSkill);
        }
        out.println(maxTeamSum);
        out.close();
    }
}
class State {
    public int maxSkill;
    public int maxSum;

    public State(int maxSkill, int maxSum) {
        this.maxSkill = maxSkill;
        this.maxSum = maxSum;
    }
}
#2

This is just throwing darts, but maybe use a two-element array instead of your State class? Not sure if it’ll help you though.

#3

Well, I guess classes are pretty slow, because once I replaced it with two matrices, the runtime was halved.

#4

The following code for MooBuzz does 10^8 operations on a int matrix, and runs in ~2 seconds:

import java.io.*;

public class MooBuzz {
    public static void main(String[] args) throws IOException {
        // To test speed of arrays / classes

        int[][] array = new int[10001][10001];
        for (int i = 1; i <= 10000; i++) {
            for (int j = 1; j <= 10000; j++) {
                array[i][j] = Math.abs(array[i - 1][j] - array[i][j - 1]);
            }
        }

        int[] rem = new int[]{-1, 1, 2, 4, 7, 8, 11, 13};
        BufferedReader in = new BufferedReader(new FileReader("moobuzz.in"));
        PrintWriter out = new PrintWriter(new FileWriter("moobuzz.out"));
        int N = Integer.parseInt(in.readLine());
        out.println(N / 8 * 15 + rem[N % 8]);
        out.close();
    }
}

The following code creates a wrapper class matrix and does 10^7 operations. It runs in the same time (~2 seconds):

import java.io.*;

public class MooBuzz {
    public static void main(String[] args) throws IOException {
        // To test speed of arrays / classes

        Test[][] array = new Test[10000][1000];
        for (int i = 0; i < 10000; i++) {
            for (int j = 0; j < 1000; j++) {
                array[i][j] = new Test(0);
            }
        }

        for (int i = 1; i < 10000; i++) {
            for (int j = 1; j < 1000; j++) {
                array[i][j].val = Math.abs(array[i - 1][j].val - array[i][j - 1].val);
            }
        }

        int[] rem = new int[]{-1, 1, 2, 4, 7, 8, 11, 13};
        BufferedReader in = new BufferedReader(new FileReader("moobuzz.in"));
        PrintWriter out = new PrintWriter(new FileWriter("moobuzz.out"));
        int N = Integer.parseInt(in.readLine());
        out.println(N / 8 * 15 + rem[N % 8]);
        out.close();
    }
}
class Test {
    public int val;

    public Test(int val) {
        this.val = val;
    }
}

So using classes can be up to 10 times slower than primitive values!

1 Like