11553 - Grid Game

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

11553 - Grid Game

Can some help me find the game technique i am not sure about it. try_try_try_try_&&&_try@try.com
This may be the address of success.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: 11553 - Grid Game

I think this problem can be solved by DP... but i can't find the recursive formula, could
someone give me a hint ? electron

seckin
New poster
Posts: 3
Joined: Sat Jan 31, 2009 5:43 pm

Re: 11553 - Grid Game

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))

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[(1<<9)];

int main(){
int i,j,k,cs,top,mn,dizi;
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<<i]=dizi[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;
}

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11553 - Grid Game

seckin wrote
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.
if this is true whats wrong to my code. i am getting WA.

Code: Select all

#include<iostream>
#include<algorithm>
using namespace std;
int n,t,txt,sum,num,i,j,tem,v;
bool bl;
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;
}

It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11553 - Grid Game

kbr_iut wrote:seckin wrote
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.
if this is true whats wrong to my code. i am getting WA. thanx in advance.
You can't choose a column more than once, and every column should be selected at the final stage

Try this case

Code: Select all

1
4
10 11 12 13
1 10 10 10
10 10 10 10
10 10 10 10
Output should be..

Code: Select all

32

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11553 - Grid Game

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.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11553 - Grid Game

kbr_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.
Well.. I just meant that the rows and the columns are one to one mapping If you really don't have any idea, see the following hint..

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

Arsalan_Mehmood
New poster
Posts: 1
Joined: Wed Apr 20, 2011 4:31 am

11553 - Grid Game

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;
}

{
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()
{

return 0;
}

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

11553 - Grid Game

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.

CSE,07 BUET

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

Re: 11553-Grid Game

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.

CSE,07 BUET

matrix2220
New poster
Posts: 9
Joined: Mon Jul 07, 2014 3:37 pm
Contact:

Re: 11553 - Grid Game

First thought:

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;

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
1
4
10 11 12 13
1 10 10 10
10 10 10 10
10 10 10 10
The correct output is 32 while this algorithm will give 40

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
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.
Hope That Help Abdelrahman Ali (MaTrix)