PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: zobayer7
Testers: mexomerf, rivalq
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Longest increasing subsequence
PROBLEM:
There’s an N\times M grid with K special cells.
From a cell (x, y):
- If it’s a special cell, Chef can move to any one of the 8 neighboring cells
- Otherwise, Chef can move to one of the 4 horizontally/vertically adjacent cells
Find the minimum number of moves to reach (N, M) from (1, 1).
EXPLANATION:
Clearly, in an optimal sequence of moves every move we make is going to be one of the following:
- (x, y) \to (x, y+1)
- (x, y) \to (x+1, y)
- (x, y) \to (x+1, y+1) (only possible from a special cell)
We need to make N-1 moves along x and M-1 moves along y, and a special cell allows us to at best combine two of these moves into one (thus saving one step). Going in the ‘wrong direction’ doesn’t decrease the number of steps we need to make, so it’s suboptimal.
This also means that any special cells of the form (x, M) or (N, y) don’t matter at all, since we can’t use them to make the third type of move. Let’s discard such special cells first.
Now, notice that if we touch s special cells along our path, the number of moves will be exactly N+M-2-s. This follows from our observation above: we make N-1+M-1 moves, and each special cell allows us to combine two of these into one.
To minimize this, we’d like to find the largest possible value of s, i.e, the largest number of special cells that we can visit along our path.
Note that if (x_1, y_1) and (x_2, y_2) are two special cells, we can visit both of them along our optimal path if and only if x_1 \lt x_2 and y_1 \lt y_2.
In particular, if we sort the special cells in ascending order of their x-coordinates, the y-coordinates must form an increasing sequence.
In other words, what we’re looking for is just the longest increasing subsequence of the y-coordinates!
This can be computed in \mathcal{O}(K\log K) time in a variety of ways: see here for a couple of them.
Note that there is one extra condition here: we need to ensure that we also pick distinct x-coordinates.
One simple way to ensure this is to sort the cells in increasing order of x, and break ties by decreasing order of y.
TIME COMPLEXITY:
\mathcal{O}(K\log K) per testcase.
CODE:
Setter's code (C++)
#include"bits/stdc++.h"
using namespace std;
#define PB push_back
#define ll long long
#ifdef LOCAL
#include"bits/debug.h"
#else
#define dbg(...) 0
#endif
#define I ios::sync_with_stdio(false); cin.tie(0);
#define Q int tt; cin>>tt ; for(int qq=1; qq <= tt; qq++)
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define x first
#define y second
int main() {
I
Q {
int n, m, k;
cin >> n >> m >> k;
vector<pii> a(k);
for (int i = 0; i < k; i++) {
cin >> a[i].x >> a[i].y;
}
sort(a.begin(), a.end());
vector<int> lis(k + 1, 1e9);
lis[0] = -1e9;
int cut = 0;
for (int i = 0; i < k;) {
vector<pii> tmp;
int i1 = i;
while(i < k && a[i].x == a[i1].x) {
if(a[i].x != n && a[i].y != m) {
int j = upper_bound(lis.begin(), lis.end(), a[i].y) -lis.begin();
if(lis[j - 1] < a[i].y) {
tmp.PB({j, a[i].y});
cut = max(cut, j);
}
}
i++;
}
for(auto [id, y] : tmp) {
lis[id] = min(lis[id], y);
}
}
cout << (n + m - 2 - cut)<< "\n";
}
return 0;
}
Tester's code (C++)
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
int sum_n = 0;
int mx = 0;
int my = 0;
// n % x = (-y)
// n % y = (-x)
//((y - 1) * x) % y = (-x)
// xy - y - x
const int N = 2e5 + 5;
struct node{
int a=0;
node (int val=-1e9){
a=val;
}
void merge(node &n1,node &n2){
this->a=max(n1.a,n2.a);
}
};
struct update{
int val=0;
update(int t=0){
val=t;
}
void combine(update &par,int tl,int tr){
maxs(val,par.val);
}
void apply(node &node){
maxs(node.a,val);
val=0;
}
};
template<typename node,typename update>
struct segtree{
node t[4*N];
bool lazy[4*N];
update zaker[4*N];
int tl[4*N];
int tr[4*N];
node nul;
inline void pushdown(int v){
if(lazy[v]){
apply(zaker[v],v);
lazy[v]=0;
zaker[v].apply(t[v]);
}
}
inline void apply(update &u,int v){
if(tl[v]!=tr[v]){
lazy[2*v]=lazy[2*v+1]=1;
zaker[2*v].combine(u,tl[2*v],tr[2*v]);
zaker[2*v+1].combine(u,tl[2*v+1],tr[2*v+1]);
}
}
void build(int v,int start,int end){
tl[v]=start;
tr[v]=end;
if(start==end){
t[v].a = 0;
}
else{
int m=(start+end)/2;
build(2*v,start,m);
build(2*v+1,m+1,end);
t[v].merge(t[2*v],t[2*v+1]);
}
}
void zeno(int v,int l,int r,update val){
pushdown(v);
if(tr[v]<l || tl[v]>r)return;
if(l<=tl[v] && tr[v]<=r){
maxs(t[v].a,val.val);
apply(val,v);
return;
}
zeno(2*v,l,r,val);
zeno(2*v+1,l,r,val);
t[v].merge(t[2*v],t[2*v+1]);
}
node query(int v,int l,int r){
if(tr[v]<l || tl[v]>r)return nul;
pushdown(v);
if(l<=tl[v] && tr[v]<=r){
return t[v];
}
node a=query(2*v,l,r);
node b=query(2*v+1,l,r);
node ans;
ans.merge(a,b);
return ans;
}
public:
node query(int l,int r){
return query(1,l,r);
}
void upd(int l,int r,update val){
return zeno(1,l,r,val);
}
};
segtree<node,update> seg;
int solve(){
int n = readIntSp(1,1e9);
int m = readIntSp(1,1e9);
int k = readIntLn(0, 2e5);
sum_n += k;
assert(sum_n <= 2e5);
maxs(mx, k);
auto compress = [&](vector<int> &a){
vector<int> t;
for(auto i: a){
t.push_back(i);
}
sort(all(t));
t.erase(unique(all(t)), t.end());
for(auto &i: a){
i = lower_bound(all(t),i) - t.begin() + 1;
}
};
vector<int> a(k + 1),b(k + 1);
set<pii> st;
set<int> st1, st2;
for(int i = 0; i < k; i++){
int x = readIntSp(1,n);
int y = readIntLn(1,m);
a[i] = x;
b[i] = y;
st.insert({x,y});
st1.insert(x);
st2.insert(y);
}
a[k] = n;
b[k] = m;
st1.insert(n);
st2.insert(m);
assert(sz(st) == k);
compress(a);
compress(b);
k++;
seg.build(1,1,k);
vector<vector<int>> pts(k + 1);
map<pii, int> dp;
// for(int i = 2; i <= k; i++){
// seg.upd(i,i,-1e9);
// }
for(int i = 0; i < k; i++){
pts[a[i]].push_back(b[i]);
}
for(int i = 1; i <= k; i++){
for(auto y: pts[i]){
int res = 1 + seg.query(1,y - 1).a;
res = max(res, 1LL);
//cout << i << " " << y << " " << res << endl;
dp[{i,y}] = res;
}
for(auto y: pts[i]){
int res = dp[{i,y}];
seg.upd(y,y, res);
}
}
cout << n + m - 1 - dp[{sz(st1),sz(st2)}] << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t = readIntLn(1,1e4);
int tmp = t;
while(t--){
solve();
}
//cerr << tmp << " " << sum_n << " " << mx << endl;
//cerr << my << " " << mx << endl;
return 0;
}
Editorialist's code (Python)
# https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/lis.py
def lis(nums, cmp=lambda x, y: x < y):
P = [0] * len(nums)
M = [0] * (len(nums) + 1)
L = 0
for i in range(len(nums)):
lo, hi = 1, L
while lo <= hi:
mid = (lo + hi) // 2
if cmp(nums[M[mid]], nums[i]):
lo = mid + 1
else:
hi = mid - 1
newL = lo
P[i] = M[newL - 1]
M[newL] = i
L = max(L, newL)
S = [0] * L
k = M[L]
for i in range(L - 1, -1, -1):
S[i], k = nums[k], P[k]
return S
for _ in range(int(input())):
n, m, k = map(int, input().split())
cells = []
for i in range(k):
x, y = map(int, input().split())
if x < n and y < m: cells.append([x, -y])
cells.sort()
vals = []
for x, y in cells: vals.append(-y)
print(n-1 + m-1 - len(lis(vals)))