# Teamwork TLE

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 {
//        PrintWriter out = new PrintWriter(System.out);
PrintWriter out = new PrintWriter(new FileWriter("teamwork.out"));
int numCows = Integer.parseInt(st.nextToken());
int maxTeam = Integer.parseInt(st.nextToken());
int[] skill = new int[numCows];
for (int i = 0; i < numCows; i++) {
}
// 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.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[rIndex + 1].maxSum = Math.max(teamSum[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;
}
}
``````

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.

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

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;
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};
PrintWriter out = new PrintWriter(new FileWriter("moobuzz.out"));
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;
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};
PrintWriter out = new PrintWriter(new FileWriter("moobuzz.out"));
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