Anurag's blog

By Anurag, 12 years ago, In English
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.
Problem C link
http://uva.onlinejudge.org/contests/253-dead8a0b/11806.html

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
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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, # |
  Vote: I like it +1 Vote: I do not like it
You can submit the problem .Now the problem is in the contest volume 
the problem no : 11806

12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
At on site contest my team mate made a direct(although little big) formula using binomial coefficient .