PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic programming
PROBLEM:
For an array B of length M, define
B is said to be good if it has some rearrangement B' for which f(B', X) = Y.
You’re given an array A, as well as the parameters X and Y.
Count the number of prefixes of A that are good.
EXPLANATION:
Given X and Y, when can an array be good?
To understand that, first look at X\bmod M. Note that:
- If X \lt M, then X\bmod M = X.
- If X\geq M, then X\bmod M \lt M.
Note that in either case, after taking the modulo with M, the resulting value is both strictly smaller than M, and not larger than X.
Now, let’s look at some array B.
Let M = \min(B).
Then, no matter how B is rearranged, the result of repeatedly reducing X modulo the elements of B will definitely result in a final value that’s \lt M; since whenever the minimum element is processed the result will fall below it, and then no further operation can increase the result.
In particular, if M \leq Y, it’s definitely impossible to end up with a value of Y, since we can only have something smaller than M.
So, for an array to be good at all, all its elements must be strictly larger than Y.
Now, suppose \min(B) \gt Y.
We need to check whether some rearrangement of B can give a result that equals Y.
Observe that it’s enough to find some subset of B that can give a result of Y when rearranged: once Y has been attained using this subset as a prefix, all the remaining values won’t change it anymore anyway.
Now, we can use dynamic programming.
Let dp_s be a boolean variable denoting whether getting a result of Y is possible via some subset of B.
Initially, dp_X = 1 and everything else is 0.
Now, process values of s in descending order, from X down to 0.
For each s,
- If dp_s = 0, we can’t make this subset, so ignore it and carry on.
- Otherwise, we can try to turn this s into an even smaller value (since we can’t increase it - this is also why we’re processing s in descending order).
This is simple: iterate over each index i of B, and set dp_{s \bmod B_i} to true.
In the end, we only need to check if dp_Y is true or false.
This DP runs in \mathcal{O}(|B| \cdot X) time.
Now, while we could run the above DP for each prefix of A, that would result in a solution that’s \mathcal{O}(N^2 X) which is too slow for N\sim 400 and X\sim 5\cdot 10^4.
First, we can make one simple optimization.
Let R be the first index such that A_R \leq Y (and R = N+1 if no such index exists).
Then any prefix \geq R definitely cannot be good, so we can just ignore them all!
Now we only consider prefixes till R-1, meaning all values are \gt Y.
Next, look at what the DP itself is doing for a single prefix: it’s telling us whether the prefix has a subset of elements for which attaining a value of Y is possible.
Let L be the first time such a subset exists.
Then, every prefix \geq L will also have this subset in it, so attaining a value of Y is always possible within them too!
This means, if we just find the two indices L and R, the answer will simply be all the indices L, L+1, \ldots, R-1.
Finding R is trivial using a simple loop, so we focus on finding L.
There are a couple of ways of finding L quickly.
The intended approach is to modify the earlier dynamic programming slightly.
Recall that we had dp_s be a boolean variable, denoting whether s is attainable or not.
Let’s change the definition a bit: dp_s will denote the smallest index i such that the prefix A[1\ldots i] has a subset that can form s (with dp_s = \infty if it’s impossible to form it).
Initially, dp_X = 0 and dp_s = \infty for all other s.
Once again, we process s in descending order.
For the transitions:
- If dp_s = \infty, ignore s since we can’t form it at all.
- Otherwise, we again use each A_i to try and make s smaller.
If we make s\bmod A_i, we need to update dp_{s\bmod A_i} with the value \max(i, dp_s).
This is because dp_s contains the smallest prefix needed to obtain s, and then we’re extending this further to include index i in order to form s\bmod A_i.
Clearly, the complexity of this remains \mathcal{O}(NX).
The index L we’re looking for now is nothing but dp_Y.
An alternate method is to just binary search for the first prefix which can attain Y, using the initial boolean DP as the check function.
This adds an extra \mathcal{O}(\log N) to the complexity but requires basically no additional thinking.
The complexity is \mathcal{O}(NX\log N), and if you have a reasonable enough implementation it will likely get AC; though suboptimal implementations with heavy constant factor may have some issues.
Once the indices L and R are known,
- If L \geq R, no prefix is valid and the answer is 0.
- Otherwise, the valid prefixes are L, L+1, \ldots, R-1, for R-L in total.
TIME COMPLEXITY:
\mathcal{O}(NX) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, x, y; cin >> n >> x >> y;
vector <int> a(n);
for (auto &z : a) cin >> z;
vector <int> dp(x + 1, INF);
dp[x] = 0;
for (int i = x; i >= 0; i--){
for (int j = 0; j < n; j++){
int v = i % a[j];
dp[v] = min(dp[v], max(dp[i], j));
}
}
int mn = INF;
vector <int> ans;
for (int k = 0; k < n; k++){
mn = min(mn, a[k]);
if (y < mn && k >= dp[y]){
ans.push_back(k);
}
}
cout << ans.size() << "\n";
for (auto z : ans){
cout << (z + 1) << " ";
}
cout << "\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;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, x, y = map(int, input().split())
a = list(map(int, input().split()))
b = [(a[i], i) for i in range(n)]
b = list(reversed(sorted(b)))
dp = [n+1]*(x+1)
# dp[i] = smallest prefix to make i
dp[x] = 0
for v, i in b:
for j in range(x+1):
if dp[j] == n+1: continue
dp[j % v] = min(dp[j % v], max(dp[j], i+1))
if dp[y] == n+1: print(0)
else:
R = 0
while R < n and a[R] > y: R += 1
dp[y] = max(dp[y], 1)
if dp[y] > R: print(0)
else:
print(R - dp[y] + 1)
print(*range(dp[y], R+1))