TopCoder SRM 434 DIV 2

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

また500で凡ミスっ・・・！
(変数)=='0'と書くところを (変数)==0 と書いてしまいました・・・

Problem 250 LeastMajorityMultiple

問題

Given five positive integers, their least majority multiple is the smallest positive integer that is divisible by at least three of them.

Given distinct ints a, b, c, d and e, return their least majority multiple.

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

Maximum size of result won't be more than 1000000 (100^3). The easiest way to solve this problem is to start from 1 and check if the number is divisible by at least three of those numbers.

http://www.topcoder.com/wiki/display/tc/SRM+434
My code
class LeastMajorityMultiple {
public:
  int leastMajorityMultiple(int a, int b, int c, int d, int e) {
    int result=0;

	vector<int> v;
	v.push_back(e);
	v.push_back(d);
	v.push_back(c);
	v.push_back(b);
	v.push_back(a);

	sort(v.begin(), v.end(), greater<int>());
	int cnt;
	for(ll i=v[2] ; ; i++){
		cnt = 0;
		for(int j=0 ; j<=4 ; j++){
			if(i%v[j]==0) cnt++;
		}
		if(cnt >= 3) return i;
	}
    return result;
  }
};

Problem 500 FindingSquareInTable

問題

You are given a String[] table representing a rectangular grid where each cell contains a digit. The j-th character of the i-th element of table is the digit in the cell at row i, column j of the grid.

Consider a sequence of distinct cells in this table where the row numbers of the cells (in the order they appear in the sequence) form an arithmetic progression, and the column numbers also form an arithmetic progression. Concatenate the digits in the cells of this sequence to obtain a number.

Among all numbers that can be obtained in this manner, find and return the largest perfect square (a square of an integer). If there are no perfect squares, return -1 instead.

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

Just like many other Div 1-250 point problem, here also brute-force is your friend. The condition says the row numbers and column numbers should be arithmetic progressions. Given 'n' how many different arithmetic progressions you can make such that all its values are less than n? The obvious idea is to try all starting values (from 0 to n-1) and all step values (from 0 to n-1). This takes n2 steps. We need to do it once for rows and once for columns. Now for each of these values, start building the arithmetic progression and check if the number built so far is a perfect square. The maximum value among all such squares is the answer. With 4 outer loops and one loop to build the number digit by digit, the complexity is O(n^5) so far. In addition to this, we need to do the 'perfect square check' every time. To speed up this 'square check', you can either store all the perfect squares of size less than 10 digits in an appropriate data structure which allows a sub-linear query time or you can find the floor of the square root and check if it squares back to the same number .

http://www.topcoder.com/wiki/display/tc/SRM+434
My code
bool isSquare(ll a){
	ll b = (ll)sqrt(double(a));
	if(b*b == a) return true;
	return false;
}

int fromDigits(deque<int> arr){
	int x=0;
	while(!arr.empty()){
		x *= 10;
		x += arr[0];
		arr.pop_front();
	}
	return x;
}

int tx, ty;

bool inRange(int x, int y){
	return x>=0 && x<tx && y >=0 && y<ty;
}

class FindingSquareInTable {
public:
  int findMaximalSquare(vector <string> table) {
    int result=-1;

	tx = table.size();
	ty = table[0].size();

	vector<int> arr;
	deque<int> v;
	// 取得する個数
	for(int s=max(tx,ty) ; s>0 ; s--){
		// i,j -> 座標
		for(int i=0 ; i<tx ; i++){
			for(int j=0 ; j<ty ; j++){
				if(table[i][j]=='0'){
					result=0;
					continue;
				}

				// k,l -> 増分
				for(int k=-tx ; k<tx ; k++){
					for(int l=-ty ; l<ty ; l++){

						if(!inRange(i+(s-1)*k,j+(s-1)*l)){
							continue;
						}
						if(k==0 && l==0) continue;

						v.clear();
						for(int m=0 ; m<s ; m++){
							v.push_back(table[i+k*m][j+l*m]-48);
						}
						cout << fromDigits(v) << endl;

						if(isSquare(fromDigits(v))){
							arr.push_back(fromDigits(v));
						}
					}
				}
			}
		}

		if(!arr.empty()) break;
	}

	if(!arr.empty()){
		sort(arr.begin(), arr.end(), greater<int>());
		return arr[0];
	}
    return result;
  }
};

Problem 1000 HexatridecimalSum

問題

Hexatridecimal notation is base 36 notation. The digits are '0' to '9' (with values 0 to 9) and 'A' to 'Z' (with values 10 to 35).

You are given a String[] numbers, where each element represents a positive integer in hexatridecimal notation. You must select exactly k digits (from the set of all digits - '0' to '9' and 'A' to 'Z') and replace all of their occurrences in all of the numbers with 'Z'. Then, calculate the sum of all the numbers.

Return the maximal possible sum you can get. The return value must be in hexatridecimal format with no leading zeroes.

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

There are at most 35 different digits (0 to 9 and A to Y. There is no need to consider 'Z') you need to consider for replacement. If we can somehow find out a way to sort them in descending order of 'importance' (a digit that gives maximum sum when replaced is the most important digit), then the solution will be to replace the top 'k' digits (in the sorted list) with 'Z' and return the sum as the result. But to do that first we need to convince ourselves that such a greedy approach actually works. Fortunately it is easy to see that this is exactly the case, if we notice that changing a digit from some value 'x' (x can be anything from 0 to 9 or A to Y) to 'Z' increases the resulting sum by a constant value and this constant value does not depend on other digits.

Since this last observation is crucial to solving this problem, let us prove this. If you change the digit 'x' occuring in the jth position (index is 0 based and starts from left so that the least significant digit will be in 0th position) of the ith number (in the input list) then the effective increase in its value will be (Z - x)*36j. The total increase you get by replacing 'x' by Z can be obtained by summing over all positions j where the digit x occurs over all numbers in the given array. Now we can clearly see, this increase in sum does not depend on other digits.

Based on the observations above, the algorithm for the solution goes as follows,

  1. For each digit x from 0 to Y, calculate the effective increase in sum (using the idea mentioned above).
  2. Sort the list in descending order.
  3. Replace the top 'k' in the above sorted list, with 'Z', calculate the sum and return the result.

The only difficulty you might face in realizing the above algorithm in code will be the base 36 - big integer values involved. Java coders were gifted with the BigInteger class which does most of the stuff for them. You can check Im2Good's fastest submission which uses BigInteger. Petr's solution is one of the many solutions which acutally implements the radix 36 - big integer arithmetic needed for the problem.

Potential Pitfalls:

  • Assuming that 'replacing the least valued digit is always better' is a potential pitfall. Consider the number Y0. Here replacing Y with Z will increase the value by 36, whereas changing 0 to Z will give you an increase of only 35. This is because of the positional value of digits.
http://www.topcoder.com/wiki/display/tc/SRM+434