The goal is to partition the array into subarrays s.t. there is a minimum # of subarrays, and the partition is valid. Note that there are only 20 distinct characters in the string. Consider a graph where the nodes are those distinct characters. For every pair of adjacent characters, add an edge from the left one to the right one. A partition can be represented by removing some of these edges. It can be shown that this graph is only valid iff there are no cycles (because if there is a cycle there is no topsort and therefore no alphabet). Thus this problem can be reduced to the problem “minimum feedback arc set”, a well known problem that has a $$$n^2 2^n$$$ bitmask dp solution on the topsort.

The obvious dijkstra approach is too slow, because there can be $$$n^2$$$ edges. The way you can fix this is by changing your state. Let $$$dist[i][j]$$$ be the minimum total distance cows need to walk s.t. a cow with color $$$j$$$ is at position $$$i$$$. Your answer is $$$dist[n][color[n]]$$$. The transitions are:

1. The current cow can move one to the left (cost 1)
2. The current cow can move one to the right (cost 1)
3. The current cow can pass the message to the cow at that location if they are compatible (cost 0)

You can solve this shortest path problem with 0-1 BFS. Another implementation detail is that the last edge taken must be of type 3. You can encode another dimension in your state, which represents a boolean value that is true if the last edge was of type 3 and false otherwise. This solution runs in $$$O(n*k)$$$ time.

Let $$$locs[i]$$$ represent the set of unique positions that cow $$$i$$$ would go to in the first $$$k$$$ moves. The sum of the sizes of $$$locs[i]$$$ is $$$\leq 2*k$$$, so you can store and compute it naively. Consider the inverse of the final permutation formed. You can solve for each cycle in that permutation independently. Let's call "hitting" a node $$$i$$$ visiting everything $$$locs[i]$$$. Each node in the cycle hits some (constant sized) range of other elements in the cycle. It also goes to some prefix of $$$locs[i]$$$ for some node $$$i$$$. You can do a sliding window on $$$locs$$$ to calculate the answer for every node in the cycle in amortized linear time. The final complexity is $$$O(n+k)$$$.

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

//Created by Maria Chrysafis
#include <iostream>
#include <fstream>

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

//Created by Maria Chrysafis
#include <iostream>
#include <fstream>


#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Problem1DanceMooves {
public:
  vector<vector<int>> adj;
  vector<bool> hasVisited;
  int N, K;
  vector<int> vis;
  void dfs(int src){
    hasVisited[src] = true;
    vis.push_back(src);
    for(int j: adj[src]){
      if(!hasVisited[j]){
        dfs(j);
      }
    }
  }
  void solve(std::istream& in, std::ostream& out) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    in >> N >> K;
    hasVisited.resize(N);
    adj.resize(N);
    //first perform the swaps
    vector<int> arr(N);
    vector<set<int>> myMap(N);
    for(int i = 0; i < N; i++){
      arr[i] = i;
      myMap[i].insert(i);
    }
    vector<pair<int,int>> swaps(K);
    for(int i = 0; i < K; i++){
      int a,b;
      in >> a >> b;
      a--;
      b--;
      myMap[arr[a]].insert(b);
      myMap[arr[b]].insert(a);
      swap(arr[a], arr[b]);
    }
    for(int i = 0; i < N; i++){
      adj[i].push_back(arr[i]);
    }
    vector<vector<int>> cc;
    for(int i = 0; i < N; i++){
      if(!hasVisited[i]){
        dfs(i);
        cc.push_back(vis);
        vis.clear();
      }
    }
    vector<int> ans;
    int pr[N];
    for(int i = 0; i < cc.size(); i++){
      set<int> s;
      for(int j: cc[i]){
        s.insert(myMap[j].begin(),myMap[j].end());
      }
      for(int j: cc[i]){
        pr[j] = s.size();
      }
    }
    for(int j: pr){
      out << j << endl;
    }
  }
};

int main() {
	Problem1DanceMooves solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

//Created by Maria Chrysafis
#include <iostream>
#include <fstream>

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Problem2NoTimeToPaint {
public:
  vector<int> pref(string s){
    vector<int> v;
    v.resize(s.length());
    map<char,bool> used;
    int counter = 0;
    for(int i = 0; i < s.length(); i++){
      if(!used[s[i]]){
        used[s[i]] = true;
        counter++;
      }
      for(char c = s[i]; c <= 'Z'; c++){
        if(c == s[i]) continue;
        if(used[c]){
          used[c] = false;
        }
      }
      v[i] = counter;
    }
    return v;
  }
  void solve(std::istream& in, std::ostream& out) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N,Q;
    in >> N >> Q;
    string s;
    in >> s;
    vector<int> Pref = pref(s);
    reverse(s.begin(),s.end());
    vector<int> Suf = pref(s);
    reverse(Suf.begin(),Suf.end());
    while(Q--){
      int l,r;
      in >> l >> r;
      l--;
      r--;
      if(l == 0 && r == s.length()){
        out << 0 << endl;
      }else if(l == 0){
        out << Suf[r + 1] << endl;
      }else if(r == s.length()){
        out << Pref[l - 1] << endl;
      }else{
        out << Pref[l - 1] + Suf[r + 1] << endl;
      }
    }
  }
};


