Optimal Strategy for a Game Problem HELP!!!

[michael10024]

Here is the pronunciation of the problem:
Consider a row of n coins of values v(1) ... v(n), where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

One example of test-data is this:
input:
6
4 7 2 9 5 2
output:
18

My algorithm is below. It is working but it takes a long time. What can i do to improve my algorithm? Please Help me!!!


#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;


int sum[101];
int N;
int best(int start,int stop);
int main(){
ifstream fin("ngame.in");
ofstream fout("ngame.out");

int i,j,k;

int table[101];
fin>>N;
for(i=1;i<=N;i++)
fin>>table[i];
fin.close();
sum[0]=0;
for(i=1;i<=N;i++)
sum[i]=sum[i-1]+table[i];

int sum1=best(1,N);
fout<<sum1<<'\n';
fin.close(); fout.close();
return 0;}

int best(int start,int stop){
if(start<=stop)
return max( (sum[stop]-sum[start-1])-best(start+1,stop),(sum[stop]-sum[start-1])-best(start,stop-1) );
else
return 0;
}

[eypros]

Call to IOStreams are slow. Use some approach not to use them too many times.

Open a file. Read the data. Process data. Write the data to a file.

Probably this is the slower part of your program

[kev82]

Use DP instead of recursion - see below. I have coded it based on a different recursion to yours - I don't understand your recursion. If you can explain how it works, I can probably help you convert it to DP.

#include <vector>
#include <iostream>

int solve(const std::vector<int> &coinval) {
	const int numCoins = coinval.size();

	std::vector<int> states;
	states.resize(numCoins*numCoins);
	
	for(int diff = 0;diff != numCoins;++diff) {
		for(int ai = 0;ai+diff != numCoins;++ai) {
			int bi = ai+diff;
			int sidx = ai*numCoins + bi;
			
			if(diff == 0) {
				states[sidx] = coinval[ai];
			} else if(diff == 1) {
				states[sidx] = std::max(coinval[ai], coinval[bi]);
			} else {
				int idxaa = (ai+2)*numCoins + bi;
				int idxab = (ai+1)*numCoins + bi-1;
				int idxba = idxab;
				int idxbb = ai*numCoins + bi-2;

				int a = coinval[ai] + std::min(states[idxaa],states[idxab]);
				int b = coinval[bi] + std::min(states[idxba],states[idxbb]);

				states[sidx] = std::max(a,b);
			}
		}
	}

	return states[numCoins-1];
}

int main() {
	std::vector<int> x;

	x.push_back(4);
	x.push_back(7);
	x.push_back(2);
	x.push_back(9);
	x.push_back(5);
	x.push_back(2);

	std::cout << solve(x) << std::endl;

	return 0;
}

[michael10024]

Thank you very much. Your code is working very quickly. :)

Can you please explain me your code because i don't understand it? :/

I 'll be grateful if you help me how to convert my code to DP.

First of all, i sum all the elements of the board such as sum[i]=A[0]+A[1]+...+A[i].
So, the maximum possible amount of money i can win if the sum[N] - the best choice of the second player.
The second player has the ability to take a coins from the start+1 or the stop-1 if i will take the first or the last coin.
The function best(int start,int stop) gives you from the sum of the elements which left, your best movement.
I know i didn't explaint it well and i hope so that you will understand it :/

Please reply if you have a question on my code and i will be pleased if you explain me your code because it is important on me to learn a way which is working perfectly! :)

[kev82]

Ok, as I read it, I think your recursion finds the best total you can get assuming the opposing player is also trying to get the best total possible. I've not been able to convince myself that this is equivalent to finding the maximum you can guarantee getting - but that's a problem in my head. It doesn't stop you using memoization/dp.

I've modified your program to count the number of times best() is called with the same values of start and stop. As you can see you are doing a lot of repeated work.

count start-stop
   1 1-0
   1 1-1
   1 1-2
   1 1-3
   1 1-4
   1 1-5
   1 1-6
   6 2-1
   5 2-2
   4 2-3
   3 2-4
   2 2-5
   1 2-6
  15 3-2
  10 3-3
   6 3-4
   3 3-5
   1 3-6
  20 4-3
  10 4-4
   4 4-5
   1 4-6
  15 5-4
   5 5-5
   1 5-6
   6 6-5
   1 6-6
   1 7-6

As you can see, you're calling best(3,5) 3 times. Each of those 3 calls is going to call best(4,5) and best(3,4), which in turn will call best(4,4) lots of times. As the number of coins increases, the number of calls you make increases exponentially. Try doing the same printout as me for n=7 or n=8.

There is a technique called memoization, it is about changing your best() function so that each time it does a calculation, it remembers the result, so that next time it has to perform the same calculation, it just looks in it's memory instead. See if you can rewrite your code to do that. It will speed up your code dramatically. Once you've got it working, post it here and I'll try and explain DP.

[michael10024]

Thank you very much my friend. You are awesome! :)

Here is my code and it is working excellent :)

#include<iostream>  
#include<fstream>  
#include<algorithm>  
 
using namespace std;  
 
 
int sum[101];
int Best[101][101]={};
int N;  
int best(int start,int stop);  
int main(){  
    ifstream fin("ngame.in");  
    ofstream fout("ngame.out");  
     
    int i,j,k;  
     
    int table[101];  
    fin>>N;  
    for(i=1;i<=N;i++)  
                     fin>>table[i];  
    fin.close();            
    sum[0]=0;  
    for(i=1;i<=N;i++)  
                     sum[i]=sum[i-1]+table[i];  
    
    for(i=1;i<=N;i++)
                     Best[i][i]=table[i]; 
    
    int sum1=best(1,N);  
    fout<<sum1<<'\n';  
    fin.close(); fout.close();  
    return 0;}  
 
int best(int start,int stop){  
    if (Best[start][stop]==0)
    Best[start][stop]= max( (sum[stop]-sum[start-1])-best(start+1,stop),(sum[stop]-sum[start-1])-best(start,stop-1) );  
    return Best[start][stop]; 
    }

[kev82]

Ok, so that's memoization. In dynamic programming, we get rid of the recursion. So your best function actually does this:

int best(int start,int stop) {
    if (Best[start][stop]==0) {
        Best[start][stop]= max( (sum[stop]-sum[start-1])-Best[start+1][stop],(sum[stop]-sum[start-1])-Best[start][stop-1] );
    }  
    return Best[start][stop]; 
}

Since there is no recursion, we will need to call Best(start,stop) for all start<=stop to fill the array. Something like:

for(int start=1;start!=N;++start) {
    for(int stop=start+1;stop!=N+1;++stop) {
        Best(start,end);
    }
}

However, this is clearly rubbish because this will call best(2,7) before it calls best(3,4). Chances are the calculation of best(2,7) will require the calculation of best(3,4), so this will return nonsense. The loops must be done in an order such that everything required for a particular calculation has already been calculated.

If you look at my original code, you will see that I use a different recursion to you, lines 20-28. However, I still have a best, a start, and a stop. This should give you and idea of how to translate between my code and your code.

N <=> numCoins
start <=> ai+1
stop <=> bi+1
Best[start][stop] <=> states[(start-1)*N+stop]

Don't worry that my recursion is different, just concentrate on my for loops. Can you figure out how I make sure that all necessary calculations are done first?