'Team Split' problem

Below is my solution for this 'Team Split' problem.

In summary, the problem is to find relative strength of 2 teams by finding the difference between their total strength (individual strengths can be found using a quadratic expression of form ax2+bx+c).

The solution in Java manages to solve the problem, but I am regularly getting the Time Limit Exceeded issue.

Can anyone offer advice on how to reduce the complexity of this code?

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

public class Main {
public static void main (String args[]) throws IOException{
try{
int a,b,c,d;
for(int i=0;i<not;i++){
int r=Integer.parseInt(s[0]);
a=Integer.parseInt(s[1]);
b=Integer.parseInt(s[2]);
c=Integer.parseInt(s[3]);
d=Integer.parseInt(s[4]);
long S[]=new long [r];
S[0]=d;
for(int k=1;k<r;k++){
S[k]=((a*S[k-1]*S[k-1])+(b*S[k-1])+c)%1000000;
//System.out.println(S[k]);
}
Arrays.sort(S);
long so1=0;
long so2=0;
long t;
for(int p=r-1,q=r-2;p>=0;p=p-2,q=q-2){
if(q>=-1){
so1=so1+S[p];
if(q>=0){
so2=so2+S[q];
}
}
}
// System.out.println(so1);
// System.out.println(so2);
t=so1-so2;
if(t<0){
t=(-1)*t;
}
System.out.println(t);
//sc.close();
}
}catch(NumberFormatException afe){
System.out.println(afe);
}
}
}

• When exactly are you getting time limit exceeded? For what inputs? Mar 23, 2014 at 16:38
• @SimonAndréForsberg You can submit your code to codechef.com/MARCH14/problems/TMSLT ... perhaps it will show you its inputs. One of the comments on that page (dated 8 Mar 2014 11:07 AM) gives one set of example inputs. Mar 23, 2014 at 16:45
• guys the issue is my solution involves sorting of arrays and that increases the complexity,any workarounds such that sorting can be avoided to solve that problem. Mar 23, 2014 at 17:24

(If you can't tell, that is supposed to say 'readability'). Leaves some things to be desired.

• Variable names: All your variable names are three characters or less. This makes it very hard to read your code. Renaming r to playerCount is a start, and S can be called strengths. so1 and so2 should also be renamed, along with t, p and q. Make variables self-documenting by giving them a reasonable name.

• Spacing: Dontyoufinditabithardtoreadtext/codethatdoesntcontainanyspacesandappropriatepunctuation? (I'm exagerating just to prove a point). Even though it is a bit easier to read lack of code spacing than lack of word-spacing in written text, I find a line like this hard to read:

S[k]=((a*S[k-1]*S[k-1])+(b*S[k-1])+c)%1000000;


For this particular line, consider rewriting it to this:

int previous = strengths[index - 1];
strengths[index] = (a * previous * previous + b * previous + c) % 1000000;


By using better variable names, adding space, extracting a variable, and removing unnecessary parenthesis that line becomes a lot more readable.

The lack of good variable names and spacing especially made this part of the code really hard for me to understand what you are doing and why:

for(int p=r-1,q=r-2;p>=0;p=p-2,q=q-2){
if(q>=-1){
so1=so1+S[p];
if(q>=0){
so2=so2+S[q];
}
}
}


Speed

Unable to reproduce / Unclear what the issues are. It seems to me that your code is quite fast. Even the input 10000000 5 6 7 8 calculated with reasonable speed IMO.

Extensibility

For testing purposes, to ensure both correct results and fast enough results, it would be useful to extract a method to do the actual calculations, and then your outermost loop could be:

        for (int i = 0; i < count; i++) {
int playerCount = Integer.parseInt(s[0]);
a = Integer.parseInt(s[1]);
b = Integer.parseInt(s[2]);
c = Integer.parseInt(s[3]);
d = Integer.parseInt(s[4]);
System.out.println(determineTeamDifferences(playerCount, a, b, c, d));
}

• That weird p-q-r for-loop can be untangled by noticing that p and q have a constant offset, by moving the bounds, removing unnecessary tests, and noticing that if(q>=0) is true when r is odd. I played a bit with the source code which makes this more obvious but doesn't improve performance (the other solutions from the challenge's page use a weird form of memoization to find repetitions – there are only 1M possible values, after all).
– amon
Mar 23, 2014 at 17:52

guys the issue is my solution involves sorting of arrays and that increases the complexity,any workarounds such that sorting can be avoided to solve that problem.

There's one Sort statement in your program:

            long S[]=new long [r];
S[0]=d;
for(int k=1;k<r;k++){
S[k]=((a*S[k-1]*S[k-1])+(b*S[k-1])+c)%1000000;
//System.out.println(S[k]);
}
Arrays.sort(S);


It seems to me that the output (for reasonable values of a,b,c) is mostly sorted already. It will wrap when it exceeds 1000000.

So an algorithm like:

long knext = ((a*S[k-1]*S[k-1])+(b*S[k-1])+c)%1000000;
if (knext >= kprev)
store in same array as kprev
else
create a new array and store as first element in new array


After you do that, you have one sorted array (if it never wrapped), or several sorted arrays to be merged. Every array is already sorted.

The above might be a large optimization: changing the data structure and algorithm.

The following might be a micro-optimization:

S[k]=((a*S[k-1]*S[k-1])+(b*S[k-1])+c)%1000000;


The above does an array lookup 3 times to calculate the expression; so the following may be a little faster (cache the previous value in a local variable instead of only in the previous element of the array):

S[0] = d;
long value = d;
for (int k = 1; k < r; ++k) {
value = ((a*value*value) + (b*value) + c) % 1000000;
S[k] = value;
}