Moving Skeleton - Editorial
The problem
Find distinct positive integers below such that their sum is or say that it is not possible.
Existence of a solution
Let’s try to determine whether a solution exists, before we look for it.
What is the smallest possible sum we can form with distinct positive integers below ? We should always take the smallest possible numbers, so the answer is .
What is the largest possible sum we can form with distinct positive integers below ? It should be clear that we should always take the largest available numbers, so this sum should be .
Let the first sum be , and the second sum be . We will now reveal a startling fact. A solution always exists as long as ! We will show this by using a constructive proof.
The key idea for this solution is that we should start with a sum of , and then increase any number that can still be increased by one without violating the two constraints (the limit of , and all numbers must be distinct), to transition our sum into . The proof that it will find all the sums is simple; we increment the sum by each time, so this will cover all sums from to .
Consider any particular set that satisfies the two constraints (no element exceeds and all elements are distinct). We will now show how we can increase the sum of the elements in this set by .
If the sum is equal to , then it must be formed by the elements in some order, because we showed earlier that this is the maximum sum possible. It is obvious that there is no way to increment anything here without violating either one of the constraints.
If the sum is not equal to , then it must be lower than . Now, we have two cases. Either the maximum element in our set is less than , or it is equal to . Let’s call the value of this maximum element .
If the is not equal to , then we are done; just increment , because incrementing it will not break either constraint (since , then , and obviously doesn’t exist in our set otherwise would not be the maximum). This will increase our sum by one.
If the maximum element is equal to , then the remaining elements must not all be in consecutive order, otherwise our set will be equal to which contradicts our assumption that the sum is not equal to . If it is not in consecutive order, then there must be at least one element with a value of for which does not exist in the set. Simply increment this element.
Hence we have showed that it is possible to make all the sums from to . In fact, our proof was constructive, in that it presented an algorithm for us to generate a set with the required sum.
Note that implementing this algorithm the way it was stated in the proof is not a good idea, as it is still rather slow. We will describe an algorithm that makes use of the above facts, that will run quickly enough and can solve this problem if implemented correctly.
First, let’s take an example input. Let and and .
Consider the smallest possible sum, which is .
Let’s increment the largest element, which is , and then we will have .
Keep incrementing the largest element while the sum is still not , and the largest element does not yet exceed . It will look like that:
We’ve reached the maximum possible value for that element, but we haven’t reached the sum yet, so we will now start incrementing the second-largest element. It will look similar to this:
Now, we stop here, because we have already reached the sum. At this point, the algorithm is obvious; start with the smallest possible elements, and then increment it from the largest to the smallest while the element can still be incremented. Stop when the sum is reached.
This clearly runs in time proportional to the number of times we can increment a number, which is approximately , but at the same time it is also bounded by the maximum required sum, which in our case is . Hence, this runs in for each test case, but it is still too slow.
Optimization to
In order to make it fast enough, we actually only need to make one more observation; we don’t actually need to increment by one each time. Instead, we can immediately check, for each number, if we set it to the maximum value, what the sum will be. If this sum still does not exceed , then we can simply set the element to the maximum and then move on to the next number. Otherwise, using some basic arithmetic, we can easily find out which number a particular number should become, in order for the sum to be exactly .
Applying this basic optimization allows us to bring our runtime to per test case, which is fast enough.
Make sure to take a few precautions when writing your code, because particular values can possibly exceed the range of a 64-bit integer. If you are having trouble getting your code accepted, you can refer to either the solution of the setter or the tester, both of which use this algorithm.
This problem is interesting because there are so many possible solutions to it. Can you find a different solution, other than the one described here?
Solution:
#include
#include
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc, b;
long long int n, k, tmin, tmax, sum, mxset;
cin >> tc;
while (tc--) {
cin >> n >> k >> b;
tmin = 0;
tmax = 0;
for (int i = 0; i < b; i++)
tmin += i+1;
for (int i = 0; i < b; i++) {
tmax += k-i;
if (tmax >= n) break;
}
if (tmin <= n && n <= tmax) {
sum = b*(long long int)(b+1)/2;
mxset = 0;
for (int i = b; i >= 1; i--) {
if (sum-i+(k-mxset) >= n) {
std::cout << n-sum+i;
for (long long int j = 1; j < b-mxset; j++) cout << ' ' << j;
for (long long int j = k-mxset; j < k; j++) cout << ' ' << j+1;
cout << '\n';
break;
} else {
sum -= i;
sum += (k-mxset);
mxset++;
}
}
}
else cout << -1 << '\n';
}
}