902 - Password Search

[rio]

thank you, Jan.

it helped me kill the bug and i got AC!

----
sory for my poor english

[sapropel]

i dont know if this is the right thread to post this issue, but i couldnt find a better one: ive tried to submit the code (in c++) for this problem, thing is it gives me a compile error! ive tried 4 times already, and i havent received an email with the g++ output error messages.

on my pc, ive compiled it with visual studio 2005, gcc 4.0 and with Comeau C++ compiler (there isnt a more standard one than that) with 0 errors/warnings.

this ever happened to anyone? and yes, ive choosen "C++" on the input form, and my ID is correct. ive tried by pasting the code into the form and by uploading the .cpp file.

:\


EDIT:
ok, i think i got the problem fixed, i wasnt uploading the updated code, which only difference is that it contains:

#include <utility>

so gcc can use std::pair, funny thing is that visual studio and comeau compile fine without that include.
sorry about this

[sapropel]

"time limit exceded"

what im doing is quite simple: a binary search tree where each node has a string (possible password) and the number of times that string shows up on the input string, a simple example would be:

Code: Select all

string: "mmedpnmm"   password size: 2

         mm:2
         /  \
       me:1 pn:1
       /   /
     ed:1 nm:1
        \
       dp:1

(each integer after string is the # times that string exists)

why using a binary tree? so i dont have to go through all the array to check if the password has been given before.

to get the most used string (which is the password) ill juts go trough the entire tree and find the string with the biggest count.

im assuming that all the lines of the input file have: "integer string" with a white space between them.

any ideias why im getting time limit excedded?
thx

edit: btw the program displays correctly the jan example

[Jan]

I think your complexity is O(n*log(n)). n can be as large as 1000000. Then it would be tough to finish it in 10 seconds.

[sapropel]

so i tried again today to solve this problem (# 902), but this time using an hashtable, by using the its_taking_forever_to_be_standard STL hash_map. the implementation is simple:

for every sub-string of size( input password size ):
try to find the sub-string on the hashtable.
found it? add 1 to its valor
didnt find it? add new key (sub-string) = 1 (becase that sub-string has appeared only once yet).

if the key was found, check if its valor its bigger then the biggest valor found so far, if it is, save the key on a string so i have immediate access to it when asking for the most used sub string.

i hope you can understand this pseudo-pseudo-pseudo-code.
i can post the source here, its quite simple and not that big (about 74 lines of code, but with lots of '{' and '}' alone on a line).

still.. im getting TLE
this is getting really frustrating, i guess i really have to improve my optimizations skills.
any tips are (extremally) welcome =)

thx

[Jan]

I used manual hashing, but I dont know whether stl hashtable will work or not.

[sclo]

so i tried again today to solve this problem (# 902), but this time using an hashtable, by using the its_taking_forever_to_be_standard STL hash_map. the implementation is simple:

for every sub-string of size( input password size ):
try to find the sub-string on the hashtable.
found it? add 1 to its valor
didnt find it? add new key (sub-string) = 1 (becase that sub-string has appeared only once yet).

if the key was found, check if its valor its bigger then the biggest valor found so far, if it is, save the key on a string so i have immediate access to it when asking for the most used sub string.

i hope you can understand this pseudo-pseudo-pseudo-code.
i can post the source here, its quite simple and not that big (about 74 lines of code, but with lots of '{' and '}' alone on a line).

still.. im getting TLE
this is getting really frustrating, i guess i really have to improve my optimizations skills.
any tips are (extremally) welcome =)

thx

I think that STL hash_map with string will be too slow, so why don't you try hashing with long long by treating the substrings as a k digits base 26 integer? You will need to create a hash function in order to do that, try to learn how to do it. The most obvious hash function works here. If you need help, pm me.
Try to get it to work with O(1) operation per substring, so that the overall complexity is O(n). If you do hash on the substrings directly, in that case then stl has predefined hash functions for it, then the overall complexity can't be any better than O(kn) where k is the length of the string.
My entire code is less than 30 lines, and even my O(n) solution takes 3.891 secs on the judge. So the the O(kn) of yours will TLE for sure.

[sapropel]

so i went and read on hash functions, i can say i learned a lot on this subject.
i ended up using Jenkins One-at-a-time hash method as seen on wikipedia, and it does the job.

i finally got AC! it is taking 7.412 seconds which is quite a lot, but at least i got AC (ill try to improve it later).

thanks a lot for the tips, you were a great help =D

[jan_holmes]

I got WA with this code, please help :

Code: Select all

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

//WA...
// UVA problem 902

class Main {
	public static void main (String[] args ) {
		Main m = new Main();
		m.process();
	}
	static void process() {
		String input = "";
		StringTokenizer token;
		int n;
		String w = "";
		int ret = 0;
		String res = "";
		int tt1 = 0;
		Hashtable num = new Hashtable();
		while ((input = readLn(255)) != null) {
			num.clear();
			res = "";
			ret =  0;
			token = new StringTokenizer(input);
			n = Integer.parseInt(token.nextToken());
			w = String.valueOf(token.nextToken());
			int len = w.length();
			for (int i=0;i<len;i++) {
				if (i+n > len) break;
				String temp = w.substring(i,i+n);
				//System.out.println(temp);
				Object ii = num.get(temp);
				Integer tt = new Integer(0);
				if (ii != null) tt = (Integer) ii;
				tt1 = Integer.parseInt(String.valueOf(tt));
				tt1++;
				num.put(new String(temp),new Integer(tt1));
				/*if (tt1 == ret) {
					if (temp.compareTo(res) < 0) {
						res = temp;
					}
				}*/
				if (tt1 > ret) {
					ret = tt1;
					res = temp;
				}
			}
			//System.out.println(num.size());
			System.out.println(res);
		}
	}
	static String readLn( int maxLg ) { 
        
        byte lin[] = new byte[ maxLg ]; 
        int lg = 0; 
        int 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; 
        
        return new String ( lin, 0, lg ); 
        
    } 

}

And how about if there are 2 or more substrings with the same length ? which one should we choose ?

[Jan]

And how about if there are 2 or more substrings with the same length ? which one should we choose ?

This question is answred already. Try reading previous posts.

[sakhassan]

I am getting RTE ... Is ma method wrong???

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 100
#define M 10001

char hash[M][N];
int cmp( const char *a, const char *b)
{

	return ( strcmp(a,b) );
}

int main()
{


   int n;
   int i,j,k;
   char str[N];
   int len;
   int count;
   int max,num;

   while(scanf("%d%s",&n,str)==2)
   {

	memset(hash,'\0',sizeof(hash));

	len = strlen(str);
	count=0;
	for(i=0;i<=len-n;i++)
	{
	      for(j=i,k=0;k<n;j++,k++)
	      {
		 hash[count][k]=str[j];

	      }
	      hash[count][k]='\0';
	      count++;
	}

	qsort(hash,count,sizeof(hash[0]),(int(*)(const void *, const void *))cmp);
	max = 0;
	strcpy(str,"");
	for(i=0;i<count;i++)
	{
	    num=1;
	    while(strcmp(hash[i],hash[i+1])==0 && i<count)
	    {
		   num++;
		   i++;
	    }
	    if(num>max)
	    {
		strcpy(str,hash[i]);
		max = num;
	    }

	}

	printf("%s\n",str);

   }

   return 0;
}

[SRX]

to sakhassan :
your "char str[N]" may be too small to read input ,
I guess the reason should be that

[sakhassan]

i have increase N up to 1000.... still RTE ( signal 11)
what does signal 11 means ??? is it some kind of alert ???

[Jan]

What if the given string has more than 1000 characters? Use str[1000000]. And better to declare large arrays globally. Hope it helps.

[sakhassan]

still no clue!!!!!!!!!! still RTE