OJ Board

Mr. arsalan_mousavian, Please explain the bug you have overcomed:

i forgot to switch the player that starts the board when the final state is draw

I assume that Johnny will choose the first board every time, then Mary chooses .. etc. I do not see anything in the problem indicating otherwise.
Also, I think that the one who start playing does not matter. You mean the one that chooses the first board, isn't it?

aminallam wrote:Mr. arsalan_mousavian, Please explain the bug you have overcomed:

i forgot to switch the player that starts the board when the final state is draw

I assume that Johnny will choose the first board every time, then Mary chooses .. etc. I do not see anything in the problem indicating otherwise.
Also, I think that the one who start playing does not matter. You mean the one that chooses the first board, isn't it?

dear aminallam
i am completely disagree with you , but first time i read the problem i thought like you , but my program didn't give correct output even for the sample IO that was given in the problem statement , it makes difference who starts the game , consider following board ( X.XO.O...) who starts the game will win the game for sure , so you see .you need a strategy for each player to choose the board, i think i described my scoring function in previous posts ( i think it helps ) , first i thought i am getting WA because of that kind of scoring function but it turns out that i made a silly mistake ( not important just Coding mikstake ) somewhere else
Arsalan

Thank you very much. I have applied your scoring function and got AC. It was only mis-interpretation, when I said "start playing" I meant that after each one choses his games, it does not matter who will play first (because he is now restricted to his chosen games only).
Thank you.
I noticed that our programs took a long time mine take about 4.6, and yours took about 7. For anyone who solved this in less time, what optimization you recommend? I precompute all 3^9 * 2 states (This took very little time), then apply O(n) choosing strategy for each case. May be the problem is that input took long time?

aminallam wrote:Thank you very much. I have applied your scoring function and got AC. It was only mis-interpretation, when I said "start playing" I meant that after each one choses his games, it does not matter who will play first (because he is now restricted to his chosen games only).
Thank you.
I noticed that our programs took a long time mine take about 4.6, and yours took about 7. For anyone who solved this in less time, what optimization you recommend? I precompute all 3^9 * 2 states (This took very little time), then apply O(n) choosing strategy for each case. May be the problem is that input took long time?

if your choosing strategy is just like me your algorithm become O(n^2 )
because on each level your algorithm should find the max value in O(n)
and with loop of n it become O(n^2) , if you choose in O(n) please inform me , i would be so happy
Arsalan

Since there is only a limited number of different scores a game can have (for each player possibly a different score), don't keep the score with all N games, but use counters on every game type. When it's time to select a game, check if the counter on the highest scoring type is greater than zero; if yes select that type and decrement the counter; if no, check the counter on the next highest scoring type, etc.
This way the selection process becomes O(N), because you don't have to scan the whole list on every selection, but only have to check a limited number of counters.

1) Give rank (0,1, or 2) for each game.
2) Sort the games according to rank (most important first).
3) Traverse the sorted list in order, giving one game for Johnny, and next game for Mary, etc, until finished. (Note that if the game has rank=i with respect to Johnny, it will have the also rank=i with respect to Mary).
- Of course the previous in O(nlogn) because of sorting. But this can be easily avoided because there are only 3 values for the rank:
- Make 3 lists, one for each rank.
- While making step (1) in the above algorithm, if you encounter a game with specific rank, put it in its associated list.
- Step (2) is not important now, and Step (3) will be: Traverse list of most important games, then the second list, then the third.