TopCoder SRM 435 DIV 2

C/C++ TopCoder
Problem Check Points
250 ◯ 216.58
500 ◯ 335.45
1000 - -

1000がもう少しで解けそうだった！
実際解けてないから点にはなってないんだけども、1000も解けそうな問題があるんだなー、と。

Problem 250 SkiFriction

問題

Kate is standing on a pair of skis at the beginning of a straight path. The path consists of n segments of equal length. You are given a String pathFriction representing the friction of the path. The i-th character of pathFriction is a digit between '1' and '9', inclusive, representing the friction of the i-th segment of the path. (All indices in this problem are 0-based.)

In this problem, we will treat Kate's skis as one single ski. The ski consists of m segments of equal length. A ski segment has the same length as a path segment. The friction of the ski is given in the String skiFriction, where the i-th character is a digit between '1' and '9', inclusive, representing the friction of the i-th segment of the ski.

Initially, Kate is standing in such a way that the i-th segment of her ski touches the i-th segment of the path. She will move forward one segment at a time until the (m-1)-th segment of her ski touches the (n-1)-th segment of the path. Each time she moves forward one segment, she moves at the speed of the slowest segment of her ski. The time required for a segment of her ski to move forward by one segment is equal to the friction of that ski segment plus the friction of the path segment it currently touches.

Return the total time required for Kate to ski to the end of the path.

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

It was a standard problem. What you were required to do is to simply simulate Kate's movement.
The only tricky test case is when skiFriction and pathFriction have the same length, and some solutions didn't pass because of it.

http://www.topcoder.com/wiki/display/tc/SRM+435
My code
class SkiFriction {
public:
  int bestPosition(string skiFriction, string pathFriction) {
    int result=0;
	int tmp,max;
	for(int i=0 ; i<pathFriction.size()-skiFriction.size(); i++){
		max=0;
		for(int j=0 ; j<skiFriction.size(); j++){
			tmp = skiFriction[j]-48+pathFriction[i+j]-48;
			if(max < tmp) max = tmp;
		}
		result += max;
	}

    return result;
  }
};

Problem 500 CellRemoval

問題

n biology, organisms have the following property: Starting from the first cell (the zygote), each cell during an organism's development process either divides into 2 other cells or does not divide at all. An organism is mature when all of its cells will not divide any further.

Let's assign a unique number to each cell in an organism's development process. For example, consider a species in which each organism starts with cell 0, which divides into cells 1 and 2. Cell 1 divides into cells 3 and 4. Cells 2, 3 and 4 do not divide. Every mature organism of this species will consist of exactly 3 cells - 2, 3 and 4.

During the development process, if we kill a cell, it will be absent in the mature form of the organism. If that cell happens to be a cell that divides, then the mature organism will be missing all of the cell's descendants as well because the cell is killed before it has a chance to divide. For example, in the organism described above, if we kill cell 1 during the development process, the mature organism will contain only cell 2.



You are given a int[] parentCell describing the development process of an organism. The i-th element of parentCell is the parent cell of cell i (where i is a 0-based index). The zygote's parent is -1. Return the number of cells the mature form of this organism would have if you killed cell deletedCell during the development process.

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

This problem can be solved in two ways:

  1. Build the graph using parent.
  2. Find the cell which is the zygote.
  3. Use any graph searching algorithm, like dfs, to count the number of final cells that will be alive and are reachable from the zygote. If you use dfs, it is enough to return 0 if current vertex number is equal to deletedCell, otherwise return 1 if vertex is a leaf (mature cell) or dfs(left) + dfs(right) if it is an internal vertex (not a mature cell).

or

Probably simpler solution was to iterate through every ancestor (parent, grandparent and so on) of every cell, and mark in some array if we are sure that some cell will be absent in mature form of the organism. We can be sure that if a cell is a parent of some other cell then it is not mature and we shouldn't count it to the result. And also if a cell has an ancestor which is a deletedCell then it also will be killed and we shouldn't count it. On the other hand if a cell is mature and do not have any ancestor killed, then we should add it to the result. Code for this solution may look as follows:

bool isOk[50];
for(int i=0; i<N; ++i) isOk[i] = true;
//deletedCell will not be in the organism
isOk[deletedCell] = false;
for(int i=0; i<N; ++i)
    //iterate trough every ancestor of i-th cell
    for(int j=parent[i]; j!=-1; j=parent[j]) {
        //since j is an ancestor of i it is not a mature cell
        isOk[j] = false;
        //since j is an ancestor of i and j is killed, i is killed too
        if(j==deletedCell)
            isOk[i] = false;
    }
int result = 0;
for(int i=0; i<N; ++i) if(isOk[i])
	result++;
