Hi, I am eager to know How to Find the Optimal Strategy When First See a Game Problem?

For example, CodeTON #2 Problem F Colouring Game, how do you know "start by taking RB/BR parts" is the smartest move, before you see the editorial?

# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3773 |

3 | Radewoosh | 3646 |

4 | ecnerwala | 3624 |

5 | jqdai0815 | 3620 |

5 | Benq | 3620 |

7 | orzdevinwang | 3612 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | cry | 161 |

2 | awoo | 160 |

2 | maomao90 | 160 |

4 | atcoder_official | 157 |

5 | -is-this-fft- | 155 |

5 | nor | 155 |

7 | adamant | 153 |

8 | maroonrk | 152 |

8 | Um_nik | 152 |

10 | djm03178 | 146 |

Hi, I am eager to know How to Find the Optimal Strategy When First See a Game Problem?

For example, CodeTON #2 Problem F Colouring Game, how do you know "start by taking RB/BR parts" is the smartest move, before you see the editorial?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/10/2024 03:40:18 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I also find Game Problems hard,and I cannot solve them in contests.

Start from the losing condition and think about how each player can prevent that from happening. Alice loses when no red cells remain and Bob loses when no blue cells remain. Therefore, Alice should minimize loss of red cells and maximize loss of blue cells.

Now think about each of the possible moves. Alice can only play WR/RW, BR/RB, or RR as she must include at lease one red cell. BR/RB is strictly better than WR/RW because both reduce red cells by 1 while BR/RB also reduces blue cells by 1. RR is even worse as it reduces red cells by 2 without affecting blue cells.

Therefore, BR/RB is the best move for Alice (and the same logic applies to Bob).

Thank you verrrrry much. I will try to apply this logic on other game problems.

Before getting too deep in the details I like to think: "If I was playing the game, how would I play?".

Right away, if I were playing as Alice I would not want to choose "RR" as that removes 2 Rs at once. Over "RR", I would prefer "RW" as it removes only 1 R, and over that I would prefer "RB" as that also removes a B for the other player. I think it's good to get a general intuition for how to play the game before trying to solve the problem.