memeset's blog

My recursion is wrong somehow? (Round 387 div2E)
By memeset, history, 8 years ago, In English

Hi all,

Could someone please look at my code to this problem? Its a simple dfs with an extra iterating variable, but I'm confused as to why it's returning wrong answer. I'm 90% sure that the string processing part of my code is correct, so that leaves the dfs() function that probably has a bug in it.

vector< string > height[] is the array that I use to store the strings that are on a certain level, and I use vector< int > comma to store the position of the commas to make it easier to extract the numbers and the strings. Also, mx is the maximum height of a comment.

Thanks for your time everyone!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

http://codeforces.me/contest/747/submission/23130844.

U r welcome

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hey memeset your recursion is fine, the problem is in pow function you use to calculate number of children of string.Its double precision makes calculation incorrect. Here is your AC code -> 23130965

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Ah, I didn't know that the default return value of pow() is double. Thanks for telling me that, I'll be sure to keep that in mind!

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody look at my code and tell why it gives memory limit exceeded verdict?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try making your array size 500000 or even 250000 because each string will have at least 4 characters: string, number, and 2 commas.

    → Reply