Превышен лимит времени проблемы с Java ⇐ JAVA

[Anonymous]

Я кодирую проблему (ссылка --http://www.codechef.com/FEB11/problems/THREECLR/)

Ниже приведен мой код р>

Код: Выделить всё

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 resultmap,HashSet b, int index)
{
boolean result=false;
for(Iterator 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 pairlist = new HashMap();
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 dishes=new HashSet();
dishes=pairlist.get(dish1);
dishes.add(dish2);
pairlist.put(dish1, dishes);
}
else
{
HashSet dishes=new HashSet();
dishes.add(dish2);
pairlist.put(dish1, dishes);
}
}
int maxrounds=1;
HashMap resultlist = new HashMap();
HashSet addresult=new HashSet();
addresult.add(1);
resultlist.put(1,addresult);
System.out.print("1");
for(int i=2;i=1;j--)
{
if(!found_one){
if(pairlistcontains)
{
if(!iscontains(resultlist,pairlist.get((Integer) i),j))
{
for(Iterator 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 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 add2list=new HashSet ();
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());}
}}

Я проверил этот код на онлайн-судьях, таких как Ideone, и получил желаемые результаты. Но когда я отправляю этот код, я получаю сообщение об ошибке превышения лимита времени. Я протестировал этот код на Ideone с достаточно большим набором входных данных, и время выполнения составило менее 1 секунды. Кажется, в нем есть ошибка или утечка памяти, которая, кажется, лишила меня всего счастья из моей жизни.
Буду очень признателен за любые подсказки/советы.

Спасибо

EDIT1 --

Спасибо за ответы, ребята, я запустил код с входными данными, сгенерированными следующий скрипт Python --

Код: Выделить всё

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()

И мой код потребовал целых 71052 миллисекунды для выполнения входных данных, предоставленных приведенным выше сценарием. Теперь мне нужно сократить время выполнения как минимум до 8000 миллисекунд.
Я работаю над заменой HashMaps и HashSets, как предложено rfeak, и мне также интересно, поможет ли мемоизация в этом сценарии. Пожалуйста, посоветуйте.

EDIT2 --
Перекодирование моего алгоритма с использованием массивов, похоже, сработало. Только повторная отправка одного и того же кода в разное время приводит к тому, что я принял решение и лимит времени превышен У меня есть другой способ использовать хэш-карты для дальнейшей оптимизации.
Большое спасибо за помощь, ребята!

Подробнее здесь: https://stackoverflow.com/questions/490 ... eded-issue