6 replies to this topic

[XAW]

Hi. I'm trying to do Sphere Online Judge (SPOJ) - Problem DICTSUB

But I'm getting timeout..So i need to speed up my algorithm. How improve my code or write new better code?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

	public static void main (String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int cases=0;
		int cases2=0;
		String slowo=" ";
		String word=" ";
		int p=0;
		cases=Integer.parseInt(br.readLine());
		for(int i=0; i<cases; i++) {
			if(slowo!=null && slowo.length()>0) {
			slowo=br.readLine();
			p=slowo.indexOf(" ");
			cases2=Integer.parseInt(slowo.substring(0,p));
			word=slowo.substring(p+1);
			for(int k=0; k<cases2; k++) {
			slowo=br.readLine();
			slowo=decode(slowo);
			int pom=0;
			int x=0;
			while(pom!=-1 && x<slowo.length()) {	
				pom=word.indexOf(slowo.charAt(x),pom);
				x++;
			}
			if(pom!=-1) System.out.println("YES");
			else System.out.println("NO");
			
			}
			}
		System.out.print("\r");
		}
	}
	
	public static String decode(String W) {
		char[] array=W.toCharArray();
		StringBuilder ret=new StringBuilder("");
		int pom=0;
		for(int i=0; i<array.length; i++)
			if(i%2==0) pom=array[i];
			else for(int k=0; k<pom; k++) ret.append(array[i]);
		return ret.toString();
	}
	
}

[Norm]

One way to seed up the code is not to read from System.in. Users are too slow entering data.

Have you tried profiling the execution of the code to see where it is spending the time? Use the java -Xprof option.

[lethalwire]

One way to seed up the code is not to read from System.in. Users are too slow entering data.

Have you tried profiling the execution of the code to see where it is spending the time? Use the java -Xprof option.

A server will probably be feeding input to standardin.

[gregwarner]

I would suggest you speed up your code by specifying the initial capacity of the StringBuilder in your 'decode' method.

The constructor StringBuilder(String str) allocates an array that is 16 plus the length of 'str' characters long. Each time you append more characters than it can hold, StringBuilder has to allocate a whole new array in memory and copy the contents over. This can be very slow. If you know ahead of time the maximum length of each string you're going to be building, you can specify this when creating the StringBuilder:

new StringBuilder(1024); // Creates a StringBuilder with an initial capacity of 1024.

This way, you can append up to 1024 characters onto this StringBuilder and it will be very fast, because it doesn't have to bother with multiple reallocations and copies every time the buffer fills up.

[Norm]

Cross posted at: http://www.java-foru...-algorithm.html

[Norm]

You need to debug your code to see what it is doing. Add some printlns to print out the values of the variables as they are given values and used The print out will show you where the problems are.

[thechef]

I'd say 99% of timeout errors are due to an insufficient algorithm not subtleties in the code. To speed this up, you need to look at your while loop. It looks at every single letter of word "T" for every word "W", making it an order N-squared algorithm. Think about parsing word "T" into a tree structure that alphabetizes its nodes. Then, for each letter in word "W", you can easily find if the letter is in "T". Here is an example for a T of "AARDVARK":

A -> A -> A -> K
A -> A -> A -> R
A -> A -> D ...
A -> A -> K ...
A -> A -> R ...
A -> A -> V ...
A -> D -> A ...
A -> D -> K
A -> D -> R ...
A -> D -> V ...
A -> K
A -> R ...
A -> V ...

I'll let you fill in the rest. Now, finding a letter is order log(N) because the letters are ordered, and your algorithm takes almost half as much time.

I hope that makes sense, and happy coding!