TopCoder SRM 427 DIV 2

C/C++ TopCoder
Problem Check Points
250 ○ 214.19
500 × -
1000 - -

500はgcdが激遅な書き方をしていたせいでタイムアウトという本末転倒な感じに。

Problem 250 LoveCalculator

問題

A girl would like to go out with one of her favorite boys, but she does not know which one to choose. Fortunately, she has a Love Calculator which can calculate the probability of love between two people. Love Calculator takes two people's names and uses the following algorithm to calculate the probability of love between them:

L := the total number of occurrences of the letter 'L' in both names.
O := the total number of occurrences of the letter 'O' in both names.
V := the total number of occurrences of the letter 'V' in both names.
E := the total number of occurrences of the letter 'E' in both names.

The percent probability of love is equal to ( (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) )%100, where % is the modulo operator. You are given a String girl containing the girl's name, and a String[] boys containing her favorite boys' names. Return the name of the boy with which the girl has the highest probability of love. If there is more than one such boy, return the one among them that comes earliest alphabetically.

http://www.topcoder.com/stat?c=problem_statement&pm=10046&rd=13518
解説

The solution for this problem can be broken in two parts. First, let's implement the method which takes two names and calculates the probability of love between them. The implementation directly follows the problem statement:

int loveProb(String a, String b) {
  String s=a+b;
  int L=0, O=0, V=0, E=0;
  for (int i=0; i<s.length(); i++) {
    if (s.charAt(i)=='L') L++;
    if (s.charAt(i)=='O') O++;
    if (s.charAt(i)=='V') V++;
    if (s.charAt(i)=='E') E++;
  }
  return ( (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) ) % 100;
}

Now, having such method implemented, we can easily complete the rest of the solution:

public String findBoy(String girl, String[] boys) {
  int bestProb = -1;
  String best = "";
  for (int i=0; i < boys.length; i++) {
    int cur = loveProb(girl, boys[i]);
    if (cur > bestProb || cur == bestProb && boys[i].compareTo(best) < 0) {
      bestProb = cur;
      best = boys[i];
    }
  }
  return best;
}

Exercise. It may seem that (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) doesn't always fit within 32-bit signed integer value (each multiplier can be up to 40, so the upper bound for the whole expression is 40^6 = 4,096,000,000). If it's really true, then there can occur an overflow in loveProb method implementation provided above. Construct an example, that makes (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) overflow 32-bit signed integer value, or prove that such example doesn't exist.

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm427
My code
class LoveCalculator {
public:
  string findBoy(string girl, vector <string> boys) {
    int maxans = -1,maxp;

	int L,O,V,E, ans;
	int gL=0,gO=0,gV=0,gE=0;

	vector<string> vvv;
	vvv.clear();

	for(int i=0 ; i<girl.size() ; i++){
		char c = girl[i];
		if(c=='L') gL++;
		else if(c=='O') gO++;
		else if(c=='V') gV++;
		else if(c=='E') gE++;
	}

	for(int i=0 ; i<boys.size() ; i++){
		L=gL;
		O=gO;
		V=gV;
		E=gE;

		for(int j=0 ; j<boys[i].size() ; j++){
			char c = boys[i][j];

			if(c=='L') L++;
			else if(c=='O') O++;
			else if(c=='V') V++;
			else if(c=='E') E++;
		}

		ans = ( (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) )%100;

		if(maxans < ans){
			vvv.clear();
			maxans = ans;
			vvv.push_back(boys[i]);
		}
		else if(maxans ==ans){
			vvv.push_back(boys[i]);
		}

	}

	sort(vvv.begin() , vvv.end());

    return vvv[0];
  }
};

Problem 500 DesignCalendar

問題

An alien civilization has advanced to the point where it needs to start keeping track of time. Its leaders have therefore decided to design a calendar. Like many Earthly calendars, this calendar is going to be based on the motion of celestial bodies: in particular the calendar must include period of rotation of their planet (a day) and the period of orbit of the planet around the sun (a real year). Unfortunately, just as is the case on Earth, a real year is not necessarily a convenient integer number of days. Their solution to this problem is to define a calendar year, which is an integer number of days long, and periodically insert an extra day into some calendar years (leap years) in order to correct the discrepancy and resychronize the start of the calendar year with the start of the real year.

The formal requirements for the calendar are as follows:

  • A normal calendar year is a length of time that is some integer number N days long.
  • A leap calendar year is exactly one day longer than a normal calendar year (N+1 days long).
  • Each calendar year is either a normal year or a leap year.
  • The calendar must have some positive integer period P, such that every P whole consecutive calendar years sum to exactly the same length of time as P real years.

The leaders wish to design the calendar to make the period P as short as possible. A day is dayLength time units long and a real year is yearLength time units long. Return the smallest achievable positive integer value of P.

http://www.topcoder.com/stat?c=problem_statement&pm=10155&rd=13518
解説

In order to solve this problem, let's do some simple math. First, we need to introduce several variables:

  • P - the period of calendar in years (we are looking for the smallest period);
  • N - the number of days in a normal year;
  • L - the number of leap years within one period.

The statement asks us to choose P, N and L in such way that each P calendar years sum to the same amount of days as P real years. It means that the average year length (in days) according to our calendar is the same as the number of days in a real year. The number of days in a real year is yearLength/dayLength. The total number of days in P calendar years is (P - L) * N + L * (N + 1) (L leap years have N + 1 days and the other years have N days). Therefore, the average year length according to the calendar is ( (P - L) * N + L * (N + 1) ) / P = (P*N - L*N + L*N + L) / P = (P*N + L) / P = N + L/P. So we have an equation to solve: N + L/P = yearLength/dayLength.

