Liebestraume

Piano Lover

IOI 2013 #2 Art Class

http://www.ioi2013.org/wp-content/uploads/tasks/day1/artclass/artclass.pdf

A classification problem, like the ones you see in the machine learning and vision area. Fortunately, you don’t need any fancy machine learning trick. Some ad-hoc criteria (hand-crafted features) are enough to pass the problem, because the four given classes of paintings are very distinctive in style.

#include "artclass.h"
#include<cstdio>
#include<queue>
using namespace std;

struct col
{
    double r, g, b;
    col(){}
    col(double r, double g, double b): r(r), g(g), b(b) {}
};

inline double dist2(col &c1, col &c2)
{
    return (c1.r-c2.r)*(c1.r-c2.r)+(c1.g-c2.g)*(c1.g-c2.g)+(c1.b-c2.b)*(c1.b-c2.b);
}

int n, m;

col a[500][500];
bool chk[500][500];

int dx[8]={-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8]={-1, 0, 1, 1, 1, 0, -1, -1};

int flood(int x, int y)
{
    int ret=0;
    queue<pair<int, int> > q;
    q.push(make_pair(x, y)); chk[x][y]=true;
    while(!q.empty())
    {
        ret++;
        pair<int, int> cur=q.front(); q.pop();
        int cx=cur.first, cy=cur.second;
        for(int k=0;k<8;k++)
        {
            int nx=cx+dx[k], ny=cy+dy[k];
            if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
            if(chk[nx][ny]) continue;
            if(dist2(a[cx][cy], a[nx][ny])<=300)
            {
                chk[nx][ny]=true;
                q.push(make_pair(nx, ny));
            }
        }
    }
    return ret;
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    n=H; m=W;
    int i, j, k;
    for(i=0;i<n;i++) for(j=0;j<m;j++) a[i][j]=col(R[i][j],G[i][j],B[i][j]);

    // criterion for style 3: measure noise
    int cnt=0;
    double vartot=0.0;
    for(i=1;i<n-1;i++) for(j=1;j<m-1;j++) for(k=0;k<8;k++)
    {
        int nx=i+dx[k], ny=j+dy[k];
        vartot+=dist2(a[i][j], a[nx][ny]);
        cnt++;
    }
    double crit3=vartot/cnt;
    if(crit3>3000) return 3;
    
    // style 4: measure noise for x and y direction and compare magnitude
    double xntot=0.0, yntot=0.0;
    int xncnt=0, yncnt=0;
    for(i=n/10;i<n*9/10;i++) for(j=m/10;j<m*9/10;j++)
    {
        if(i<n-1){xntot+=dist2(a[i][j], a[i+1][j]); xncnt++;}
        if(j<m-1){yntot+=dist2(a[i][j], a[i][j+1]); yncnt++;}
    }
    xntot/=xncnt; yntot/=yncnt;
    double crit4=max(xntot, yntot)/min(xntot, yntot);
    if(crit4>2.0) return 4;

    // style 2: measure how "green" the picture is
    cnt=0;
    double ngtot=0.0;
    for(i=0;i<n;i++) for(j=0;j<m;j++)
    {
        double penalty;
        if(a[i][j].g>=60) penalty=0;
        else penalty=(60-a[i][j].g)*(60-a[i][j].g);
        ngtot+=(a[i][j].r*a[i][j].r+a[i][j].b*a[i][j].b)+penalty;
        cnt++;
    }
    double crit2=ngtot/cnt;
    if(10000<crit2 && crit2<33000) return 2;
    
    // style 4 again: number of "areas" is small
    cnt=0;
    for(i=0;i<n;i++) for(j=0;j<m;j++)
    {
        if(chk[i][j]) continue;
        int area=flood(i, j);
        if(area>10) cnt++;
    }
    if(cnt<10) return 4;

    // style 1 (can be improved): colors consist of white, black, red, blue, yellow,
    //                            and two misc. colors observed from the samples
    const int r=7;
    col vib[r];
    vib[0]=col(255,0,0);
    vib[1]=col(255,255,255);
    vib[2]=col(0,0,0);
    vib[3]=col(0,0,255);
    vib[4]=col(255,255,0);
    vib[5]=col(190,190,190);
    vib[6]=col(180,180,210);
    cnt=0;
    for(i=0;i<n;i++) for(j=0;j<m;j++)
    {
        double mdist=dist2(vib[0], a[i][j]);
        for(k=1;k<r;k++) mdist=min(mdist, dist2(vib[k], a[i][j]));
        if(mdist<=2500) cnt++;
    }
    double crit1=(double)(cnt)/(n*m);
    if(crit1>0.3) return 1;

    // misc. criteria
    if(crit3>2000) return 3; // not that noisy but fairly so
    if(crit1<0.05) return 4; // more likely to be of type 4 than 1
    return 1; // give up and return 1, for which the criterion wasn't good enough anyway
}

IOI 2010 #6 TRAFFIC

http://plg1.cs.uwaterloo.ca/~gvcormac/day2task2/

This problem is very similar to one of the IOI 2003 sample (!) problems Balancing Act; this is nothing but a generalized version of the old problem. Basically, you want to find a node such that when removed from a tree, produces the most “balanced” forest, where each node has a weight. Both the algorithm and the implementation are pretty simple.

#include "traffic.h"
#include <algorithm>
using namespace std;

struct edge{int e, nxt;};
edge e[1<<21];
int sp[1<<20];

int m;
int tot;
int q[1<<20], hd, tl;
int tots[1<<20], maxs[1<<20];
int par[1<<20];
bool v[1<<20];

int LocateCentre(int N, int pp[], int S[], int D[]) {
   int i, k;
   for(i = 0; i < N; i++) tot += pp[i];
   for(i = 0; i < N - 1; i++) {
      e[++m].e = D[i]; e[m].nxt = sp[S[i]]; sp[S[i]] = m;
      e[++m].e = S[i]; e[m].nxt = sp[D[i]]; sp[D[i]] = m;
   }
   q[0] = 0; v[0] = true; par[0] = -1;
   hd = 0; tl = 1;
   while(hd < tl) {
      for(i = sp[q[hd]]; i; i = e[i].nxt) {
         if(v[e[i].e]) continue;
         v[e[i].e] = true;
         q[tl++] = e[i].e;
         par[e[i].e] = q[hd];
      }
      hd++;
   }
   for(k = N - 1; k >= 0; k--) {
      i = q[k];
      tots[i] += pp[i];
      maxs[i] = max(maxs[i], tot - tots[i]);
      if(par[i] >= 0) {
         tots[par[i]] += tots[i];
         maxs[par[i]] = max(maxs[par[i]], tots[i]);
      }
   }
   int minval = tot + 1;
   int ret = -1;
   for(i = 0; i < N; i++)
      if(minval > maxs[i]) {
         minval = maxs[i];
         ret = i;
      }
   return ret;
}

IOI 2010 #5 MEMORY

http://plg1.cs.uwaterloo.ca/~gvcormac/day2task1/

I was working on a Windows machine, so I coded this up without compiling… I’ll have to use the lab computer for the other problems though. This one was easy enough to code without compiling. I verified the code on the IOI testing server.

#include "grader.h"
#include "memory.h"
#include <vector>
using namespace std;

vector<int> mem[26];

void play() {
   int i;
   for(i = 1; i <= 50; i+=2) {
      char c = faceup(i);
      mem[c-'A'].push_back(i);
      c = faceup(i+1);
      mem[c-'A'].push_back(i+1);
   }
   for(i = 0; i < 25; i++) {
      faceup(mem[i][0]);
      faceup(mem[i][1]);
   }
}

IOI 2010 #3 QUALITY

http://plg1.cs.uwaterloo.ca/~gvcormac/day1task3/

The solution is to use binary search on the answer. See one of my latest posts for more details. My argument in the post was not entirely correct, but it’s fixed now. Note the inequality <= in line 26. This tests whether the current guess is feasible or is “pessimistic.” In any case, we can proceed in the same way.

#include "quality.h"
#include <memory.h>

int a[3001][3001];

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
   int i, j;
   for(i = R; i >= 1; i--) {
      for(j = C; j >= 1; j--) Q[i][j] = Q[i-1][j-1];
   }
   int s = 1, e = R * C, mid;
   int ret = 0;
   memset(a, 0, sizeof(a));
   while(s <= e) {
      mid = (s + e) / 2;
      for(i = 1; i <= R; i++) {
         for(j = 1; j <= C; j++) {
            a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1];
            if(Q[i][j] > mid) a[i][j]++;
            else if(Q[i][j] < mid) a[i][j]--;
         }
      }
      bool flag = false;
      for(i = H; i <= R; i++) {
         for(j = W; j <= C; j++) {
            if(a[i][j] - a[i-H][j] - a[i][j-W] + a[i-H][j-W] <= 0) {
               flag = true;
               break;
            }
         }
         if(flag) break;
      }
      if(flag){ret = mid; e = mid - 1;}
      else s = mid + 1;
   }
   return ret;
}

IOI 2010 #1 CLUEDO

http://plg1.cs.uwaterloo.ca/~gvcormac/day1task1/

I feel sorry to those who didn’t get 100 points on this problem, as this had a 10-line solution…

#include "grader.h"
#include "cluedo.h"

void Solve(){
   int r;
   int a[4]={0, 1, 1, 1};
   while((r = Theory(a[1], a[2], a[3])) != 0)
       a[r]++;
}

Project Euler 255

http://projecteuler.net/index.php?section=problems&id=255

This problem bugged me for a long time. Basically the problem asks you to find the sum of f(n) for all 14-digit n. The trick here is to use the fact that f(n) changes very slowly. Then, instead of looping over n and compute the sum, we can loop over the value of f(n) and compute the number of n which gives the designated f(n) value. I’ve ran into a similar problem before. If I remember correctly, the problem was to compute the sum of n mod k for all k such that 1 <= k <= n. Two different approaches can be used together in this problem to yield an O(sqrt(n)) algorithm.

KOI 2010 #2 CHAIN

The original problem is in Korean and I can’t find any translated version, so I just rephrase the problem here.

There is a city represented by a connected graph with N nodes (N <= 100000) and bidirectional M weighted edges connecting these nodes. Each node is adjacent to at most five edges, and all weights are positive. Among the nodes, exactly three of them are residential areas. Let’s denote them as A, B, and C. You want to build a store at one of the nodes such that the distances to the residential districts are small. Among all the candidate locations, some of them are strictly worse then the others. For example, let p and q be candidate locations, and the distances to the residential areas from p be a, b, c, and the distances from q be x, y, z. If a > x, b > y, and c > z, p is strictly worse than q and we don’t want to build a store there. Given Q queries about the candidate locations (Q <= N), determine whether they are strictly worse than some other locations or not.

Quite an easy graph problem. Basically, each location can be represented as a triplet (x, y, z), where the numbers denote the distance to the residential areas. Then, we want to find all “minimal” (not “minimum”) elements. The first step is to compute the minimum distances from A, B, and C, and this can be done by running Dijkstra’s algorithm three times. This step takes O(N log N) time since the degree of each node is at most 5, which is constant. After generating all these triplets, we sort them by the first coordinate, leaving only (y, z) pairs. Now, (y2, z2) is worse than (y1, z1) if (y1, z1) appears earlier in the list and has y1 < y2 and z1 < z2. The second step is to find all pairs that are worse than something else. I implemented this by using a binary indexed tree. For the current (y2, z2) pair, find the minimum value of z1 whose y1 value is smaller than y2. If z1 < z2, we check (y2, z2) as bad. Otherwise, we put z2 into the tree at location y2, so that we can look up this value later on. The time complexity is therefore O(N log N). Here is my not-very-clean source code. But it works. Whatever.

#include<cstdio>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#define mp make_pair
using namespace std;
FILE *ifp=fopen("input.txt", "r");
FILE *ofp=fopen("output.txt", "w");
struct edge{int e, len;};
struct coord
{
	int x, y, z, ind;
	const bool operator < (const coord& o) const
	{
		if(x!=o.x) return x<o.x;
		if(y!=o.y) return y<o.y;
		if(z!=o.z) return z<o.z;
		return ind<o.ind;
	}
};
const int inf=2000000000;
int n;
int deg[131072];
edge a[131072][8];
int dis[3][131072];
bool chk[131072];
coord b[131072];
bool bad[131072];
int c[262144], sp;
void dijkstra(int s, int *d)
{
	int i;
	for(i=1;i<=n;i++) d[i]=inf;
	d[s]=0;
	memset(chk, false, sizeof(chk));
	priority_queue<pair<int, int> > q;
	q.push(mp(0, s));
	while(!q.empty())
	{
		pair<int, int> cur=q.top(); q.pop();
		int x=cur.second, dis=-cur.first;
		if(dis>d[x] || chk[x]) continue;
		chk[x]=true;
		for(i=1;i<=deg[x];i++)
		{
			if(d[a[x][i].e]<=dis+a[x][i].len) continue;
			d[a[x][i].e]=dis+a[x][i].len;
			q.push(mp(-d[a[x][i].e], a[x][i].e));
		}
	}
	map<int, int> newdis;
	set<int> diss;
	set<int>::iterator it;
	for(i=1;i<=n;i++) diss.insert(d[i]);
	for(i=0, it=diss.begin();it!=diss.end();i++, ++it)
		newdis[*it]=i;
	for(i=1;i<=n;i++) d[i]=newdis[d[i]];
}
int get_minimum(int s, int e)
{
	int ret=inf;
	s+=sp; e+=sp;
	while(s<=e)
	{
		if(s==e)
		{
			ret=min(ret, c[s]);
			break;
		}
		if(s&1){ret=min(ret, c[s]); s=(s+1)>>1;}
		else s>>=1;
		if(e&1) e>>=1;
		else{ret=min(ret, c[e]); e=(e-1)>>1;}
	}
	return ret;
}
void insert_bit(int x, int val)
{
	x+=sp;
	while(x && c[x]>val){c[x]=val; x>>=1;}
}
int main()
{
	int i, j;
	int m;
	int s1, s2, s3;
	fscanf(ifp, "%d", &n);
	fscanf(ifp, "%d%d%d", &s1, &s2, &s3);
	fscanf(ifp, "%d", &m);
	while(m--)
	{
		int s, e, len;
		fscanf(ifp, "%d%d%d", &s, &e, &len);
		a[s][++deg[s]].e=e; a[s][deg[s]].len=len;
		a[e][++deg[e]].e=s; a[e][deg[e]].len=len;
	}
	dijkstra(s1, &dis[0][0]);
	dijkstra(s2, &dis[1][0]);
	dijkstra(s3, &dis[2][0]);
	for(i=1;i<=n;i++)
	{
		b[i].x=dis[0][i];
		b[i].y=dis[1][i];
		b[i].z=dis[2][i];
		b[i].ind=i;
	}
	sort(&b[1], &b[n+1]);
	for(sp=1;sp<n;sp<<=1);
	for(i=1;i<(sp<<1);i++) c[i]=inf;
	for(i=1;i<=n;i=j)
	{
		for(j=i;b[j].x==b[i].x;j++)
		{
			if(get_minimum(0, b[j].y-1)<b[j].z) bad[b[j].ind]=true;
		}
		for(j=i;b[j].x==b[i].x;j++)
			insert_bit(b[j].y, b[j].z);
	}
	fscanf(ifp, "%d", &m);
	while(m--)
	{
		fscanf(ifp, "%d", &i);
		fprintf(ofp, "%s\n", bad[i]?"NO":"YES");
	}
	return 0;
}

IOI 2006 #5 POINTS

http://olympiads.win.tue.nl/ioi/ioi2006/contest/day2/points/Joining%20points_1.2.pdf

This was problem number 5 when I first went to the IOI, and only one person actually solved this problem completely. I got the third highest point in this problem which was 46 out of 100. The complete result of the contest is here. Basically everybody except him was destroyed by this problem, but it had such a nice, simple, and very math competition-like solution. This is easily my favorite IOI problem. Whoever came up with this fantastic problem, thank you so much.

I couldn’t solve this problem during the contest, and what I implemented was a somewhat smart brute-force algorithm. I read the solution of the problem the day after the contest, but I never implemented it. I did just now, and the code is here. Please refer to the solution sketch before reading the code.

#include<cstdio>
#include<vector>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define GREEN false
#define RED true
using namespace std;
typedef long long ll;
struct point
{
	ll x, y;
	bool color;
	int index;
};
vector<point> a;
ll s;
point ul, ur, dl, dr;
char ch[]="gr";
vector<pair<pair<int, int>, char> > ans;

