MCC 2025 Editorial

Go through each column and count the number of grass cells. The answer is the minimum number of grass cells in a column.

• Python
• C++

• n, m = [int(x) for x in input().split()]
  grid = [input() for _ in range(n)]
  grass_col_count = [0] * m
  for i, row in enumerate(grid):
      for j, cell in enumerate(row):
          if cell == ".":
              grass_col_count[j] += 1
  print(min(grass_col_count))
  

• #include <bits/stdc++.h>
  using namespace std;
  
  int main() {
      int n, m;
      cin >> n >> m;
      vector<string> s(n);
      for (auto& i : s) cin >> i;
  
      int minv = n;
      for (int j = 0; j < m; j++) {
          int cnt = 0;
          for (int i = 0; i < n; i++) {
              if (s[i][j] == '.') cnt++;
          }
          minv = min(minv, cnt);
      }
      cout << minv << "\n";
      return 0;
  }
  

Let $s = c_1 + \cdots + c_N$ and $m = \max c_i$. If $s - m \ge m - 1$, the answer is $s$. Otherwise, the answer is $2(s - m) + 1$.

Intuition

The only time we cannot use all sticks is when we have too many sticks of the same colour, forcing us to put two of them together. Suppose colour $1$ is the most frequent stick colour. Let $s = c_1 + c_2 + \cdots + c_N$ be the total number of sticks. Then, the “worst” sequence we can make is $(1, ?, 1, \ldots, ?, 1)$ (where $?$s are not $1$), where colour $1$ appears one more time than the total number of other colours, i.e. $c_1 - 1 = s - c_1$.

So, intuitively:

• If $c_1 - 1 \le s - c_1$, we can use all sticks and the answer is $s$.
• Otherwise, we reduce colour 1 to be one more than $s - c_1$, so the answer is $(s - c_1 + 1) + (s - c_1) = 2(s - c_1) + 1$.

Formal proof

Suppose we have $s = c_1 + c_2 + \cdots + c_N$ sticks in total. Since the order of groups does not matter, assume $c_1$ is the maximum $c_i$.

Consider the easier question: When is it (not) possible to use all $s$ sticks? If color $i$ appears $c_i$ times, to avoid two adjacent color $i$ sticks, we must have at least $c_i - 1$ sticks of other colors between them. Mathematically, we must have $s - c_i \ge c_i - 1$ for all $i$. It is enough if the condition holds for the max $c_i$, i.e. $s - c_1 \ge c_1 - 1$.

If $s - c_1 \ge c_1 - 1$ holds, does that mean we can always use all $s$ sticks? The answer is yes. Put all $c_1$ colour 1 sticks in a row. This separates the row into $c_1 + 1$ sections.

• For each of the other colours $i$, since $c_i \le c_1 < c_1 + 1$, we can put the $c_i$ sticks in different sections, guaranteeing that they are not adjacent.
• We also need to ensure the colour 1 sticks are separated. We need $c_1 - 1$ other sticks to separate the $c_1$ colour 1 sticks. Since $s - c_1 \ge c_1 - 1$, we have enough sticks to fill in all gaps.

Back to the original problem, we can reduce it to: “What is the max number of sticks we can take such that $s - m \ge m - 1$ where $m = \max c_i$?”

Observation: In an optimal solution, at most one group of sticks is not fully taken.

• Proof: Suppose there are two groups of sticks not fully taken with colours $a$ and $b$, and the optimal sequence of stick colours is $(x_1, x_2, \ldots, x_K)$. If $x_1 \ne b$, a longer valid sequence is $(a, b, x_1, \ldots, x_K)$. Otherwise, $x_1 = b \ne a$, so a longer valid sequence is $(b, a, x_1, \ldots, x_K)$. In both cases, we can make a longer sequence, contradiction.

Therefore, if we cannot take all sticks ($s - m < m - 1$), we should only remove sticks of one colour, and we must reduce $m$ by removing the most frequent colour.

In conclusion, if $s - m \ge m - 1$ already holds, the answer is $s$. Otherwise, we reduce $m$ to $s - m + 1$, which gives the answer $(s - m + 1) + (s - m) = 2(s - m) + 1$.

• Python
• C++