int main() {
	Problem2NoTimeToPaint solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

//Created by Maria Chrysafis
#include <iostream>
#include <fstream>

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Problem3SpacedOut {
public:
  vector<vector<int>> mat;
  int N;
  int MAX(){
    int counter = 0;
    for(int i = 0; i < N; i++){
      int cur = 0;
      int pos = 0;
      for(int j = 0; j < N; j++){
        if((abs(i - j)) % 2 == 0){
          cur += mat[i][j];
        }
        pos += mat[i][j];
      }
      cur = max(cur, pos - cur);
      counter += cur;
    }
    return counter;
  }
  int MAX1(){
    int counter = 0;
    for(int i = 0; i < N; i++){
      int cur = 0;
      int pos = 0;
      for(int j = 0; j < N; j++){
        if((i + j) % 2 == 0){
          cur += mat[i][j];
        }
        pos += mat[i][j];
      }
      cur = max(cur, pos - cur);
      counter += cur;
    }
    return counter;
  }
  void solve(std::istream& in, std::ostream& out) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    in >> N;
    mat.resize(N);
    for(int i = 0; i < N; i++){
      mat[i].resize(N);
      for(int j = 0; j < N; j++){
        in >> mat[i][j];
      }
    }
    int ANS = max(MAX(),MAX1());
    vector<vector<int>> new_mat = mat;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        new_mat[j][i] = mat[i][j];
      }
    }
    mat = new_mat;
    ANS = max(MAX(),max(ANS,MAX1()));
    out << ANS << endl;
  }
};


int main() {
	Problem3SpacedOut solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

After finally understanding the statement, we get that we can have at most 20 letters. This usually points to a solution using bitmasks, but how? First things first, let’s talk about the first subtask (which meant we have at most 8 letters if I remember correctly). We assign a “score” to each letter, from 1 to 8. We go through each permutation. Say we have string “abdcefghab” and the values a = 1, b = 2, and so on. The string will become “1234567812”. Now, how do we count the number of times we have to say the alphabet? Well, when we get from a bigger to a smaller value, we simply add 1 to “ans”. The answer will be ans + 1. Now, we can’t simply go through the string for each permutation, but we can make the observation that we only care about consecutive pairs. We count the frequency of each pair. For example, in “abc” we count (a, b) and (b, c) once. Now, when we have a permutation, we simply add the frequency of the pairs that are of the form (nr1, nr2), where nr1 >= nr2. But, how do we solve the full problem? We will solve it using bitmask dp. Our mask will consist of 0’s (indicating we don’t consider that letter and put a “_” instead) and 1’s (we consider that letter). For example, “Mildred” and our mask considers letters “d” and “i”, we have i_d_d. Now, iterate through each letter in the mask and suppose it has the greatest “score”. Let’s denote it as “ch”. This means that if we encounter pairs of (ch, some other letter in the mask), we have to “split” the sequence and count the number of times we do this. The recurrence is dp[mask] = the number of splits + dp[mask]-(1<<(the bit corresponding to ch)); Note that when I was referring to pairs, I was considering it in the same way as in the first subtask solution, consecutive letters. The overall time complexity is O(2^n * nr_distinct_letters^2).

On this problem, I’ve got 12/13 tests. I had an observation, which made sense in my mind, but I don’t know if it’s completely true and I just missed a case, or if it’s false and got lucky with the tests. The observation was that you only care about the first and the last cows (I can’t remember what the problem was about) of each type. Why? Suppose you want to go from type “a” to type “c”, using type “b”. Say we have something like a__cb__b__ (and you can go from a to b and from b to c). In this case, you choose the first b. In fact, you always choose the first b (unless b is at position n, which ends the process). My explanation was that if the next character you go to is before the first b, then you choose the first b, to minimize the steps you go back (you are obligated to take at least n — 1 steps, the backward steps are the problem), and if c is after the first b, you again go to the first b, to go to c for “free” (I only consider the cost of backward steps). So we only care about 2 cows of each type, create a graph, and do Dijkstra. (I picked 2 cows, because, as I’ve said earlier, you may want to end the process by going to the nth position). I have no idea if this is correct, feel free to counter my argument.