SPOJ 3407. Candy

Here I come up with yet another SPOJ Problem. This problem appeared in my college’s tech fest’s programming contest(Code d basiCs). This is a lot simpler and smaller problem than my last post’s problem.

Problem code: SAMER08C

Little Charlie is a nice boy addicted to candies. He is even a subscriber to All Candies Magazine and was selected to participate in the International Candy Picking Contest.

In this contest a random number of boxes containing candies are disposed in M rows with N columns each (so, there are a total of M ×N boxes). Each box has a number indicating how many candies it contains.

The contestant can pick a box (any one) and get all the candies it contains. But there is a catch (there is always a catch): when choosing a box, all the boxes from the rows immediately above and immediately below are emptied, as well as the box to the left and the box to the right of the chosen box. The contestant continues to pick a box until there are no candies left.

The figure bellow illustrates this, step by step. Each cell represents one box and the number of candies it contains. At each step, the chosen box is circled and the shaded cells represent the boxes that will be emptied. After eight steps the game is over and Charlie picked 10+9+8+3+7+6+10+1 = 54 candies.

For small values of M and N, Charlie can easily find the maximum number of candies he can pick, but when the numbers are really large he gets completely lost. Can you help Charlie maximize the number of candies he can pick?

Input

The input contains several test cases. The first line of a test case contains two positive integers M and N (1 ≤ M ×N ≤ 10⁵), separated by a single space, indicating the number of rows and columns respectively. Each of the following M lines contains N integers separated by single spaces, each representing the initial number of candies in the corresponding box. Each box will have initially at least 1 and at most 10³ candies.

The end of input is indicated by a line containing two zeroes separated by a single space.

Output

For each test case in the input, your program must print a single line, containing a single value, the integer indicating the maximum number of candies that Charlie can pick.

Example

Input:

5 5
1 8 2 1 9
1 7 3 5 2
1 2 10 3 10
8 4 7 9 1
7 1 3 1 6
4 4
10 1 1 10
1 1 1 1
1 1 1 1
10 1 1 10
2 4
9 10 2 7
5 1 1 5
0 0

Output:
54
40
17

---

Added by:	Diego Satoba
Date:	2008-11-23
Time limit:	2s
Source limit:	50000B
Languages:	C C++ 4.0.0-8 C++ 4.3.2 TCL SCALA JAVA PYTH 2.6.2
Resource:	South American Regional Contests 2008

---

______________________________________________________________________________________________

Solution:

One can solve the game by making the computer play the game by selecting among all possible choices and then among the remaining ones. Finally output the case with least sum as the answer. If that was the desired solution certainly Charlie would not have asked us to write a program for him.

The most interesting part of the game is to spot the underlying problem which enables us to maximize the overall sum for the game. Did you find it? Not yet? Well then let me tell you, the problem simply requires us to find the sequence for maximum sum in a row such that no two numbers are consecutive. After we recognize the hidden problem this tricky looking game boils down to finding the numbers of a sequence which gives maximum sum and no two numbers are consecutive either. After that we do the same with the result of each row in vertical direction. So basically now we have extracted the entire hidden problem but it is not over yet, this problem itself can be a bit tricky. So let’s now concentrate on the problem at hand i.e.

To find the numbers from a  given sequence  such that it has a maximum sum and no two of the selected numbers are consecutive . (say the given list of numbers is a₀ to a_n).

Approach 1

We can keep picking non consecutive numbers until it is not possible to pick any more and then update the minimum sum found so far. This approach is correct but it runs in exponential time.

Approach 2

Now if we split the series in two series on either side of a randomly chosen number in a way such that we have maximum sum from the series on both sides of this number and this number which splits the series into two is not selected in any of the two series. Then it satisfies our criteria. The problem which arises here is, splitting along which number we can always have the maximum sum on either side is not known to us.

One can implement dynamic programming with the following recurrence relation:

_k=j

For i<j, S(i,j)=Min_k=i {S(i,k-1)+S(k+1,j)};……………(2.1)

For i=j, S(i,j)=S(i,i)=a_i; ………………(2.2)

For i>j, S(i,j)=0 ; ……………..(2.3)

This looks to be a perfect implementation of dynamic programming but the bad news is it does not satisfy the time constraint of the problem. It runs in O(n*n*n) …………………(2,4)

It is a pitfall i have dragged you into. So we need a better one.

Approach 3

Actually the problem is not so complex.

Note, when a number is selected for partitioning at some other point it would need us to check this numbers selection again about some other partitioning. Therefore we still have over-lapping sub-cases.We have used dynamic programming and yet we have not been able to avoid re-computation completely. Isn’t it? Now note, we can not have 3 consecutive unselected numbers. There should be at least 1 and at most 2 not selected among those 3 consecutive numbers.but we didn’t utilize this property.

So When we chose a number randomly the question is why should we check iteratively all n such numbers to find which correctly splits the series when it can be decided among 3.It suffice to check immediate neighbors only(the one preceding and the one succeeding). The problem is that the way we defined our recurrence relation we did not leave any scope to know the status of the two neighbors (not even 1 neighbor).

Now check this recurrence definition where S(i) denote the sum max sum series from a₀ to a_i.

S(i)=Max{S(i-2) +a_i, S(i-1)} [ for 2<=i<=n-1 ]………….……(3.1)

S(0)=a₀ ….……………………(3.2)

S(1)=Max{a₁,a₀} ………………………(3.3)

Answer=Max{S(n-2),S(n-1)} ………………………….…(3.4)

Applying dynamic programming on this recurrence takes a time O(n)

Now returning back to Charlie’s game, for m rows it would take O(m*n) time plus time to compute vertically O(m).i.e. O(m*n)……………………………..…(3.5)

This algorithm scores full marks. Readers please help me optimize it further.

Advertisement