### Anurag's blog

By Anurag, 12 years ago,
Yesterday i participated in this contest On UVA OJ from Bangladesh

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=253

I am here to discuss about problem C(Cheerleaders) which i couldnot submit. The first two problems A and B were easier for me.

Am i right? The problem can be solved considering the following cases
Case1 : There is non-zero solution only when K>=2. otherwise zero solution
if Case1 is true, then
Case2 :  The arrangment can be done in following way:
I. place 2 Cheerleaders on the one of the opposite corners and the rest          leaders can be  put in the rest of N*M-2 cells .
II place 2 Cheerleaders on other opposite corners and the rest leaders can be put in the rest of N*M-2 cells
III place 2 cheerleaders in adjacent corner and 1 leader on one side and the rest in the remaining N*M-3 cells
IV III way can  be repeated 3 more times
V place 3 cheerleaders in 3 corners and the rest in N*M-3 cells
VI V way can be repeated 2 more times
VII place 1 cheerleader(it will cover 2 sides) on one of the corner and 2 leaders on the other 2 sides and the rest leaders on N*M-3 cells
VIII VII way can be repeated 3 more times as we have 4 corners in total
IX
place 4 cheerleaders on all the 4 sides aand the remaining cheerleaders on the N*M-4 cellls

Thats'all
K
should be appropriately dealt as sometimes (k has to be)
I K>=2
II K>=3
III K>=4

Please comment whether this can provide a solution or not
One thing more at the UVA site can't i submit the solution to this problem any more?

Thanks for ur response

• 0

 12 years ago, # |   0 My solution: First find out all the points on four sides. It will have (n + m) * 2 - 4 points at most. Every point can cover some sides. We use a binary number to describe the 'ability' of every point.E.g. If a point can cover sides 1 & 3 , then we give it a number 2^0 + 2 ^ 2 Then use dynamic programming: F[S][tot][Mark] means how many ways are there if we put tot cheerleaders on first S points and the state of the sides is Mark.....The things following is too simple :)
 12 years ago, # |   +1 You can submit the problem .Now the problem is in the contest volume the problem no : 11806
•  12 years ago, # ^ |   0 Thanks
 12 years ago, # |   0 At on site contest my team mate made a direct(although little big) formula using binomial coefficient .