11855 - Buzzwords

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

Moderator: Board moderators

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

11855 - Buzzwords

Post by Angeh » Mon Oct 04, 2010 5:08 am

why is the First Input
5
4
4
2
2

???

Edit :
GOT AC ... in 0.9
The Test Cases Are Wrong ...
But How to get AC in Less Time ... ???
I Used Trie !! counted the max of each Level .... 26 * N(N-1)/2
is There Any other solution ?????
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11855 - Buzzwords

Post by Igor9669 » Mon Oct 04, 2010 10:45 am

I use hash in my solution!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11855 - Buzzwords

Post by Angeh » Mon Oct 04, 2010 12:59 pm

Hi ,Igor ...
0.536 is Good Time
do you hash all n(n-1)/2 strings ?
Then How do you Hash them whats your Function for hashig ... ?
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11855 - Buzzwords

Post by Igor9669 » Mon Oct 04, 2010 1:27 pm

Yes!

Code: Select all

long long getHash(string s)
{
const int p = 31;
long long hash = 0, p_pow = 1;
for (int i=0; i<s.length(); ++i)
{
	hash += (s[i] - 'a' + 1) * p_pow;
	p_pow *= p;
}
return hash;
}

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11855 - Buzzwords

Post by Angeh » Mon Oct 04, 2010 1:36 pm

wouldn't long long overflow for strings of size = 999 ?
31^999 ??
Does your Code Work for Case:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
?
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11855 - Buzzwords

Post by Igor9669 » Mon Oct 04, 2010 2:36 pm

Of cousre it will,but this is not a problem it works like you get it by module!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11855 - Buzzwords

Post by Angeh » Mon Oct 04, 2010 2:41 pm

I have Got AC this Problem ...
so would you please send me your code
angeh.a2@gmail.com
i Just want to learn more from your code implementation
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11855 - Buzzwords

Post by Igor9669 » Mon Oct 04, 2010 2:44 pm

Sorry,but I don't save the codes of Ac problems in my computer((

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11855 - Buzzwords

Post by Igor9669 » Mon Oct 04, 2010 2:52 pm

But I could explain my idea here if you want???

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11855 - Buzzwords

Post by Angeh » Mon Oct 04, 2010 3:12 pm

ok no problem ...
i have Tried what you said ...
but i Get Runtime Error ...
is your Code Somthing like this .... ?

Code: Select all

maxes[ k ] is the most repete of string lenght k ...
        map<long long ,int> MAP;
        long long P=31;
        FOR(i,n){
            long long Hash=0,Pow=1;
            for(int j=i;j<n;++i){
                Hash += (line[j]-'A'+1)*Pow;
                MAP[Hash]++;
                maxes[j-i]<MAP[Hash] ? maxes[j-i]=MAP[Hash] :0 ;
                Pow*=P;                
            }
        }
printf out put .... 
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11855 - Buzzwords

Post by Igor9669 » Mon Oct 04, 2010 3:14 pm

Yes,it was something likes yours!
try to increase the size of array m!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11855 - Buzzwords

Post by Angeh » Mon Oct 04, 2010 3:22 pm

Igor9669 wrote:Yes,it was something likes yours!
try to increase the size of array m!
Array m ?????
do you use STL map to save the Hashes ?
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11855 - Buzzwords

Post by Igor9669 » Mon Oct 04, 2010 3:24 pm

sorry,maxes I mean!
No I don't use map!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11855 - Buzzwords

Post by Angeh » Mon Oct 04, 2010 3:27 pm

thanks for your help and sorry for this much Question ...
but if you dont use map , how do save the Hashes ???
i'm confused :(
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11855 - Buzzwords

Post by Igor9669 » Mon Oct 04, 2010 3:29 pm

)) map is also a good choice, but I use an array with type of pair<long long,int>!

Post Reply

Return to “Volume 118 (11800-11899)”