MohamedHamada_'s blog

Need help in SnackDown Online Pre-Elimination Round B , problem C
By MohamedHamada_, history, 8 years ago, In English

i tried to solve this problem in the contest time but it gave me a WA . today i try to understand why my answer is wrong .i used an accepted code and try some test cases ... one of them was :

so it locks like :

and the the fences should (i think) be like :

so my answer is 5 ... but the Accepted code output is 3 !

i can't understand how to but only 3 fences to prevent the snakes communicate with each other . can any one explain this problem to me ?

thanks in advance .

UPD: the optimal solution for the above sample :

Thanks :)

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

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

If you use a horizontal line, you split the grid into a top and bottom compartment of size 6. Then if you place a vertical line after the 2nd and 4th snakes, you end up with 6 compartments of size 2. So with just three lines you can split each snake into their own compartment.

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

Draw a horizontal line and two vertical lines before the 2nd and 3rd upper row star.This gives seperates all the stars

→ Reply