cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2020 · EasySorting

Two Stamp Albums

Autumn Tournament (2020)

Submission name: albums.cpp

Solve in Editor →

Problem summary

Two stamp albums contain distinct stamp numbers within each album. Find the numbers appearing in both albums and list them in increasing order.

Input

n and m; n numbers from the first album; m numbers from the second.

Output

The intersection size k, then its k numbers in increasing order on the next line.

Constraints

1 ≤ n,m ≤ 100000; stamp numbers are between 1 and 10^9.

Worked example

Original statement sample.

Input

5 6
2 10 5 13 4
6 2 13 3 10 1

Output

3
2 10 13

Solution analysis

  1. Sort both albums. Keep indices i and j pointing at the smallest not-yet-processed number in each sorted list.
  2. If the numbers match, save the common value and advance both pointers. Otherwise advance the pointer with the smaller number: that value cannot occur later in the other sorted list, whose current and future values are already larger.
  3. The sample sorts to [2,4,5,10,13] and [1,2,3,6,10,13]. The matching values encountered by the scan are 2,10,13. They are already in increasing order, so no final sorting is necessary.

Why it works

Each pointer advance either records an equality or safely discards a value too small to match any remaining value. The scan therefore finds every common stamp exactly once.

Complexity: O(n log n + m log m) time for sorting, followed by O(n+m) scanning; O(n+m) space for the albums and result.

Watch out. The input lists are not sorted initially. Print zero and an empty second line when there are no shared stamps. Uniqueness is guaranteed within each album.

Commented C++17 solution

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>first(n),second(m),common;
    for(int&value:first){
        cin>>value;
    }
    for(int&value:second){
        cin>>value;
    }
    sort(first.begin(),first.end());
    sort(second.begin(),second.end());
    int i=0,j=0;
    // Discard only the smaller value; sorted order makes it impossible to match later.
    while(i<n&&j<m){
        if(first[i]==second[j]){
            common.push_back(first[i]);
            i++;
            j++;
        }
        else if(first[i]<second[j]){
            i++;
        }
        else{
            j++;
        }
    }
    cout<<common.size()<<'\n';
    for(int index=0;index<static_cast<int>(common.size());index++){
        if(index>0){
            cout<<' ';
        }
        cout<<common[index];
    }
    cout<<'\n';
}

Source: Arena Olimpiici ↗