Match Editorial

Match summary

The third Online Round for the TCO07 reduced the number of coders competing for the title from 300 to 150. The round started with an easy "do what it says" problem, which more than 90% of the coders had no problems with. It continued with a difficult medium, with which a lot of the coders had considerable difficulty. About a third of the coders managed to solve it, with scores spread out from 150 to almost 500. The hard was a hidden bipartite matching problem, which 37 coders managed to solve.

In the end any of the following was enough to advance to the last Online Round: two problems, a fast easy, a not too slow medium, a hard, a problem and a challenge or a lot of challenges. First was antimatter, who seems to be on his way back up again, followed by Petr and tomek.

The Problems

Value	250
Submission Rate	287 / 290 (98.97%)
Success Rate	266 / 287 (92.68%)
High Score	JongMan for 245.52 points (3 mins 51 secs)
Average Score	219.70 (for 266 correct submissions)

This is just a "do what it says"-problem. One possible solution is to loop over all elements of data and determine if it satisfies all requirements:

int totalVolume(vector <string> data, vector <string> requirements) {
    int ret=0;
    for(int i=0;i<(int)data.size();++i) {
      istringstream iss(data[i]); int edge,quality; string color;
      iss>>edge>>quality>>color;
      bool ok=true;
      for(int j=0;j<(int)requirements.size();++j) if(requirements[j][0]=='E') {
        int x=atoi(requirements[j].c_str()+5); if(edge!=x) ok=false;
      } else if(requirements[j][0]=='Q') {
        int x=atoi(requirements[j].c_str()+8); if(quality<x) ok=false;
      } else {
        string s=requirements[j].substr(6); if(color!=s) ok=false;
      }
      if(ok) ret+=edge*edge*edge;
    }
  return ret;
}

Value	500
Submission Rate	204 / 290 (70.34%)
Success Rate	100 / 204 (49.02%)
High Score	tteesstt for 480.50 points (5 mins 46 secs)
Average Score	295.24 (for 100 correct submissions)

When looking at a problem statement like this, you have to ask yourself: "What are the important variables that I need to determine?" You have to be able to express the constraints as well as the objective in these variables. This is an important step in solving the problem, and the wrong choice may lead to disaster.

In this case, the best choice for the variables is, "how long am I going to burn each candle of type 1 and how long am I going to burn each candle of type 2?" Let's call these variables burn1 and burn2 respectively. Now let's look at the constraints:

