math, programming, and little something to laugh

TopCoder SRM 439 DIV 2

C/C++ TopCoder

Problem	Check	Points
250	○	164.76
500	○	247.74
1000	-	-

初めて500が通ったぞー！

Problem 250 SquareOfDigits

問題

You are given a String[] data representing a rectangular grid where each cell contains a digit. Find the largest square in this grid that contains the same digit in all of its corner cells. The sides of the square must be parallel to the sides of the grid. If there is more than one such largest square, pick any one of them.
Return the number of cells in the square. Note that a single cell is also considered a square, so there will always be an answer.
http://www.topcoder.com/stat?c=problem_statement&pm=10395&rd=13747

各セルに数字が含まれている長方形のグリッドを表すString []のデータが与えられる。このグリッドの中から、全ての角のセルが同じ数であるような一番大きい正方形を見つけよ。正方形の辺はグリッドの辺に平行でなければならない。最大の正方形が1つ以上ある場合は1つだけ選んで答えとする。
正方形のセルの数を返せ。1つのセルも面積1の正方形と考えられるので、どんな場合でも答えが存在する。

解説

This is simple brute force problem. The idea is:

Loop through all possible size of squares. (note that maximum size of squares is the smaller edge)

Loop through all possible top left corners of the squares

Get the largest square.

Java code:
int maxSize = Math.min(data.length, data[0].length());

for (int i = maxSize - 1; i >= 0; i--) {
    for (int j = 0; j < data.length - i; j++) {
        for (int k = 0; k < data[0].length() - i; k++) {
            if (data[j].charAt(k) == data[j].charAt(k + i) 
                && data[j].charAt(k) == data[j + i].charAt(k + i)
                && data[j].charAt(k) == data[j + i].charAt(k))
                return (i + 1)*(i + 1);
            }    
        }
    }
}
return 1; 
http://www.topcoder.com/wiki/display/tc/SRM+439

これはシンプルなbrute forceの問題です。方法は以下の通り。

あり得る全ての正方形のサイズについてループを行う(正方形の最大のサイズは小さい方の辺であることに注意する)

あり得る全ての正方形の左上のコーナーについてループを行う

最大の正方形を得る。

My code

class SquareOfDigits {
public:
  int getMax(vector <string> data) {
    int nohe=0;
	
	int width  = data.size();
	int height = data[0].size();


	int s1, s2, s3, s4, max=1;
	for(int i=0 ; i<width ; i++){
		for(int j=0 ; j<height ; j++){
			for(int k=j+1 ; k<height ; k++){
				if(i+k-j<0 || i+k-j>=width) continue;
				s1 = data[i][j]-48;
				s2 = data[i][k]-48;
				s3 = data[i+k-j][j]-48;
				s4 = data[i+k-j][k]-48;

				if(s1 == s2 && s2 == s3 && s3 == s4 && max < (k-j+1)*(k-j+1)){
					max = (k-j+1)*(k-j+1);
				}

			}
		}
	}
	return max;
  }
};

Problem 500 PouringWater

問題

You have N bottles, each with unlimited capacity. Initially, each bottle contains exactly 1 liter of water. You want to carry these bottles to another location, but you can only carry K bottles at a time. You don't want to waste any water and you don't want to make more than one trip, so you decide to redistribute the contents of the bottles until you end up with no more than K non-empty bottles.
You are only allowed to redistribute your water using the following method. First, pick two bottles that contain an equal amount of water. Then, pour the entire content of one of those bottles into the other. Repeat this process as many times as necessary.
Because of this restriction, it may be impossible to end up with no more than K non-empty bottles using only the N bottles that you have initially. Fortunately, you can also buy more bottles. Each bottle that you buy will contain exactly 1 liter of water and have unlimited capacity. For example, consider the case where N is 3 and K is 1. It's impossible to get from 3 bottles to 1. If you pour one bottle into another, you end up with one 2 liter bottle and one 1 liter bottle. At that point, you're stuck. However, if you then buy another bottle, you can pour that bottle into the 1 liter bottle, and pour the resulting 2 liter bottle into the other 2 liter bottle to end up with just one 4 liter bottle.
Return the minimum number of additional bottles you must buy in order to achieve your goal. If it's impossible, return -1 instead.
http://www.topcoder.com/stat?c=problem_statement&pm=10408&rd=13747

