PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Milind Jain and Anton Trygub
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
3139
PREREQUISITES:
None
PROBLEM:
Consider an infinite sequence X_i of nonnegative integers, in which X_1 = A, X_2 = B, X_3 = C, and for i\ge 4,
X_i = \max(X_{i-3}, X_{i-2}, X_{i-1}) - \min(X_{i-3}, X_{i-2}, X_{i-1})
Find the K-th term of this sequence.
EXPLANATION:
(The details of the solution below is due to Anton Trygub. I try my best to find a natural leading thought process for this solution, but if it turns out unnatural, please do let me know!)
Observe that at all time, \max(a, b, c) is non-increasing. In fact, if we can show that this quantity decreases multiplicatively, we can simply solve the problem using direct simulation. Turns out this is not true generally for this problem, but we can still work out some details.
Assume that, for example, M = \max(a, b, c) doesn’t decrease by 10\% in at most 7 moves. Let’s see what condition leads to this decrement. More specifically, the sequence goes a, b, c, x_1, x_2, x_3, x_4, x_5, x_6, x_7, and \max(x_5, x_6, x_7) \gt 0.9 \cdot M. Let’s see what condition leads to this example:
- Among x_5, x_6, and x_7, there exists one element larger than 0.9M. Let this be x_k.
- This means at least one among x_{k - 3}, x_{k - 2}, x_{k - 1} is less than 0.1M. Let this be x_t.
- Then all of x_{t - 3}, x_{t - 2}, x_{t - 1} must be larger than 0.9M.
In any case, we see that there exists position t such that x_{t - 2}, x_{t - 1} \gt 0.9M, while x_t \lt 0.1M. Let these be our new a, b, c. We will show that from this state, we will soon reach a state where there exists a quick formulation to calculate future states (more specifically, this state is a \ge b \ge 4c and a - b \le c):
- If a \le b, then our sequence proceeds as a, b, c, b - c, b - c, b - 2c, c. The last 3 forms the state we need.
- If a \ge b, then there are two cases here:
- If a - c \le b, then a, b, c is already our desired state.
- Else, the sequence proceeds as a, b, c, a - c, a - 2c, a - 3c, c. The last 3 forms the state we need.
Lastly, let’s see why we desire this state. From this state, the sequence proceeds as a, b, c, a - c, b - c, a - 2c, c, b - 2c, a - 3c, b - 3c, c. We can see that in 8 moves, a and b decreases by 3c. That means that we can quickly calculate that in 8k moves, the state would be a - 3kc, b - 3kc, c. When the process stops cycling, we know that \max(a, b, c) = a \lt 4c \lt 0.4M, so we have also decreased M by a multiplicative amount.
So we have proven that either we will decrease \max(a, b, c) by 10% in at most 7 moves, or we reach the desired state in a constant amount of move, from which we can quickly calculate a future state that also decrease \max(a, b, c) by a multiplicative amount. Therefore, the algorithm runs in at most \log(K) step, which is fast enough.
TIME COMPLEXITY:
Time complexity is O(\log K) for each test case.
SOLUTION:
Setter's Solution
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ld = double;
typedef tree<
pair<int, int>,
null_type,
less<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define mp make_pair
int MOD = 998244353;
int mul(int a, int b) {
return (1LL * a * b) % MOD;
}
int add(int a, int b) {
int s = (a+b);
if (s>=MOD) s-=MOD;
return s;
}
int sub(int a, int b) {
int s = (a+MOD-b);
if (s>=MOD) s-=MOD;
return s;
}
int po(int a, ll deg)
{
if (deg==0) return 1;
if (deg%2==1) return mul(a, po(a, deg-1));
int t = po(a, deg/2);
return mul(t, t);
}
int inv(int n)
{
return po(n, MOD-2);
}
mt19937 rnd(time(0));
const int LIM = 1000005;
vector<int> facs(LIM), invfacs(LIM), invs(LIM);
void init()
{
facs[0] = 1;
for (int i = 1; i<LIM; i++) facs[i] = mul(facs[i-1], i);
invfacs[LIM-1] = inv(facs[LIM-1]);
for (int i = LIM-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
for (int i = 1; i<LIM; i++) invs[i] = mul(invfacs[i], facs[i-1]);
}
int C(int n, int k)
{
if (n<k) return 0;
if (n<0 || k<0) return 0;
return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}
struct DSU
{
int n;
vector<int> sz;
vector<int> parent;
vector<int> pos; //From parent
vector<int> gcd;
void make_set(int v) {
parent[v] = v;
sz[v] = 1;
}
int find_pos(int v)
{
if (v==parent[v])
return 0;
return (pos[v] + find_pos(parent[v]))%n;
}
int find_set(int v) {
if (v == parent[v])
return v;
return find_set(parent[v]);
}
ll eval(int v)
{
v = find_set(v);
return gcd[v];
}
void union_sets(int a, int b, int d) {
int da = find_pos(a);
int db = find_pos(b);
int diff = (da + d - db + n)%n;
//cout<<"DIFF: "<<diff<<endl;
if (find_set(a) == find_set(b))
{
a = find_set(a);
gcd[a] = __gcd(gcd[a], diff);
}
else
{
a = find_set(a);
b = find_set(b);
if (sz[a] < sz[b])
{
swap(a, b);
diff = (n - diff)%n;
}
parent[b] = a;
sz[a] += sz[b];
pos[b] = diff;
gcd[a] = __gcd(gcd[a], gcd[b]);
}
}
DSU (int N)
{
n = N;
parent.resize(n);
sz.resize(n);
gcd = vector<int>(n, n);
pos = vector<int>(n);
for (int i = 0; i<n; i++) make_set(i);
}
};
void print(vector<int> a)
{
for (auto it: a) cout<<it<<' ';
cout<<endl;
}
void print(vector<bool> a)
{
for (auto it: a) cout<<it<<' ';
cout<<endl;
}
void print(vector<pair<ll, ll>> a)
{
for (auto it: a) cout<<it.first<<' '<<it.second<<"| ";
cout<<endl;
}
void print(vector<pair<int, int>> a)
{
for (auto it: a) cout<<it.first<<' '<<it.second<<"| ";
cout<<endl;
}
/*const int mod = 998244353;
template<int mod>
struct NTT {
static constexpr int max_lev = __builtin_ctz(mod - 1);
int prod[2][max_lev - 1];
NTT() {
int root = find_root();//(mod == 998244353) ? 31 : find_root();
int rroot = power(root, mod - 2);
vector<vector<int>> roots(2, vector<int>(max_lev - 1));
roots[0][max_lev - 2] = root;
roots[1][max_lev - 2] = rroot;
for (int tp = 0; tp < 2; ++tp) {
for (int i = max_lev - 3; i >= 0; --i) {
roots[tp][i] = mul(roots[tp][i + 1], roots[tp][i + 1]);
}
}
for (int tp = 0; tp < 2; ++tp) {
int cur = 1;
for (int i = 0; i < max_lev - 1; ++i) {
prod[tp][i] = mul(cur, roots[tp][i]);
cur = mul(cur, roots[tp ^ 1][i]);
}
}
}
template<bool inv>
void fft(int *a, int lg) const {
const int n = 1 << lg;
int pos = max_lev - 1;
for (int it = 0; it < lg; ++it) {
const int h = inv ? lg - 1 - it : it;
const int shift = (1 << (lg - h - 1));
int coef = 1;
for (int start = 0; start < (1 << h); ++start) {
for (int i = start << (lg - h); i < (start << (lg - h)) + shift; ++i) {
if (!inv) {
const int y = mul(a[i + shift], coef);
a[i + shift] = a[i];
inc(a[i], y);
dec(a[i + shift], y);
} else {
const int y = mul(a[i] + mod - a[i + shift], coef);
inc(a[i], a[i + shift]);
a[i + shift] = y;
}
}
coef = mul(coef, prod[inv][__builtin_ctz(~start)]);
}
}
}
vector<int> product(vector<int> a, vector<int> b) const {
if (a.empty() || b.empty()) {
return {};
}
const int sz = a.size() + b.size() - 1;
const int lg = 32 - __builtin_clz(sz - 1), n = 1 << lg;
a.resize(n);
b.resize(n);
fft<false>(a.data(), lg);
fft<false>(b.data(), lg);
for (int i = 0; i < n; ++i) {
a[i] = mul(a[i], b[i]);
}
fft<true>(a.data(), lg);
a.resize(sz);
const int rn = power(n, mod - 2);
for (int &x : a) {
x = mul(x, rn);
}
return a;
}
private:
static inline void inc(int &x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
static inline void dec(int &x, int y) {
x -= y;
if (x < 0) {
x += mod;
}
}
static inline int mul(int x, int y) {
return (1LL * x * y) % mod;
}
static int power(int x, int y) {
if (y == 0) {
return 1;
}
if (y % 2 == 0) {
return power(mul(x, x), y / 2);
}
return mul(x, power(x, y - 1));
}
static int find_root() {
for (int root = 2; ; ++root) {
if (power(root, (1 << max_lev)) == 1 && power(root, (1 << (max_lev - 1))) != 1) {
return root;
}
}
}
};
NTT<mod> ntt;
*/
ll a, b, c, k;
void gen_step()
{
ll M = max({a, b, c});
ll m = min({a, b, c});
a = b; b = c; c = M - m;
k--;
}
void step()
{
if (k>=9 && a>=b && a-b<=c && b>=4*c)
{
ll steps = (k-1)/8;
if (c) steps = min(steps, (b-c)/(3*c));
a-=c*(steps*3);
b-=c*(steps*3);
k-=(steps*8);
}
else gen_step();
}
void solve()
{
cin>>a>>b>>c>>k;
while (k!=1) step();
cout<<a<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int t; cin>>t;
while (t--) solve();
}
/*
1
1000000000 1000000000 1000000000 101
*/
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll solve(ll a,ll b,ll c,ll k){
if(k==0) return c;
if(a<b || b<c || b+4*c<4*a || k<=20){
ll d=max(a,max(b,c))-min(a,min(b,c));
return solve(b,c,d,k-1);
}
ll ph=k/8;
ll del=3*a-3*c;
if(del==0 || ph==1 || a/del>=ph-1){//overflow sanity check
ll na=a-(ph-1)*del;
ll nb=b-(ph-1)*del;
ll nc=c-(ph-1)*del;
if(nb+4*nc>=4*na){
return solve(a-ph*del,b-ph*del,c-ph*del,k-ph*8);
}
}
ph=1;
while(ph*2<k/8) ph*=2;
while(ph>=1){
if(a/del>=ph-1){//overflow sanity check
ll na=a-(ph-1)*del;
ll nb=b-(ph-1)*del;
ll nc=c-(ph-1)*del;
if(nb+4*nc>=4*na){
a-=ph*del;b-=ph*del;c-=ph*del;k-=ph*8;
}
}
ph/=2;
}
return solve(a,b,c,k);
}
int main(){
ios::sync_with_stdio(false);
int t;cin >> t;
while(t--){
ll a,b,c,k;cin >> a >> b >> c >> k;
if(k<=3){
if(k==1) cout << a << '\n';
else if(k==2) cout << b << '\n';
else cout << c << '\n';
continue;
}
ll ans=solve(a,b,c,k-3);
cout << ans << '\n';
}
}