Pho Restaurant (Problem H, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 2 sec
Author: Ammar Fathin Sabili

# Problem Statement

As you may know, pho is one of the most common dishes in Hanoi. It contains a special kind of flour noodles, meat (usually beef or chicken), and green onions dipped in a tasty broth. Vietnamese people enjoy pho for breakfast, lunch, dinner, and even light meals. For tourists, trying pho is a must, especially in the cold of Hanoi.

You own a phở bò (beef pho) restaurant in Vietnam with $n$ tables, numbered 1 to $n$. The 2024 ICPC Asia Pacific Championship contestants are currently in your restaurant. Each contestant is initially seated at one of the tables and there is at least one contestant initially seated at each table.

Each contestant would like to order one of the two most well-known kinds of pho: *phở tái* (pho with medium-rare beef) or *phở chín* (pho with well-done beef). The initial state of table $i$ is represented by the binary string $S_i$. The length of $S_i$ is the number of contestants initially seated at table $i$. The $j$-th character of $S_i$ is 0 if the $j$-th contestant initially seated at the table would like to order a *phở tái*, and 1 if the contestant would like to order a *phở chín*.

To make it easier to track the orders, the restaurant wants the contestants seated at the same table to have the same order. That is, for each table, at least one of the following must be true:

- All of the contestants seated at that table would like to order a *phở tái*.
- All of the contestants seated at that table would like to order a *phở chín*.

To satisfy this requirement and the contestants’ orders, you want to move zero or more contestants to a different table. The destination table must be one of the $n$ tables. In other words, you must not add new tables. There is no limit to the number of contestants that can be seated at the same table. After moving the contestants, the following condition should be satisfied by each table: either there is no contestant seated at that table or all contestants seated at that table would like to order the same dish.

Since moving contestants takes some time, you would like to compute the minimum number of contestants you need to move.

# Input

The first line of input contains one integer $n$ ($2 \leq n \leq 100\,000$). Each of the next $n$ lines contains a binary string. The $i$-th line contains $S_i$ ($1 \leq |S_i| \leq 200\,000$). The sum of $|S_i|$ across all $i$ does not exceed $500\,000$.

# Output

Output an integer representing the minimum number of contestants you need to move.

# Sample Input #1
```
4
11101101
00
10001
10
```
# Sample Output #1
```
5
```
### _Explanation for the sample input/output #1_

You can move

- the seventh contestant initially seated at table 1 to table 3,
- the fourth contestant initially seated at table 1 to table 4,
- the first and fifth contestants initially seated at table 3 to table 1, and
- the first contestant initially seated at table 4 to table 1.

You will then have all contestants seated at table 1 ordering *phở chín*, while the contestants seated at the other tables will be ordering *phở tái*. It can be shown that you cannot move fewer than 5 contestants to satisfy the requirements.

# Sample Input #2
```
2
101010
010101
```
# Sample Output #2
```
6
```
# Sample Input #3
```
5
0000
11
0
00000000
1
```
# Sample Output #3
```
0
```

Sample inputs:
4
11101101
00
10001
10

2
101010
010101

5
0000
11
0
00000000
1

Sample outputs:
5

6

0

# Solution Analysis
Analysis author: Ammar Fathin Sabili

Consider an easier version of this problem where we can add new tables. Clearly, it is optimal if, for the tables that are seated by different orders, we move the _minority_, i.e. the lesser orders between the two types of pho, to a new table.

One can assume that this strategy also works for the original problem. However, it only works if existing tables accommodate the minorities. This will not be an issue if we can have both types of pho to be a non-minority on some tables. But in case non-minorities are just one type (which also means there is just one type of minority), we need to choose a table that is dedicated to accommodating minorities instead. As this table will move the non-minority orders, it is not optimal to choose more than one dedicated table. Thus, a single careful iteration will suffice.

There is also an alternative solution that uses DP-Bitmask where we have four bits to represent: there is a table where we need to move ‘0’, there is a table where we need to move ‘1’, there is a table dedicated to consist of only ‘0’, and there is a table dedicated to consist of only ‘1’.

All solutions run in $O(n + \sum_{i=1}^{n} |S_i|)$.

Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to tcframe format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}