MCO 2015 Questions and Answers ?>

MCO 2015 Questions and Answers

Assalamualaikum everyone. On 19th April 2015, IIUM hosted the Malaysia Computing Olympiad 2015. MCO is basically the IOI (International Olympiad Informatics) for Malaysia. And IOI is basically ACM-ICPC for high school student. The format are also a bit different compared to ACM ICPC. In IOI, they contestant compete individually instead of in teams. Also, in IOI they are given 5 problems and 3 hours 2 days to solve. And instead of a ‘Yes/No’ verdict, they have 3 ‘levels’ of correctness (‘sub-tasks’ to be more precise). For example, if they use a naive method, the may pass first level. But not the other 2 level. If they manage to make an efficient solution, then they may pass all the ‘level’. These are the question given on MCO 2015.

MCO 2015 Question


We do not have the data set, only the question. However after the competition, we were given a period of time to access the judge system to try the question ourself. In this post I will discuss my solution for the questions. Personally I think the question are quite tough. No to mention for high school student. Also, it seems that the only allowed programming language are C/C++. Because of that, in this post I will not bother to put lots of comment, remove my macros and put a separate solution for Java. So for beginners, my solution may be hard to digest.

Badminton

The first question, Badminton are quite easy. Just simulate it. No tricks detected.

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

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

#ifdef DEBUG
#define dbg(msg) msg
#define dbgp(msg) cout << msg << endl;
#define var(v) cout << #v << " = " << v << endl;
#else
#define dbg(msg) //msg
#define dbgp(msg) //cout << msg << endl;
#define var(v) //cout << #v << " = " << v << endl;
#endif

using namespace std;

int main(int argv, char** argc){
  cin.sync_with_stdio(0);

  string input;
  cin >> input;

  int ascore=0;
  int bscore=0;
  int awin = 0;
  int bwin = 0;

  REP(i,input.size()){
    if(input[i] == 'A'){
      ascore++;
    }else{
      bscore++;
    }

    if(ascore == 21 || bscore == 21){
      if(ascore == 21){
        awin++;
      }else{
        bwin++;
      }
      cout << ascore << "-" << bscore << endl;
      ascore = 0;
      bscore = 0;
    }
  }

  if(awin > bwin){
    cout << "A" << endl;
  }else{
    cout << "B" << endl;
  }

  return 0;
}

Honey

The second question, Honey is a bit tough. It involve getting the highest amount of honey possible given a certain bucket size the bee can carry and a maximum of K trip. It all looks fine. “Lets just simulate it!”. And then you see the limit for K is 2 billion. Even if you do it in linear time, it won’t work if you do a straight simulation. The trick however is not to simulate one trip at a time. But simulate multiple trip at each iteration.At each iteration, we take the flower with the highest m. If a flower have m=M*n+E amount of honey, then first, assume he took M*n bucket at one iteration where n is either m/M or K left which one is minimum. Then remove the flower, and add another flower with honey E, unless E is 0. If n = 0, then we took E honey, and remove the flower. So now, we have a maximum of 2N loop. To efficiently take the flower with highest m and put it back in a list, we use a priority queue which works at logarithmic time. So the complexity for this solution is N log N.

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

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

#ifdef DEBUG
#define dbg(msg) msg
#define dbgp(msg) cout << msg << endl;
#define var(v) cout << #v << " = " << v << endl;
#else
#define dbg(msg) //msg
#define dbgp(msg) //cout << msg << endl;
#define var(v) //cout << #v << " = " << v << endl;
#endif

using namespace std;

int main(int argv, char** argc){
  cin.sync_with_stdio(0);

  ll N,M,K;
  ll total = 0;
  cin >> N >> M >> K;

  priority_queue<ll> queue;

  REP(i,N){
    ll cur;
    cin >> cur;
    queue.push(cur);
  }

  while(queue.size() && K > 0){
    ll cur = queue.top(); queue.pop();
    ll takecount = cur/M;
    takecount = min(takecount, K);

    ll take;
    if(takecount == 0){
      K--;
      take = cur;
    }else{
      K-= takecount;
      take = M*takecount;
    }
    total += take;
    cur -= take;
    if(cur != 0){
      queue.push(cur);
    }
  }

  cout << total << endl;

  return 0;
}

Bitcoin

Personally I think Bitcoin is the hardest problem. Me and my friends keeps wondering, how in the world, will a high school student answer this question? In fact, I’m not even sure that the solution that I gave under here is the correct solution, because I tried several solution. At first glance, we see that the problem is a simple find the maximum distance between a pair of point. Simple, we just do an O(n^2) algorithm. Except that the maximum number of n is 1 million. Therefore, with a time limit of 1 second, O(n^2) is far from fast enough. After extensive googling, I figure out that we could answer this question by finding the convex hull first, then do an O(n^2) check on the outer points. That is the correct solution. However, it is still not enough to pass the third sub-task. The problem is either one of two thing, which I’m not exactly sure which one. Probably both. First, we need to remove duplicated points. Second, it turns out, the problem is limited by IO speed. And using even scanf is not fast enough. So I googled a faster IO and found this article. With the combined technique of convex hull, unique check and faster IO, I finally cracked the third sub-task. Contest for high school student right? I do found another solution based on dynamic programming which exploit the limited range of points. It basically find the longest diagonal line. It does two pass, diagonal up and diagonal down. However, it is still not fast enough (barely) to pass the third sub-task.

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

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

#ifdef DEBUG
#define dbg(msg) msg
#define dbgp(msg) cout << msg << endl;
#define var(v) cout << #v << " = " << v << endl;
#else
#define dbg(msg) //msg
#define dbgp(msg) //cout << msg << endl;
#define var(v) //cout << #v << " = " << v << endl;
#endif

using namespace std;

#define MAX_N 2250000
#define EPS 0.00001
#define PI 3.14159265

pii coordinates[MAX_N+10];
pii convex_hull[MAX_N+10];
pii anchor;
ll N;
ll CH_N;
ll M;

//Stolen from the internet
#define gc getchar_unlocked
void scanint(ll &x)
{
  register ll c = gc();
  x = 0;
  ll neg = 0;
  for(;((c<48 || c>57) && c != '-');c = gc());
  if(c=='-') {neg=1;c=gc();}
  for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  if(neg) x=-x;
}

ll sedistance(const pii &p1,const pii &p2){
  return (ll)(p1.first-p2.first)*(ll)(p1.first-p2.first) + (ll)(p1.second-p2.second)*(ll)(p1.second-p2.second);
}

inline int cross_product(pii p1,pii p2,pii p3){
  pii v1 = MP(p3.first-p1.first, p3.second-p1.second);
  pii v2 = MP(p2.first-p1.first, p2.second-p1.second);

  //return (p3.first-p1.first)*(p2.second-p1.second) - (p3.second-p1.second)*(p2.first-p1.first);
  return v1.first*v2.second - v1.second*v2.first;
}

void do_convex_hull(){

  sort(coordinates,coordinates+N);

  CH_N = 0;

  if(N <= 2){
    REP(i,N){
      convex_hull[CH_N++] = coordinates[i];
    }
    return;
  }
  var(N);

  REP(i,N){
    while(CH_N >= 2 && cross_product(convex_hull[CH_N-2], convex_hull[CH_N-1], coordinates[i]) <= 0){
      CH_N--;
    }
    convex_hull[CH_N++] = coordinates[i];
  }

  for(int i = N-2, t = CH_N+1; i>= 0; i--){
    while(CH_N >= t && cross_product(convex_hull[CH_N-2], convex_hull[CH_N-1], coordinates[i]) <= 0){
      CH_N--;
    }
    convex_hull[CH_N++] = coordinates[i];
  }

  CH_N--;
}

int main(int argv, char** argc){

  //assert(cross_product(MP(0,0), MP(0,1), MP(0, 2))==0);
  //assert(cross_product(MP(0,0), MP(0,1), MP(1, 2))>0);
  //assert(cross_product(MP(0,0), MP(0,1), MP(-1, 2))<0);

  clock_t start = clock();

  //cin.sync_with_stdio(0);
  scanint(N);
  scanint(M);
  //scanf("%d %d", &N, &M);
  //cin >> N >> M;
  var(N);

  REP(i,N){
    ll x,y;
    scanint(x);
    scanint(y);
    //scanf("%d %d", &x, &y);
    //cin >> x >> y;
    coordinates[i].first = x;
    coordinates[i].second = y;
  }

  /*
  REP(i,N){
    cout << coordinates[i].first << " " << coordinates[i].second << endl;
  }
  */

  clock_t input = clock();
  //printf("Input %d\n",input-start);

  N = unique(coordinates,coordinates+N)-coordinates;

  clock_t unique_t = clock();
  //printf("Unique t %d\n",unique_t-input);

  if(N == 1){
    cout << 0 << endl;
    return 0;
  }
  if(N == 2){
    cout << sedistance(coordinates[0],coordinates[1]);
    return 0;
  }

  /*
   * Convex hull
   */

  do_convex_hull();

  ll ans = 0;

  REP(i,CH_N){
    REP(i2,CH_N){
      ans = max(ans,sedistance(convex_hull[i],convex_hull[i2]));
    }
  }

  cout << ans << endl;

  return 0;
}

Trains

Trains is (personally) the third hardest question. It is basically a Dikstra question. However, to pass all three sub-task, the solution must be *perfect*. That means, make sure you use a multidimensional array to represent the node, instead of a logarithmic map. It is not fast enough. Also, make sure you store the current minimum with long long int data type. And then we have the basic Dijkstra optimization like using a logarithmic priority queue container to find the shortest cumulative path.

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

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