• All ceremonies have the same length. This wasn't stated in the problem, but was broadcast as a clarification during the contest. This means that we can replace "how long am I going to burn," with "how many ceremonies am I going to burn." Furthermore, because a candle either burns an entire ceremony or it doesn't burn at all during a ceremony, burn1 and burn2 should be integers.
• Afterwards all candles need to have the same length. This means that burn1*r1=burn2*r2. Now we have an integer equation, which we can solve using a little algebra. The lowest possible positive values for which the equation is true (let's call them step1 and step2), is when step1*r1=step2*r2=lcm(r1,r2), so step1=lcm(r1,r2)/r1=r2/gcd(r1,r2) and step2=lcm(r1,r2)/r2=r1/gcd(r1,r2). All solutions to the equations are of the form burn1=times*step1 and burn2=times*step2. So now we have only one variable left to determine.
• We have to minimize the number of ceremonies, which is equal to (n1*burn1+n2*burn2)/n=times*(n1*step1+n2*step2)/n, so we have to minimize times. This also implies that times*(n1*step1+n2*step2) is divisible by n. In the contest, you could do this by simply looping over the variable times until this condition was met, or using some algebra you could directly derive that the lowest positive valid value for times is n/gcd(n,n1*step1+n2*step2).
• Finally, at each ceremony n candles are lit. This again means that times*(n1*step1+n2*step2) should be divisible by n, but also that it should be possible to assign n candles to each ceremony in such a way that all candles burn the amount of time we want. Example 2 shows what can go wrong. I think this is the hardest part of the problem, and I've seen several ways to do it.
  • If we need to burn a candle of one of the types more times than we have ceremonies, it is obviously impossible. In other words, we should return -1 if max(times*step1,times*step2)>times*(n1*step1+n2*step2)/n or if n*max(step1,step2)>(n1*step1+n2*step2). Otherwise it turns out that it is always possible (proof left as an exercise for the reader).
  • If the total number of burns for candles of a type is smaller than the minimal number of burns for candles of that type, then it is also impossible. We should return -1 if n1*step1<(n-n1)*step2 or n2*step2<(n-n2)*step1. Regarding the first formula: we need exactly n1*step1 burns of type 1 candles, but we need at least step2 different ceremonies to satisfy the candles of type 2 (you cant burn one candle multiple times during a ceremony) and at each ceremony, we have to burn at least n-n1 candles of type 1 at each ceremony. After rearranging terms, this formula turns out to be equivalent to the one in the previous paragraph.
  • Just simulate the process using the following strategy: at each ceremony burn the candles that need the most burns. If you ever have to burn a candle that already has enough burns, return -1.

int ceremonies(int n, int n1, int r1, int n2, int r2) {
    int step1=r2/__gcd(r1,r2),step2=r1/__gcd(r1,r2);
    if(n*max(step1,step2)>n1*step1+n2*step2) return -1;
    int times=n/__gcd(n,n1*step1+n2*step2);
    return times*(n1*step1+n2*step2)/n;
}  

Value	1000
Submission Rate	101 / 290 (34.83%)
Success Rate	37 / 101 (36.63%)
High Score	Petr for 817.15 points (14 mins 6 secs)
Average Score	594.97 (for 37 correct submissions)

First we are going to reformulate the problem in graph concepts. Let the nodes of the graph be the voters and draw an edge between two voters if they are not allowed to vote both, i.e. they are allies and they have different opinions. The problem now basically asks to find the largest set of voters, such that there does not exist an edge between two voters in this set. You have to return the complement of this set, taking some tiebreaking rules in account.

Experienced coders should recognize immediately that this is a 'Maximum independent set'-problem, which is NP-hard. So there must be some trick that makes it possible to calculate efficiently. The first thing to check for is if the graph is bipartite, in which case there are efficient algorithms. This is indeed the case, because the set of voters can be partitioned into two subsets -- the yes-voters and the no-voters -- and there are no edges between voters in the same subset.

To find the 'maximum independent set' in a bipartite graph we can use bipartite matching. The only thing left is the tiebreaking rule. We can take this it into account as follows: first calculate the number of voters who need to abstain, and call this res. Now let the first voter abstain from voting and calculate the additional number of voters who need to abstain. If this number is less than it was previously (it will always be one less in this case), there is a set of voters who abstain from voting which includes the first voter, so the return set must include the first voter. Otherwise, there is no set of voters who abstain which includes the first voter, so the return set does not include the first voter. Continue this process with the second voter, etc. until all voters have been processed. After this we will have constructed the lexographically least set of voters who can abstain from voting, so we just return this set.

int n;
int ally[50][50];

int nrleft,nrright;
int left[50],right[50];
int can[50];

int done[50],match[50];

bool augment(int i) {
  if(!can[left[i]]||done[i]) return false; else done[i]=true;
    for(int j=0;j<nrright;++j) if(ally[left[i]][right[j]]&&can[right[j]])
      if(match[j]==-1||augment(match[j])) {
        match[j]=i;
        return true;
      }
  return false;
}

int maxflow() {
  memset(done,0,sizeof(done));
  memset(match,-1,sizeof(match));
  int ret=0;
  for(int i=0;i<nrleft;++i) if(augment(i)) {
    ++ret;
    memset(done,0,sizeof(done));
  }
  return ret;
}

vector <int> abstainers(vector <string> voter) {
  n=(int)voter.size();
  memset(ally,0,sizeof(ally));
  for(int i=0;i<n;++i) {
    istringstream iss(voter[i].c_str()+1); int j;
    while(iss>>j) { --j; ally[i][j]=ally[j][i]=1; }
  }

  nrleft=0,nrright=0;
  for(int i=0;i<n;++i) if(voter[i][0]=='N') {
    left[nrleft++]=i;
  } else {
    right[nrright++]=i;
  }
  for(int i=0;i<n;++i) can[i]=true;
      
  int res=maxflow();
  vector<int> ret;
  for(int i=0;i<n;++i) {
    can[i]=false;
    if(maxflow()==res-1) {
      ret.push_back(i+1);
      --res;
    } else {
      can[i]=true;
    }
  }
  return ret; 
}