---
author: hoangviet
tags: dp, data structures, greedy
title: Imppos Solution
---

$\Huge\text{Imppos Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/1YTkPrfTldA4Pl2TyY1hq28GVD_uNfWMA/view?usp=share_link)
📌 Tags: `dp` `data structures` `greedy`
✍️ Writer: Hoàng Việt
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài

Ta có một bảng kích thước $n$ x $m$ và $k$ ô có phần thưởng. Bạn xuất phát từ ô $\text{(1, 1)}$ và sẽ kết thúc ở ô $\text{(n, m)}$. Trong quá trình di chuyển, bạn chỉ có thể đi xuống dưới hoặc đi qua phải. Với mỗi ô có quà mà bạn đi qua, bạn sẽ nhận được một phần quà ở trong ô đó.


Nhiệm vụ của bạn là tìm sô lượng ô mà nếu xóa ô đó thì số lượng phần quà tối đa mà bạn sẽ nhận được bị giảm đi 1.

-----

## Subtask 1

$\Large n, m, k \leq 100$

Gọi $dp[i]$ là số lượng phần quà tối đa mà bạn có thể nhận được nếu đi từ ô $(1, 1)$ và kết thúc ở ô có quà thứ $i$.

Để tính được mảng $dp$ thì trước tiên các bạn cần phải sắp xếp thứ tự của $k$ ô có quà theo thứ tự tăng dần.

Ban đầu tất cả $dp[i]$ đều bằng $1$ có nghĩa là đã lấy phần quà tại ô đó.

Đi qua các ô có quà sau khi đã sắp xếp, khi đến ô thứ $i$ thì:

> $dp[i] = max(dp[i], dp[j] + 1)$ với $j < i$, $x[j] < x[i]$, $y[j] < y[i]$

Đi qua $k$ ô đã cho, khi đến ô thứ $i$ thì tính xem nếu như xóa đi phần quà tại ô thứ $i$ thì số lượng phần quà tối đa bạn nhận được sẽ là bao nhiêu bằng phương pháp quy hoạch động ở trên, nếu như nó bé hơn số quà tối đa bạn nhận được khi đầy đủ $k$ điểm thì kết quả được cộng thêm $1$.

Độ phức tạp thuật toán: $O(k^3)$.

-----

## Subtask 2

$\Large n, m \leq 10^6, k \leq 10^3$

Sử dụng lại mảng $dp$ và phương pháp tính mảng này như ở $Subtask$ $1$. Nhưng bây giờ với $k \leq 10^3$ thì chúng ta phải tối ưu phần tìm các ô.

Thay vì đến số lượng ô mà sau khi xóa nó tổng sẽ giảm thì chúng ta sẽ đếm số lượng ô mà nếu xóa nó tổng không giảm.

Gọi $maxsum$ là tổng số quà lớn nhất bạn có thể nhận được với đầy đủ $k$ điểm.

Gọi $check[i]$ là nếu điểm $i$ có thể đi đến một điểm $j$ có $dp[j]$ = $maxsum$ thì $check[i]$ = $true$ ngược lại $check[i] = false$.

Đi qua các điểm theo thứ tự từ sau tới, khi đến điểm $i$ ban đầu $check[i] = true$ nếu $dp[i] = maxsum$ hoặc tồn tại một điểm $j > i$ mà từ điểm i có thể đi đến điểm j được và $dp[i] + 1 == dp[j]$ thì $check[i]$ |= $check[j]$.

Gọi $cnt$ là số lượng các điểm có thể xóa mà tổng không giảm, ban đầu $cnt = 0$.

Sau khi tính xong mảng $check$, chúng ta đi qua các điểm một lần nữa, với mỗi điểm $i$ nếu $check[i] == false$ hoặc số lượng các điểm $j$ mà điểm $i$ có thể đi đến điểm $j$ và $check[j] == true$ và $dp[i] + 1 == dp[j]$ lớn hơn $1$ thì cộng cnt thêm 1.

Kết quả bài toán sẽ là $k$ - $cnt$.

Độ phức tạp thuật toán: $O(k^2)$.

-----

## Subtask 3

$\Large n, m \leq 10^9, k \leq 10^5$

