3
\$\begingroup\$

I recently tried my hand at CodeSprint2 through Interview Street. Having not coded in quite some time, I wasn't surprised that I had difficulty writing optimized code, but on one problem in particular I can't find where I've gone wrong. I've compared my code to successful algorithms used by other programmers, and I don't see much difference. I tried in both Java and Ruby and hit a wall at the 4th test case with both (I'm just learning Ruby so thought it would be a fun exercise to try it - I tweaked my algorithm a little in the process).

The problem is Picking Cards and the description is here.

Code in Java:

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

public class Cards3 {

    public Cards3()
    {
    }

     public void run()
    {
        ArrayList<Integer> cards = new ArrayList<Integer>();
        try{
            /*
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String input = reader.readLine();

            StringTokenizer tokenizer = new StringTokenizer(input);
            int T = Integer.parseInt(tokenizer.nextToken());
            */

            DataInputStream reader = new DataInputStream(System.in);
            int T = reader.readInt();
            reader.readChar();
            System.out.println("T = " + T);
            //read in and test each subsequence
            for(int i = 0; i<T; i++)
            {
                /*
                input = reader.readLine();
                tokenizer = new StringTokenizer(input);
                int N = Integer.parseInt(tokenizer.nextToken());

                //read in and store cards
                String nextLine = reader.readLine();
                tokenizer = new StringTokenizer(nextLine);
                */

                int N = reader.readInt();
                reader.readChar();

                for(int j=0; j<N; j++)
                {
                    int next = reader.readInt();//Integer.parseInt(tokenizer.nextToken());
                    reader.readChar();
                    cards.add(next);
                }
                Collections.sort(cards);
                System.out.println(numWays(cards) % 1000000007);
                cards = new ArrayList<Integer>();
            }

            reader.close();
        }
        catch (IOException e)
        {
            System.out.println("Can not read input.");
        }
    }

    //computers the number of ways to pick up cards in currCards given that
    //numPicked cards have already been picked up
    public long numWays(ArrayList<Integer> cardsLeft)
    {
        int numPicked = 0;
        long numWays = 1;

        //calculate until all cards are picked up
        while(cardsLeft.size() >= 1)
        {
            //if we can't pick up the next card, we're at a dead end - no solutions
            if(cardsLeft.get(0) > numPicked)
                return 0;

            int numCanPick = 0;

            for(int i: cardsLeft)
            {   
                if(i <= numPicked)
                {
                    numCanPick++;

                }
                else
                {
                    break;
                }
            }

            cardsLeft.remove(0);
            numWays *= numCanPick;
            numWays = numWays % 1000000007;
            numPicked++;
        }

        return numWays;
    }

     public static void main(String args[])
       {
            Cards3 d = new Cards3();
            d.run();
       }
}

Code in Ruby

def runProgram
  answers = []
  t = STDIN.gets.to_i
  t.times{ 
    n = STDIN.gets
    numWays = 1
    cards = STDIN.gets.split.map(&:to_i)
    numPicked = 0
    for i in 0...cards.length
      numCanPick = cards.count{|a| a<= i}
      numWays = numWays * (numCanPick-i)
      break if numCanPick==0
      numWays = numWays % 1000000007
    end
     answers << numWays
  }

  puts answers
end

if __FILE__ == $0
 runProgram
 end
\$\endgroup\$
2

1 Answer 1

3
\$\begingroup\$

The immediate thing that jumps out to me is your use of an ArrayList for this. By continuously removing the first element, you force the array list to shift everything left one space each time (an O(n) operation assuming no underlying optimizations!)

Instead of removing from the array list (incurring an expensive shift), I would recommend that you keep an index.

    while(cardsLeft.size() >= 1)
    {
        //if we can't pick up the next card, we're at a dead end - no solutions
        if(cardsLeft.get(0) > numPicked)
            return 0;

        // ...
        for(int i: cardsLeft)
        {   
             // ...
        }

        // ...

        cardsLeft.remove(0);
        // ...
    }

becomes

    int cardIndex = 0;
    while(cardIndex < cardsLeft.length())
    {
        //if we can't pick up the next card, we're at a dead end - no solutions
        if(cardsLeft.get(cardIndex) > numPicked)
            return 0;
        // ...
        for(int i = cardIndex; i < cardsLeft.length(); ++i)
        {   
             // ...
        }
        // ...

        //cardsLeft.remove(0);
        ++cardIndex
        // ...
    }
\$\endgroup\$
1
  • \$\begingroup\$ I made the change and still hit the time limit after 3 test cases. \$\endgroup\$ Commented Jan 31, 2012 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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