Colossus20's blog

373C / 372A — Counting Kangaroos is Fun

By Colossus20, history, 4 years ago, In English

Hi!

I was solving this Counting Kangaroos is Fun problem, but after trying a (wrong) greedy aproach I read the editorial. However, I don't get it yet. Why can we assume that the first half of kangaroos do not hold any kangaroos, and last half of kangaroos are not held by any kangaroos ? And how should be assigned the kangaroos?

Any help will be apreciated.

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

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

we match first half with second half to make a big gap between kangaroos and select more of them. assume this example :2 2 3 5 5 10 we can select 10 with 5 and 5 with 2 but we cant select 3 with 2 because we reduce big differnecs but we can select them using two half algorithm .

hope it will__

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

I think key observation is, that if there is a perfect match with maximum possible number of pairs, then it is exactly the one where the upper half puts one of the lower half into its pocket.

→ Reply