APIO 2016 Problem and Solution

APIO 2016 Problem and Solution

The official APIO 2016 Problems and solutions in this post.

Problem – A (Boat) :

en-3

Solution – A (Boat) :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint ipow(int x, int p){
	lint ret = 1, piv = x;
	while(p){
		if(p & 1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret;
}

int n, s[505], e[505];
lint inv[1005], dp[505], sum[505], dp2[505][505];
vector<int> v;

int main(){
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> s[i] >> e[i];
		e[i]++;
		v.push_back(s[i]);
		v.push_back(e[i]);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	for(int i=1; i<=1000; i++){
		inv[i] = ipow(i, mod - 2);
	}
	dp[0] = 1;
	for(int i=1; i<v.size(); i++){
		int st = v[i-1], ed = v[i];
		vector<int> cnd;
		sum[0] = 1;
		for(int j=1; j<=n; j++){
			sum[j] = (sum[j-1] + dp[j]) % mod;
			if(s[j] <= st && ed <= e[j]){
				cnd.push_back(j);
			}
		}
		for(int i=1; i<=cnd.size() && i <= ed - st; i++){
			for(int j=i-1; j<cnd.size(); j++){
				if(i == 1){
					dp2[i][j] = sum[cnd[j] - 1] * (ed - st);
					if(j) dp2[i][j] += dp2[i][j-1];
					dp2[i][j] %= mod;
				}
				else{
					dp2[i][j] = (dp2[i-1][j-1] * inv[i] % mod) * (ed - st + 1 - i) + dp2[i][j-1];
					dp2[i][j] %= mod;
				}
			}
		}
		for(int i=1; i<=cnd.size() && i <= ed - st; i++){
			for(int j=i-1; j<cnd.size(); j++){
				int cnt = dp2[i][j] - (j ? dp2[i][j-1] : 0) + mod;
				cnt %= mod;
				dp[cnd[j]] += cnt;
				dp[cnd[j]] %= mod;
			}
		}
	}
	int ret= 0;
	for(int i=1; i<=n; i++){
		ret += dp[i];
		ret %= mod;
	}
	cout << ret;
}

Problem – A (Fireworks) :

en-4

Solution – A (Fireworks) :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const lint inf = 1e16;
 
int n, m, sz[300005];
lint dep[300005], c[300005];
 
vector<int> gph[300005];
 
struct func{
    priority_queue<lint> pq;
    lint cost;
    int slope;
    void init(){
        cost = 0;
        slope = -1;
        pq.push(0);
        pq.push(0);
    }
    void upperize(int x){
        cost += c[x];
        while(!pq.empty() && slope + (int)pq.size() > 1){
            pq.pop();
        }
        vector<lint> v;
        while(!pq.empty() && slope + (int)pq.size() >= 0){
            v.push_back(pq.top());
            pq.pop();
        }
        while(!v.empty()){
            pq.push(v.back() + c[x]);
            v.pop_back();
        }
    }
}dp[300005];
 
bool cmp(int a, int b){
    return sz[a] > sz[b];
}
 
void dfs(int x){
    if(x > n){
        sz[x] = 1;
        return;
    }
    for(int i=0; i<gph[x].size(); i++){
        dep[gph[x][i]] = dep[x] + c[gph[x][i]];
        dfs(gph[x][i]);
        sz[x] += sz[gph[x][i]];
    }
    sort(gph[x].begin(), gph[x].end(), cmp);
}
 
int solve(int x){
    if(x > n){
        dp[x].init();
        return x;
    }
    int ret = solve(gph[x][0]);
    dp[ret].upperize(gph[x][0]);
    for(int i=1; i<gph[x].size(); i++){
        int t = solve(gph[x][i]);
        dp[t].upperize(gph[x][i]);
        dp[ret].cost += dp[t].cost;
        dp[ret].slope += dp[t].slope;
        while(!dp[t].pq.empty()){
            dp[ret].pq.push(dp[t].pq.top());
            dp[t].pq.pop();
        }
    }
    return ret;
}
 
int main(){
    cin >> n >> m;
    for(int i=2; i<=n+m; i++){
        int p;
        scanf("%d %lld",&p,&c[i]);
        gph[p].push_back(i);
    }
    dfs(1);
    func ret = dp[solve(1)];
    ret.upperize(0);
    lint ansp = ret.pq.top();
    lint ans = ret.cost + ansp * ret.slope;
    while(!ret.pq.empty()){
        ans += ansp - ret.pq.top();
        ret.pq.pop();
    }
    printf("%lld",ans);
}

Problem – C (Gap) :

en-5

Solution – C (Gap) :

#include "gap.h"
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;

pi query(lint s, lint e){
	pi ret;
	MinMax(s, e, &ret.first, &ret.second);
	return ret;
}

long long findGap(int T, int N)
{
	vector<lint> a;
	lint ret = 0;
	if(T == 1){
		lint s = 0, e = 2e18;
		while(N >= 1){
			auto t = query(s, e);
			a.push_back(t.first);
			a.push_back(t.second);
			s = t.first + 1, e = t.second - 1;
			N -= 2;
		}
	}
	else{
		pi q = query(0, 2e18);
		lint triv = (q.second - q.first + N - 2) / (N - 1);
		ret = triv;
		for(lint p = q.first; p <= q.second; p += triv + 1){
			auto t = query(p, p + triv);
			a.push_back(t.first);
			a.push_back(t.second);
		}
	}
	sort(a.begin(), a.end());
	for(int i=0; i<a.size()-1; i++){
		ret = max(ret, a[i+1] - a[i]);
	}
	return ret;
}

 77 total views,  1 views today

Post Disclaimer

The hole problem statement are given by apio-olympiad.org but the solution are generated by the sltechnicalacademy authority if any of the query regarding this post or website fill the following contact form thank you. 

Leave a Reply

Your email address will not be published. Required fields are marked *