無制限の容量を持つN個のボトルがある。初めに、各ボトルには1リットルの水が入っている。これを別の場所まで運びたいのだが、一度に運ぶことができるのはK個のボトルだけである。あなたは水を全部運びたいし、1回より多く運ぶのも嫌なので、空でないボトルがK個以下になるように、ボトルの水を移動することにした。
水の移動は以下の方法だけが許される。まず同じ水の量が入った2つのボトルを選び、一方の水をもう一方のボトルに全て入れる。これを必要な回数だけ繰り返す。
この制約により、はじめに持っているN個のボトルだけでは、空でないK個のボトル以下にすることが不可能であるかもしれない。しかし幸いにも、必要に応じて1リットルが入った、容量が無制限のボトルを買うことができる。例えばNが3、Kが1の場合を考える。3つのボトルを1つにするのは不可能である。1つのボトルをもう1つのボトルに移し替えると、2リットルの水が入ったボトルが1つと1リットルの水が入ったボトルが1つになり、そこで終わってしまう。しかし、もしもう1つボトルを買うことが出来れば、このボトルの水を1リットルの水が入ったボトルに移し替えて、2リットルの水が入ったボトルが2つとなり、4リットルの水が入ったボトル1つを得ることができる。
ゴールに辿り着くまでに、買わなければいけないボトルの最小の数を返せ。もし不可能ならば-1を返せ。

解説

The key to a nice solution was noticing that for N bottles the minimum number of bottles that can remain after a sequence of legal operations is equal to the number of ones in the binary representation of N.
Because N <= 10^7, one can use brute force at this point, adding one bottle at a time until the number of ones in the current number's binary representation drops below K + 1.
C++ code follows:
unsigned n = N;

while (__builtin_popcount(n) > K)
    ++n;

return n - N;
One can also do the problem without this observation, thus essentially calculating the number of ones in a slower way.
We can calculate the minimum number of bottles remaining for a given N greedily. Create as many 2-liter bottles as possible, then as many 4-liter bottles as possible and so on.
For example, for N = 5 we can make floor(5/2) = two 2-liter bottles, and the 5th bottle will remain. Then we combine the two 2-liter bottles into a 4-liter bottle.
Finally, we cannot make any 8-liter bottles, so the number of remaining bottles is 2.
int getMinBottles(int N, int K)
{
    unsigned n = N;

    while (bottlesRemaining(n) > K)
        ++n;
    return n - N;
}

int bottlesRemaining(unsigned n)
{
    int nBottles = 0;
    while (n > 0)
    {
        nBottles += n % 2;
        n /= 2;
    }
    return nBottles;
}
http://www.topcoder.com/wiki/display/tc/SRM+439

良い解法の鍵は、N個のボトルについて、一連の手順を終えた後に残るボトルの最小の数が、Nのバイナリ表現の1の数と等しいということに気づくことです。
Nは10の7乗以下なので、この点についてはbrute forceを行うことができ、現在の値のバイナリ表現がK+1以下になるまでボトルを加えていけばよいのです。

これ以外の方法も考えられます。
与えられたNについて、貪欲法によって残っているボトルの最小の数を計算することができます。
2リットルのボトルをできるだけ作り、さらに4リットルのボトルをできるだけ作り・・・という操作を繰り返します。
例えばN=5の場合、floor(5/2)によって2つの2リットルのボトルを得ることができ、5番目のボトルは残ります。さらに、2つの2リットルのボトルをあわせ、4リットルのボトルにすることができます。最後に、8リットルのボトルはつくることができないので、残ったボトルの数は2です。

My code

const int bitsize = sizeof(int)*8;
int c[bitsize];

int countBit(int N){
	int bit = 1, count=0;

	for(int i=0 ; i<bitsize ; i++){
		if(N&bit) count++;
		bit <<=1;
	}
	return count;
}