#ifdef DEBUG
#define dbg(msg) msg
#define dbgp(msg) cout << msg << endl;
#define var(v) cout << #v << " = " << v << endl;
#else
#define dbg(msg) //msg
#define dbgp(msg) //cout << msg << endl;
#define var(v) //cout << #v << " = " << v << endl;
#endif

using namespace std;

ll grid[410][410];
ll cur_min[410][410];
int N;
int ax,ay,bx,by;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

ll djikstra(){

  if(grid[ax][ay] == -1){
    return -1;
  }

  multiset< pair<ll, pii> > pqueue;
  pqueue.insert(MP(grid[ax][ay],MP(ax,ay)));
  cur_min[ax][ay] = grid[ax][ay];

  while(pqueue.size()){
    pair<ll, pii> curdat = *pqueue.begin();
    pqueue.erase(pqueue.begin());

    ll curdist = curdat.first;
    pii curcoor = curdat.second;

    if(curcoor.first == bx && curcoor.second == by){
      return curdist;
    }

    REP(i,4){
      int nx = curcoor.first + dx[i];
      int ny = curcoor.second + dy[i];
      pii ncoor = MP(nx,ny);
      if(nx < 0 || ny < 0 || nx >= N || ny >= N){
        continue;
      }

      if(grid[nx][ny] == -1) continue;

      ll ndist = curdist + grid[nx][ny];
      if(cur_min[nx][ny] > ndist){
        pqueue.erase(MP(cur_min[nx][ny], ncoor));
        cur_min[nx][ny] = ndist;
        pqueue.insert(MP(ndist, ncoor));
      }

    }

  }

  return -1;

}

int main(int argv, char** argc){
  cin.sync_with_stdio(0);

  cin >> N;
  cin >> ax >> ay >> bx >> by;
  ax--;ay--;bx--;by--;

  REP(i,N){
    REP(i2,N){
      cin >> grid[i2][i];
      cur_min[i2][i] = LLONG_MAX;
    }
  }

  cout << djikstra() << endl;

  return 0;
}

Secret

Secret is another “How in the world will a high school student answer this?” question. I think this is the second hardest question. The question involve finding if one sequence of number is the rotation of the second sequence of number. And the number of number can be up to 100,000. A brute force solution would involve, rotate and check N times. Rotate will take N loop as it need to modify every character. Check will take N loop as it need to test every character. And because this will be done N times, the overall complexity is O(N^3). Far from fast enough. One trick is to append the first sequence with itself, creating a sequence of length 2N. Then see if the second sequence is a substring of the first sequence. Using an O(N^2) substring algorithm, this will result in an overall O(N^2) complexity as the appending sequence with itself would take a linear time, which is still not fast enough. What we need is a substring algorithm that runs in linear time. My solution involve using the Knuth-Morris-Pratt (KMP) algorithm as the substring algorithm.

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

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

#ifdef DEBUG
#define dbg(msg) msg
#define dbgp(msg) cout << msg << endl;
#define var(v) cout << #v << " = " << v << endl;
#else
#define dbg(msg) //msg
#define dbgp(msg) //cout << msg << endl;
#define var(v) //cout << #v << " = " << v << endl;
#endif

using namespace std;

#define MAX_N 100000

ll sample1[MAX_N*2];
ll sample2[MAX_N];
int kmpback[MAX_N];

ll N;

void prepare_KMP(){

  kmpback[0] = -1;
  int i=1;
  int j=0;

  while(i<N){
    if(sample2[i-j] == sample2[j]){
      kmpback[i] = j;
      j++;
      i++;
    }else if(j>0){
      j = kmpback[i];
    }else{
      kmpback[i] = j;
      i++;
      j++;
    }
  }

}

bool has_substring(){

  prepare_KMP();

  dbg(
  REP(i,N){
    cout << kmpback[i] << " ";
  }
  cout << endl;
  );

  int i=0;
  int j=0;

  while(i<N){
    if(sample1[i+j] == sample2[j]){
      if(j == N-1){
        return true;
      }
      j++;
    }else{
      if(kmpback[i] > -1){
        var(i);
        var(j);
        i = i+ j-kmpback[j];
        j = kmpback[j];
        j = max(0,j);
      }else{
        j=0;
        i++;
      }
    }
  }

  return false;
}

int main(int argv, char** argc){
  cin.sync_with_stdio(0);

  cin >> N;

  REP(i,N){
    cin >> sample1[i];
  }

  REP(i,N){
    cin >> sample2[i];
  }

  copy(sample1,sample1+N,sample1+N);

  if(has_substring()){
    cout << "YES";
  }else{
    cout << "NO";
  }

  return 0;
}

Conclusion

After solving all 5 question, I keep thinking, “How in the world will a high school student answer these question?”. And I still can’t figure out how. This is harder than the ACM ICPC national level. Plus, to solve these question individually instead of in teams. Anyway, it is a good exercise, and for MCO contestants, I salute you.