APIO 2017 Problems and Solutions

The official APIO 2017 Problems and solutions in this post.

Problem – A (Koala Game) :

Solution – A (Koala Game) :

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;

#define FO(i,a,b) for (int i = (a); i < (b); i++)
#define pb push_back
#define sz(v) ((int)v.size())

struct Query {
    vector <int> am;
};

struct Response {
    vector <bool> v;
};

int N, W;

Response makeQuery (Query q) {
    int *B = (int *)malloc(sizeof(int)*N);
    FO (i,0,N) B[i] = q.am[i];
    int *R = (int *)malloc(sizeof(int)*N);
    playRound(B,R);
    Response r;
    FO (i,0,N) {
        if (R[i] > B[i]) {
            r.v.pb(true);
        } else {
            r.v.pb(false);
        }
    }
    free(B);
    free(R);
    return r;
}

Response makeUniformQuery (set<int> &cand, int am) {
    Query q;
    FO (i,0,N) {
        if (cand.find(i) != cand.end()) {
            q.am.pb(am);
        } else {
            q.am.pb(0);
        }
    }
    return makeQuery(q);
}

set<int> responseToSet (Response r) {
    set <int> s;
    FO (i,0,N) if (r.v[i]) s.insert(i);
    return s;
}

int minValue(int _N, int _W) {
    N = _N; W = _W;
    set <int> cand;
    cand.insert(0);
    Response r = makeUniformQuery(cand, 1);
    FO (i,0,N) {
        if (!r.v[i]) return i;
    }
    assert (false);
}

int actualGetMax() {
    set <int> cand;
    FO (i,0,N) cand.insert(i);
    while (cand.size() > 1) {
        Response r = makeUniformQuery(cand, W/(int)cand.size());
        set <int> newC;
        FO (i,0,N) if (cand.find(i) != cand.end() && r.v[i]) newC.insert(i);
        cand = newC;
    }
    return *(cand.begin());
}

int maxValue(int _N, int _W) {
    N = _N; W = _W;
    return actualGetMax();
}

int greaterValue(int _N, int _W) {
    N = _N; W = _W;
    set <int> f2 = {0,1};
    int cands[4] = {1,3,6,8};
    int lo = 0;
    int hi = 3;
    int mid;
    while (lo <= hi) {
        mid = (lo+hi)/2;
        Response r = makeUniformQuery(f2, cands[mid]);
        set <int> origRes = responseToSet(r);
        set <int> res;
        for (auto c : f2) {
            if (origRes.find(c) != origRes.end()) res.insert(c);
        }
        switch (res.size()) {
            case 0:
                hi = mid-1;
                break;
            case 1:
                return *(res.begin());
            case 2:
                lo = mid+1;
                break;
        }
    }
    assert(false);
}

vector <int> sortRange (vector <int> vals);
void solveMain(int *P);
void allValues(int _N, int _W, int *P) {
    N = _N; W = _W;
    if (_W == 2*_N) {
        vector <int> startVals;
        FO (i,0,N) startVals.pb(i);
        vector <int> endVals = sortRange(startVals);
        FO (i,0,N) P[endVals[i]] = N-i;
    } else {
        solveMain(P);
    }
}

// returns greater of the 2
int sub4cmp(int a, int b) {
    set<int> vals = {a,b};
    set<int> takens = responseToSet(makeUniformQuery(vals, W/2));
    if (takens.find(a) != takens.end()) return a;
    else return b;
}

vector <int> sortRange (vector <int> vals) {
    if (vals.size() == 1) return vals;
    vector <int> fV, sV;
    FO (i,0,sz(vals)) {
        if (i%2) sV.pb(vals[i]);
        else fV.pb(vals[i]);
    }
    vector <int> sF = sortRange(fV);
    vector <int> sS = sortRange(sV);
    int fI(0), sI(0);
    vector <int> retV;
    while (fI < sz(sF) || sI < sz(sS)) {
        if (fI == sz(sF)) retV.pb(sS[sI++]);
        else if (sI == sz(sS)) retV.pb(sF[fI++]);
        else {
            if (sub4cmp(sF[fI], sS[sI]) == sF[fI]) {
                retV.pb(sF[fI++]);
            } else {
                retV.pb(sS[sI++]);
            }
        }
    }
    return retV;
}

set <int> lowestVals;
#define N_BUCKETS 9
#define B_SIZ 10
vector <int> startBuckets[N_BUCKETS];
vector <int> sortedB[N_BUCKETS];
int valToPos[105];

