902 - Password Search

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Oct 28, 2006 2:11 pm

thank you, Jan.

it helped me kill the bug and i got AC!

----
sory for my poor english

sapropel
New poster
Posts: 4
Joined: Wed Nov 22, 2006 2:26 pm

Post by sapropel » Wed Nov 22, 2006 2:32 pm

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
Last edited by sapropel on Wed Nov 22, 2006 3:21 pm, edited 1 time in total.

sapropel
New poster
Posts: 4
Joined: Wed Nov 22, 2006 2:26 pm

Post by sapropel » Wed Nov 22, 2006 2:45 pm

"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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Nov 22, 2006 5:21 pm

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.
Ami ekhono shopno dekhi...
HomePage

sapropel
New poster
Posts: 4
Joined: Wed Nov 22, 2006 2:26 pm

Post by sapropel » Fri Nov 24, 2006 2:21 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Nov 24, 2006 8:24 pm

I used manual hashing, but I dont know whether stl hashtable will work or not.
Ami ekhono shopno dekhi...
HomePage

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Nov 24, 2006 10:06 pm

sapropel wrote: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
New poster
Posts: 4
Joined: Wed Nov 22, 2006 2:26 pm

Post by sapropel » Sat Nov 25, 2006 9:04 pm

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
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sat Dec 02, 2006 5:39 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Dec 03, 2006 2:21 am

jan_holmes wrote: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.
Ami ekhono shopno dekhi...
HomePage

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Mon Dec 04, 2006 8:35 am

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;
}


Time that gone is gone forever ...

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Mon Dec 04, 2006 9:06 am

to sakhassan :
your "char str[N]" may be too small to read input ,
I guess the reason should be that 8)
studying @ ntu csie

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Mon Dec 04, 2006 1:06 pm

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Dec 04, 2006 1:10 pm

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

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Mon Dec 04, 2006 4:50 pm

still no clue!!!!!!!!!! :oops: :( :( :( still RTE
Time that gone is gone forever ...

Post Reply

Return to “Volume 9 (900-999)”