ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1431. Diplomas

Just simply Greedy
Posted by SerailHydra 29 Aug 2007 20:56
There is no need to use DP.
Re: Just simply Greedy
Posted by svr 29 Aug 2007 21:08
Can your write proveness of Greedy for this problem?
Dp as a rule absolute correct optimization method
but greedy often well to next rejudgement.

Yes!! AC
Very hidden information needed: Dimploms of
one type must be placed in one row.
During a long time I thought that after changing
conditions we can placed them in any different rows.

Edited by author 24.01.2008 11:04
Re: Just simply Greedy
Posted by Lomir 29 Aug 2007 23:56
Let's try to proove it with one additional statement: "There is only one type of diploms with some size S".

First we put all type of diploms in seperate lines. Now we must minimize the number of rows.
By the problem description we have:
We can merge two (x and y) rows into one if and only if equality is statisfied:
|size(x)-size(y)| == 1

So, some diplom row x can be merged only with row y. Where: size(y) == size(x)+1 or size(y) == size(x)-1.

If none of y diploms row exist, then row x can not be merged and it must stay.

If only one dimplom row y exist, then we must do this megre not looking on y at all. Even if y has other possible merging global minimus isn't affected. If we can megre x and y or y and z, we can merge only one pair.

The last type of merge left, then x can be merged from both sides. Here we cant choose the prefered merge so easily.
So let's sort all rows and analise them in accessing order.
Then this situation just can not happen, cause all size(y)-1 merging row will be merged before, then analysing Y row.

Now lets apply this proof to out problem. We just have to divide all dimploms into sets. In set A goes all dimpols x with size(x) == A. So we must minimize the sum of all set's power by same apporach.