SRM 701 Div2

Easy. SquareFreeString:

Problem Description:
Given a string, determine whether there is a substring that is squared (e.g., ww).

Constraints:
s.size ≤ 50

Solution:
O(s.size ** 4)

Code:

class SquareFreeString {
 public:
   std::string isSquareFree(std::string s) {
     for (size_t i = 0; i < s.size(); ++i) {
       for (size_t j = i + 1; j <= s.size(); ++j) {
         if (j - i & 1) continue;
         if (s.substr(i, j - i >> 1) == s.substr(i + (j - i >> 1), j - i >> 1)) return "not square-free";
       }
     }
     return "square-free";
   }
};

Medium. SortingSubsets

Problem Description:
You are given an array a.
You can choose a subset, and permute however you like.
Print the minimal size of subset you must choose to sort the array.

Constraints:
1 ≤ a.size ≤ 50
1 ≤ a[i] ≤ 100

Solution:
Sort a as b.
Let x be the number of different values in a and b at same positions.
It is impossible to sort a with less than subset of size x, but it is always possible with x.

Code:

class SortingSubsets {
 public:
  int getMinimalSize(std::vector<int> a) {
    std::vector<int> b = a;
    std::sort(b.begin(), b.end());
    return std::accumulate(a.begin(), a.end(), 0, [&, i = 0](int x, int y) mutable { return x + (y != b[i++]); });
  }
};

Hard. ThueMorseGame

Problem Description:
Alice and Bob plays game in turn.
There is initially a pile of stones (N stones).
At a player's turn, one should:
1. Pick a number x within 1..M, where x does not exceed the size of the current pile
2. Remove x stones from the pile
3. If the current number of stones is zero, this player wins. However, if the bitcount of the current number of stones is odd, this player loses.
Find the winner when both play optimally.

Constraints:
1 ≤ n ≤ 5e8
1 ≤ m ≤ 50

Solution:
DP, but accelerate with bit operation.

Code:

class ThueMorseGame {
 public:
   std::string get(int n, int m) {
     uint64_t straight = (1ULL << m) - 1;
     uint64_t dp = straight;
     for (int i = 0; i <= n; ++i) {
       dp = dp << 1 | __builtin_popcount(i) % 2 | dp != straight;
       dp &= straight;
     }
     if (dp & 1) return "Alice";
     return "Bob";
   }
};