PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
For two integers x and y, where x \lt y, define a function f_{x, y} as:
- f_{x, y}(0) = x
- f_{x, y}(1) = y
- For every integer k \ge 2, f_{x, y}(k) = 3\cdot f_{x, y}(k-1) - 2\cdot f_{x, y}(k-2)
Given N and M, find any pair (x, y) such that 1 \le x \lt y \le N and M = f_{x, y}(k) for some k \ge 0.
EXPLANATION:
First off, if M \le N we have a trivial solution: either x or y can be chosen to be M because both x and y appear in f_{x, y} by definition.
So, if M = 1 one answer is (1, 2), and if 1 \lt M \le N one answer is (1, M).
We only work with M \gt N from now on.
Let’s look at the function f_{x, y} a bit closer.
More specifically, let’s look at what the expression 3\cdot f_{x, y}(k-1) - 2\cdot f_{x, y}(k-2) actually tells us.
Suppose we try to plot out the values of the function on a line.
The first two points are x and y.
Then,
- The third point is 3y - 2x = y + 2\cdot (y-x)
- The fourth point is 3\cdot (3y-2x) - 2y = 7y-6x = y + 6\cdot (y-x)
- The fifth point, if you work out the algebra, will be y + 14\cdot (y-x)
\vdots
In general, observe that what is happening is that the distance between adjacent points keeps doubling!
- The distance between x and y is (y-x)
- The distance between y and y + 2\cdot (y-x) is 2\cdot (y-x)
- The distance between y + 2\cdot (y-x) and y + 6\cdot (y-x) is 4\cdot (y-x)
And so on.
So, if we let d = y - x, it can be seen that for all k \ge 2, we have
(In fact, this formula works even for k = 0 and k = 1, nicely enough. Since we already took care of the M \le N case earlier though, this doesn’t matter much to us.)
The above observation can now be used to solve the problem.
Note that because d \gt 0, the term (2^k - 2) \cdot d grows very quickly.
In particular, for k \gt 30, it will certainly exceed 10^9, so we don’t need to care about larger values of k at all - the function value can never take the value M there, regardless of what x and y are.
So, there are very few choices for what k can be.
Let’s now fix a value of k between 2 and 30.
With this fixed, we’re now looking for a pair (y, d) such that:
- M = y + (2^k-2)\cdot d,
- 1 \le y \le N, and
- y-d \ge 1 (because x = y-d by definition of d)
Because the constraints guarantee that the sum of N won’t exceed 2\cdot 10^5, we can now simply try all possible values of y from 1 to N, which will then uniquely fix the value of d to be
If this d is a positive integer and satisfies y-d \ge 1, we’ve found a valid solution.
This gives us a solution to the problem in \mathcal{O}(30\cdot N) time; or more precisely \mathcal{O}(N\log M) time since k \gt \log_2 (M+2) doesn’t need to be checked.
As a bonus, if you’d like to try, it’s possible to further optimize this solution to run in just \mathcal{O}(\log M) time.
Of course, this was not necessary to get AC on the problem.
TIME COMPLEXITY:
\mathcal{O}(N\log M) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
ll n, m; cin >> n >> m;
if (m <= n) {
cout << 1 << ' ' << max(2ll, m) << '\n';
continue;
}
bool done = false;
for (int y = 1; y <= n and !done; ++y) {
ll mul = 2;
while (y + mul <= m) {
// m = y + d*mul
// d = (m - y) / mul
if ((m - y) % mul == 0) {
ll d = (m - y) / mul;
ll x = y - d;
if (x >= 1 and x < y) {
cout << x << ' ' << y << '\n';
done = true;
break;
}
}
mul = mul*2 + 2;
}
}
if (!done) cout << -1 << '\n';
}
}