इम एक समस्या कोडिंग पार कर (संदर्भ --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<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());}
}}
मैंने इस कोड को आइडोन जैसे ऑनलाइन न्यायाधीशों पर चेक किया है और वांछित परिणाम प्राप्त कर रहे हैं। लेकिन जब मैं यह कोड जमा करता हूं, तो मुझे टाइम सीमा से अधिक त्रुटि मिलती है। मैंने इनपुट पर पर्याप्त रूप से बड़े सेट के साथ इस कोड का परीक्षण किया है और निष्पादित करने के लिए लिया गया समय 1 सेकंड से कम था। ऐसा लगता है कि एक बग या मेमोरी लीक है जो मेरे जीवन से सारी खुशी को मिटा देती है। किसी भी पॉइंटर्स/टिप्स की सराहना की जाएगी।
धन्यवाद
EDIT1 -
उत्तर लोगों के लिए धन्यवाद, मैं निम्नलिखित अजगर स्क्रिप्ट द्वारा उत्पन्न इनपुट के साथ कोड दौड़ा -
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()
और मेरे कोड एक whopping ले लिया उपरोक्त स्क्रिप्ट द्वारा प्रदान किए गए इनपुट पर निष्पादित करने के लिए 71052 मिलीसेकंड। मुझे अब कम से कम 8000 मिलीसेकंड तक निष्पादन समय कम करना होगा। मैं रैफक द्वारा सुझाए गए हैश मैप्स और हैशसेट्स को बदलने की कोशिश करने पर काम कर रहा हूं और यह भी सोच रहा हूं कि इस परिदृश्य में ज्ञापन मदद करेगा या नहीं। कृपया सलाह दें।
EDIT2 - मेरी algo सरणियों का उपयोग कर recoding काम किया है लगता है। केवल तभी, अलग-अलग समय पर एक ही कोड को पुनः सबमिट करने से मुझे स्वीकार्य समाधान मिलता है और समय सीमा पार हो जाती है: डी मेरे पास हैशैप्स का उपयोग करने के लिए एक और तरीका है जो थोड़ा आगे अनुकूलित करने के लिए है। धन्यवाद दोस्तों के लिए एक लोड धन्यवाद!
क्या आपने माना है कि वे इसे बहुत बड़ा इनपुट खिला रहे हैं और आपके कोड को संसाधित करने में बहुत लंबा समय लगता है? –
क्या आप जानते हैं कि वे डेटासेट कितना बड़ा सबमिट कर रहे हैं? क्या आप उस डेटा सेट को रोक सकते हैं? –
मेरा अनुमान है कि आप ऐसे इनपुट की अपेक्षा कर रहे हैं जो ऐसा नहीं होता है या कोई इनपुट होता है जो आपके प्रोग्राम को अनंत लूप में जाने का कारण बनता है। –