PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Dijkstra
PROBLEM:
You’re given integers N and M. Define the infinite arrays A and B, where A_i = \max(i, \frac{N}{i}) if i divides N and 0 otherwise; B is defined similarly for M.
The cost of point (x, y) is A_x \times B_y.
Find the minimum cost of a path from (1, 1) to (P, Q) given that you’re allowed to move one step in any cardinal direction, in one move, while remaining with positive coordinates.
EXPLANATION:
At first glance, this seems like a simple shortest path problem: we have a graph with us, we’d like to move from one point to other, find the minimum cost.
However, looking at the limits should immediately show that the limits are way too large for any traditional shortest path algorithm to be fast enough, so we need to make some observations about the specific setup we have.
For this, we use the fact that A_x\times B_y = 0 if either A_x or B_y is 0, i.e. if we ever move to reach a number that’s not a factor of N (or M), we’ll be able to move for free along that row (respectively, column) however far we like.
In particular, we’ll have some rows and columns such that every point in them will have a cost of 0; and we will always be able to freely move from any such 0-cost point to any other 0-cost point without ever going through a point with positive cost.
Now, looking at the rows/columns that are all zeros, observe that they break the 2D plane into several disjoint rectangles; where within each rectangle the costs are positive.
We start at the rectangle containing (1, 1), and will end up in the rectangle containing (P, Q).
Note that since we can freely travel along the zeros, there’s no need to ever enter another rectangle.
This reduces the problem a lot.
There are now only two possibilities: (1, 1) and (P, Q) might be in the same rectangle, or they might not be.
If (1, 1) and (P, Q) are in different rectangles, the optimal path is quite clear: we must start at (1, 1) and reach some row/column that’s 0 as cheaply as possible; then go near the rectangle containing (P, Q), enter it from somewhere, and then reach (P, Q).
This can be thought of as basically two separate paths: one that starts at (1, 1) and reaches a 0 cost cell, and another that starts at (P, Q) and reaches a 0 cost cell.
So, for this case, we need to be able to find the minimum cost to start at some cell and reach a 0 cost cell.
This is easy to do: just run Dijkstra’s algorithm from the starting cell, for example.
The only concern is whether this will be fast enough - but as it happens, the non-zero values we’re working with are divisors, so this is indeed pretty fast!
Proof
One can prove that in no more than 20 steps, we’ll always reach a zero row/column, irrespective of starting position.
Suppose that we’re standing at cell (i, j) initially, and all of (i, j), (i, j+1), (i, j+2), \ldots (i, j+k) have non-zero values.
For this to happen, j, j+1, j+2, \ldots, j+k must all be divisors of M.But this means all of 2, 3, 4, \ldots, k+1 are divisors of M, because if you take x consecutive numbers then x will divide one of them.
So, \text{lcm}(2, 3, 4, \ldots, k+1) must be a divisor of M.However, LCM grows pretty quickly - in particular, the LCM of the first 19 numbers already exceeds 10^8, which is larger than any value of M in this problem.
This proves our point: the non-zero rectangle containing any point has dimensions not more than 20\times 20, so running Dijkstra only within this rectangle will be fast enough.
We thus have a solution for the case when (1, 1) and (P, Q) lie in different rectangles: run Dijkstra’s algorithm starting from each of them to find the lowest cost to reach a 0 cost cell, and add these values.
This leaves the case when (1, 1) and (P, Q) lie in the same rectangle.
This only gives us one more case to work with, where we don’t leave the rectangle at all. To compute this, just start a Dijkstra at (1, 1) and compute the cost to reach (P, Q) without exiting the rectangle.
Note that in this case it might still be optimal to leave the rectangle and take a 0-path, so the first case also does need to be considered anyway - just take the minimum of both options as the final answer.
TIME COMPLEXITY:
\mathcal{O}(B^2 \log B) per testcase, where B \approx 20 is the largest number of consecutive factors of any integer \leq 10^8.
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);
vector<array<int, 2>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int t; cin >> t;
while (t--) {
int n, m, p, q; cin >> n >> m >> p >> q;
if (p == 1 and q == 1) {
cout << 1ll*n*m << '\n';
continue;
}
ll ans = LLONG_MAX;
auto go = [&] (int x, int y, bool start = false) {
map<array<int, 2>, ll> dist;
if (n%x != 0 or m%y != 0) {
return 0ll;
}
dist[{x, y}] = 1ll * max(x, n/x) * max(y, m/y);
set<array<ll, 3>> st;
st.insert({dist[{x, y}], x, y});
ll res = LLONG_MAX;
while (!st.empty()) {
auto [d, i, j] = *begin(st);
st.erase(begin(st));
for (auto [dx, dy] : dir) {
int nx = i + dx, ny = j + dy;
if (min(nx, ny) < 1) continue;
ll cost = d;
if (n % nx == 0 and m % ny == 0) {
cost += 1ll * max(nx, n/nx) * max(ny, m/ny);
if (!dist.count({nx, ny}) or cost < dist[{nx, ny}]) {
st.erase({dist[{nx, ny}], nx, ny});
dist[{nx, ny}] = cost;
st.insert({dist[{nx, ny}], nx, ny});
}
}
else res = min(res, cost);
if (start and nx == p and ny == q) {
ans = min(ans, cost);
}
}
}
return res;
};
ll val1 = go(1, 1, 1), val2 = go(p, q);
cout << min(ans, val1 + val2) << '\n';
}
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
vector<ll> dx = {-1,1,0,0};
vector<ll> dy = {0,0,-1,1};
void solve(int test_case){
ll n,m,p,q; cin >> n >> m >> p >> q;
auto f = [&](ll i, ll j){
ll x = 0, y = 0;
if(n%i == 0) x = max(i,n/i);
if(m%j == 0) y = max(j,m/j);
return x*y;
};
ll siz1 = 0, siz2 = 0;
rep1(i,inf1){
if(n%i){
siz1 = i;
break;
}
}
rep1(j,inf1){
if(m%j){
siz2 = j;
break;
}
}
vector<ll> rows,cols;
rep1(i,siz1) rows.pb(i);
for(int i = p-25; i <= p+25; ++i){
if(i >= 1){
rows.pb(i);
}
}
sort(all(rows));
rows.resize(unique(all(rows))-rows.begin());
rep1(i,siz2) cols.pb(i);
for(int i = q-25; i <= q+25; ++i){
if(i >= 1){
cols.pb(i);
}
}
sort(all(cols));
cols.resize(unique(all(cols))-cols.begin());
rows.insert(rows.begin(),0);
cols.insert(cols.begin(),0);
siz1 = sz(rows)-1;
siz2 = sz(cols)-1;
priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pq;
ll dis[siz1+5][siz2+5];
memset(dis,0x3f,sizeof dis);
bool vis[siz1+5][siz2+5];
memset(vis,0,sizeof vis);
pq.push({f(1,1),1,1});
while(!pq.empty()){
auto [cost,i,j] = pq.top();
pq.pop();
if(vis[i][j]) conts;
vis[i][j] = 1;
dis[i][j] = cost;
rep(x,4){
ll i2 = i+dx[x], j2 = j+dy[x];
if(i2 < 1 or i2 > siz1 or j2 < 1 or j2 > siz2) conts;
if(vis[i2][j2]) conts;
pq.push({cost+f(rows[i2],cols[j2]),i2,j2});
}
}
ll i = lower_bound(all(rows),p)-rows.begin();
ll j = lower_bound(all(cols),q)-cols.begin();
ll ans = dis[i][j];
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}