PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: piyush_2007
Testers: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
The extended Euclidean algorithm
PROBLEM:
You are given integers a, b, K.
Find any array A of minimum length such that
EXPLANATION:
First, note that for any array A, S(A) is a linear combination of a and b.
So, if \gcd(a, b) doesn’t divide K, no solution can exist.
Now, since our aim is to minimize the length of A, let’s try a couple of smaller lengths and see where we get.
N = 1
Suppose A has length 1.
The \sum_{i=1}^N \sum_{j=i+1}^N \left|A_i - A_j\right| term now completely disappears, so we have S(A) = b\cdot A_1.
This can only equal K when b is a factor of K, in which case we have A_1 = \frac{K}{b}.
N = 2
Next, let’s try for N = 2.
In this case, we obtain
Let x = |A_1 - A_2| and y = A_1 + A_2.
If we’re able to obtain a solution to a\cdot x + b\cdot y = K such that:
- x\geq 0; and
- x and y have the same parity.
we’ll then be able to extract a valid A_1 and A_2 out of them.
The equation a\cdot x + b\cdot y = K is a linear diophantine equation, and is well-studied (see here if you’re unfamiliar with them).
In particular, it’s known that the solutions of this equation are exactly all pairs (x, y) such that
where g = \gcd(a, b), (x_0, y_0) is any solution for the equation, and k is any integer.
Finding one solution (x_0, y_0) can be done using the extended Euclidean algorithm, so we can in fact find all solutions by simply varying k.
With this information in mind, once we have an initial (x_0, y_0), we want to choose a k such that x_0 + k\cdot \frac{b}{g} \geq 0, and both x and y are even.
The first part is simple enough: just choose a large enough k.
The second is also simple: either k or k+1 must work; or else there’s no way to give x and y the same parity (after all, k is the only variable here, so only its parity matters.)
If a valid k is found, great! Compute x and y, and then A_1 and A_2 from them.
Otherwise, we need to look further.
N = 3
This analysis will continue on from N = 2, so read that first if you haven’t.
In this case, rather than x = |A_1 - A_2| and y = A_1 + A_2, we redefine x to be the sum of all pairwise differences of A, and y to be the sum of A (After all, that’s what the coefficients in the equation are.)
If we’ve reached this case, we know that we’re in a situation where x and y have different parities no matter which k we choose.
In particular, this means \frac{a}{g} and \frac{b}{g} must both be odd. (Do you see why?)
Let (x_1, y_1) be a solution to the equation such that x_1 is even (and hence y_1 is odd), and also x_1 is positive and reasonably large.
It’s always possible to find such a solution since \frac{b}{g} is odd.
Now, let’s look at our array of length 3.
Suppose its elements are [A_1, A_1 + d_1, A_1 + d_1 + d_2], where A_1 can be anything, but d_1, d_2 \geq 0 (so we’re looking at a sorted array, which is fine since S(A) doesn’t depend on order anyway).
Observe that with this definition,
So, x = 2\cdot d_1 + 2\cdot d_2 and y = 3\cdot A_1 + 2\cdot d_1 + d_2.
This means y = 3A_1 + x - d_2.
Recall that we found a solution (x_1, y_1) where x_1 was a positive even number.
Plugging that solution in,
- y_1 = 3A_1 + x_1 - d_2, meaning 3A_1 = y_1 - x_1 + d_2.
The only constraint on d_2 is that it should be a non-negative integer.
So, choosing d_2 as either 0, 1, or 2 will allow the RHS to become a multiple of 3.
This also fixes A_1. - x_1 = 2\cdot d_1 + 2\cdot d_2.
Since x_1 is a ‘large enough’ positive even number, subtracting 2\cdot d_2 from it still leaves it as a positive even number (recall that d_2 \leq 2).
This also defines d_1 uniquely.
With all three of A_1, d_1, d_2 known, we have our array!
TIME COMPLEXITY:
\mathcal{O}(\log\min(a, b)) per testcase.
CODE:
Author's code (C++)
// ॐ
#include <bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323846
#define int long long int
#define ld long double
int gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
g = gcd(abs(a), abs(b), x0, y0);
if (c % g) {
return false;
}
x0 *= c / g;
y0 *= c / g;
if (a < 0) x0 = -x0;
if (b < 0) y0 = -y0;
return true;
}
const int INF=1e18;
bool check(vector<int> ans,int a,int b,int k){
__int128 term1=0,term2=0;
int n=(int)ans.size();
for(int i=0;i<n;i++){
assert(ans[i]>=(-INF) && ans[i]<=INF);
for(int j=i+1;j<n;j++)
term1+=(ans[i]>ans[j]) ? ans[i]-ans[j] : ans[j]-ans[i];
term2+=ans[i];
}
term1*=a;
term2*=b;
__int128 actual = term1 + term2, exp = k;
return (actual == exp);
}
void simplify_2(int &x,int &y,int a,int b){
for(int i=-5;i<=5;i++){
int xx=x+a*i;
int yy=y-b*i;
if(xx>=0 && ((abs(xx)%2)==(abs(yy)%2))){
x=xx;
y=yy;
return;
}
}
}
void simplify_3(int &x,int &y,int a,int b){
for(int i=-10;i<=10;i++){
int xx=x+a*i;
int yy=y-b*i;
if(xx>=5 && abs(xx)%2==0){
x=xx;
y=yy;
return;
}
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
cin>>test;
while(test--){
int a,b,k;
cin>>a>>b>>k;
if(a==0 && b==0){
if(k==0)
cout<<"1\n1\n";
else
cout<<"-1\n";
continue;
}
if(a==0){
if(k%b==0){
cout<<"1\n"<<k/b<<'\n';
}
else{
cout<<"-1\n";
}
continue;
}
if(b==0){
if(k%a==0 && k*a>=0){
if(k==0)
cout<<"1\n1\n";
else{
cout<<"2\n"<<"0 "<<k/a<<'\n';
}
}
else{
cout<<"-1\n";
}
continue;
}
int g=__gcd(abs(a),abs(b));
if(k%g){
cout<<"-1\n";
continue;
}
if(k%b==0){
cout<<"1\n";
cout<<(k/b)<<'\n';
continue;
}
int x=0,y=0;
assert(find_any_solution(a,b,k,x,y,g));
if(x<0){
int mul1=b/g,mul2=a/g;
int req=abs(x/mul1) + 10;
int sgn = (b/g) > 0 ? 1 : -1;
x+=req*sgn*mul1;
y-=req*sgn*mul2;
}
simplify_2(x,y,b/g,a/g);
if((abs(x)%2)==(abs(y)%2)){
cout<<"2\n";
vector<int> ans={(y-x)/2,(y+x)/2};
assert(check(ans,a,b,k));
for(auto u : ans){
cout<<u<<' ';
}
cout<<'\n';
continue;
}
simplify_3(x,y,b/g,a/g);
int r=((x-y)%3+3)%3;
int p=(y-x+r)/3;
int q=(x-2*r)/2;
assert(q>=0 && r>=0);
vector<int> ans={p,p+q,p+q+r};
cout<<"3\n";
for(auto u : ans){
cout<<u<<' ';
}
assert(check(ans,a,b,k));
cout<<"\n";
}
return 0;
}
Tester's code (C++)
//Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
array<int, 3> extend_euclid(int a, int b) {
array<int, 3> x = {1, 0, a};
array<int, 3> y = {0, 1, b};
while (y[2] > 0) {
int k = x[2] / y[2];
for (int i = 0; i < 3; i++) { x[i] -= k * y[i]; }
swap(x, y);
}
return x;
}
void solve()
{
int a,b,k;
cin >> a >> b >> k;
int g1 = __gcd(abs(b-a),abs(b+a));
int g2 = __gcd(abs(b),abs(2*a));
if(a == 0 && b == 0 && k){
cout << "-1\n";return;
}
if(b == 0 && k == 0){
cout << 1 << "\n" << 1 << "\n";
return;
}
if(b && ((k%abs(b)) == 0)){
cout << 1 << "\n";
cout << k/b << "\n";
return;
}
if((k%g1) == 0){
auto res = extend_euclid(abs(b-a),abs(b+a));
if((b-a) < 0)res[0] *= -1;
if((b+a) < 0)res[1] *= -1;
res[0] *= k/res[2];
res[1] *= k/res[2];
if(res[1] >= res[0]){
cout << 2 << "\n";
int y = res[1];
int x = res[0];
cout << x << " " << y << "\n";
// assert((b-a)*x + (b+a)*y == k);
return;
}
else if(b){
int y = res[1];
int x = res[0];
// cout << x << " " << y << "hi\n";
// cout << __gcd(x,y) << "\n";
cout << 2 << "\n";
int t;
if(b > 0){
t = (y-x)*g1/(2*b) - 3;
}
else{
t = (y-x)*g1/(2*b) + 3;
}
// cout << t << "hi\n";
y = y - t*(b-a)/g1;
x = x + t*(b+a)/g1;
assert(y >= x);
cout << x << " " << y << "\n";
// assert((b-a)*x + (b+a)*y == k);
return;
}
}
if((k%g2) == 0){
auto res = extend_euclid(abs(b),abs(2*a));
if(b < 0)res[0] *= -1;
if(2*a < 0)res[1] *= -1;
res[0] *= k/res[2];
res[1] *= k/res[2];
int beta = res[0];
int alpha = res[1];
int x,y,z;
if(alpha > 1){
int temp = beta - alpha;
while(abs(temp)%3){
temp--;
}
x = temp/3;
z = x + alpha;
y = beta - alpha - 2*x;
assert(x <= y);
assert(y <= z);
cout << 3 << "\n";
cout << x << " " << y << " " << z << "\n";
// assert((b-2*a)*x + b*y + (b+2*a)*z == k);
return;
}
else if(b){
int t;
if(b > 0){
t = (alpha-2)*g2/b - 3;
}
else{
t = (alpha-2)*g2/b + 3;
}
alpha = alpha - t*(b)/g2;
beta = beta + t*(2*a)/g2;
assert(alpha > 1);
int temp = beta - alpha;
while(abs(temp)%3){
temp--;
}
x = temp/3;
z = x + alpha;
y = beta - alpha - 2*x;
assert(x <= y);
assert(y <= z);
cout << 3 << "\n";
cout << x << " " << y << " " << z << "\n";
// assert((b-2*a)*x + b*y + (b+2*a)*z == k);
return;
}
}
cout << "-1\n";
}
signed main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
cin >> t;
while(t--)
solve();
return 0;
}