TopCoder SRM 433 DIV 2

C/C++ TopCoder
Problem Check Points
250 ◯ 243.98
500 × -
1000 - -


今回の500は難しい。いや、System Checkが通らないのはいつものことだけど、通るようにどうやればいいのかが難しかった。(計算量的に。)
250はスピード勝負でした。

Problem 250 RoyalTreasurer

問題

Once upon a time, there was a kingdom where math was always a big problem. When the post of the royal treasurer needed to be filled, applicants were presented with the following problem:

"We have two arrays of integers, A and B. A and B each contain exactly N elements. Let's define a function S over A and B:
S = A0*B0 + ? + AN-1*BN-1
Rearrange the numbers in A in such a way that the value of S is as small as possible. You are not allowed to rearrange the numbers in B.?
The problem writers need a program to check the correctness of the applicants' answers. Given int[]s A and B, return the smallest possible value for S.

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

This was a pretty classical problem. If you want to minimize the sum of Ai * Bi, you should multiply the smallest Ai by the largest Bi, the second-smallest Ai by the second-largest Bi, and so on. In other words, if Bi > Bj, then Ai must not be greater than Aj (you can prove this by contradiction). The java code follows:

public int minimalArrangement(int[] A, int[] B) {
	Arrays.sort(A);
        Arrays.sort(B);
	int res = 0;
	for (int i=0; i < A.length; i++)
		res += A[i] * B[B.length - i - 1];
	return res;
}
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm433
My code
class RoyalTreasurer {
public:
  int minimalArrangement(vector <int> A, vector <int> B) {
    int result=0;

	vector<int> v1, v2;

	for(int i=0 ; i<A.size() ; i++){
		v1.push_back(A[i]);
		v2.push_back(B[i]);
	}

	sort(v1.begin() , v1.end());
	sort(v2.begin() , v2.end(), greater<int>());
	
	for(int i=0 ; i<A.size() ; i++){
		result+= v1[i]*v2[i];
	}

    return result;
  }
};

Problem 500 MagicWords

問題

Consider a string T containing exactly L characters. The string T(i) is a cyclic shift of T starting from position i (0 <= i < L). T(i) contains exactly the same number of characters as T. For each j between 0 and L-1, inclusive, character j of T(i) is equal to character (i+j)%L of T. Let's call T a magic word if there are exactly K positions i such that T(i) = T.

You are given a String[] S containing exactly N words. For each permutation p = (p[0], p[1], ..., p[N-1]) of integers between 0 and N-1, inclusive, we can define a string generated by this permutation as a concatenation S[p[0]] + S[p[1]] + ... + S[p[N-1]]. Return the number of permutations that generate magic words. All indices in this problem as 0-based.

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

This problem was harder than a usual problem of this slot. Nevertheless, there are at least 3 solutions which are guaranteed to pass any test under the given constraints.

  1. Let us call a string S which has exactly K shifts equal to itself a K-magic string. You may notice that string S being K-magic is equivalent to "string S can be divided into K equal substrings and cannot be divided into X > K equal substrings". For example, string S = "ABCABCABCABC" is 4-magic because it consists of 4 "ABC"-s and can not be divided into a larger number of equal substrings.

Therefore, to check whether string S of length L is K-magic you must first check if S is a concatenation of K equal substrings. If it doesn't, then S definitely is not K-magic. If it does, S can still possibly be divisible into X > K substrings. To ensure S is a K-magic string, S must not be a multiple of a substring of length L / i (for each i between (K + 1) and L). Each this check can be done in O(L) if i divides L, and in constant time if not, which gives us the total estimation of O(L * sqrt(L)). Multiplying this by the number of permutations of the input strings, we get the final time estimation at O(N! * L * sqrt(L)). nika's solution is an example of this approach.

  1. Another approach was to use a KMP or some other string searching algorithm. After choosing a permutation from N! possibilities and obtaining a concatenation S (with length L) of the permuted strings, take string S2=S+S. The number of indices i (0 <= i < L) such that S = S2.substr(i,L) is exactly the number of shifts of S equal to the original. Using a Knuth-Morris-Pratt algorithm, you can find this number in O(L). So the overall complexity is O(N! * L).
  2. You also may write an inefficient algorithm and optimize it using the following trick. Let us permute the input strings in order {2,3,0,1} and concatenate to receice string S. If S is K-magic, then concatenations of input for permutations {3,0,1,2}, {0,1,2,3}, {1,2,3,0} will be K-magic as well. (all these concatenations are cyclic shifts of each other). Therefore, your solution may check only permutations of the input which leave the first element of input on its place, and then multiply the result by the total number of elements in the input.

