ManikantanV's blog

By ManikantanV, history, 5 years ago, In English

Hi,

I tried to solve the problem by creating a 10 — character hash code for every pokemon for every gym in which it appears and then appending all hash codes for every type of pokemon.

The hash code format is : Gym Number(padded to 5 digits) + Number of occurrences in given gym(padded to 5 digits)

I decided on 5 digits for each part since max. value is 100000, which can be rolled back to 00000.

The hash codes are entered into a trie for processing. The trie is implemented using node pointer with 10 child nodes, representing each of the digits.

The expected memory complexity of my solution is — O(Total number of pokemons * 10)

Since total number of pokemons is at max 5*10^5 , memory used is at most around 5 * 10^6.

Is this a large enough memory consumption to cause runtime error?

Thanks in advance

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is this your latest code : http://codeforces.com/contest/757/submission/23781814 ?

If it is, from little understanding of your code I think your array of strings is too big. If each string of your code is 1 character long (1 byte) we'll have 10^6 bytes, which is 1 MByte. Think if the entire code stores more than 256 characters your code is done.

Maybe I'm wrong, check it out! :-)

Also, the code break just when the test case uses the maximum value of m, so check every other aspect that m can interfere.