TopCoder SRM 430 DIV 2

Problem	Check	Points
275	○	235.02
500	○	265.10
1000	-	-

久しぶりに1問目、2問目ともに正解！今回は点数も良かったので満足。

Problem 275 CreateGroups

問題

あなたの学校では新学期が始まり、生徒たちは新しいスケジュールを選択しなければなりません。あなたにはi番目の要素がi番目のスケジュールを選択した学生の人数が入っている、 int[] groups が与えられます。あなたの学校では、各スケジュールは生徒の人数がminSizeからmaxSizeの間でなければならないという規則があるのですが、登録時にはその規則が守られていません。この規則を満たすように生徒を再登録させるのがあなたの仕事です。再登録はある生徒のスケジュールを別のスケジュールに変更することを言います。あなたが再登録しなければいけない最小の人数を返してください。もし規則を満たすことができない場合は-1を返してください。新しいスケジュールを作ったり、存在するスケジュールを削除することはできないとします。

http://www.topcoder.com/stat?c=problem_statement&pm=8376&rd=13521

解説

Let N denote the number of schedules. It is easy to see that the problem has no solution if and only if the total number of students is either too big (i.e., there are more than maxSize*N students) or too small (less than minSize*N). Otherwise, there are two ways to calculate the minimal number of reassignments. The first one is to simulate the reassignments. On each step, we find the largest group, the smallest group, and reassign some students from the largest group to the smallest.

The second approach has been used by the majority of coders. It calculates the result in linear time and works in the following manner:

1. Let consider schedules, where the number of students is greater than maxSize and calculate the total number of students needed to leave those groups (needToErase).
2. Then consider schedules, where the number of students is less than minSize. Calculate the total number of students needed to join them (needToAccept).

The answer to the problem, as can be easily proved, is the maximum of needToErase and needToAccept.

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

My code

class CreateGroups {
public:
  int minChanges(vector <int> groups, int minSize, int maxSize) {
    int result=0;

	int sum = 0;
	for(int i=0 ; i<groups.size() ; i++){
		sum += groups[i];
	}
	if((double)sum/(double)groups.size()>maxSize || (double)sum/(double)groups.size()<minSize) return -1;

	sum = 0;
	int lack = 0;
	for(int i=0 ; i<groups.size() ; i++){
		if(groups[i] > maxSize) sum += groups[i]-maxSize;
		else if(groups[i] < minSize) lack += minSize - groups[i];
	}

	return max(sum,lack);
  }
};

Problem 500 BitwiseEquations

問題

You are given two positive integers x and k. Return the k-th smallest positive integer y (where k is 1-based) for which the following equation holds:
x + y = x | y
where '|' denotes the bitwise OR operator.

http://www.topcoder.com/stat?c=problem_statement&pm=9921&rd=13521

解説

One can prove that number y is a solution of the given equation if and only if y has zeroes in all positions where x has ones (in binary notation, of course). In other words, we need to determine the digits of y for positions where x has zeroes. For instance, if x = 1001101001 in binary (617 in decimal notation), then the last ten digits of y must be y= 0**00*0**0, where '*' denotes either zero or one. Also, we can pad any number of any digits to the beginning of the number, since all higher bits are zeroes.

Any replacement of all '*' by binary digits gives us a solution. Clearly, the smallest non-zero solution can be received by replacing asterisks by "00001" for the asterisks, so it will be 1001101011 (or 619 in decimal). The second smallest solution replaces asterisks by "00..00010", the third - by "00011", and so on. In other words, the K-th smallest solution can be received by replacing all asterisks in x by digits of binary representation of number K.

My code

const int BitSize = sizeof(int) * 8; // 整数型のビットサイズを算出

deque<int> dtob(int x) {
  int bit = 1, i;
  deque<int> v;

  for (i = 0; i < BitSize; i++) {
    if (x & bit) //v[i] = 1;
		v.push_front(1);
    else         //v[i] = 0;
		v.push_front(0);
    bit <<= 1;
  }
  return v;
}

ll btod(deque<int> v){
	ll ans = 0;
	ll bit = 1;
	while(!v.empty()){
		ans += v.back()*bit;
		v.pop_back();
		bit <<= 1;
	}
	return ans;
}

deque<int> insert(deque<int> a, deque<int> b){
	deque<int> ans;
	ans.clear();

	while(!b.empty()){
		if(!a.empty() && a.back() == 1){
			ans.push_front(0);
			a.pop_back();
		}
		else{
			ans.push_front(b.back());
			b.pop_back();
			if(!a.empty()) a.pop_back();
		}
	}
	return ans;
}

class BitwiseEquations {
public:
  long long kthPlusOrSolution(int x, int k) {
    ll result=0;

	deque<int> tmp;
	tmp = dtob(k);

	deque<int> ans;
	ans = insert(dtob(x), tmp);

	return btod(ans);
  }
};

Problem 1000 ImageTraders

問題

There is a community of art lovers who meet from time to time and trade images with each other. Each image transaction must obey the following rules:

1. The price at which the image is sold must be greater than or equal to the price at which it was bought.
2. No trader is allowed to buy the same image more than once.

A new image has just appeared on the market. Trader 0 bought it from an unknown artist for the price of '0', and he is now ready to trade it among his fellow art lovers. You are given a String[] price, where the j-th character of the i-th element is a digit representing the price at which trader j will buy the image from trader i. '0' is the lowest price, and '9' is the highest. Assuming all transactions obey the rules mentioned above, determine the longest possible sequence of transactions involving the new image. After all the transactions are done, return the number of people who have owned the image at some point in time, including both the final owner and trader 0.

http://www.topcoder.com/stat?c=problem_statement&pm=7583&rd=13521

解説

Probably, experienced coders didn't need much time to determine this one is a DP problem. The state of the problem can be represented by a triple (mask, i, p), where the image is ownded by trader i, who bought it for price p, and only traders from mask didn't own the image yet. For example, state (0010110, 3, 5) means that trader 3 owns the image, bought it for price of 5 and he may sell it to traders 3, 5 and 6. Since each trader can sell the image to maximum of N traders, each such a subproblem can be solved in linear time.

Using memoization instead of DP provides some advantages to implement the idea above. See smilitude fastest solution as a short implementation of this.

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