Java time limit exceeded

Question

Im coding the problem (link --http: //www.codechef.com/FEB11/problems/THREECLR/)

Below is my code

import java.io.*; import java.util.*; public class Main { static String ReadLn (int maxLg) // utility function to read from stdin { byte lin[] = new byte [maxLg]; int lg = 0, car = -1; String line = ""; try { while (lg < maxLg) { car = System.in.read(); if ((car < 0) || (car == '\n')) break; lin [lg++] += car; } } catch (IOException e) { return (null); } if ((car < 0) && (lg == 0)) return (null); // eof return (new String (lin, 0, lg)); } public static boolean iscontains(HashMap<Integer,HashSet<Integer>> resultmap,HashSet<Integer> b, int index) { boolean result=false; for(Iterator<Integer> iter = b.iterator();iter.hasNext();) { int tmp=Integer.valueOf(iter.next().toString()); if(resultmap.get(index).contains(tmp)) result=true; } return result; } public static void main(String[] args) throws InterruptedException, FileNotFoundException { try { HashMap<Integer,HashSet<Integer>> pairlist = new HashMap<Integer,HashSet<Integer>>(); String input=null; StringTokenizer idata; int tc=0; input=Main.ReadLn(255); tc=Integer.parseInt(input); while(--tc>=0) { input=Main.ReadLn(255); idata = new StringTokenizer (input);idata = new StringTokenizer (input); int dishnum= Integer.parseInt(idata.nextToken()); int pairnum= Integer.parseInt(idata.nextToken()); while (--pairnum>=0) { input=Main.ReadLn(255); idata = new StringTokenizer (input);idata = new StringTokenizer (input); int dish1=Integer.parseInt(idata.nextToken()); int dish2=Integer.parseInt(idata.nextToken()); if(pairlist.containsKey((Integer)dish1)) { HashSet<Integer> dishes=new HashSet<Integer>(); dishes=pairlist.get(dish1); dishes.add(dish2); pairlist.put(dish1, dishes); } else { HashSet<Integer> dishes=new HashSet<Integer>(); dishes.add(dish2); pairlist.put(dish1, dishes); } } int maxrounds=1; HashMap<Integer,HashSet<Integer>> resultlist = new HashMap<Integer,HashSet<Integer>>(); HashSet<Integer> addresult=new HashSet<Integer>(); addresult.add(1); resultlist.put(1,addresult); System.out.print("1"); for(int i=2;i<=dishnum;i++) { boolean found_one=false; boolean second_check=false; int minroundnum=maxrounds; boolean pairlistcontains=false; pairlistcontains=pairlist.containsKey(i); for(int j=maxrounds;j>=1;j--) { if(!found_one){ if(pairlistcontains) { if(!iscontains(resultlist,pairlist.get((Integer) i),j)) { for(Iterator<Integer> resultiter = resultlist.get(j).iterator();resultiter.hasNext();) { if(pairlist.get(resultiter.next()).contains(i)) second_check=true; } if(second_check==false) { found_one=true; minroundnum=j; j=0; //second_check=false; } } } else { for(Iterator<Integer> resultiter = resultlist.get(j).iterator();resultiter.hasNext();) { if(pairlist.get(resultiter.next()).contains(i)) second_check=true; } if(second_check==false) { found_one=true; minroundnum=j; j=0; //second_check=false; } } second_check=false; } } if((minroundnum==maxrounds)&&(found_one==false)) { ++minroundnum; ++maxrounds; } else { found_one=false; } HashSet<Integer> add2list=new HashSet<Integer> (); if(resultlist.containsKey(minroundnum)) { add2list=resultlist.get(minroundnum); add2list.add(i); } else { add2list.add(i); } resultlist.put(minroundnum,add2list); System.out.print(" "); System.out.print(minroundnum); } if((tc !=-1)) System.out.println(); } } catch(Exception e){System.out.println(e.toString());} }} 

I tested this code on online judges like Ideone and got the desired results. But when I submit this code, I get time limit exceeded. I tested this code on Ideone with a fairly large set of input data, and the time taken to execute was less than 1 second. He seems to have a mistake or a memory leak that seems to have drained all the happiness from my life. Any pointers / hints would be greatly appreciated.

thanks

EDIT1 -

Thanks for the answers guys, I ran the code with the input generated by the following python script -

 import random filename="input.txt" file=open(filename,'w') file.write("50") file.write("\n") for i in range(0,50): file.write("500 10000") file.write("\n") for j in range(0,10000): file.write(str(random.randrange(1,501))+" "+str(random.randrange(1,501))) file.write("\n") file.close() 

And my code took a whopping 71052 milliseconds to execute on the input provided by the above script. Now I have to reduce the execution time to 8000 milliseconds. I am working on checking the replacement of HashMaps and HashSets, as suggested by rfeak, and I am also wondering if memoization will help in this scenario. Please inform.

EDIT2 - It seems that recoding my algorithm using arrays has worked. Only when I repeated the same code at different times I got a valid solution and time limit: D I have another way to use hash maps to optimize a bit further. Thanks for helping the guys!

Answer 1

How much memory does your program use when running locally?

If they run your Java program without enough memory, you can spend a lot of time collecting garbage. This can destroy your 1 second.

If you need to save time and memory (to determine ...), I have 2 suggestions.

Replace HashSet<Integer> with BitSet . A similar interface, a much faster implementation, and uses much less memory. Especially with the numbers that I see in the problem.

Replace Map<Integer,X> with X[] - the Integer key may just be the int index (primitive) in your array. Again, faster and smaller.