## h4ck4r

BAN USER- 0of 0 votes

AnswersThere are total of n boxes kept in a single row next to each other .

- h4ck4r in India for none

Each box has weight W(i) .

How to split the boxes into two groups such that the difference between the total weight of the two groups is minimum and

the boxes in each group maintain the order in which they were initially.Also there is a condition that there if the total number of boxes is even ,

then both the groups should have n/2 boxes and if n is odd , one group should have (n-1)/2 and other (n+1)/2 boxes.

for example....

lets say there are 3 boxes of weight 6,12,5.

then the solution would be that one group has 6,5 and other has 12| Report Duplicate | Flag | PURGE

A9 Area Sales Manager Algorithm

- 0 Answers
**codechef question**Hi..can anyone give test case for the following question where alice wins other than when m=1,n=1...

- h4ck4r November 04, 2012

Alice and Bob have come to spend their day in a FunFair which is close to their house. They have played almost all games and seen all the attractions. But there's one game left which has caught their attention. The winner of this game could get a LOT of candies! The game is as follows:

The game is a two-player game which is played on an NxM grid.

Each cell of the grid has a certain number of candies. A[i][j] denotes the number of candies in the jth column of the ith row.

The players make alternate turns.

In each turn, a player must remove one complete row or one complete column from the grid. He will add all the candies in that row/column into his account.

The only possible rows that a player can remove in his/her turn are the top row or the bottom row. Similarly, only leftmost column or the rightmost column can be removed in one turn.

After removing the row or column, the game is played on the new reduced grid with one less row or column respectively.

When the entire matrix is emptied, the player with higher number of candies wins the game and can take all those candies with him/her. The loser has to give back the candies collected so far and return empty-handed.

If both players have equal number of candies, both of them are declared winners.

Alice and Bob want to take as many candies home as possible. They don't have much time with themselves. So they come up with a strategy using which they want to increase Bob's share of candies and decrease Alice's share. This way, they plan to make Bob win and take his entire share of candies! The strategy is as follows:

Alice decides to pick the row or column from the present grid which has the least number of candies in every turn of hers.

If there are more than one such options, then her order of preference will be:

1) first row

2) last row

3) first column

4) last column.

For example, if all these 4 rows/columns have the same number of candies, she will remove the first row in this turn.

Bob chooses an optimal strategy through which he maximizes his share of candies in the end of the game. Note that Bob's strategy maximizes the number of his candies, not winner's candies. Also note that Bob knows Alice's strategy, of course, and he will take into account her strategy when he decides his move.

It's quite evident that their strategy is not optimal. It might happen that Bob loses a game. And sometimes, both might win (with equal number of candies). Given the grid and the number of candies in each cell, your task is to tell them how many candies will the winner get if they play with this combined strategy. Alice will always start the game (Ladies first!).

Input:

First line of the test data contains a single integer T, the number of test cases.

Each test case starts with two space separated integers N and M, the number of rows and columns of the grid respectively.

Then follow N lines containing M space separated integers A[i][j]. These lines describe the grid.

Output:

For each test case, output a single line containing the number of candies the winner(s) gets.

Constraints:

1 ≤ T ≤ 25

1 ≤ N, M ≤ 50

0 ≤ A[i][j] ≤ 1000000000

Example:

Input:

3

3 3

0 9 9

0 6 6

0 9 6

2 2

1 1

1 1

1 4

1 2 3 4

Output:

39

4

9| Flag | PURGE

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

@ eugene.yarovoi : It will be great if you can post your logic for this question.

- h4ck4r October 29, 2012