7860. Judging Troubles
The
organizers of NWERC decided to improve the automatic judging of submissions in
the contest and are now using two systems: DOMjudge and Kattis. Each submission
is evaluated by both systems, and the results are compared to ensure the
systems are consistent. However, a failure occurred while setting up
communication between the systems: the jury now only knows the sets of results
from both systems, but not which result corresponds to which submission.
Your task
is to help determine how many results could have matched between the systems.
Input. Consists of:
·
A single integer n (1 ≤ n ≤ 105) – the number of
submissions;
·
n lines – the results from the DOMjudge system in arbitrary order;
·
n lines – the results from the Kattis system, also in arbitrary order.
Each line is a result string of length between 5 and 15
characters, consisting only of lowercase Latin letters.
Output. Print a single number – the maximum number of
results that could have matched in both systems.
|
Sample input |
Sample output |
|
5 correct wronganswer correct correct timelimit wronganswer correct timelimit correct timelimit |
4 |
SOLUTION
data
structures
Algorithm analysis
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)