Besides those approaches, many coders had solutions using hash, memoization or other coding optimizations.

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm433
My code
int cnt;
int L;

bool isMagicWord(string s,int K){
	L = s.size();
	cnt=0;
	for(int i=0 ; i<L ; i++){
		if(s==s.substr(i)+s.substr(0,i)) cnt++;
		if(cnt > K || L-i < cnt-K) return false;
	}

	if(cnt==K) return true;
	return false;
}

class MagicWords {
public:
  int count(vector <string> S, int K) {
    int result=0;

	if(K>160) return 0;

	int myints[] = {1,2,3,4,5,6,7,8,9};
	sort(myints, myints+S.size());

	int cnt=0;
	string ss;
	do{
		ss="";
		for(int i=0 ; i<S.size() ; i++){
			ss += S[myints[i]-1];
		}
		if(isMagicWord(ss,K)) cnt++;
	} while (next_permutation(myints+1, myints+S.size()));

    return cnt*S.size();
  }
};

Problem 1000 MakingPotions

問題

An old witch is making a love potion. She has a lot of recipes and each of them has the following form:

S=N1S1+?+NkSk

where N1, ?, Nk are single-digit integers between 1 and 9, inclusive, S1, ?, Sk are names of ingredients, k is an integer greater than or equal to 1, and S is name of the resulting potion (all names contain only uppercase letters). This means that if she mixes N1 units of S1, ..., Nk units of Sk all together, she will obtain 1 unit of S. There may be multiple recipes for the same potion. In that case, the potion can be obtained using any one of them. The ingredients are also potions, and some of them can be bought at the market.

You want to create 1 unit of the potion called LOVE. You are given String recipes, each element of which is a recipe formatted as described above. You are also given a String marketGoods and a int[] cost. Each element of marketGoods is the name of a potion you can purchase at the market. The i-th element of cost is the cost of 1 unit of the i-th potion in marketGoods. Return the cheapest cost of obtaining 1 unit of LOVE. If this cost is greater than 1,000,000,000, return 1,000,000,001 instead. If the potion cannot be obtained, return -1 instead.

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

This problem splits into 2 independent parts: parsing the input into some data structure (should be easy for most coders trying to solve the problems of this level) and computing the price of LOVE. We'll concentrate on the latter.

Computing the price of any potion should be simple - either the potion could be bought on the market, or there is a recipe which results in that potion. Unfortunately, you need to compute the prices of recipes in a specific order - for example, if you need WATER to get COFFEE, then you can not compute the price of COFFEE until you know the price of WATER. To make things worse, the dependencies may be cyclic, so you can not topologically sort the potions to get the order of computations.

Fortunately, the constraints on this problem are quite low, so we can try using the following algorithm:

  1. Set the price of each potion to the market price (or to infinity, if the potion is unavailable on the market).
  2. For each recipe, compute the price of the resulting potion using the current prices of all ingredients. Update the current price of the resulting potion if needed.
  3. Return to point 2 if needed.

In general, the algorithm is not that hard. The only problem is "if needed" part. How do we know whether we've achieved the optimal price? The answer to this question is very simple: if (in point 2) we tried all recipes and didn't update the price for any of the resulting components, then we've reached the optimum. See the fastest solution for an example of implementation (note that osan didn't bother with checking for update on each loop).

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm433