USACO 2024 December Contest Bronze Division - Farmer John's Favorite Permutation#
Problem link: here
Video link: here
Solution Author: Stefan Dascalescu
Problem Solution#
In order to solve this problem, one has to first rely on a brute force solution to see some patterns related to how the answer changes and we will observe that in a valid solution, the number of distinct values in the array they give us has to be \(N-1\) or \(N-2\) and if the number is \(N-1\), then we just append the missing value to the end of the initial values, otherwise we can do some casework based on the two missing values.
One key observation is the fact that we can reverse engineer the entire process based on the two values we have at first and this will help us find the answer in the end.
Source codes#
The source codes in C++ and Python can be seen below.
#include <bits/stdc++.h>
using namespace std;
int main()
{
/* brute force code attached here, could have been done much easier
map<vector<int>, vector<int> > mp;
int N = 8;
vector<int> v;
for(int i = 0; i < N; i++)
v.push_back(i+1);
do{
vector<int> sol;
int cnt1 = 0;
int L = 0, R = N-1;
while(L < R)
{
if(v[L] > v[R])
{
if(v[L+1] == 1)
cnt1++;
sol.push_back(v[L+1]);
L++;
}
else
{
if(v[R-1] == 1)
cnt1++;
sol.push_back(v[R-1]);
R--;
}
}
set<int> ss;
for(int i = 0; i < sol.size(); i++)
ss.insert(sol[i]);
if(mp.find(sol) == mp.end())
{
mp[sol] = v;
if(v[0] != 1)
{
for(int i = 0; i < sol.size(); i++)
cout << sol[i] << " ";
cout << '\n';
for(int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << '\n';
}
}
}while(next_permutation(v.begin(), v.end()));
*/
/*
1 5 3 2 7 8 1
4 5 3 2 7 8 1 6
we know 4 and 6 start out, we want the last value at the end so let's see
4......6
we find 1 so it's before 6
4.....16
we find 5 so it's after 4
45....16
we find 3 so it's after 5
453...16
we find 2 so it's after 3
4532..16
we find 7 so it's after 1
45327816
*/
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
for(; t; t--)
{
int n;
cin >> n;
set<int> actuals;
vector<int> v(n-1);
long long sum = 1LL * n * (n+1) / 2;
for(int i = 0; i + 1 < n; i++)
{
cin >> v[i];
actuals.insert(v[i]);
sum -= v[i];
}
if(actuals.size() == n-1)
{
if(sum != 1)
{
for(int i = n-2; i >= 0; i--)
cout << v[i] << " ";
cout << sum << '\n';
}
else
{
cout << -1 << '\n';
}
}
else
{
if(actuals.size() < n-2)
{
cout << -1 << '\n';
continue;
}
vector<int> answer(n);
for(int i = 1; i <= n; i++)
if(actuals.find(i) == actuals.end())
{
if(answer[0] == 0)
answer[0] = i;
else
answer[n-1] = i;
}
int L = 0;
int R = n-1;
for(int i = 0; i + 1 < n; i++)
{
if(answer[L] > answer[R])
{
answer[L+1] = v[i];
L++;
}
else
{
answer[R-1] = v[i];
R--;
}
}
vector<int> sol;
L = 0, R = n-1;
while(L < R)
{
if(answer[L] > answer[R])
{
sol.push_back(answer[L+1]);
L++;
}
else
{
sol.push_back(answer[R-1]);
R--;
}
}
bool ok = 1;
for(int i = 0; i < sol.size(); i++)
if(sol[i] != v[i])
ok = 0;
if(ok == 0)
{
cout << -1 << '\n';
continue;
}
for(int i = 0; i < n; i++)
{
cout << answer[i];
if(i != n-1)
cout << " ";
}
cout << '\n';
}
}
return 0;
}
import sys
data = sys.stdin.read().split()
idx = 0
t = int(data[idx])
idx += 1
output_lines = []
for _ in range(t):
n = int(data[idx])
idx += 1
actuals = set()
v = []
sum_total = n * (n + 1) // 2
for i in range(n - 1):
x = int(data[idx])
idx += 1
v.append(x)
actuals.add(x)
sum_total -= x
if len(actuals) == n - 1:
if sum_total != 1:
# Output the sequence v in reverse order, then the missing number, v[::-1] reverses the list.
line = " ".join(str(x) for x in v[::-1]) + " " + str(sum_total)
output_lines.append(line)
else:
output_lines.append("-1")
else:
if len(actuals) < n - 2:
output_lines.append("-1")
continue
answer = [0] * n
for i in range(1, n + 1):
if i not in actuals:
if answer[0] == 0:
answer[0] = i
else:
answer[n - 1] = i
L = 0
R = n - 1
for i in range(n - 1):
if answer[L] > answer[R]:
answer[L + 1] = v[i]
L += 1
else:
answer[R - 1] = v[i]
R -= 1
sol = []
L = 0
R = n - 1
while L < R:
if answer[L] > answer[R]:
sol.append(answer[L + 1])
L += 1
else:
sol.append(answer[R - 1])
R -= 1
ok = True
for i in range(len(sol)):
if sol[i] != v[i]:
ok = False
break
if not ok:
output_lines.append("-1")
continue
output_lines.append(" ".join(str(x) for x in answer))
sys.stdout.write("\n".join(output_lines))