return result;
http://www.topcoder.com/wiki/display/tc/SRM+435
My code
class CellRemoval {
public:
  int cellsLeft(vector <int> parent, int deletedCell) {

	bool haveChild[100];
	
	for(int i=0 ; i<100; i++) haveChild[i] = false;
	
	for(int i=0 ; i<parent.size() ; i++){
		for(int j=0 ; j<parent.size() ; j++){
			if(i==parent[j]){
				haveChild[i] = true;
				break;
			}
		}
	}

	int tmp=0,cnt=0;
	for(int i=0 ; i<parent.size() ; i++){
		if(haveChild[i]) continue;
				
		tmp = i;
		if(tmp==deletedCell) continue;

		while(1){
			if(parent[tmp]==deletedCell) break;
			if(parent[tmp]==-1){
				cnt++;
				break;
			}
			tmp = parent[tmp];
		}
	}

    return cnt;
  }
};

Problem 1000 BirdsCounting

問題

In ecology, there are several ways of estimating the size of a population in a given area. We are interested in estimating the size of a population of birds. To do this, we will use the following procedure.

First, there will be a data collection phase that lasts exactly daysNumber days. Initially, all the birds are unmarked. During each day of data collection, we will catch exactly caughtPerDay birds. At the end of each day, we will examine each of the birds we have caught. If a bird is unmarked, we will mark it. If a bird is already marked, we will leave it alone (and it will remain marked). We will then release all of them back into the wild before the next day begins.

After the data collection phase is complete, we can use the number of unmarked birds caught each day to estimate the size of the population.

To help our fellow ecologists in analyzing the collected data, we must compute the probability that after daysNumber days of data collection, there will be exactly birdsMarked marked birds assuming that there are birdsNumber birds in this area. Assume that the probability of being caught is exactly the same for every bird on every day.

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

This problem requires some math skills and can be solved using dynamic programming.

Algorithm should work as follows: knowing probabilities that exactly 0, 1, ..., birdsNumber birds are marked after (i-1)-th day of collecting data phase, compute these probabilities after i-th day.

Let's hold this probabilities in the array dp. dp[d][m] is the probability that after d days there will be exactly m birds marked.

Also, let's introduce function prop(add, prev), which computes the probability that during a single day there will be exactly add new birds marked if there were previously prev marked birds in the area. I will write later how to compute value of this function.

Now, let's try to compute dp[d][m] knowing all values dp[d-1][0], dp[d-1][1], ..., dp[d-1][birdsNumber].

dp[d][m] = prop(0,m)*dp[d-1][m] + prop(1,m-1)*dp[d-1][m-1] + prop(2,m-2)*dp[d-1][m-2] + ... + prop(caughtPerDay,m-caughtPerDay)*dp[d-1][m-caughtPerDay] - because ecologists may mark between 0 to caughtPerDay new birds during a single day and we need to add probabilities for every of these events.

So the only difficulty now is how to compute the value of prop function. Value of prop(add, prev) is the probability that there will be add new birds marked if there were already prev birds marked in the area. What it means is that during a single day there will be add previously unmarked birds caught, and there will be (caughtPerDay-add) birds marked that have been marked earlier. Now use some combinatorics. We need to catch this new add birds from the set of unmarked birds (it's size is birdsNumber-prev), and we need to catch (caughtPerDay-add) from the set of marked brids of size prev. Different ways on how we can do that is: C(add, birdsNumber-prev)*C(caughtPerDay-add, prev), where C(i,j) is the number in i-th column of j-th row in Pascal's triangle. Since the overall number of ways on which we can catch birds during a single day is C(caughtPerDay, birdsNumber), and probability of catching every bird every day is the same, then prop(add,prev) = C(add, birdsNumber-prev)*C(caughtPerDay-add, prev) / C(caughtPerDay, birdsNumber).

http://www.topcoder.com/wiki/display/tc/SRM+435
My code
double ans;
int birdsNumber2;
int caughtPerDay2;
int daysNumber2;
int birdsMarked2;

ll factorial(ll m, ll n){
	ll ans = 1;
	for(ll i=m ; i<=n ; i++) ans *= i;
	return ans;
}

// mCn
ll combination(ll m, ll n){
	ll ans = 1;
	if(n==0) return 1;

	ll mf = factorial(m-n+1,m);
	ll nf = factorial(1,n);

	ans = ((ll)mf/(ll)nf);
	return ans;
}


void dfs(int marked, int day, double p){
	if(day==daysNumber2){
		if(marked==birdsMarked2) ans += p;
		return;
	}

	double tmpp;
	for(int i=0 ; i<=caughtPerDay2 ; i++){
		tmpp = (double)(combination(marked,caughtPerDay2-i)*combination(birdsNumber2-marked,i))/(double)combination(birdsNumber2,caughtPerDay2);
		dfs(marked+i, day+1, p*tmpp);
	}
}

class BirdsCounting {
public:
  double computeProbability(int birdsNumber, int caughtPerDay, int daysNumber, int birdsMarked) {
	  ans = 0;
	  birdsNumber2 = birdsNumber;
	  caughtPerDay2 = caughtPerDay;
	  daysNumber2 = daysNumber;
	  birdsMarked2 = birdsMarked;

          dfs(caughtPerDay,1,1);
	  return ans;
  }
};