USACO US Open 2009 Gold 3 - Tower of Hay

USACO US Open 2009 Gold 3 - Tower of Hay
BOJ 6116 케이크

1st Step

First, we can consider a greedy approach.
By the following perspective: "lower the last floor, better it is"So we greedily choose the lowest last floor possible. (e.g. the last floor consists of only one bale)
ex) 9 1 2 4 7 => 9 / 1 2 4 / 7

 

However we can find out this is wrong.
Consider "3 3 1 2".
choosing only '2' at the last eventually makes a wrong solution.
we should chooose 3 / 3 / 1 2

2nd Step

Let's flip the array for our future convinience.
In this case, we want to make a tower of increasing layer width.

 

consider "2 1 3 3" again.
choosing only '2' led to make 2 / 1 3
which made the tower's top width more larger than 2 1 / 3
From this example, we should make the lowest-top-width among the same-height towers.

We need one observation for our next step.

Argument: for Towers made of bales $[1,i]$, minimum top width is non-increasing respect to the tower height if it exists.

proof: It looks kinda trivial, but it turns out this is hard to prove it. I'm not even sure this is actually true.

 

Let's find some another good observation.
Here it is.
Instead of the above lemma, let's prove below.

Lemma: The highest tower has the minimum top width.

proof:
let tower A be any maximum height tower.
and tower B be any minimum top width tower.

 

let Tower A consist of layer
$[A_{a},A_{a-1}-1], [A_{a-1}, A_{a-2}-1], \cdots ,[A_{1},n]$

 

let Tower B consist of layer
$[B_{b},B_{b-1}-1], [B_{b-1}, B_{b-2}-1], \cdots ,[B_{1},n]$

 

Note that index is from the top, $A_{a}=B_{b}=1$, and $a \ge b$

 

$A_{1} \le B_{1}$ by the definition of A and B.

 

there exists some minimum $k$ such that

$A_{k}\ge B_{k}, \ A_{k-1}\le B_{k-1}$

 

which implies $B_{k} \le A_{k} \le A_{k-1} \le B_{k-1}$,
the $k$th layer of B entirely includes the $k$th layer of A.

 

if we expand the $k$th layer of $A$, it still holds the width increasing condition, and we can just simply apply the rest $k-1$ layer of $B$.

 

Impressive! We can now obtain the Tower that has the same height with Tower A, and the same top layer width with Tower B.

 

The very first lemma can be proven using a similar way.

3rd Step

By the Lemma, we derive that the tower having the highest height will simultaneously have the smallest width.
let
$dp(i)$: highest height using $[1,i]$
$width(i)$: the minimum top width using $[1,i]$
$s(i)$: prefix sum of $w(i)$.

 

we can handle $dp(i)$ and $width(i)$ together!

 

we need to find some maximum $j$ such that
$width(j) \le wsum([j+1,i]) = s(i) - s(j)$
Note that choosing maximum $j$ will lead to minimum top width, which leads to maximum height.

 

organizing the inequality, $width(j) + s(j) \le s(i)$ ---- (#)

let $val(i) = width(j) + s(j)$
monotonicity:  for $a < b$, if $val(a) \ge val(b)$, we don't need to consider $a$ at all.

 

Therefore we can maintain a deque that manages $val(i)$ strictly increasing.
since $s(i)$ is increasing at (#), we can find the maximum $j$ for each $i$ in amortized $O(1)$, total $O(N)$.

Source Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int s[N], dp[N], width[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin>>n;
    for(int i=n;i>=1;i--) cin>>s[i];
    deque<int> dq = {0};
    auto val = [&](int i){ return width[i] + s[i];};
    for(int i=1,j;i<=n;i++){
        s[i] += s[i-1];
        while(!dq.empty() && val(dq.front()) <= s[i]) j = dq.front(), dq.pop_front();
        dq.push_front(j);
        dp[i] = dp[j] + 1;
        width[i] = s[i] - s[j];
        while(val(i) <= val(dq.back())) dq.pop_back();
        dq.push_back(i);
    }
    cout<<dp[n];
}