codeforce 1600

COFO::1469C Building a Fence

cofo problem

COFO::1469C Building a Fence

Link : COFO::1469C

Problem

level : 1600
tag : dp, greedy, implementation, two pointers
TIME
- to understand : 10
- to algorithm : 20
- to code : 30
- to debug : 40
- understanding edit and solve with edit: 3
- Tried to solve the problem before read edit :

Point

h is given which is the ground level
Find if we can put sections above the ground correctly
Below rules should be satisfied
- the consecutive sections should have a common side of length at least 1
- the first and the last sections should stand on the corresponding ground level
- the sections between may be either on the ground level or higher, but no higher than k-1

Design

The logic is quite a simple, but the impmentation isn’t
Well, we need to manage lowest level and hight level that each section can be
- It can be corrected by comparing previous section
- Because there should be at least 1 common side
So, we compare them when we iterates the sections
- if current section does not satisfy one of the rules, it fails.

Thought process

open/close

. 그냥 다 평평하면?  무조건 된다. 
  . 그냥 주르륵 같은 높이로 세우면 높이가 1이상 겹칠테니

. Top 에서는 벽돌을 띄우면 안된다.
. 아래로 내려갈수록 최대한 그 전칸과 1칸만 겹치게한다? ( greedy )
-> greedy 가 맞다면, 이 방법대로 하면 될 것 같은데,, 


. 어려운 상황은 이런 경우에 만들어짐
  . i, i + 1, i + 2 가 있는데, i+1 의 ground 가 낮은 경우 ( TC 3 처럼 )
  . 근데 어차피 내려가야 하는 상황에는 i+1 은 i 에만 맞춰서 최대한 내려가면, 
    이는 알아서 i+2 를 만족하게 되어있음.

Complexity

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;

bool solve() {
    int n, k; cin >> n >> k;
    vector<int> gnd(n, 0);
    rep(i, 0, n) cin >> gnd[i];
    
    
    // [ prvBtm  prvBtm+1 prvBtm+2 ... prvTop -1 ] prvTop
    int prvBtm = gnd[0] + 1, prvTop = gnd[0] + k;
    rep(i, 1, n) {
        int curBtm = gnd[i] + 1, curTop = gnd[i] + (i == n-1 ? (k) : (2 * k - 1));
        if (prvTop < curBtm || curTop < prvBtm) return false;
        
        if (prvTop < curTop)
            curTop = min(curTop, prvTop + k - 1);
        
        else if (prvTop > curTop)
            curBtm = max(curBtm, prvBtm - k + 1);
        
        if (curBtm > curTop || curTop <= 0 || curTop - curBtm < k - 1) return false;
        
        prvBtm = curBtm, prvTop = curTop;
    }
    return true;
}
int main(){
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int tc; cin >> tc; while(tc--) {
        if (solve()) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}