TurtleShip's blog

My solutions to CROC Qualification Round
By TurtleShip, 12 years ago, In English

Hi,

I posted my solutions to all 5 problems with explanations in my blog http://sk765.blogspot.com/2012/04/croc-champ-2012-qualification-round.html

I tried to upload the content in codeforces blog, but I failed.

I wrote the editorial so that I can better understand problems I solved and possibly receive feedbacks on my approach. And it would be great if anybody could benefit from my blog.

Please feel free to give me feedbacks.

Have an awesome day :-)

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

»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Long longs were not needed in C. The answers (barely) fit in an int. Also, in E, it is actually not needed to create the tree data structure, it suffices to think that we are traversing the tree while parsing the input (because the input is given in the order in which we would traverse the tree anyway). We only need to maintain a current stack of tags (and, for every tag, the indexes i of the solved[i] that we will need to decrement when we close that tag).

In absence of an editorial, it's very good that you wrote this post, I'm sure that some coders will find it useful :)

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

    Thank you for your tips. Somehow I thought the max value for int was 2 * 10^9. Now I know the max value for int is 2,147,483,647, so the answer does fit into int as you said :-)

    And you are absolutely right about E. As a matter of fact, using tree structure slows down the program a bit. In other words, the approach you mentioned is faster. I used the tree structure because it was the approach I tried to use during the contest.

    Thanks for your tips. I will update my blog accordingly :-)

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

I have a more simple and faster solution for D (280 ms for 1 10000000)

1479055

→ Reply