• def solve():
      _n = int(input())
      c = [int(x) for x in input().split()]
      c_max = max(c)
      c_sum = sum(c)
      if c_sum - c_max >= c_max - 1:
          print(c_sum)
      else:
          print((c_sum - c_max) * 2 + 1)
  
  
  t = int(input())
  for _ in range(t):
      solve()
  

• #include <bits/stdc++.h>
  using namespace std;
  
  int main() {
      int t;
      cin >> t;
      while (t--) {
          int n;
          cin >> n;
  
          long long maxv = 0, sum = 0;
          for (int i = 0; i < n; i++) {
              long long a; cin >> a;
              maxv = max(maxv, a);
              sum += a;
          }
  
          if (maxv >= sum - maxv + 1) {
              cout << (sum - maxv) * 2 + 1 << "\n";
          } else {
              cout << sum << "\n";
          }
      }
      return 0;
  }
  

Task 1–3 ($N \le 500$)

Try every possible triple of candy packs $i, j, k$ ($1 \le i < j < k \le N$) and check whether the condition is satisfied. Tasks 1–2 are small enough to be brute-forced by hand.

Time complexity: $O(N^3)$.

Task 4 ($N \le 5000$)

From this point onward, since the order of colors within a pack does not matter, we normalize each pack by ensuring $a_i \le b_i$ (swapping the values if necessary). This makes counting and lookup more convenient.

Instead of checking all triples of packs directly, observe that once we choose the first two packs, the colors required for the third pack are completely determined by the condition. Therefore, we iterate over all pairs of packs $i$ and $j$ with $i < j$, compute the colors that the third pack must have, and then add the number of remaining packs matching those colors to our total. Each valid triple is counted three times through this process, so we divide the final count by 3.

To quickly find how many packs have a specific color pair, we store the frequency of each normalized pair in a hash map (a dict in Python or std::unordered_map in C++).

Time complexity: $O(N^2)$.

Task 5 ($a_i, b_i \le 2$)

When colors are restricted to $1$ and $2$, there are only two possible valid triples (up to ordering of the packs): $(1, 1), (1, 2), (2, 2)$ and $(1, 2), (1, 2), (1, 2)$.

Let $c_{xy}$ be the number of packs with the color pair $(x, y)$. The first type contributes $T_1 = c_{11} c_{12} c_{22}$ triples, while the second type contributes $T_2 = \binom{c_{12}}{3} = \frac{c_{12}(c_{12} - 1)(c_{12} - 2)}{6}$.

The final answer is $T_1 + T_2$.

Time complexity: $O(N)$.

Task 6 ($N \le 200\,000$)

Generalizing Task 5, we apply the same counting strategy to every distinct color pair $(x, y)$ with $x \ne y$. For each such pair, compute the number of valid triples as in Task 5 and sum them all together. Again, use a hash map to maintain frequencies efficiently.

Time complexity: $O(N)$.

• Python
• C++

• import math
  from collections import Counter
  
  n = int(input())
  packs = [(int(x) for x in input().split()) for _ in range(n)]
  # packs = [[1, 2], [2, 3], [4, 1], ...]
  packs = [(a, b) if a <= b else (b, a) for a, b in packs]
  counter = Counter(packs)
  ans = 0
  for (a, b), count in counter.items():
      if a == b:
          continue
      ans += counter[(a, a)] * count * counter[(b, b)]
      ans += math.comb(count, 3)
  print(ans)
  

• #include <bits/stdc++.h>
  using namespace std;
  
  int main() {
      ios::sync_with_stdio(false);
      cin.tie(0);
  
      int n = 0;
      cin >> n;
  
      unordered_map<int, long long> aa;
      map<pair<int, int>, long long> ab;
  
      for (int i = 0; i < n; i++) {
          int a, b;
          cin >> a >> b;
          if (a > b) swap(a, b);
          if (a == b) {
              if (aa.find(a) == aa.end()) aa[a] = 0;
              aa[a]++;
          }
          else {
              pair<int, int> p = make_pair(a, b);
              if (ab.find(p) == ab.end()) ab[p] = 0;
              ab[p]++;
          }
      }
      long long ans = 0;
      for (auto [p, cnt] : ab) {
          if (cnt >= 3) {
              ans += (long long)(cnt * (cnt - 1) * (cnt - 2)) / 6;
          }
  
          if (aa.find(p.first) != aa.end() && aa.find(p.second) != aa.end()) {
              ans += cnt * aa[p.first] * aa[p.second];
          }
      }
      cout << ans << "\n";
      return 0;
  }
  

