a game

[liangchenen]

Problem:

code:

A Game IOI'96 - Day 1 Consider the following two-player game played with a sequence of N positive integers (2 <= N <= 100) laid onto a game board. Player 1 starts the game. The players move alternately by selecting a number from either the left or the right end of the sequence. That number is then deleted from the board, and its value is added to the score of the player who selected it. A player wins if his sum is greater than his opponents. Write a program that implements the optimal strategy. The optimal strategy yields maximum points when playing against the "best possible" opponent. Your program must further implement an optimal strategy for player 2. PROGRAM NAME: game1 INPUT FORMAT Line 1:         N, the size of the board Line 2-etc:     N integers in the range (1..200) that are the contents of the game board, from left to right SAMPLE INPUT (file game1.in) 6 4 7 2 9 5 2 OUTPUT FORMAT Two space-separated integers on a line: the score of Player 1 followed by the score of Player 2. SAMPLE OUTPUT (file game1.out) 18 11

here is my code :

code:

/*     ID: chenenmat1     LANG: C++     PROG: game1     */         #include <iostream>     #include <fstream>     #include <algorithm>     #include <deque>     using namespace std;         ifstream filein("game1.in");     ofstream fileout("game1.out");     int num;     deque <short>game;     int score[2];     short turn=0;             short check()     {      int a,b;      //case number1      if (game.size()<=3)      {       if (game.front()>=game.back())       return 1;       else       return 2;      }      //case number2      if (game[0]-game[1]>game[game.size()-1]-game[game.size()-2])      {       return 1;      }      else if (game[0]-game[1]<game[game.size()-1]-game[game.size()-2])      {       return 2;         }      else      {        a=1;                 b=game.size()-2;                while(1)       {        if (game[a]-game[a+1]<game[b]-game[b-1])        return 1;        else if (game[a]-game[a+1]>game[b]-game[b-1])        return 2;        a++;        b--;        if (a>=b) return 1;       }      }           }     void game1()     {      if (check()==1)      {      score[turn]+=game.front();      game.pop_front();      }      else      {      score[turn]+=game.back();      game.pop_back();           }      //switch turn      turn ++;      if (turn==2)      turn=0;     }         int main()     {         int x; //counter         int dummy;        filein>>num;                for (x=0;x<num;x++)        {         filein>>dummy;         game.push_back(dummy);        }          while(!game.empty())      {       game1();      }      fileout<<score[0]<<' ';      fileout<<score[1]<<endl;        system("pause");        filein.close();        fileout.close();       return 0;     }

it only works for some cases, here is my algo:
u can take a number from either side, it is silly to alwayz take the largest one because if you have this 2 10 3 1
apparently, if you take 2, u will give your opponent a chance to take the 10, so, you take 1 instead.
so, I compare the difference from the numbers on the ends and the numbers beside it.
1-3 > 2-10 and we take the value that's the largest.
but this won't alwayz work, I konw there something wrong with my logic, so can anybody help?

[bugzpodder]

minor changes in code so it doesnt provide the correct answer

for (i=0;i<N;i++){
for (j=1;j<=N-1;j++) //arr[i][j] is the sum of first i# from j
for (int k=i;k>=i-j;k--)
arr[j][k]+=arr[0][i];
}


for (i=1;i<N;i++)
for (j=0;j<N-i+1;j++)
if (arr[i-1][j]<arr[i-1][j+1])
arr[i][j]-=arr[i-1][j];
else //subtract the smaller of my opponent's score
arr[i][j]-=arr[i-1][j+1];

[wtd]

Don't write bastardizations of C and C++.

What am I talking about?

Well, things like needlessly declaring a loop counter in an outer scope.

code:

int x; for (x = 0; x < n; x++) {   yada; }

Can be more correctly written as:

code:

for (int x(0); x < n; x++) {   yada; }

Use spaces. Code like the following is harder to understand, and the compiler doesn't care one way or the other.

code:

game[0]-game[1]>game[game.size()-1]-game[game.size()-2]

Instead, write:

code:

game[0] - game[1] > game[game.size() - 1] - game[game.size() - 2]

Better yet, let's take a cue from a language like Python, where to get the last element in a list type structure you can write:

code:

list[-1]

Let's subclass deque to get this effect. Something like:

c++:

template <typename _t> struct my_deque : public std:deque {    my_deque() : std::deque<_t>() { }    ~my_deque() { delete this; }    _t operator[](int index) const    {       return std::deque<_t>::operator[]((index >= 0 ? 0 : size()) + index);    }    _t& operator[](int index)    {       return std::deque<_t>::operator[]((index >= 0 ? 0 : size()) + index);    } };

If this works (I haven't yet tested it), we could write:

code:

game[0] - game[1] > game[-1] - game[-2]

And last but not least, never ever use global variables. The variables you have declared at the top of your program should be declared inside the main function and then passed via function parameters to any function that needs them.

[liangchenen]

first of all, can you guys plz tell me where I did wrong with my algorithm. it is easier for me to understand


secondly, why it is not good to declare global variables?
I thought the more parameters you pass around functions, the more times it takes to run.
also, on the CCC stage 2 , I declared int matrix[1000][1000] in main , or maybe something even larger, then the program won't compile because the matrix is too large, I was trying to figure why and people told me to put that in global and then everything should be fine. So, in that case, is it better to make matrix global?

[bugzpodder]

wtd is probably talking about coding styles in a commerical setting where hundreds of people work on the same program.
In a contest setting, the rules are different, since it is often the goal to produce something correct in a short time span (~1 hour)

your algorithm is greedy (considers a single state), and it doesnt work. You can try to find a counter example by yourself. dynamic programming (considers all possible states) needs to be used, which I have showned you (as I said, I purposely changed a few things here and there to produce incorrect results).

thirdly, it is often more helpful to do USACO questions by yourself as opposed to ask for help.

[md]

liangchenen wrote:

first of all, can you guys plz tell me where I did wrong with my algorithm. it is easier for me to understand

Seems to me like a solution that works has been provided; well... mostly. Honestly I haven't checked to see what needs to be changed.

liangchenen wrote:

secondly, why it is not good to declare global variables?
I thought the more parameters you pass around functions, the more times it takes to run.
also, on the CCC stage 2 , I declared int matrix[1000][1000] in main , or maybe something even larger, then the program won't compile because the matrix is too large, I was trying to figure why and people told me to put that in global and then everything should be fine. So, in that case, is it better to make matrix global?

Global varables are bad because if you are reading the code it is confusing as to where these variables come from. Globals also make it very easy to start relying on artifacts of the way a certain part of your code works to get another part to work. Basically you might rely on the fact that a function changes a global (when it doesn't have to) to get another function to work properly... what happens when you change the first function so the global is no longer changed? You'll break your code! Yeah... not the best description, but I'll come up with an example later.

As for the matrix; it's because you are trying to declare a very large variable on the stack; and on most computers the stack has a hardware limited size of 32k (intel) or 64k (powerpc + some others). If you want to declare a matrix like that you should declare it on the heap; look into dynamic memory allocation.

No matter teh enviroment; it's best to avoid global variables, because it's easiest to get out of the habit of not using them if you never start.

[bugzpodder]

that being said. in a CCC setting, dont let it prevent you from declaring global vars... after all, I would do it just because it initializes your global vars to 0... saving me a memset if anything. and why the hell would you use "short"? just stick to either int or long longs. dont use anything else (in CCC).

[wtd]

The compiler will optimize for you. It will do a better job if you write good code.