Table of Contents

ExplanationImplementation

Official Editorial (C++)

Explanation

Since NN can go all the way up to 10510^5, it would take much too long to iterate through all possible values of (i,j)(i, j).

Instead, let's iterate through all possible values of jj and determine how many values of ii can be paired with it. To do this, we need to determine the number of elements in AA that are equal to BCjB_{C_j} for all j∈[1,N]j \in [1, N]. This can be done with a map and some pre-calculation.

Official Solution

The official solution goes through all values of ii instead, but it's pretty much the same idea.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <iostream>
#include <map>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


int main() {
	int n;

Java

import java.io.*;
import java.util.*;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		read.readLine();  // n not needed
		int[] a = Arrays.stream(read.readLine().split(" "))
		              .mapToInt(Integer::parseInt)
		              .toArray();

Python

input()  # n not needed
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]


# Stores for each number in A how many times it appears in total
occ_a_num = {}
for i in a:
	if i not in occ_a_num:
		occ_a_num[i] = 0

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum