11553 - Grid Game

[Obaida]

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

[f74956227]

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

[seckin]

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

[kbr_iut]

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

thanx in advance.

[helloneo]

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

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]

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.

[helloneo]

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]

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

Code: Select all

ifptr.close();
ofptr.close();
}
int main()
{
readFromFile();

return 0;
}

[BUET]

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

[BUET]

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

[matrix2220]

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