algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

can-i-win.cpp (2191B)


      1 class Solution {
      2 public:
      3 
      4     bool solve(bitset<21> bs, int score, bool firstTurn, int maxChoice, int target, unordered_map<long long,bool>& memo) {
      5 
      6         if(target == 0) {
      7             return true;
      8         }
      9         if(score >= target) {
     10             return !firstTurn;
     11         }
     12         long long key = (bs.to_ulong() << 43);
     13         key += (((long long)target) << 11);
     14         key += firstTurn;
     15 
     16         if(memo.contains(key)) {
     17             return memo[key];
     18         }
     19 
     20         for(int i = 1; i <= maxChoice; ++i) {
     21             if(bs[i] == 1) {
     22                 bitset<21> bsc = bs;
     23                 bsc[i] = 0;
     24                 bool next = solve(bsc, score+i, !firstTurn, maxChoice, target, memo);
     25                 if(firstTurn && next) {
     26                     memo[key] = true;
     27                     return true;
     28                 }
     29                 if(!next && !firstTurn) {
     30                     memo[key] = false;
     31                     return false;
     32                 }
     33             }
     34         }
     35         memo[key] = !firstTurn;
     36         return !firstTurn;
     37     }
     38 
     39     bool canIWin(int maxChoosableInteger, int desiredTotal) {
     40         // first to reach or exceed total wins
     41         // no reuse
     42         // true means first person can win
     43 
     44         // what's optimal play?
     45             // there's always minimax, but that'd be a bit surprising for this problem / mediume / time constrained
     46                 // also quite expensive
     47         
     48         // do I run it up?
     49         // do I run it down?
     50             // 1 <= maxChoosableInteger <= 20
     51             // 0 <= desiredTotal <= 300
     52         
     53         // small problem space
     54             // dp state := s(bitmask, currentScore, turn)
     55                     // bitmask has 2**20 states, currentScore has 301 possible states, turn has two stated
     56                         // 2**20 * 301 * 2
     57                         // 631_242_752
     58         bitset<21> bs {};
     59         for(int i = 1; i <= maxChoosableInteger; ++i) {
     60             bs[i] = 1;
     61         }
     62 
     63         unordered_map<long long,bool> memo {};
     64         if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
     65         return solve(bs,0,true, maxChoosableInteger, desiredTotal, memo);
     66     }
     67 };