![:(](./images/smilies/icon_frown.gif)
11553 - Grid Game
Moderator: Board moderators
11553 - Grid Game
Can some help me find the game technique i am not sure about it. ![:(](./images/smilies/icon_frown.gif)
![:(](./images/smilies/icon_frown.gif)
try_try_try_try_&&&_try@try.com
This may be the address of success.
This may be the address of success.
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 ?![:o](./images/smilies/icon_eek.gif)
someone give me a hint ?
![:o](./images/smilies/icon_eek.gif)
electron
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))
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;
}
-
- Experienced poster
- Posts: 103
- Joined: Tue Mar 25, 2008 11:00 pm
- Location: IUT-OIC, DHAKA, BANGLADESH
- Contact:
Re: 11553 - Grid Game
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;
}
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
It is more tough to become a good person.
I am trying both...............................
Re: 11553 - Grid Game
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
-
- 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.
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...............................
It is more tough to become a good person.
I am trying both...............................
Re: 11553 - Grid Game
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.
![:-)](./images/smilies/icon_smile.gif)
If you really don't have any idea, see the following hint..
http://forums.topcoder.com/?module=Thre ... dID=619109
-
- 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;
}
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;
}
![:wink:](./images/smilies/icon_wink.gif)
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
ofptr.close();
}
int main()
{
readFromFile();
return 0;
}
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.
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
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.
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
-
- New poster
- Posts: 9
- Joined: Mon Jul 07, 2014 3:37 pm
- Contact:
Re: 11553 - Grid Game
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
![:)](./images/smilies/icon_smile.gif)
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.
![:)](./images/smilies/icon_smile.gif)
Abdelrahman Ali (MaTrix)