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
}