COFO::1437D Minimal Height Tree

• Link : COFO::1437D

Problem

• level : 1600
• tag : graphs, greedy, shortest paths, trees
• TIME
  • to understand : 5
  • to algorithm : 15
  • to code : 5
  • to debug : 0
  • understanding edit : 0

Point

• There’s a tree
• We search the tree by using BFS from the root of the tree as 1
• But we only have an array ‘a’ which is visited indices order
• Find the minimal height of the tree
• There’s one more thing
  • If there are some children from a vertex, their values are should be ascending order

Design

• This is the necessary observation to solve this problem
  • Let’s distinguish layers by height
  • Count of layer 1 will be 1 ( Because there’s only ‘1’ as root )
  • A : number of counts of layer i
  • B : number of counts of layer i+1
  • A <= B holds
  • Since we have to squeeze numbers as many as possible, every time we see sorted ascending order of numbers we put them on the same parent node
• And it’s not hard to make the algorithm to code
  • Just remember A and B
  • Which are the group sizes
    • A will be the vertices count on layer i
    • B will be at least number of A
      • If they are not sorted, B will be same number as A

Complexity

• O(N)

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;

void solve(){
	int n; cin >> n;
	vector<int> a(n + 1, 0);
	rep(i, 0, n) cin>> a[i];
	
	int gSz = 1, pos = 1, H = 0;
	while(pos < n){
		int st = pos;
		H++;
		int counted = 0;
		int en = pos;
		rep(i, st, n){
			if (a[i] > a[i+1]) counted++;
			if (counted == gSz) {
				en = i;
				break;
			}
		}
		
		if (counted < gSz) break;
		gSz = en - st +1;
		pos = en + 1;
		
	}
	cout << H << endl;
}
int main(){
    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}