0w1

SRM 630 Div2

Easy. DoubleLetter

Problem Description:
You are given a string S.
Each time you can choose two consecutive letters that are identical, and remove them.
After removal, both sides are connected, i.e., the result still remains to be a string.
You are asked to return the whether it is possible to repeat the process until the string is empty.

Constraints:
1 ≤ S.size ≤ 50

Solution:
It is intuitive that removing such substrings in any order produces the same result.
Hence simulate the process until no more moves can be made.
Complexity is O(N ** 3), which is sufficient for the constraints.

Code:

class DoubleLetter {
 public:
   std::string ableToSolve(std::string S) {
     if (S.size() == 0u) return "Possible";
     for (size_t i = 0; i + 1 <= S.size(); ++i) {
       if (S[i] == S[i + 1]) {
         return ableToSolve(S.substr(0, i) + S.substr(i + 2));
       }
     }
     return "Impossible";
   }
};

Medium. Egalitarianism3Easy

Problem Description:
There are N cities and some bidirectional edges connect them.
Note that the graph is a tree.
Find the size of the maximum subset such that every pair of cities in the subset has the same distance.

Constraints:
1 ≤ N ≤ 10
1 ≤ W[i] ≤ 1000

Solution:
Preprocess pairwise distance with Floyd Warshall's algorithm.
Then enumerate every possible subset and evaluate.

Code:

class Egalitarianism3Easy {
 public:
  int maxCities(int n, std::vector<int> a, std::vector<int> b, std::vector<int> len) {
    std::vector<std::vector<int>> dist(n, std::vector<int>(n, 0x3f3f3f3f));
    for (int i = 0; i < a.size(); ++i) {
      dist[a[i] - 1][b[i] - 1] = dist[b[i] - 1][a[i] - 1] = len[i];
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        for (int k = 0; k < n; ++k) {
          dist[j][k] = std::min(dist[j][k], dist[j][i] + dist[i][k]);
        }
      }
    }
    int res = 1;
    for (int s = 0; s < 1 << n; ++s) {
      if (__builtin_popcount(s) <= res) continue;
      std::vector<int> set;
      for (int i = 0; i < n; ++i) {
        if (s >> i & 1) {
          set.emplace_back(i);
        }
      }
      bool ng = false;
      for (int i = 0; i < set.size(); ++i) {
        for (int j = i + 1; j < set.size(); ++j) {
          ng |= dist[set[i]][set[j]] != dist[set[0]][set[1]];
        }
      }
      if (!ng) res = __builtin_popcount(s);
    }
    return res;
  }
};

Hard. SuffixArrayDiv2

Problem Description:
Given a string S, you can compute suffix array for S, denoted as sa(S).
Return whether there is a string T such that sa(T) == sa(S) and T < S.

Constraints:
1 ≤ S.size ≤ 50

Solution:
Let P be the minimum string such that sa(P) == sa(S).
Then T exists iff P < S.
Note that P.size == T.size == S.size must hold.
Hence we construct sa(S) first. The most naive method is sufficient for the constraints.
Then we construct rank array rk for sa(S), i.e.:
rk[sa[i]] = i for each i
Then we examine each element in sa in order.
The first index in sa is independent of any other elements, i.e. no other index will force it to be larger.
Hence we will assign ans[sa[0]] the minimum possible character, which is 'a' in this case.
As we visit elements in sa, we will update ans[sa[i + 1]] with ans[sa[i]], and try not to increase ans[sa[i + 1]].
However, ans[sa[i + 1]] can choose not to increase iff its next suffix is greater than the next suffix of ans[sa[i]].
In the end we will construct P as desired.

Code:

class SuffixArrayDiv2 {
 public:
   std::string smallerOne(std::string s) {
     std::vector<int> sa(s.size()); {
       std::iota(sa.begin(), sa.end(), 0);
       std::sort(sa.begin(), sa.end(), [&](int i, int j) { return s.substr(i) < s.substr(j); });
     }
     std::vector<int> rk(s.size() + 1, -1); {
       for (int i = 0; i < sa.size(); ++i) {
         rk[sa[i]] = i;
       }
     }
     std::string lex_min(s.size(), '_'); {
       lex_min[sa[0]] = 'a'; // independent
       for (int i = 0; i + 1 < s.size(); ++i) { // it must make difference here if the next suffix is not less
         lex_min[sa[i + 1]] = lex_min[sa[i]] + (rk[sa[i] + 1] >= rk[sa[i + 1] + 1]);
       }
     }
     return lex_min == s ? "Does not exist" : "Exists";
   }
};