Với giới hạn $k$ lớn như vậy thì chúng ta không thể tính mảng $dp$ với độ phức tạp $k^2$ được cho nên phải tối ưu hóa cách tính mảng $dp$.

Trước tiên, phải nén tọa độ các điểm có phần thưởng, sau khi nén thì tọa độ hàng và tọa độ cột của mỗi điểm sẽ bé hơn hoặc bằng k.

Ta có thể nén như sau:

cin >> n >> m >> k;

pair<ll, ll> a[k];
vector<ll> x, y;

for(int i = 0; i < k; i ++) {
    cin >> a[i].fi >> a[i].se;
    x.push_back(a[i].fi);
    y.push_back(a[i].se);
}

x.push_back(1); x.push_back(n);
y.push_back(1); y.push_back(m);

sort(x.begin(), x.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
sort(y.begin(), y.end());
y.resize(unique(y.begin(), y.end()) - y.begin());

map<ll, ll> mp;
for(int i = 0; i < x.size(); i ++)
    mp[x[i]] = i;
for(int i = 0; i < k; i ++)
    a[i].fi = mp[a[i].fi];
mp.clear();
for(int i = 0; i < y.size(); i ++)
    mp[y[i]] = i;
for(int i = 0; i < k; i ++)
    a[i].se = mp[a[i].se];

sort(a, a + k);

n = x.size(); m = y.size();

Có thể tối ưu hóa quy hoạch động bằng cấu trúc dữ liệu [segment tree](https://vnoi.info/wiki/translate/codeforces/Efficient-and-easy-segment-trees.md).

Đi qua các điểm có phần thưởng, khi đến điểm thứ $i$ gọi $x$ là giá trị $max$ trong đoạn từ $1$ đến $y[i]$ trên cây segment tree, gán $dp[i] = x + 1$ và cập nhật lại cây segment tree ở điểm $y[i]$ với giá trị $dp[i]$.

Chúng ta có nhận xét mới là với mỗi giá trị trong mảng $dp$ là $val$ thì chúng ta chỉ có duy nhất một điểm $i$ mà có $dp[i] == val$ và nếu xóa điểm đó đi thì tổng có được sẽ giảm đi $1$ hoặc không có điểm nào như vậy.

Sau khi tính toán xong mảng $dp$ thay vì chúng ta sẽ đếm số lượng ô thì chúng ta sẽ đếm số lượng giá trị mà sau khi xóa tổng sẽ không giảm.

Gọi vector $b[val]$ là vector chứa các chỉ số $i$ mà $dp[i] == val$, ban đầu tất cả vector đều rỗng.

Vẫn sẽ có mảng $check$ như ở $Subtask$ $2$, nhưng bây giờ chúng ta sẽ tối ưu cách tính như sau.

Đi qua các điểm từ sau tới, khi đến điểm $i$ thì tiếp tục đi qua các điểm nằm trong vector $b[dp[i] + 1]$, gọi $j$ là điểm hiện tại đi tới trong vector $b[dp[i] + 1]$ nếu từ điểm $i$ có thể đi đến điểm $j$ thì $check[i]$ |= $check[j]$, nếu $check[i] == true$ thì $break$ để tránh những thao tác thừa ở sau, sau đó thêm điểm $i$ vào vector $b[dp[i]]$ để xét tiếp những điểm tiếp theo.

Gọi lại $cnt$ là số lượng giá trị mà sau khi xóa tổng sẽ không giảm.

Khi đã có được mảng $check$, đi qua các giá trị $val$ từ $1$ đến $maxsum$ đếm xem trong vector $b[val]$ xem có nhiều hơn 1 điểm $i$ có $check[i] == true$ hay không nếu đúng thì $cnt$ được cộng thêm một, có nghĩa là nếu xóa một điểm này có giá tri bằng val thì vẫn sẽ có một điểm khác để thay thế.

Kết quả của bài toán là $maxsum - cnt$.

Độ phúc tạp thuật toán $O(k * log(k))$

-----

Nếu thấy khó về việc cài đặt, bạn có thể tham khảo code mẫu ở [đây](https://ideone.com/40pxxo).