-----------------------------------

liangchenen

Fri Jul 01, 2005 12:36 pm


a game

-----------------------------------

Problem:

A Game
IOI'96 - Day 1

Consider the following two-player game played with a sequence of N positive integers (2 game[game.size()-1]-game[game.size()-2])
     {
      return 1;
     }
     else if (game[0]-game[1]=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>dummy;
        game.push_back(dummy);
       }
    
     while(!game.empty())
     {
      game1();
     }
     fileout 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

Mon Jul 04, 2005 9:38 am



-----------------------------------

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

Mon Jul 04, 2005 11:57 am



-----------------------------------

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

Mon Jul 04, 2005 1:27 pm



-----------------------------------

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.


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

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

Mon Jul 04, 2005 2:16 pm



-----------------------------------

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

Mon Jul 04, 2005 2:33 pm



-----------------------------------

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