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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

902 - Password Search

Post by Darko » Sat Sep 30, 2006 7:17 am

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).

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Re: 902 Password Search

Post by Timo » Sat Sep 30, 2006 9:11 am

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 think your implementation of Hashtable is wrong.
I have use Hashtable too.. and it give me AC
"Life is more beautiful with algorithm"

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sat Sep 30, 2006 9:27 am

I used java.util.Hashtable, I don't have my own.

So, that's the only way to solve it? I guess I'll have to reinvent yet another wheel :(

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » Sat Sep 30, 2006 11:31 am

think about hashing so you can get rid of slen constant :: "To simplify things, you can assume that the text only includes lower case letters."

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Sat Sep 30, 2006 3:01 pm

Darko wrote:I used java.util.Hashtable, I don't have my own.

So, that's the only way to solve it? I guess I'll have to reinvent yet another wheel :(
don't store the substring in the hashtable, just store the value....

26^10 < 10^18

I hope you understand....


:D
"Life is more beautiful with algorithm"

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » Mon Oct 02, 2006 6:09 am

Hi.
Could anyone help check the output of these cases?
2 ababcdcd
2 cdcdabab
10 a
1 a
--
DJWS, a newbie in programming :wink:

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

Post by Jan » Mon Oct 02, 2006 12:41 pm

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

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

Re: 902 Password Search

Post by StanleY Yelnats » Sat Oct 07, 2006 4:14 pm

Timo wrote: I think your implementation of Hashtable is wrong.
I have use Hashtable too.. and it give me AC
I used Rabin Karp method for hashing but it gave me a WA
what is your method?

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Oct 09, 2006 2:08 pm

It can be solved with a simple qsort.

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

Post by StanleY Yelnats » Tue Oct 10, 2006 9:45 pm

well with a qsort you will have m*n element which results in O((mn)log(mn))

n = string lenght
m = password lenght

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Wed Oct 11, 2006 11:56 pm

No, you will have n elements O((n)log(n)).
Exactly n-m+1 elements.
Each element can be of m as lenght, or you can solve it with only an array of chars and another array of char pointers.

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

Post by StanleY Yelnats » Thu Oct 12, 2006 10:03 am

Emilio wrote:No, you will have n elements O((n)log(n)).
Exactly n-m+1 elements.
Each element can be of m as lenght, or you can solve it with only an array of chars and another array of char pointers.
you're absolutely right :wink:

my mistake! :oops:

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Re: 902 Password Search

Post by Timo » Wed Oct 18, 2006 5:46 am

StanleY Yelnats wrote:
Timo wrote: I think your implementation of Hashtable is wrong.
I have use Hashtable too.. and it give me AC
I used Rabin Karp method for hashing but it gave me a WA
what is your method?
sorry for late reply...

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"

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 12:59 pm

is there any tricky input? i can't get AC..
some i/o will help me.

thanks in advance.

---
sory for my poor english

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

Post by Jan » Sat Oct 28, 2006 2:02 pm

There are no special cases. Try the following i/o set...
Input:

Code: Select all

1 thequickbrownfoxjumpsoverthelazydog
3 thequickbrownfoxjumpsoverthelazydog
4 testingthecodetofindtheerrortestandtestagain
5 thearraycanbetoobigsobecarefulandtherecantberarecasescanbe
Output:

Code: Select all

o
the
test
canbe
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 9 (900-999)”