sorting array can help improving O(N^3) to O(N^2)

>+ 10. 8

12
14 2 6 7 3 9 7 1 2 1 2 1

let's take
12
{10,4} 2 6 {5,2} 3 9 7 1  2 1 2 1
then we have seven pairs (is not true)?:
(2,1) (2,1) (1,2) (6,7) (2,3) (4,5) (10,9)

P.S. sorry for eng. and I got AC.

Edited by author 14.06.2011 17:25

Edited by author 14.06.2011 17:25

Thanks. But I dont understand what is the DP.
May be you mean Brut Forse

can't we split the 10 in 6 and 4 and then:
1 row: 6 5
2 row: 4 3

?

I have the same answer, but i still have WA 6. Could you give some more tests?

What do you mean?

It means that, for example, sequence
1 2 1 2 1 2 1
is valid, while sequence
1 1 2 1 2 1 1
is invalid.
More precise: if we put two different types of diploma into the same row, then no two diploma of the same type should be adjacent.

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.

why?

Edited by author 03.07.2007 15:36

Edited by author 01.06.2008 12:33

Edited by author 03.07.2007 15:41

Edited by author 01.06.2008 12:34

Edited by author 01.06.2008 12:35