Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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{
            BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
            int not=Integer.parseInt(sc.readLine());
            int a,b,c,d;
            for(int i=0;i<not;i++){
                String s[]=sc.readLine().trim().split(" ");
                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);
        }
    }
}
share|improve this question
1  
When exactly are you getting time limit exceeded? For what inputs? –  Simon André Forsberg Mar 23 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. –  ChrisW Mar 23 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. –  arunkrishnamurthy01 Mar 23 at 17:24
    
@arunkrishnamurthy01 I have asked once: Which inputs are giving you time limit exceeeded? I understand your concerns about speed and I'd gladly help you with them (if ChrisW's answer below isn't enough for you) if your code would have been easier to read and I'd had known what inputs are causing the time limit exceeded issue. Given the current state of your code and question, the time limit isn't your biggest problem IMO. –  Simon André Forsberg Mar 24 at 13:02

2 Answers 2

Rewafadhabihlgdity

(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++) {
            String s[] = sc.readLine().trim().split(" ");
            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));
        }
share|improve this answer
1  
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 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.

Merging those sorted arrays into one array ought to be cheaper than sorting one big, unsorted array.


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;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.