Codeforces 1083E. The Fair Nut and Rectangles (DP+Convex-Hull Trick)

日付: 12月 11, 2018

[Problem - 1083E - Codeforces](https://codeforces.com/contest/1083/problem/E)
## Problem
Given <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n points <math><semantics><mrow><mo>(</mo><msub><mi>x</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>y</mi><mi>i</mi></msub><mo>)</mo></mrow><annotation encoding="application/x-tex">(x_i, y_i)</annotation></semantics></math>(xi,yi), each represents a rectangle <math><semantics><mrow><mo>[</mo><mo>(</mo><mn>0</mn><mo separator="true">,</mo><mn>0</mn><mo>)</mo><mo separator="true">,</mo><mo>(</mo><mn>0</mn><mo separator="true">,</mo><msub><mi>y</mi><mi>i</mi></msub><mo>)</mo><mo separator="true">,</mo><mo>(</mo><msub><mi>x</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>y</mi><mi>i</mi></msub><mo>)</mo><mo separator="true">,</mo><mo>(</mo><msub><mi>x</mi><mi>i</mi></msub><mo separator="true">,</mo><mn>0</mn><mo>)</mo><mo>]</mo></mrow><annotation encoding="application/x-tex">[(0,0), (0,y_i), (x_i,y_i), (x_i,0)]</annotation></semantics></math>[(0,0),(0,yi),(xi,yi),(xi,0)] and no rectangles are nested. Each rectangle has a value <math><semantics><mrow><msub><mi>a</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">a_i</annotation></semantics></math>ai.

The task is to select some rectangles such that the unioned area minus sum of <math><semantics><mrow><msub><mi>a</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">a_i</annotation></semantics></math>ai is maximum.

**Contraints:** <math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>n</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>6</mn></msup><mo separator="true">,</mo><mtext> </mtext><mn>1</mn><mo>≤</mo><msub><mi>x</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>y</mi><mi>i</mi></msub><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>9</mn></msup><mo separator="true">,</mo><mtext> </mtext><mn>0</mn><mo>≤</mo><msub><mi>a</mi><mi>i</mi></msub><mo>≤</mo><msub><mi>x</mi><mi>i</mi></msub><msub><mi>y</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">1\le n \le 10^6, \ 1\le x_i,y_i \le 10^9,\ 0\le a_i \le x_iy_i</annotation></semantics></math>1≤n≤106, 1≤xi,yi≤109, 0≤ai≤xiyi

## Solution
First sort all rectangles by <math><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>x. Let <math><semantics><mrow><msub><mi>f</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">f_i</annotation></semantics></math>fi be the maximum result if the <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i-th rectangle is selected. Then the **state-transition equation** is: <math><semantics><mrow><msub><mi>f</mi><mi>i</mi></msub><mo>=</mo><mi>m</mi><mi>a</mi><mi>x</mi><mo>{</mo><msub><mi>f</mi><mi>j</mi></msub><mo>+</mo><msub><mi>y</mi><mi>i</mi></msub><mo>(</mo><msub><mi>x</mi><mi>i</mi></msub><mo>−</mo><msub><mi>x</mi><mi>j</mi></msub><mo>)</mo><mo>−</mo><msub><mi>a</mi><mi>i</mi></msub><mi mathvariant="normal">∣</mi><mn>0</mn><mo>≤</mo><mi>j</mi><mo>&lt;</mo><mi>i</mi><mo>}</mo></mrow><annotation encoding="application/x-tex">f_i = max\{f_j + y_i(x_i-x_j) - a_i | 0\le j &lt; i\}</annotation></semantics></math>fi=max{fj+yi(xi−xj)−ai∣0≤j<i}

This is <math><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2) but we can solve it in <math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math>O(n) by **convex-hull trick**.
 
 * Let <math><semantics><mrow><mi>k</mi><mo>&lt;</mo><mi>j</mi><mo>&lt;</mo><mi>i</mi></mrow><annotation encoding="application/x-tex">k &lt; j &lt; i</annotation></semantics></math>k<j<i, where <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i is the current processing index.
 * If <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j is better than <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k for transition to <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i, <math><semantics><mrow><mfrac><mrow><msub><mi>f</mi><mi>j</mi></msub><mo>−</mo><msub><mi>f</mi><mi>k</mi></msub></mrow><mrow><msub><mi>x</mi><mi>j</mi></msub><mo>−</mo><msub><mi>x</mi><mi>k</mi></msub></mrow></mfrac><mo>&gt;</mo><msub><mi>y</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">\frac{f_j-f_k}{x_j-x_k} &gt; y_i</annotation></semantics></math>xj−xkfj−fk>yi, the left side is called *gradient* from <math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k to <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j, lets denote it by <math><semantics><mrow><msub><mi>G</mi><mrow><mi>k</mi><mi>j</mi></mrow></msub></mrow><annotation encoding="application/x-tex">G_{kj}</annotation></semantics></math>Gkj. We can prove that: If <math><semantics><mrow><msub><mi>G</mi><mrow><mi>k</mi><mi>j</mi></mrow></msub><mo>&lt;</mo><msub><mi>G</mi><mrow><mi>j</mi><mi>i</mi></mrow></msub></mrow><annotation encoding="application/x-tex">G_{kj} &lt; G_{ji}</annotation></semantics></math>Gkj<Gji, <math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j cannot be the best index for transition to <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i
 * Maintain a queue <math><semantics><mrow><mi>Q</mi></mrow><annotation encoding="application/x-tex">Q</annotation></semantics></math>Q of indexes that could be the best one for transition to <math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i, make sure the gradients is not increasing (forming a convex hull). The best index is the last whose gradient is greater than <math><semantics><mrow><msub><mi>y</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">y_i</annotation></semantics></math>yi. (In this problem, <math><semantics><mrow><msub><mi>y</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">y_i</annotation></semantics></math>yi is decreasing so that we can drop all indexes before the best one)

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

// CF. 1083E
const int N = 1e6 + 5;
struct State { int x, y; LL a; } S[N];
int n, hq = 0, tq = 1, Q[N];
LL ans = 0, F[N];

double slope(int j, int i) { return 1. * (F[i] - F[j]) / (S[i].x - S[j].x); }
LL calc(int j, int i) { return F[j] + 1LL * S[i].y * (S[i].x - S[j].x) - S[i].a; }

int main() {
 scanf("%d", &n);
 FI(i, 1, n) scanf("%d%d%lld", &S[i].x, &S[i].y, &S[i].a);
 sort(S + 1, S + 1 + n, [&](const auto & a, const auto & b) { return a.x < b.x; });
 FI(i, 1, n) {
 while (hq + 1 < tq && calc(Q[hq], i) < calc(Q[hq + 1], i)) hq++;
 F[i] = calc(Q[hq], i);
 ans = max(ans, F[i]);
 while (hq + 1 < tq && slope(Q[tq - 2], Q[tq - 1]) < slope(Q[tq - 1], i)) tq--;
 Q[tq++] = i;
 }
 printf("%lld\n", ans);
}
```

KONGROOの基地

このブログを検索

Codeforces 1083E. The Fair Nut and Rectangles (DP+Convex-Hull Trick)

コメント

コメントを投稿