### 11553 - Grid Game

Posted:

**Wed Dec 24, 2008 11:34 am**Can some help me find the game technique i am not sure about it.

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=50&t=42540

Page **1** of **1**

Posted: **Wed Dec 24, 2008 11:34 am**

Can some help me find the game technique i am not sure about it.

Posted: **Thu Jan 22, 2009 5:50 pm**

I think this problem can be solved by DP... but i can't find the recursive formula, could

someone give me a hint ?

someone give me a hint ?

Posted: **Mon Feb 09, 2009 6:37 pm**

yes, it can be done using dp but before that i realized that BOB can take which number he wants from the board. so just choose the numbers with the minimum sum. it is enough to pass since i implemented it and passed in 0.030sec.

BTW, i tried to solve it with DP too but get WA. i tried some test-cases but can't figure out what is wrong.

it would be very nice to have challenging test cases.

here is my DP code:

(dp[x][y] holds the minimum number that can be collected from first x rows using only the encoded columns in y (y is bitmask))

BTW, i tried to solve it with DP too but get WA. i tried some test-cases but can't figure out what is wrong.

it would be very nice to have challenging test cases.

here is my DP code:

(dp[x][y] holds the minimum number that can be collected from first x rows using only the encoded columns in y (y is bitmask))

Code: Select all

```
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <queue>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ll long long
#define sz(a) int((a).size())
#define pb push_back
#define SORT(x) sort((x).begin(),(x).end());
#define VI vector<int>
#define VII vector < vector <int> >
using namespace std;
int n,dp[10][(1<<9)];
int main(){
int i,j,k,cs,top,mn,dizi[10][10];
ifstream fin ("in.in",ios::in);
ofstream fout ("out.out",ios::out);
n=0;
fin>>cs;
for(;cs>0;cs--){
mn=(1<<27);
fin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
fin>>dizi[i][j];
memset(dp,0x1f,sizeof(dp));
for(i=0;i<n;i++)
dp[1][1<<i]=dizi[0][i];
for(j=2;j<=n;j++)
for(int kul=1;kul<(1<<n);kul++)
if(__builtin_popcount(kul)==j-1)
for(int ek=0;ek<n;ek++)
if((kul&(1<<ek))==0){
dp[j][(kul|(1<<ek))]=min(dp[j-1][kul]+dizi[j-1][ek],
dp[j][(kul|(1<<ek))]);
if(j==n) mn=min(mn,dp[j][(kul|(1<<ek))]);
}
fout<<mn<<endl;
}
return 0;
}
```

Posted: **Fri Feb 13, 2009 12:27 am**

seckin wrote
thanx in advance.

if this is true whats wrong to my code. i am getting WA.yes, it can be done using dp but before that i realized that BOB can take which number he wants from the board. so just choose the numbers with the minimum sum. it is enough to pass since i implemented it and passed in 0.030sec.

Code: Select all

```
#include<iostream>
#include<algorithm>
using namespace std;
int n,t,txt,sum,num,i,j,tem,v[25][25];
bool bl[25];
int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&v[i][j]);
sum=0;
fill(bl,bl+25,true);
for(i=0;i<n;i++){
tem=0;
for(j=1;j<n;j++)if(bl[j]&&v[i][j]<=v[i][tem])tem=j;
bl[tem]=false;
sum+=v[i][tem];
}
printf("%d\n",sum);
}
return 0;
}
```

Posted: **Fri Feb 13, 2009 2:57 am**

You can't choose a column more than once, and every column should be selected at the final stagekbr_iut wrote:seckin wroteif this is true whats wrong to my code. i am getting WA.yes, it can be done using dp but before that i realized that BOB can take which number he wants from the board. so just choose the numbers with the minimum sum. it is enough to pass since i implemented it and passed in 0.030sec.thanx in advance.Code: Select all

Try this case

Code: Select all

```
1
4
10 11 12 13
1 10 10 10
10 10 10 10
10 10 10 10
```

Code: Select all

`32`

Posted: **Fri Feb 13, 2009 10:19 am**

thanx helloneo for ur reply and useful suggestion.

but I am still not getting the point.

what do u mean by "............ and every column should be selected at the final stage".

if u have time pliz let me know.

again thanx in advance.

but I am still not getting the point.

what do u mean by "............ and every column should be selected at the final stage".

if u have time pliz let me know.

again thanx in advance.

Posted: **Fri Feb 13, 2009 5:32 pm**

Well.. I just meant that the rows and the columns are one to one mappingkbr_iut wrote:thanx helloneo for ur reply and useful suggestion.

but I am still not getting the point.

what do u mean by "............ and every column should be selected at the final stage".

if u have time pliz let me know.

again thanx in advance.

If you really don't have any idea, see the following hint..

http://forums.topcoder.com/?module=Thre ... dID=619109

Posted: **Wed Apr 20, 2011 4:58 am**

Can some body help me to find out why i am getting run time error (response from uva online judge) when there is no error on exicution on mine side, thanks in Advance .....

mine code is :

# include <iostream>

# include <fstream>

using namespace std;

int gridGame ( int** maze, int k , int count, bool* col )

{

if ( count == 0 )

return 0;

int temp2 = 10000, temp, tempCount = count;

for ( int j=0; tempCount != 0; j++ )

{

if ( col[j] == 1 )

{

col[j] = false;

temp = maze[k][j];

temp += gridGame(maze, k+1, count-1, col );

col[j] = true;

if ( temp2 > temp )

{

temp2 = temp;

}

tempCount--;

}

}

return temp2;

}

