PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: ranya0706
Tester: tabr
Editorialist: ranya0706
DIFFICULTY:
Med-Hard
PREREQUISITES:
None
PROBLEM:
For an array A, define f_m(A) = \sum_{i=1}^N A_i \cdot i^m
You’re given N and C. Array A is said to be good if its length is at most N, it is non-decreasing, and:
- f_0(A) = N
- f_1(A) = C
Find any good array that minimizes f_2(A).
EXPLANATION:
If the current sequence A satisfies f_0(A) = N (call this condition (1)) and f_1(A) = C (condition (2)), it can be observed that there are two operations that will make the conditions still satisfied:
- (x,y,z)\Rightarrow (x+1,y-2,z+1)
- (x,y,z)\Rightarrow (x-1,y+2,z-1)
Here, (x, y, z) refers to three contiguous elements in A.
Note that we’re not considering the non-decreasing condition for now.
Let’s call the first operation "sub", which will make the middle number smaller and the front and back number bigger.
Note that the sub operation changes f_2(A) = \sum_{i=1}^K A_i\cdot i^2 by
which upon cancellation is just 2.
Similarly, call the second operation "add", which will make the middle number bigger, the front and back number smaller and decreases f_2(A) by 2.
Obviously, these two operations are inverses of each other.
Next, we prove that the answer sequence is unique and can become a sequence (hereinafter referred to as a frog sequence) that satisfies conditions (1) and (2), and contains less than or equal to two positive integers.
Further, if there are two positive integers, they will be adjacent.
Part 1: The answer sequence can be transformed into a frog sequence. The proof is as follows:
Let the current sequence satisfy (1) and (2). We’ll also extend the sequence to have length exactly N by appending zeros to it (note that this doesn’t change any of the f_m(A) values.
Suppose the current answer sequence is
where,1\leq l\leq r=K\leq N
When we do "add" on (a_l,a_{l+1},a_{l+2}),(a_{l+1},a_{l+2},a_{l+3}),\dots,(a_{r-2},a_{r-1},a_r), we can see that this is equivalent to a_l\Rightarrow a_l-1,a_{l+1}\Rightarrow a_{l+1}+1,a_{r-1}\Rightarrow a_{r-1}+1,a_r \Rightarrow a_r+1
For the answer sequence, we keep repeating this process, and it will eventually become a frog sequence.
Part 2: The answer sequence is unique. The proof is as follows:
Let’s use p, x, y to represent the frog sequence, which is of the form
(0,0,\dots,a_{p-1}=x,a_p=y,\dots,0,0)
We then have:
So,
which means that C+x \equiv 0 \pmod N.
However, along with x \lt N, this uniquely fixes x = \left\lceil \frac C N \right\rceil \times N - C.
According to Part 1, we know that the frog sequence must be obtained from the answer sequence after continuous "add" operations.
Because "add" and "sub" operations are inverse, we can definitely restore the answer sequence through a certain number of "sub" operations.
We greedily use as few "sub" operations as possible to prevent the sequence from ever decreasing, due to the fact that each "sub" operation increases f_2(A) by 2.
Consider the following process:
- If x\leq y, no operation is required.
- If x > y, we can see that doing
"sub"on x must be better than doing"sub"on y. - Let t be the number of times we do
"sub"on A_{p-1}, ensuring that it is the smallest number that makes a_{p-1}\le a_p. - Then, we can obtain a sequence of the form (0,0,\dots,t,x-2t,y+t,\dots,0,0) where$
x-2t\le y+t,x-2t+2>y+t-1.- If t \le x-2t, the construction is complete.
- If t > x-2t, the equation is as follows:
\begin{cases} t>x-2t \Rightarrow x<3t\\ x-2t+2>y+t-1 \Rightarrow x>y+3t-3 \end{cases} \Rightarrow y+3t-3<x<3t \
Because x is an integer, y+3t-2\le x\le3t-1 \Rightarrow y+3t-2 \le 3t-1 \Rightarrow y\le 1.
Since y is an integer and y>0, the value of y can only be 1. Substitute y=1 into the inequality
y+3t-3<x<3t,
to obtain 3t-2<x<3t \Rightarrow x=3t-1.
So, the current sequence is of the form (0,0,\dots,A_{p-2}=t,A_{p-1}=t-1,A_p=t+1,\dots,0,0).
Then you only need to perform "sub" on A_ {p-2} once. If A_ {p-2}\leq 2, there is no solution.
From the above greedy process, it can be inferred that the answer sequence is unique.
Considering the adjustment method, for each step, if the "sub" operation is performed at other positions, then adjusting to the position in the above process must not be inferior.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
ll read() {
ll x=0; char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=x*10+ch-48, ch=getchar();
return x;
}
int n;
ll C;
void print(int a, int b, int c, int d, int k) {
int cnt=4-(!a)-(!b)-(!c)-(!d);
if (k<cnt) return puts("-1"), void();
ll res=0;
k-=4;
k++; if (k>=1) res+=1ll*k*k*a;
k++; if (k>=1) res+=1ll*k*k*b;
k++; if (k>=1) res+=1ll*k*k*c;
k++; if (k>=1) res+=1ll*k*k*d;
printf("%lld\n%d\n", res, k);
k-=4;
for (int i=1; i<=k; i++) printf("0 ");
k++; if (k>=1) printf("%d ", a);
k++; if (k>=1) printf("%d ", b);
k++; if (k>=1) printf("%d ", c);
k++; if (k>=1) printf("%d ", d);
return puts(""), void();
}
void solve() {
n=read(), C=read();
ll p=ceil(1.0*C/n);
int x=n*p-C, y=n-x;
if (p>n||p==0) return puts("-1"), void();
if (x<=y) return print(0, 0, x, y, p);
int t=ceil((x-y)/3.0);
x-=t*2, y+=t;
if (t<=x) return print(0, t, x, y, p);
if (t<=2) return puts("-1"), void();
return print(1, t-2, x+1, y, p);
}
int T;
int main() {
T=read();
while (T--) solve();
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
void solve(istringstream cin) {
int n;
long long c;
cin >> n >> c;
for (int k = 1; k <= n; k++) {
if (1LL * k * n < c) {
continue;
}
vector<int> a(k);
a[k - 1] = n;
long long t = n * 1LL * k;
while (t > c) {
bool ok = false;
for (int i = k - 1; i >= 1; i--) {
if (a[i] - 1 >= a[i - 1] + 1 && t - 1 >= c) {
a[i]--;
a[i - 1]++;
t--;
ok = true;
break;
}
}
if (!ok) {
break;
}
}
if (t > c) {
cout << -1 << '\n';
} else {
long long sum = 0;
for (int i = 0; i < k; i++) {
sum += a[i] * (i + 1LL) * (i + 1LL);
}
cout << sum << '\n';
cout << k << '\n';
for (int i = 0; i < k; i++) {
cout << a[i] << " \n"[i == k - 1];
}
}
return;
}
cout << -1 << '\n';
}
////////////////////////////////////////
// #define IGNORE_CR
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 1e6);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(1, 1e6);
in.readSpace();
long long c = in.readLong(1, 1e18);
in.readEoln();
sn += n;
ostringstream sout;
sout << n << " " << c << '\n';
solve(istringstream(sout.str()));
}
cerr << sn << endl;
assert(sn <= 1e6);
in.readEof();
return 0;
}