Let's reduce the fraction yearLength/dayLength. Set yearLength' = yearLength/d, dayLength' = dayLength/d, where d is the greatest common divisor of yearLength and dayLength. Then the equation from the previous paragraph can be written as (N*P + L) / P = yearLength' / dayLength'. Now, since the fraction in the right part is irreducible, it becomes clear that the minimum possible value of P is dayLength'. It's left to show that this value for P is feasible, i.e. to provide the correct values for N and L, but it's easy to do: N = yearLength' DIV dayLength' and L = yearLength' MOD dayLength'. These values will work because (N*P + L) / P = ((yearLength' DIV dayLength')*dayLength' + yearLength' MOD dayLength') / dayLength' = yearLength' / dayLength'.

The implementation is really easy and straightforward. We just need to calculate dayLength / gcd(dayLength, yearLength):

public class DesignCalendar {
  int gcd(int a, int b) {
    while (a>0 && b>0)
      if (a>b) a%=b; else b%=a;
    return a+b;
  }

  public int shortestPeriod(int dayLength, int yearLength) {
    return dayLength / gcd(dayLength, yearLength);
  }
}
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm427
My code
ll gcd( ll m, ll n )
{
	if ((0==m) || (0==n)) return 0;
	ll tmp;
	while(m%n!=0){
		tmp = n;
		n = m%n;
		m = tmp;
	}
	return n;
}

ll lcm( ll m, ll n ){
	if ((0==m) || (0==n)) return 0;
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

class DesignCalendar {
public:
  int shortestPeriod(int dayLength, int yearLength) {
	  return dayLength/gcd(dayLength,yearLength);
  }
};

Problem 1000 Teaching

問題

A language teacher in Antarctica wants his students to be able to read as many words as possible. However, he only has time to teach them K letters. After that, the students will only be able to read words containing only those K letters. Your task is to determine which K letters should be taught to maximize the number of words that the students will be able to read.



The Antarctican language is famous because it only contains words that start with "anta" and end with "tica" (quotes for clarity only). You are given a String[] words containing all the words in the language. Return the maximum number of words the students will be able to read if they learn the optimal set of K letters.

http://www.topcoder.com/stat?c=problem_statement&pm=10044&rd=13518
解説

This problem is solved using brute force, i.e. by checking all possibilities. The basic idea is simple: we need to iterate through all subset of K letters, check for each of them how many words it allows to read and return the maximum. However, inefficient implementation of this approach will lead to time out. There can be up to C(26, 13) = 26! / (13! * 13!) = 10,400,600 possible subsets and checking each of them requires iterating through each letter of each word (at most 50*15 = 750 operations). Overall, it gives 10,400,600 * 750 = 7,800,450,000 operations, what is obviously way too much.

To obtain working solution, let's apply two optimizations:

  1. We certainly should teach letters 'a', 'n', 't', 'i', 'c', otherwise our students won't be able to read even a single word. Therefore, if K < 5, we can return 0, and if K > 5, we teach 'a', 'n', 't', 'i', 'c' and then iterate through all possible subsets of K - 5 letters among the rest of 21 letters. This reduces the number of possible subsets to C(21, 10) = 21! / (10! * 11!) = 352,716. So this optimization makes our solution work faster in almost 30 times.
  2. It's convenient to represent the subsets of letters by 26-bit masks. The i-th bit in mask is set if and only if the i-th letter in alphabet is present in the subset represented by mask. This allows for faster checking whether a subset of letters represented by subsetMask is enough to read the word represented by wordMask. The mask for a subset of unknown letters can be calculated as 226 - 1 - subsetMask. It's possible to read the word if and only if there's no unknown letter which is present in the word, that is, if wordMask & (226 - 1 - subsetMask) = 0. So instead of iterating through all the characters of the word, we can perform this simple check and save running time.

With these 2 optimization, in the worst case our solution will require 352,716 * 50 = 17,635,800 checks, what is still pretty much, but enough to fit within 2 seconds time limit. Java implementation of this approach follows:

public class Teaching {
  int K;
  int[] wordMask;
  int res = 0;

  // recursive method for checking subsets
  // pos is the index of letter we are currently at
  // have is the number of taken letters
  // mask is the mask of taken letters
  void go(int pos, int have, int mask) {
   // if the subset is completely formed
   if (pos == 26) {
     // if the number of taken letters is not K, skip the subset
     if (have != K) return;

     // calculate how many words we can read
     int cnt = 0;
     for (int i=0; i < wordMask.length; i++)
       if ((wordMask[i] & ((1<<26)-mask-1)) == 0) cnt++;

     // update maximum if needed
     if (cnt > res) res = cnt;
     return;
   }

   // if the letter is none of 'a', 'n', 't', 'i', 'c', try skipping it
   if ("antatica".indexOf((char)((int)'a'+pos)) == -1) go(pos+1, have, mask);
   
   // try learning the letter
   go(pos+1, have+1, mask + (1<<pos));
  }

  public int count(String[] words, int K) {
    // precalculate the masks for all words
    wordMask = new int[words.length];
    for (int i=0; i<words.length; i++)
      for (int j=0; j<words[i].length(); j++)
        wordMask[i] |= (1 << (words[i].charAt(j) - 'a'));

    this.K = K;

    // start recursive checking of all subsets
    go(0, 0, 0);

    return res;
  }
}
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm427