USACO 2022 February Contest Bronze Division - Photoshoot 2

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We will want to store for each value its position in the initial and the final array and then when we go through the values in the second array, we check whether it's at the front or at the target position, and if it is behind, we will have to move it and mark it as moved.

We will also store another array, swapped, which tells us whether we moved a certain number or not in order to avoid having to run a brute force algorithm for the given problem.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

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

    vector<int> v(n), v2(n);

    for(int i = 0; i < n; i++)
        cin >> v[i], v[i]--;
    for(int i = 0; i < n; i++)
        cin >> v2[i], v2[i]--;

    vector<int> pos(n), pos2(n); // position arrays 
    for(int i = 0; i < n; i++)
    {
        pos[v[i]] = i;
        pos2[v2[i]] = i;
    }

    vector<int> swapped(n);

    // for each value we check if it's in front and if not, we add a swap and jump over potential holes
    int ans = 0;
    int pos_first = 0;
    for(int i = 0; i < n; i++) // in second array
    {
        while(pos_first < n && swapped[v[pos_first]] == 1)
            pos_first++;
        if(v[pos_first] == v2[i])
            pos_first++;
        else
        {
            ans++;
            swapped[v2[i]] = 1;
        }
    }

    cout << ans;
    return 0;
}

n = int(input())
v = list(map(int, input().split()))
v = [x - 1 for x in v]
v2 = list(map(int, input().split()))
v2 = [x - 1 for x in v2]
swapped = [0] * n
ans = 0
pos_first = 0
for i in range(n):
    while pos_first < n and swapped[v[pos_first]] == 1:
        pos_first += 1
    if pos_first < n and v[pos_first] == v2[i]:
        pos_first += 1
    else:
        ans += 1
        swapped[v2[i]] = 1
print(ans)