902  Password Search
Moderator: Board moderators
902  Password Search
I was going to write "gripe about 902", but that was taken already
First of all  input does not follow the specification, number and string don't have to be on the same line. I think I figured out how to read it properly, but it's TLE now.
I optimized my Java code as much as I could short of fiddling with I/O, but I/O alone is just 0.7 secs, shouldn't make that much of a difference.
This is what I do (n  number given (<=10), slen  length of the string):
 read string into an array (O(n))
 sort pointers to substrings (O(n*slen*log(slen)) < bad?
 go through list of pointers and find the longest repeating sequence (O(n*slen))
I guess my algorithm is too slow, I am not sure what to do to speed things up. I was going to do it in C, but that would involve some learning on my part (strings, sorting,...), so I am trying to avoid it
If it can be done without sorting, please let me know. Oh, I did try using Hashtable, but it gives me MLE  it is just too expensive to use (on UVa, at least).
First of all  input does not follow the specification, number and string don't have to be on the same line. I think I figured out how to read it properly, but it's TLE now.
I optimized my Java code as much as I could short of fiddling with I/O, but I/O alone is just 0.7 secs, shouldn't make that much of a difference.
This is what I do (n  number given (<=10), slen  length of the string):
 read string into an array (O(n))
 sort pointers to substrings (O(n*slen*log(slen)) < bad?
 go through list of pointers and find the longest repeating sequence (O(n*slen))
I guess my algorithm is too slow, I am not sure what to do to speed things up. I was going to do it in C, but that would involve some learning on my part (strings, sorting,...), so I am trying to avoid it
If it can be done without sorting, please let me know. Oh, I did try using Hashtable, but it gives me MLE  it is just too expensive to use (on UVa, at least).
Re: 902 Password Search
I think your implementation of Hashtable is wrong.Darko wrote: Oh, I did try using Hashtable, but it gives me MLE  it is just too expensive to use (on UVa, at least).
I have use Hashtable too.. and it give me AC
"Life is more beautiful with algorithm"
I think your first two cases are wrong. Because then there would be a special judge for the problem.
The third case is also wrong, since you cant find a 10 letter password from a string with just one letter.
You can assume that 'N' is less than or equal to the length of the given string and there is always a unique password.
And for the final case the output is obviously 'a'.
The third case is also wrong, since you cant find a 10 letter password from a string with just one letter.
You can assume that 'N' is less than or equal to the length of the given string and there is always a unique password.
And for the final case the output is obviously 'a'.
Ami ekhono shopno dekhi...
HomePage
HomePage

 New poster
 Posts: 12
 Joined: Tue Sep 12, 2006 6:54 pm
Re: 902 Password Search
I used Rabin Karp method for hashing but it gave me a WATimo wrote: I think your implementation of Hashtable is wrong.
I have use Hashtable too.. and it give me AC
what is your method?

 New poster
 Posts: 12
 Joined: Tue Sep 12, 2006 6:54 pm

 New poster
 Posts: 12
 Joined: Tue Sep 12, 2006 6:54 pm
Re: 902 Password Search
sorry for late reply...StanleY Yelnats wrote:I used Rabin Karp method for hashing but it gave me a WATimo wrote: I think your implementation of Hashtable is wrong.
I have use Hashtable too.. and it give me AC
what is your method?
I used my own method to solve this problem ^ ^ (that's secret), but if you have used Rabin Karp it should give AC, maybe your implementation is wrong or there is a part of your code has wrong (maybe little mistake).
"Life is more beautiful with algorithm"
There are no special cases. Try the following i/o set...
Input:
Output:
Hope it helps.
Input:
Code: Select all
1 thequickbrownfoxjumpsoverthelazydog
3 thequickbrownfoxjumpsoverthelazydog
4 testingthecodetofindtheerrortestandtestagain
5 thearraycanbetoobigsobecarefulandtherecantberarecasescanbe
Code: Select all
o
the
test
canbe
Ami ekhono shopno dekhi...
HomePage
HomePage