void INPUT()
{
	int g, r;
	point p;
	FILE *fp=fopen("points.in", "r");

	fscanf(fp, "%d", &g);
	for(int i=1;i<=g;i++)
	{
		fscanf(fp, "%lld%lld", &p.x, &p.y);
		if(s<p.x) s=p.x;
		p.color=GREEN;
		p.index=i;
		a.pb(p);
	}

	fscanf(fp, "%d", &r);
	for(int i=1;i<=r;i++)
	{
		fscanf(fp, "%lld%lld", &p.x, &p.y);
		if(s<p.x) s=p.x;
		p.color=RED;
		p.index=i;
		a.pb(p);
	}

	fclose(fp);
}

inline ll area(point p1, point p2, point p3)
{
	return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}

bool inside(point x, point p1, point p2, point p3)
{
	return area(p1, p2, x)>0 && area(p2, p3, x)>0 && area(p3, p1, x)>0;
}

void recurse(vector<point>& points, point p, point q1, point q2)
{
	if(!points.size()) return;

	bool colors[2]={false, false};
	for(int i=0;i<points.size();i++)
		colors[points[i].color]=true;
	if(!colors[GREEN] || !colors[RED])
	{
		for(int i=0;i<points.size();i++)
		{
			if(points[i].color==p.color)
				ans.pb(mp(mp(points[i].index, p.index),
					ch[p.color]));
			else
				ans.pb(mp(mp(points[i].index, q1.index),
					ch[q1.color]));
		}
		return;
	}

	for(int i=0;i<points.size();i++)
	{
		if(points[i].color==p.color)
		{
			swap(points[0], points[i]);
			break;
		}
	}
	point pivot=points[0];
	ans.pb(mp(mp(pivot.index, p.index), ch[p.color]));

	vector<point> v1, v2, v3;
	for(int i=1;i<points.size();i++)
	{
		if(inside(points[i], p, q1, pivot)) v1.pb(points[i]);
		else if(inside(points[i], q1, q2, pivot)) v2.pb(points[i]);
		else v3.pb(points[i]);
	}
	points.clear();

	recurse(v1, q1, pivot, p);
	recurse(v2, pivot, q1, q2);
	recurse(v3, q2, p, pivot);
}

void process()
{
	vector<point> u, d;
	for(int i=0;i<a.size();i++)
	{
		if(a[i].x==0 && a[i].y==0) dl=a[i];
		else if(a[i].x==s && a[i].y==0) dr=a[i];
		else if(a[i].x==0 && a[i].y==s) ul=a[i];
		else if(a[i].x==s && a[i].y==s) ur=a[i];
		else if(a[i].x>a[i].y) d.pb(a[i]);
		else u.pb(a[i]);
	}
	random_shuffle(d.begin(), d.end());
	random_shuffle(u.begin(), u.end());
	ans.pb(mp(mp(dl.index, dr.index), ch[dl.color]));
	ans.pb(mp(mp(ul.index, ur.index), ch[ul.color]));
	recurse(u, dl, ur, ul);
	recurse(d, ur, dl, dr);
}

void OUTPUT()
{
	FILE *ofp=fopen("points.out", "w");

	for(int i=0;i<ans.size();i++)
		fprintf(ofp, "%d %d %c\n",
			ans[i].first.first,
			ans[i].first.second,
			ans[i].second);

	fclose(ofp);
}

int main()
{
	INPUT();
	process();
	OUTPUT();
	return 0;
}

Project Euler 268

http://projecteuler.net/index.php?section=problems&id=268

I used an extension of PIE to compute the number of elements which are contained in at least 4 sets. The code is rather short, but figuring out the formula took some time. Good problem.

Project Euler 48

http://projecteuler.net/index.php?section=problems&id=48

I almost tempted to do this with Mathematica, but I thought it would be too cheap. Fortunately, you can solve this without using big integers. 64-bit integers are fine.

#include<cstdio>
#include<ctime>
double start_time=clock();
typedef long long ll;
ll sum;
int main()
{
	int i, j;
	ll d;
	ll BASE=1;
	for(i=1;i<=10;i++) BASE*=10;
	for(i=1;i<=1000;i++)
	{
		d=1;
		for(j=1;j<=i;j++) d=(d*i)%BASE;
		sum=(sum+d)%BASE;
	}
	printf("%lld\n", sum%BASE);
	printf("%.3lf secs\n", (clock()-start_time)/CLOCKS_PER_SEC);
	return 0;
}