USACO 2023 December Contest Silver Division - Cycle Correspondence

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

First, we observe that the numbers that don't occur in either of the arrays can be labeled in the same way. For every other number, we have to rotate one of the cycles in such a way that we maximize the number of overlaps when we look from the perspective of both arrays.

In order to do that, we keep an array which keeps the delta between the positions of the values in both of the cycles, as well as the frequency of each position. We do this for both cycles and add to the answer the maximum frequency obtained, something we will do for both orientations of the arrays (normal and reversed).

The algorithm will be linear in runtime.

Source code

The source code in C++ can be seen below.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> v(k), v1(k), poz(n + 1, -1), poz1(n + 1, -1), c(n + 1, 0);

    for (int i = 0; i < k; i++) {
        cin >> v[i];
        poz[v[i]] = i;
    }

    for (int i = 0; i < k; i++) {
        cin >> v1[i];
        poz1[v1[i]] = i;
    }

    int ret = 0;
    for (int i = 0; i < k; i++) {
        if (poz[v1[i]] != -1) {
            c[(i - poz[v1[i]] + k) % k]++;
        }
    }

    ret = *max_element(c.begin(), c.end());
    fill(c.begin(), c.end(), 0);

    for (int i = k - 1; i >= 0; i--) {
        if (poz[v1[i]] != -1) {
            c[(k - 1 - i - poz[v1[i]] + k) % k]++;
        }
    }

    ret = max(ret, *max_element(c.begin(), c.end()));
    for (int i = 1; i <= n; i++) {
        if (poz1[i] == -1 && poz[i] == -1) {
            ret++;
        }
    }

    cout << ret << '\n';
    return 0;
}