int maxInSet(set<int> &s) {
    // Need this:
    assert(s.size() <= 9);
    set<int> qSet(s);
    for (int i = 10; i >= 1; i--) {
        if (qSet.size() == 9) break;
        qSet.insert(valToPos[i]);
    }
    set<int> taken;
    if (s.size() == 1) {
        taken = responseToSet(makeUniformQuery(qSet, 10));
    } else {
        taken = responseToSet(makeUniformQuery(qSet, 11));
    }
    for (int v : s) {
        if (taken.find(v) != taken.end()) return v;
    }
    assert(false);
}

void solveMain (int *P) {
    lowestVals.clear();
    FO (i,0,N_BUCKETS) {
        startBuckets[i].clear();
        sortedB[i].clear();
    }
    int mx = actualGetMax();
    set<int> mxSet({mx});
    set<int> notLowestVals = 
        responseToSet(makeUniformQuery(mxSet, 10));
    FO (i,0,N) {
        if (notLowestVals.count(i) == 0) lowestVals.insert(i);
    }
    assert(lowestVals.size() == 10);
    FO (i,0,N) {
        if (lowestVals.find(i) != lowestVals.end()) continue;
        FO (b,0,N_BUCKETS) {
            if (startBuckets[b].size() < B_SIZ) {
                startBuckets[b].pb(i);
                break;
            }
        }
    }
    // Get bottom 10:
    set <int> lowLeft (lowestVals);
    while (lowLeft.size()) {
        if (lowLeft.size() == 1) {
            valToPos[1] = *lowLeft.begin();
            break;
        }
        set <int> res =
            responseToSet(makeUniformQuery(lowLeft, lowLeft.size()-1));
        for (int v : res) {
            if (lowLeft.find(v) != lowLeft.end()) {
                valToPos[lowLeft.size()] = v;
                lowLeft.erase(v);
                break;
            }
        }
    }
    FO (b,0,N_BUCKETS) {
        set <int> remThings(startBuckets[b].begin(), startBuckets[b].end());
        while (remThings.size()) {
            if (remThings.size() == 10) {
                // one special case:
                set <int> res = responseToSet(makeUniformQuery(remThings, 10));
                set <int> cMax;
                for (int v : res) {
                    if (remThings.find(v) != remThings.end()) {
                        cMax.insert(v);
                    }
                }
                if (cMax.size() == 2) {
                    int mx = maxInSet(cMax);
                    sortedB[b].pb(mx);
                    cMax.erase(mx);
                    sortedB[b].pb(*cMax.begin());
                    remThings.erase(mx);
                    remThings.erase(*cMax.begin());
                } else if (cMax.size() == 1) {
                    sortedB[b].pb(*cMax.begin());
                    remThings.erase(*cMax.begin());
                } else {
                    assert(false);
                }
            } else {
                int mx;
                if (remThings.size() == 1) mx = *remThings.begin();
                else mx = maxInSet(remThings);
                sortedB[b].pb(mx);
                remThings.erase(mx);
            }
        }
    }
    // Merge buckets:
    // Sort buckets into increasing order not decreasing:
    FO (i,0,N_BUCKETS) reverse(sortedB[i].begin(), sortedB[i].end());
    vector <int> sortedAll;
    while(true) {
        set <int> cFronts;
        FO (i,0,N_BUCKETS) {
            if (sortedB[i].size()) {
                cFronts.insert(sortedB[i].back());
            }
        }
        if (cFronts.empty()) break;
        int mx = maxInSet(cFronts);
        sortedAll.pb(mx);
        FO (i,0,N_BUCKETS) {
            if (sortedB[i].size() && sortedB[i].back() == mx) {
                sortedB[i].pop_back();
            }
        }
    }
    for (int i = 10; i >= 1; i--) {
        sortedAll.pb(valToPos[i]);
    }
    FO (i,0,sz(sortedAll)) {
        P[sortedAll[i]] = N-i;
    }
}

Download Full Solution File

Problem – B (Merchant) :

en-1

Solution – B (Merchant) :

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, lint> pi;

int n, m, k;
int b[105][1005], s[105][1005];
int adj[105][105], dx[105][105];
llf gph[105][105];

bool trial(llf t){
	// TotalProfit - t * TotalTime > 0
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(adj[i][j] > 1e9 + 10) gph[i][j] = -1e12;
			else gph[i][j] = dx[i][j] - t * adj[i][j];
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			for(int k=1; k<=n; k++){
				gph[j][k] = max(gph[j][k], gph[j][i] + gph[i][k]);
			}
		}
	}
	for(int i=1; i<=n; i++){
		if(gph[i][i] >= 0) return 1;
	}
	return 0;
}

