Judging Troubles (Editorial)

The task is to count which and how many judging results were produced by the DOMjudge and $Kattis$ systems. If a result $s$ was produced $a$ times by DOMjudge and $b$ times by $Kattis$, then the number of matching results $s$ is $min(a,b)$.

First, we use a map map<string, int> cnt to count the occurrences of each result $s$ produced by DOMjudge. Then, for each result $s$ produced by $Kattis$, we decrease $cnt[s]$ by one (if cnt[s] > 0). The number of such decrements will be equal to the maximum number of results that matched between the two systems.

Example

Let's count the number of results produced by the DOMjudge and $Kattis$ systems in the given example.

There were 4 matching results.

Algorithm implementation

Declare a map $cnt$, where $cnt[s]$ will store the number of times the result $s$ was produced by the DOMjudge system.

map<string, int> cnt;

Read the number of submissions $n$.

cin >> n;

Count the number of results produced by the DOMjudge system.

for (i = 0; i < n; i++)
{
  cin >> s;
  cnt[s]++;
}

Process the results from the $Kattis$ system.

res = 0;
for (i = 0; i < n; i++)
{
  cin >> s;

If the result $s$ was found in DOMjudge (cnt[s] > 0), decrease $cnt[s]$ by one and increase the counter $res$ — the number of results that could have been the same in both systems.

  if (cnt[s] > 0)
  {
    cnt[s]--;
    res++;
  }
}

Print the answer.

cout << res << endl;

Java implementation

import java.util.*;

public class Main
{
  static Map<String, Integer> cnt = new HashMap<String, Integer>();
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
  
    for(int i = 1; i <= n; i++)
    {
      String s = con.next();
      if (!cnt.containsKey(s))
        cnt.put(s, 1);
      else
        cnt.put(s, cnt.get(s) + 1);
    }

    int res = 0;
    for(int i = 1; i <= n; i++)
    {
      String s = con.next();
      if (cnt.containsKey(s) && cnt.get(s) > 0)
      {
        cnt.put(s, cnt.get(s) - 1);
        res++;
      }
    }
    
    System.out.print(res);
    con.close();  
  }
}

Python implementation

Read the number of submissions $n$.

n = int(input())

Count the number of results produced by the DOMjudge system.

cnt = {}
for _ in range(n):
  s = input()
  cnt[s] = cnt.get(s, 0) + 1

Process the results from the $Kattis$ system.

res = 0
for _ in range(n):
  s = input()
  if cnt.get(s, 0) > 0:
    cnt[s] -= 1
    res += 1

Print the answer.

print(res)