class PouringWater {
public:
  int getMinBottles(int N, int K) {
	if(countBit(N) <= K) return 0;

	int a = N;

	for(ll i=1 ; i<=10000000 ; i++){
		a++;
		if(a<0) return -1;
		if(countBit(a)<=K) return i;
	}

	return -1;
  }
};

Problem 1000 PalindromeFactory

問題

A palindrome is a string that reads the same forward and backward. Not all strings are palindromes and we are going to fix that.
In this problem we consider four edit operations:

Insert a character at any position of a string (including the beginning and the end)

Delete a character at any position of a string

Change a character at any position of a string

Swap any two different characters (not necessarily adjacent)

You can apply the first three operations any number of times, but the last operation can be applied at most once.
You are given a String initial. Return the minimal number of operations needed to make a palindrome from it.
http://www.topcoder.com/stat?c=problem_statement&pm=10380&rd=13747

回文とは、前から見ても後ろから見ても同じになる文字列です。全ての文が回文となるわけではなく、操作をすることで回文にすることができます。
この問題では、以下の4つの操作を考えます。

文字列の任意の場所に文字を挿入する(最初と最後を含む)

文字列の任意の場所の文字を削除する

文字列の任意の場所の文字を変更する

2つの異なる文字を交換する(隣接している必要はない)

上の3つの操作は何度行っても良いですが、最後の操作は最大1回とします。
最初に与えられた文字列に対して、これを回文にするのに必要な操作の最小回数を返しなさい。

解説

This is a classic dynamic programming problem. First, let's notice that we don't need insert operation. Indeed, instead of inserting some character we can delete the character that would have been it's mirrored copy in the resulting palindrome. This means that we can always do the swap before any other operation. Ok, we know how to handle the nasty swap operation, but how to find the minimal number of operation needed to make palindrome using only operations insert, delete and edit? This is where DP comes in.
Let S be our initial string. Let dp[i][j] is a minimum number of operations needed to make a palindrome from substring S[i,j] (from i-th to j-th symbol, inclusive). Obviously, dp[i][i] = 0, since a string with one character is always a palindrome. To compute dp[i][j] let's notice a key property of a palindrome. Its first letter equals to the last letter, and if we remove first and last letters it's still a palindrome. We have a recurrent structure, which allows us to use dynamic programming. There are four options what to do with the first and last letter.

Take them both

Take none of them

Take the first and not the last

Take the last and not the first

If we take both letters, they must be equal, so if they are not we can change one of them to match another. This gives the following recursive schema to find dp[i][j].
dp[i][j] = minimum of values ( dp[i+1][j-1] + (S[i]==S[j] ? 0 : 1), dp[i+1][j]+1, dp[i][j-1]+1 )
http://www.topcoder.com/wiki/display/tc/SRM+439

これは古典的な動的計画法の問題です。まず、挿入の操作には意味が無いことに気づきましょう。実際には、挿入の代わりにその反対側の文字を消去すれことで回文を得ることができます。これは、何かの操作を行う前に交換を行えば良いということになります。交換の操作は非常に厄介なのですが、これを挿入、削除、変更だけを用いて表すことができないでしょうか？ここにDPを用います。
Sを最初の文字列、dp[i][j]を、サブ文字列S[i,j](i文字目からj文字目まで)を回文数にするための操作の最小の数とします。
明らかにdp[i][j]=0ですから、1文字の文字列は常に回文です。dp[i][j]を計算するためには、回文の性質に気づく必要があります。回文の最初の文字と最後の文字と等しく、最初と最後の文字を消去しても回文のままです。これは再帰的な構造であり、DPを用いることができます。最初と最後の文字については、以下の4つの操作があります。

両方とる

両方残す

最初だけとる

最後だけとる

もし両方とった場合は、それらが等しくなければならないので、もしそうでなかったら片方をもう片方と合うように変更することができます。これは以下のdp[i][j]を求める再起の概要を与えます。
dp[i][j] = minimum of values ( dp[i+1][j-1] + (S[i]==S[j] ? 0 : 1), dp[i+1][j]+1, dp[i][j-1]+1 )

1000とか見た時点で諦めてた。DPを勉強しよう