902 - Password Search

[Darko]

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]

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

[Darko]

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]

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]

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

[DJWS]

Hi.
Could anyone help check the output of these cases?

2 ababcdcd
2 cdcdabab
10 a
1 a

--
DJWS, a newbie in programming

[Jan]

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

[StanleY Yelnats]

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]

It can be solved with a simple qsort.

[StanleY Yelnats]

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

n = string lenght
m = password lenght

[Emilio]

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]

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

my mistake!

[Timo]

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

[rio]

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]

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.