PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07 and everule1
Tester: sky_nik
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Graph traversal
PROBLEM:
You have two piles of stones, one initially empty and one with a stone of weight W.
You also have infinite stones of N types, the i-th type having value A_i.
Do the following:
- Choose an index i, and add a stone of weight A_i to the lighter pile.
After this, it should now be the heavier pile.
Find a sequence of at most 7500 moves that uses every type of stone at least once.
N\leq 500 and A_i, W \leq 5000.
EXPLANATION:
As a first step, let’s simplify the situation a bit.
Rather than dealing with two piles of stones, let’s define d = |W_1 - W_2| to be the difference between the weights of the piles, and work with only this difference.
Our operation then changes as follows:
- Choose an index i such that A_i \gt d, and replace d with A_i - d.
The A_i\gt d condition comes from the fact that we need to make the difference ‘negative’ to transfer which of the piles is the heavier one, and of course the new difference is |d - A_i| = A_i - d.
Since we’re forced to choose an A_i that’s larger than d in every step, in some sense our limiting quantity is A_1, the lightest stone type.
In particular, if we ever want to use A_1, we need to end up with d \lt A_1; otherwise it’s impossible.
On the other hand, observe that if we do end up with d\lt A_1, there’s a trivial strategy that uses every stone: use A_1, then A_2, then A_3, and so on till A_N.
After all, if 0 \lt d \lt A_i, then 0 \lt A_i - d \lt A_i, and we’re given that A_i \lt A_{i+1} so we can definitely operate with A_{i+1} the next move.
In other words, as long as we’re able to get down to d \lt A_1, we can use N more moves and ensure that every type is used.
All that remains is to figure out whether we can reach d\lt A_i (and a sequence of moves to reach there).
For that, we use the fact that constraints are small: N\leq 500 and A_i \leq 5000.
Consider a graph on A_N vertices (representing the differences 1, 2, 3, \ldots, A_N, where for each x and index i such that A_i \gt x, there’s an edge between x and A_i - x.
This graph encapsulates all the possible moves that can be made, and has N\cdot \max(A) edges at most, which is 500\cdot 5000 = 2.5\cdot 10^6, not too large.
We start out with a difference of W, so simply perform a search (using BFS/DFS or a DSU) in the connected component of W to find whether it includes a value smaller than A_1.
If it does, find a path to it from W (which uses at most \max(A) \leq 5000 moves), and once you’re there use N more moves as noted earlier to ensure that every type gets used at least once.
If every value in the component of W is \geq A_1, no solution exists.
TIME COMPLEXITY:
\mathcal{O}(N\cdot \max(A)) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, w; cin >> n >> w;
vector <int> a(n);
for (auto &x : a) cin >> x;
int max = a[n - 1] + 1;
vector <bool> vis(max + 1, false);
vector <int> par(max + 1, -1);
vis[w] = true;
par[w] = -2;
queue <int> q;
q.push(w);
while (!q.empty()){
int u = q.front(); q.pop();
for (int i = 0; i < n; i++){
if (a[i] > u && !vis[a[i] - u]){
vis[a[i] - u] = true;
q.push(a[i] - u);
par[a[i] - u] = i;
}
}
}
for (int i = 0; i < a[0]; i++){
if (vis[i]){
vector <int> ord;
while (par[i] != -2){
ord.push_back(par[i] + 1);
i = a[par[i]] - i;
}
reverse(ord.begin(), ord.end());
for (int i = 1; i <= n; i++){
ord.push_back(i);
}
// cout << 1 << "\n";
// return;
cout << ord.size() << "\n";
for (auto x : ord){
cout << x << " ";
}
cout << "\n";
return;
}
}
cout << -1 << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t; while (t--) {
int n, w;
cin >> n >> w;
vector<int> a(n);
for (auto& ai : a) {
cin >> ai;
}
int mn = w;
vector<int> argmin, path;
set<int> seen;
auto dfs = [&](auto&& self, int w) -> void {
seen.insert(w);
if (mn > w) {
mn = w;
argmin.clear();
copy(path.cbegin(), path.cend(), back_inserter(argmin));
}
for (int i = 0; i < n; ++i) {
if (a[i] > w && !seen.count(a[i] - w)) {
path.push_back(i);
self(self, a[i] - w);
path.pop_back();
}
}
};
dfs(dfs, w);
if (mn >= a[0]) {
cout << -1 << '\n';
} else {
cout << argmin.size() + 2 * n << '\n';
for (const auto i : argmin) {
cout << i + 1 << ' ';
}
for (int i = 1; i <= n; ++i) {
cout << i << ' ' << i << ' ';
}
cout << '\n';
}
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n, w = map(int, input().split())
a = list(map(int, input().split()))
par = [0]*5005
par[w] = n+1
que = [w]
for x in que:
for i in reversed(range(n)):
if a[i] <= x: break
if par[a[i]-x] == 0:
par[a[i]-x] = i+1
que.append(a[i]-x)
mn = min([i for i in range(5005) if par[i] > 0])
if mn >= a[0]:
print(-1)
continue
path = []
x = mn
while x != w:
path.append(par[x])
x = a[par[x]-1] - x
print(len(path) + n)
path = path[::-1]
for i in range(n): path.append(i+1)
print(*path)
