# FTOL - Editorial

Author: zobayer7
Testers: mexomerf, rivalq
Editorialist: iceknight1093

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 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[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(){

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++){
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 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)))


3 Likes

I guess something wrong with the test cases

I am attaching 2 codes which are exactly same except few changes but one is giving correct answer while the other is giving wrong answer.

I hope both are same except the in first code I am iterating over loop and taking max cut.

Please let me know if I am wrong

Anyway nice problem !!

check this testcase:
1
1 10 1
1 1

In both codes it is giving correct answer which is 9.

The first submission is wrong when K\gt 0 but arr is empty (which is the case when every special cell is on the border) because it always prints 0 in that case.

Initializing ans to n+m-2 instead of 0 makes it get AC.

Edit: also the test case provided by zobayer7 above is indeed a countercase, if you run the code you linked on that case it outputs 0 and not 9.

1 Like