int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1; i<=n; i++){
		for(int j=0; j<k; j++) scanf("%d %d",&b[i][j],&s[i][j]);
	}
	memset(adj, 0x3f, sizeof(adj));
	for(int i=0; i<m; i++){
		int s, e, x;
		scanf("%d %d %d",&s,&e,&x);
		adj[s][e] = x;
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			for(int k=1; k<=n; k++){
				adj[j][k] = min(adj[j][i] + adj[i][k], adj[j][k]);
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			for(int l=0; l<k; l++){
				if(~s[j][l] && ~b[i][l]) dx[i][j] = max(dx[i][j], s[j][l] - b[i][l]);
			}
		}
	}
	llf s = 0, e = 2e9;
	for(int i=0; i<100; i++){
		llf m = (s+e)/2;
		if(trial(m)) s = m;
		else e = m;
	}
	printf("%lld",(lint)floor(e));
}

Problem – C (Land of the Rainbow Gold) :

en-2

Solution – C (Land of the Rainbow Gold) :

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
const int MAXT = 20000000;
const int MAXN = 200005;

struct node{
	int l, r, sum;
}pool[MAXT];
int piv;

int newnode(){ return ++piv; }

void init(int s, int e, int p){
	if(s == e) return;
	int m = (s+e)/2;
	pool[p].l = newnode();
	pool[p].r = newnode();
	init(s, m, pool[p].l);
	init(m+1, e, pool[p].r);
}

void add(int pos, int s, int e, int prv, int cur){
	pool[cur].sum = pool[prv].sum + 1;
	if(s == e) return;
	int m = (s+e)/2;
	if(pos <= m){
		pool[cur].l = newnode();
		pool[cur].r = pool[prv].r;
		add(pos, s, m, pool[prv].l, pool[cur].l);
	}
	else{
		pool[cur].l = pool[prv].l;
		pool[cur].r = newnode();
		add(pos, m+1, e, pool[prv].r, pool[cur].r);
	}
}

int query(int s, int e, int ps, int pe, int p){
	if(e < ps || pe < s) return 0;
	if(s <= ps && pe <= e) return pool[p].sum;
	int pm = (ps + pe) / 2;
	return query(s, e, ps, pm, pool[p].l) + query(s, e, pm+1, pe, pool[p].r);
}

int tree[4][MAXN];
vector<int> v[4][MAXN];
int minx = 1e9, miny = 1e9, maxx = -1e9, maxy = -1e9, yMax;

void init(int R, int C, int sr, int sc, int M, char *S) {
	auto upload = [&](int x, int y){
		v[0][x].push_back(y);
		v[0][x].push_back(y + 1);
		v[0][x + 1].push_back(y);
		v[0][x + 1].push_back(y + 1);
		v[1][x].push_back(y);
		v[1][x].push_back(y + 1);
		v[2][x].push_back(y);
		v[2][x + 1].push_back(y);
		v[3][x].push_back(y);
		minx = min(minx, x); maxx = max(maxx, x + 1);
		miny = min(miny, y); maxy = max(maxy, y + 1);
	};
	upload(sr, sc);
	for(int i=0; i<M; i++){
		if(S[i] == 'N') sr--;
		if(S[i] == 'S') sr++;
		if(S[i] == 'E') sc++;
		if(S[i] == 'W') sc--;
		upload(sr, sc);
	}
	yMax = C + 1;
	for(int i=0; i<4; i++){
		tree[i][0] = newnode();
		init(1, yMax, tree[i][0]); 
		for(int j=1; j<=R+1; j++){
			sort(v[i][j].begin(), v[i][j].end());
			v[i][j].resize(unique(v[i][j].begin(), v[i][j].end()) - v[i][j].begin());
			int prv = tree[i][j-1];
			for(auto &k : v[i][j]){
				int nxt = newnode();
				add(k, 1, yMax, prv, nxt);
				prv = nxt;
			}
			tree[i][j] = prv;
		}
	}
}

int colour(int ar, int ac, int br, int bc) {
	auto query_helper = [&](int idx, int sx, int ex, int sy, int ey){
		return query(sy, ey, 1, yMax, tree[idx][ex]) 
		- query(sy, ey, 1, yMax, tree[idx][sx - 1]);
	};
	int V = query_helper(0, ar + 1, br, ac + 1, bc);
	int E = query_helper(1, ar, br, ac + 1, bc) + query_helper(2, ar + 1, br, ac, bc);
	int F = query_helper(3, ar, br, ac, bc);
	if(ar < minx && maxx < br + 1 && ac < miny && maxy < bc + 1){
		return 2 + E - V - F;
	}
	return 1 + E - V - F;
}

40 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.

SL TECH ACADEMY