Edit Distance (Problem A, 2018 ICPC Asia Jakarta Regional Contest, 2018)
Time limit: 1 sec
Memory limit: 256MB
Author: Alham Fikri Aji, Jonathan Irvin G.

# Problem Statement

A binary string is a non-empty sequence of 0’s and 1’s, e.g., 010110, 1, 11101, etc. The edit distance of two binary strings $S$ and $T$, denoted by $edit(S, T)$, is the minimum number of single-character edit (insert, delete, or substitute) to modify $S$ into $T$. For example, the edit distance of 0011 and 1100 is 4, i.e. 0011 → 011 → 11 → 110 → 1100. The edit distance of 1100101 and 1110100 is 2, i.e. 1100101 → 1110101 → 1110100.

Ayu has a binary string $S$. She wants to find a binary string with the same length as $S$ that maximizes the edit distance with $S$. Formally, she wants to find a binary string $T_{max}$ such that $|S| = |T_{max}|$ and $edit(S, T_{max}) \geq edit(S, T')$ for all binary string $T'$ satisfying $|S| = |T'|$.

She needs your help! However, since she wants to make your task easier, you are allowed to return any binary string $T$ with the same length as $S$ such that the edit distance of $S$ and $T$ is more than half the length of $S$. Formally, you must return a binary string $T$ such that $|S| = |T|$ and $edit(S, T) > \frac{|S|}{2}$.

Of course, you can still return $T_{max}$ if you want, since it can be proven that $edit(S, T_{max}) > \frac{|S|}{2}$ for any binary string $S$. This also proves that there exists a solution for any binary string $S$. If there is more than one valid solution, you can output any of them.

# Input

Input contains a binary string $S$ ($1 \leq |S| \leq 2000$).

# Output

Output in a line a binary string $T$ with the same length as $S$ that satisfies $edit(S, T) > \frac{|S|}{2}$.

# Sample Input #1
```
0011
```
# Sample Output #1
```
1100
```
# Explanation for the sample input/output #1

As illustrated in the example above, the edit distance of `0011` and `1100` is 4. Since $4 > \frac{4}{2}$, `1100` is one of the valid output for this sample.

# Sample Input #2
```
1100101
```
# Sample Output #2
```
0011010
```

Sample inputs:
0011

1100101

Sample outputs:
1100

0011010

# Solution Analysis
Analysis author: Suhendry Effendy

If the problem requires us to find a binary string $T$ of the same length as the input $S$ which has the largest edit distance to $S$, then this problem can be more challenging. Fortunately, that’s not the case; this problem only asks us to find a binary string $T$ of the same length as input which has an edit distance strictly larger than half of $S$’s length.

There are many possible outputs which satisfy the requirement. Here, we will discuss a simple one.

First, count how many $0$ and $1$ does $S$ has. If $S$ has more $0$ than $1$, then simply set $T$ to be all $1$. If $S$ has more $1$ than $0$, then simply set $T$ to be all $0$. The problem is what we should do with the case where the number of $0$ and $1$ are equal. In this case, we can set $T$ to be either `01111..` or `10000..` depends on the first character of $S$, i.e. $S_1$. Specifically, if $S_1$ is `0`, then $T$ is `10000..`; otherwise, $T$ is `01111..`

Special judge (C++ scorer):
#include <bits/stdc++.h>
using namespace std;

int wa(int status = 0) {
  cout << "WA" << endl;
  cerr << status << endl;
  return 0;
}

int ac() {
  cout << "AC" << endl;
  return 0;
}

bool is_binary_string(const string& str) {
  for (int i = 0; i < str.size(); ++i) {
    if (str[i] != '0' && str[i] != '1') {
      return false;
    }
  }
  return true;
}

int edit_distance(const string& s, const string& t) {
  vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1));
  for (int i = 0; i <= t.size(); ++i) {
    dp[s.size()][i] = t.size() - i;
  }
  for (int i = 0; i <= s.size(); ++i) {
    dp[i][t.size()] = s.size() - i;
  }
  for (int i = s.size() - 1; i >= 0; --i) {
    for (int j = t.size() - 1; j >= 0; --j) {
      if (s[i] == t[j]) {
        dp[i][j] = dp[i + 1][j + 1];
      } else {
        dp[i][j] = min(dp[i + 1][j + 1], min(dp[i + 1][j], dp[i][j + 1])) + 1;
      }
    }
  }
  return dp[0][0];
}

int checks(istream& tc_in, istream& tc_out, istream& con_out) {
  string S, T;

  tc_in >> S;
  if (!(con_out >> T)) {
    return wa(1);
  }
  if (S.size() != T.size()) {
    return wa(2);
  }
  if (!is_binary_string(T)) {
    return wa(3);
  }
  if (edit_distance(S, T) <= (int)S.size() / 2) {
    return wa(4);
  }
  if (con_out >> T) {
    return wa(5);
  }
  return ac();
}

int main(int argc, char* argv[]) {
  ifstream tc_in(argv[1]);
  ifstream tc_out(argv[2]);
  ifstream con_out(argv[3]);

  return checks(strcmp(argv[1], "-") == 0 ? cin : tc_in,
                strcmp(argv[2], "-") == 0 ? cin : tc_out,
                strcmp(argv[3], "-") == 0 ? cin : con_out);
}