TopCoder SRM 429 DIV 2

C/C++ TopCoder
Problem Check Points
250 ○ 230.75
500 ○ 223.25
1000 - -

1000は時間かければできそうだけど・・・

Problem 250 LinearPolyominoCovering

問題

You have an infinite number of the following two polyominoes: AAAA and BB.
You are given a String region, filled with characters '.' and 'X'. You need to cover (without overlapping) all the 'X' characters with the given polyominoes.
Return a String that contains the same region with cells marked '.' left untouched, and cells marked 'X' changed to 'A' or 'B', according to the polyomino that covers the cell.
If there is no solution, return the String "impossible" (quotes for clarity only).
If there are multiple solutions, return the lexicographically smallest one.

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

First, it is never advantageous to put two BB polyominoes next to each other. Indeed, we can always replace "BBBB" with "AAAA" and thus get a lexicographically smaller string.

Now, consider a group of 'X' cells (surrounded by dots or borders of the region). Denote its length L.

  • If L is odd, there is no way to cover this group (the polyominoes have even length), so the answer is "impossible".
  • If L is a multiple of 4, use L/4 AAAA polyominoes to cover this group.
  • If L is even but doesn't divide by 4, one BB polyomino has to be used. To make the answer lexicographically smallest, it should be placed in the end of the group, preceded by (L-2)/4 AAAA polyominoes.

Using patterns can make the code extremely short:

public String findCovering(String region) {
    region = region.replaceAll("XXXX", "AAAA").replaceAll("XX", "BB");
    return region.contains("X") ? "impossible" : region;
}
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm429
My code
class LinearPolyominoCovering {
public:
  string findCovering(string region) {
    string result = "";

	for(int i=0 ; i<region.size() ; i++){
		if(region[i]=='.'){
			result += '.';
			continue;
		}

		int j = i;
		int cnt = 0;
		while( j<region.size() && region[j]=='X'){
			cnt++;
			j++;
		}

		if(cnt%2!=0) return "impossible";
		if(cnt>=4){
			result += "AAAA";
			i+=3;
		}
		else{
			result += "BB";
			i++;
		}
		
	}

    return result;
  }
};

Problem 500 SubrectanglesOfTable

問題

Tanya has a rectangular table filled with letters.

First, she makes four copies of this table, and arranges the copies as a 2×2 rectangle.

Then she lists all subrectangles of the resulting table.

For example, for the following original table:

OK
she will arrange the copies like this:

OKOK
OKOK
and then she will list the following 30 subrectangles (dots for clarity only):
OKOK .... OKOK OKO. .... OKO. .KOK .... .KOK
OKOK OKOK .... OKO. OKO. .... .KOK .KOK ....

OK.. .... OK.. .KO. .... .KO. ..OK .... ..OK
OK.. OK.. .... .KO. .KO. .... ..OK ..OK ....

O... .... O... .K.. .... .K.. ..O. .... ..O. ...K .... ...K
O... O... .... .K.. .K.. .... ..O. ..O. .... ...K ...K ....
(Note that she is considering all subrectangles based on their positions rather than their content, so the same subrectangle might appear multiple times in the list. In this case, subrectangle "K" appears four times because it occurs at four different positions.)

Tanya wonders how frequently each letter of the alphabet occurs among all these subrectangles. You are given a String table, where the j-th character of the i-th element is the letter at row i, column j of the original table. Return a long containing exactly 26 elements, where the i-th element is the number of occurrences of the i-th letter in the alphabet among all of Tanya's subrectangles. 'A' is the 0-th letter, 'B' is the 1-st letter, etc.

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

Contestants were asked to count all letters in all subrectangles of the given table.

The straight-forward algorithm looks like this: iterate over all subrectangles and for each subrectangle, count the letters inside it. Unfortunately, this algorithm takes O((h×w)3) time for a h×w table and doesn't fit in 2 seconds for a 100×100 table.

The correct algorithm is to iterate over all cells of the table, and for each cell, count the number of times it appears in subrectangles.

For a cell (i, j), the number of subrectangles that contain this cell is equal to (i + 1)(2h - i)(j + 1)(2w - j).

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm429
My code
class SubrectanglesOfTable {
public:
  vector<long long> getQuantity(vector <string> table) {
    vector<long long> result;

	vector<string> T;
	for(int i=0 ; i<table.size()*2 ; i++){
		T.push_back("");
	}

	for(int i=0 ; i<table.size()*4 ; i++){
		T[i%T.size()] += table[i%table.size()];
	}

	for(int i=0 ; i<26 ; i++){
		result.push_back(0);
	}

	for(int i=0 ; i<T.size() ; i++){
		for(int j=0 ; j<T[0].size() ; j++){
			result[T[i][j]-65] += ( (i+1)*(T.size()-i) )*( (j+1)*(T[0].size()-j) );
		}
	}
	
    return result;
  }
};

Problem 1000 IngredientProportions

問題

Your friend has invented a splendid cocktail consisting of N ingredients. However, she has forgotten the amount of each ingredient that goes into the recipe.

For N-1 pairs of ingredients, she remembers the proportion in which the ingredients within each pair should be added to the cocktail. Fortunately, these N-1 proportions are sufficient to restore the recipe of the entire cocktail.

You are given a String proportions containing the N-1 proportions. Each element is formatted "#< a > and #< b > as < p >:< q >" (quotes for clarity), which means that the mass of ingredient < a > divided by the mass of ingredient < b > in the cocktail must be equal to < p >/< q > (all ingredients are 0-indexed). Return a int containing exactly N elements, where the i-th element is the mass of ingredient i, such that all the given proportions are satisfied and the total mass is as small as possible. The total mass must be greater than 0.

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

The solution can be split in 2 parts - first we find any masses which satisfy the given receipt, and then we change the solution to make the total mass as small as possible. The latter part is easy - as soon as we have a solution (M1, ..., Mn), we compute the greatest common divisor of all Mi and divide each Mi by this divisor.

The former part - finding any vector of masses which satisfies the receipt - can be done in multiple ways. Since the total number of ingredients is very low, we can forget about optimizations - it will be hard to construct an algorithm which will NOT work in time.

The most natural approach is to find the proportion for all pairs of ingredients, set the mass of ingredient 1 to some value and compute the masses of all other ingredients using the proportions. Computing the matrix of proportions is easy - parse all input proportions and run some kind of Floyd-Warshall algorithm (so, if we know ingredients A and B are in proportion a:b and ingredients B and C are in proportion c:d, then we conclude A and C are in proportion (a * c):(b * d)).

So, the only missing part of the solution is the selection of the mass of ingredient 1. This mass has to be selected in such way that the masses of all other ingredients will be integer as well (for example, if ingredients 3 and 1 are in proportion 2 : 3, then mass of the first ingredient must be a multiple of 3). In other words, if ingredient 1 and ingredient k are in proportion Ak : Bk, then the mass of the first ingredient must be divisible by Ak (for all k). Therefore, we can pick the least common multiple of all Ak's as the mass of the first ingredient.

And the algorithm altogether:

Parse all input proportions.

  • Compute the proportions between all pairs of ingredients.
  • Calculate the mass of the first ingredient using the LCM above.
  • Compute the masses of all other ingredients.
  • Minimize the total mass dividing all masses by their GCD.