Task 1 - 3 ($M = 4$)

The common additional constraint across these tasks is that $M=4$. Moreover, there are only 26 different lowercase characters (‘a’ to ‘z’). Hence, we can enumerate all the possible word of length 4, which totals to $26^4 \approx 4 \times 10^5$.

While enumerating each candidate word, we need to compute its distance to each given word. Observe that, by definition of anagram, the order of characters in a string does not matter. Therefore, for each string, we can count the occurences of each letter (‘a’ to ‘z’) and compute the sum of absolute difference between the occurence counts of both string. This quantity is twice actual distance between them.

To select the lexicographically smallest optimal string, we may store all candidate strings that achieve the minimum total distance, and then sort them using the standard library of the programming language of your choice. Time complexity for computing the distance is $O(nm)$, coming mainly from counting letter occurrences.

Key observations from these tasks:

1. Order of characters in a string does not matter.
2. The distance between two string is sum of absolute difference between the occurence counts of both string divide by 2.

Task 4 (Given strings are anagram)

Since the given strings are anagram, the answer is simply the the lexicographically smallest string that is an anagram to any of the given string. To solve this, note again that the order of characters does not matter. Therefore, letters that appear earlier in alphebet should be placed earlier in the final string. As a result, sorting any one of the given strings yields the correct answer.

Key observation from the tasks:

1. Sort the string before printing the answer (for a fixed set of letter occurences, this guarantees that it is the lexicographical smallest)

Task 5 - 7 (Strings consists of only ‘a’ and ‘b’)

With the observation from Task 4, the final answer must consists of some number of ‘a’ characters followed by some number of ‘b’ characters. Formally, if the final string contains $i$ occurences of ‘a’, then there must be $m - i$ occurences of ‘b’, since its total length must be $m$. This lead to the key idea: enumerate all possible values of $i$ (i.e. the number of character ‘a’ in the final string).

For each choice of $i$, construct the corresponding candidate string (with $i$ ‘a’s followed by $m - i$ ‘b’s) and compute its total distance to the given strings using the same method applied in Tasks 1–4. Select the candidate with the minimum total distance. In case of ties, prioritize the larger value of $i$.

Task 8 - 10 (No Additional Constraints)

Since there are 26 letters, method from task 5-7 does not works. There are 2 different greedy solution for these tasks. We present both solution and intuition on their correctness then follows by a rigorous proof.

Group 1: No road is damaged

The problem setup can be modelled as a graph, where each city is a node and each road is an edge with weight equal to its length. Let $G$ be the graph of the Magical Charming Conurbation before the apocalypse, and $G'$ be the graph after the apocalypse.

Since no roads are damaged during the apocalypse, the answer will be the same for all queries. This answer is the number of cities reachable from city $1$ regardless of distance. Hence, we can perform a depth first search (DFS) or breadth first search (BFS) on graph $G$ to find the size of the connected component containing city $1$, which is our answer.

Time complexity: $O(N+M)$

Group 2: $N, M, Q \leq 5000$

We answer each query independently. For each query, we can run a single-source shortest path algorithm (e.g. Dijkstra’s algorithm) from node $1$ on graph $G$. Let $A$ be the set of nodes that can be reached from node $1$ in under distance $K$.

Now, a node is reachable if and only if it can be reached from one of the nodes in $A$ by travelling on the edges in $G'$. We can check how many nodes are reachable by finding which component each node belongs to in $G'$ (using DFS, BFS or Disjoint Set Union (DSU)), and checking if each node belongs to a component that contains a node which is in $A$.

Time complexity: $O(QN \log M)$

Group 3: No additional constraints

Sort the queries. Just like in the solution for Group 2, run a single-source shortest path algorithm from node $1$ on graph $G$, and also find which component each node belongs to in $G'$. We create a list $B$ of all the nodes, sorted by their distance from node $1$.

For each query, find the reachable nodes within distance K that weren’t reachable in the previous query by shifting a pointer on list $B$ (maintain the first index $i$ such that node $B_i$ cannot be reached from node $1$ within distance $K$). For each of these newly reachable nodes, we check if its connected component in $G'$ has previously already been reachable. If it wasn’t reachable previously, we add the size of its connected component to the answer.

Time complexity: $O((N+M) \log N + Q)$

Subtask 1

The only increasing subsequence are of length 1 (the individual elements in the array), so the answer is the sum of all elements in $A$.

Time complexity: $O(N)$

Subtask 2

Loop through all the $2^N$ subsequences of $A$ and check if each of these subsequences is good in $O(N)$.

Time complexity: $O(N \cdot 2^N)$

Subtask 3

The only possible increasing subsequences with length greater than 1 will be of the form $[1,2,3]$. So we just need to count the number of subsequences of $A$ that are equal to $[1,2,3]$. For each index $i$, we find the number of 1s to the left of it (inclusive) $L_i$, and the number of 3s to the right of it (inclusive) $R_i$. This can be done in $O(N)$ time. Now for every index $i$ such that $A_i = 2$, add $2L_iR_i$ to the answer. Don’t forget the 1-length subsequences, just add the sum of elements of $A$ to the answer.

Time complexity: $O(N)$

Subtask 4

Consider counting the contribution of each median to the answer (this hints at the general solution). We iterate over each element at index i as the median, then we iterate over $k = 1$ to $\min(i, N-i-1)$, and add $\binom{i}{k} \binom{N-i-1}{k}$ to the answer. Here $k$ represents the number of elements to either side of the median element. Finally, just add A_i * contribution of i to the answer. Bonus: In fact, rewriting as $\binom{i}{k} \binom{N-i-1}{k}$ as $\binom{i}{k} \binom{N-i-1}{N-i-1-k}$, the contribution of element i is simply $\binom{N-1}{\min(i, n-i-1)}$. Therefore, we can solve this subtask in $O(N)$ time.

Time complexity: $O(N^2)$ or $O(N)$

Subtask 5

Similar to subtask 4, consider counting the contribution of each median. Let $dp(i, j)$ be the number of increasing subsequences of length j ending at index i.

Base case: $dp(i, 1) = 1$.

Transition: Add $dp(k, j-1)$ to $dp(i,j)$ for all $k < i, A_k < A_i$.

This dp table can be computed in $O(N^3)$ time.

We can define $dp2(i,j)$ as the number of increasing subsequences of length $j$ starting at index $i$. This table can be generated in a similar manner to $dp$.

Now the contribution of the element at index i is the sum of $dp(i, k) \cdot dp2(i, k)$ for all $k$ satisfying $1 \le k \le \min(i, N-i-1) + 1$.

Time complexity: $O(N^3)$

Subtask 6

Notice that the bottleneck of our naive DP solution is the $O(N)$ transition. We can use $N$ Fenwick trees, where each Fenwick tree corresponds to a value of $j$. At index $i$ of the array stored in the Fenwick tree, the sum of $dp(k, j)$ for all $k$ such that $A_k = i$ is stored. We can now calculate the transition in $O(\log N)$ time, by querying the prefix sum up to index $A_i-1$ in Fenwick tree $j-1$ when calculating $dp(i,j)$.

Time complexity: $O(N^2 \log N)$

Space complexity: $O(N \max(A_i))$

Subtask 7

We can perform coordinate compression on the values of $A$, then apply our solution to Subtask 6.

Time complexity: $O(N^2 \log N)$

Space complexity: $O(N^2)$

Footnote on constant factors

When writing the model solution for this problem, the initial code took 50 seconds to run although it had a time complexity of $O(N^2 \log N)$, running even slower than some $O(N^3)$ solutions. After some constant optimization I managed to get it to run in 1.5 seconds. Here are the optimizations that caused a significant speedup, from most to least significant:

• For C++, turning on -O2 optimization when compiling.
• Using std::unordered_map for coordinate compression and precomputing the compressed array instead of compressing on the spot when needed. This reduced the number of map accesses from $O(N^2)$ to $O(N)$.
• The second dimension of the dp array only needs to have size $\frac{N}{2}+1$ instead of $N+1$
• When computing the modulo some places, we can do a -= mod instead of a %= mod. This is quicker as the subtraction operation is faster than the modulo operation.