void readFromFile()

{

int N, size, i, j;

int **maze;

bool *col;

ofstream ofptr;

ifstream ifptr;

ifptr.open("input.txt");

ofptr.open("output.txt");

ifptr>>N;

while ( N )

{

ifptr>>size;

maze = new int *[size];

col = new bool [size];

for ( i=0; i<size; i++ )

{

maze* = new int [size];*

col* = true;*

}

for ( i=0; i<size; i++ )

{

for ( j=0; j<size; j++ )

ifptr>>maze*[j]; *

}

ofptr<<gridGame(maze, 0, size, col)<<endl;

for ( i=0; i<size; i++ )

{

delete [] maze*;*

}

delete [] maze;

delete [] col;

N--;

}

ifptr.close();

ofptr.close();

}

int main()

{

readFromFile();

return 0;

}

mine code is :

# include <iostream>

# include <fstream>

using namespace std;

int gridGame ( int** maze, int k , int count, bool* col )

{

if ( count == 0 )

return 0;

int temp2 = 10000, temp, tempCount = count;

for ( int j=0; tempCount != 0; j++ )

{

if ( col[j] == 1 )

{

col[j] = false;

temp = maze[k][j];

temp += gridGame(maze, k+1, count-1, col );

col[j] = true;

if ( temp2 > temp )

{

temp2 = temp;

}

tempCount--;

}

}

return temp2;

}

void readFromFile()

{

int N, size, i, j;

int **maze;

bool *col;

ofstream ofptr;

ifstream ifptr;

ifptr.open("input.txt");

ofptr.open("output.txt");

ifptr>>N;

while ( N )

{

ifptr>>size;

maze = new int *[size];

col = new bool [size];

for ( i=0; i<size; i++ )

{

maze

col

}

for ( i=0; i<size; i++ )

{

for ( j=0; j<size; j++ )

ifptr>>maze

}

ofptr<<gridGame(maze, 0, size, col)<<endl;

for ( i=0; i<size; i++ )

{

delete [] maze

}

delete [] maze;

delete [] col;

N--;

}

Code: Select all

ofptr.close();

}

int main()

{

readFromFile();

return 0;

}

Posted: **Wed Aug 21, 2013 2:11 pm**

Brute-force approach can run well within time limit.

You need to consider all permutation of columns only. Because Bob will choose columns. We do not need to consider permutation of rows. Ultimately Alice have to cut all rows and how Bob will cut columns is the main question. Alice's order of row cutting is not important.

Shadek

CSE,07 BUET

You need to consider all permutation of columns only. Because Bob will choose columns. We do not need to consider permutation of rows. Ultimately Alice have to cut all rows and how Bob will cut columns is the main question. Alice's order of row cutting is not important.

Shadek

CSE,07 BUET

Posted: **Wed Aug 21, 2013 2:13 pm**

Brute-force approach can run well within time limit.

You need to consider all permutation of columns only. Because Bob will choose columns. We do not need to consider permutation of rows. Ultimately Alice have to cut all rows and how Bob will cut columns is the main question. Alice's order of row cutting is not important.

Shadek

CSE,07 BUET

You need to consider all permutation of columns only. Because Bob will choose columns. We do not need to consider permutation of rows. Ultimately Alice have to cut all rows and how Bob will cut columns is the main question. Alice's order of row cutting is not important.

Shadek

CSE,07 BUET

Posted: **Tue Jul 08, 2014 5:47 pm**

First thought:

This algorithm gives right results in case Bob just select the column with the element with the min value in each row! But since they both play optimally then Bob will not do that, If he gonna lose then he must let Alice win as minimum candy as possible.

for example a case written by @helloneo

For 32 to appear Alice may choose any row, if she choose row 1 (o-based) then Bob will choose column 0 to just lose one candy, then regardless of the row she will choose he will try to remove the values 12 13 in order to give here 11 candies from row 0!

So let's assume Alice choices and Bob's corresponding optimal choices

Alice----Bob

0---------1 >> giving Alice 11

2---------2 >> giving Alice 10

3---------3 >> giving Alice 10

1---------0 >> giving Alice 1

Total = 32

We can see that Alice order of choosing rows is useless, It all depends on Bob's choices!

And as @BUET said

Code: Select all

```
Alice = 0;
while(There Still rows)
{
get Min. of each row and add them in Min Array;
get Max. value in Min Array;
add M(i,j) to Alice;
remove row i and column j;
}
print Alice;
```

for example a case written by @helloneo

The correct output is 32 while this algorithm will give 401

4

10 11 12 13

1 10 10 10

10 10 10 10

10 10 10 10

For 32 to appear Alice may choose any row, if she choose row 1 (o-based) then Bob will choose column 0 to just lose one candy, then regardless of the row she will choose he will try to remove the values 12 13 in order to give here 11 candies from row 0!

So let's assume Alice choices and Bob's corresponding optimal choices

Alice----Bob

0---------1 >> giving Alice 11

2---------2 >> giving Alice 10

3---------3 >> giving Alice 10

1---------0 >> giving Alice 1

Total = 32

We can see that Alice order of choosing rows is useless, It all depends on Bob's choices!

And as @BUET said

Hope That HelpBrute-force approach can run well within time limit.

You need to consider all permutation of columns only. Because Bob will choose columns. We do not need to consider permutation of rows. Ultimately Alice have to cut all rows and how Bob will cut columns is the main question. Alice's order of row cutting is not important.