Official

B - Hit and Blow Editorial by en_translator


This problem is an exercise of for statement. If you couldn’t solve this problem because if you were not used to the usage of for statement, we recommend you to understand the solution for this problem and learn how to use for statement.
In the problem, you are asked to print the following two values:

  1. The number of integers \(i\) such that \(A_i = B_i\).
  2. The number of pairs of integers \((i, j)\) such that \(A_i = B_j, i \neq j\).

For 1., it can be solved by the following for statement. The computational complexity is \(\mathrm{O}(N)\) because the loop is iterated \(N\) times.

for i in range(N):
  if A[i] == B[i]:
    answer1 += 1

Next, 2. can be calculated with nested for loops with the indices \(i\) and \(j\).

for i in range(N):
  for j in range(N):
    if A[i] == B[j] and i != j:
      answer2 += 1

As you can see, the key is to nest for statements.
We will consider the computational complexity. The outer loop iterates \(N\) times, and the inner one loops \(N\) times as well, so the innermost if statement is evaluated \(N^2\) times. Therefore, the complexity is \(\mathrm{O}(N^2)\).
In this problem, \(N \leq 1000\), so \(\mathrm{O}(N^2)\) works fast enough for getting AC (Accepted). (In general, it is said that the program is sufficiently fast to get AC if the argument of \(\mathrm{O}\) is less than \(10^7\).) Therefore, the problem has been solved.

Here is a sample code in Python.

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

answer1 = 0
answer2 = 0

for i in range(N):
  if A[i] == B[i]:
    answer1 += 1

for i in range(N):
  for j in range(N):
    if A[i] == B[j] and i != j:
      answer2 += 1

print(answer1, answer2, sep="\n")

Alternatively, there is a faster \(\mathrm{O}(N)\) solution that uses an associative array. Briefly speaking, in the refined solution the elements of B are recorded to an associative array so that we can obtain “the position of \(x\) in \(B\)” in an \(\mathrm{O}(1)\) time, so that the double loop is reduced to a single loop.
If you want to tackle Problem C and further, this kind of idea is required.

Here is a sample code of \(\mathrm{O}(N)\) solution in Python.

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

answer1 = 0
answer2 = 0

B_dict = dict()
for i, b_i in enumerate(B):
  B_dict[b_i] = i

for i in range(N):
  if A[i] == B[i]:
    answer1 += 1

for i in range(N):
  if A[i] in B_dict:
    if B_dict[A[i]] != i:
      answer2 += 1

print(answer1, answer2, sep="\n")

posted:
last update: