USACO 2020 January Contest Bronze Division - Photoshoot

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Brute force all possible values for first position, as everything else can be uniquely deduced.

Source codes

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

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

int main()
{
    ifstream cin("photo.in");
    ofstream cout("photo.out");

    int n;
    cin >> n;

    vector<int> v(n);

    for(int i = 1; i < n; i++)
        cin >> v[i];

    vector<int> ans(n+1);
    for(int i = 1; i <= n; i++)
    {
        vector<int> pos(n+1);
        set<int> perm;
        pos[1] = i;
        for(int j = 1; j < n; j++)
            pos[j+1] = v[j] - pos[j];
        bool ok = 1;
        for(int j = 1; j <= n; j++)
        {
            perm.insert(pos[j]);
            if(pos[j] >= 1 && pos[j] <= n);
            else
                ok = 0;
        }
        if(ok && perm.size() == n)
        {
            ans = pos;
            break;
        }
    }

    for(int i = 1; i <= n; i++)
    {
        cout << ans[i];
        if(i != n)
            cout << " ";
    }
    return 0;
}

with open("photo.in", "r") as fin:
    tokens = fin.read().split()
n = int(tokens[0])
v = [0] * (n + 1)
for i in range(1, n):
    v[i] = int(tokens[i])
ans = []
for start in range(1, n + 1):
    pos = [0] * (n + 1)
    pos[1] = start
    for j in range(1, n):
        pos[j+1] = v[j] - pos[j]
    ok = True
    perm = set()
    for j in range(1, n + 1):
        if pos[j] < 1 or pos[j] > n:
            ok = False
            break
        perm.add(pos[j])
    if ok and len(perm) == n:
        ans = pos
        break
with open("photo.out", "w") as fout:
    fout.write(" ".join(str(ans[i]) for i in range(1, n+1)))