TopCoder SRM 426 DIV 2

C/C++ TopCoder
Problem Check Points
250 ○
500 - -
1000 - -

500の問題がひどすぎる。全く意味がわからずタイムオーバー。

Problem 250 KnockoutTourney

問題

You have just entered a knockout tournament with N competitors. The tournament is structured as follows: at the start, the competitors are written down in a list. Adjacent competitors in the list are then paired off, starting from the first competitor on the list, and each pair plays a match (competitor 1 plays against 2, 3 plays against 4, etc.). The losers of each match are eliminated and their names are crossed off the list, while the winners progress to the next round. If there are an odd number of competitors in a round, then the last competitor in the list advances to the next round automatically, without having to play a match. This process then repeats with the new list of competitors, until only a single competitor remains, who is declared the winner. Note that the ordering of the competitors is preserved between rounds.

Your arch-rival has also entered the tournament and you want to know when you might end up playing against him. Your position in the list for the first round is you and your rival's position is rival (both indexed from 1). Assuming that both you and your rival win all the matches before you play each other, return the number of the round in which you will meet (counting the rounds from 1).

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

As with most easy division II problems, the solution here is simply a case of simulating the process. In each round, every competitor in an odd numbered position of the list is paired against the competitor 1 position higher, so if at any point you and your oppenent are in such a pair of positions, then you will meet in the current round. Otherwise, you need to calculate your position in the list for the next round. This is simply a case of noticing that if your position is p (1 based indexing), then exactly p/2 competitors (rounded down) before you in the list will be eliminated each round. Your position for the next round is therefore p - (p/2). The situation is exactly the same for your rival. The problem lends itself nicely to recursive solution. Note that the total number of competitors N is actually irrelevant.

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm426
My code
class KnockoutTourney {
public:
  int meetRival(int N, int you, int rival) {
	
	 
	 if(you > rival){
		 int tmp = you;
		 you = rival;
		 rival = tmp;
	 }

	 for(int i=1 ; i<1000 ; i++){
		 if(you%2==1 && rival%2==0 && you+1 == rival) return i;

		 if(you%2==0) you /=2;
		 else you = you/2+1;

		 if(rival%2==0) rival /=2;
	     else rival = rival/2+1;
	 }

	 return -1;
  }
};

Problem 500 ShufflingMachine

問題

A card shuffling machine is a device designed to randomize the order of a deck of cards. A particularly poor (but unfortunately relatively common) design of machine works as follows: an integer N is selected uniformly at random between 1 and maxShuffles, inclusive, and a series of N exactly similar deterministic shuffles are performed. A deterministic shuffle is a fixed permutation of the cards. The randomness of the resulting ordering is clearly therefore only dependent on the number of shuffles chosen. After the deck has been shuffled N times, the cards are distributed to the players.

A particularly dishonest player has decided that he wishes to cheat. He has identified K cards in the deck that he wants to receive when the cards are distributed. He has managed to figure out both the fixed shuffle that the machine uses and also the maximum number of shuffles chosen. The fixed shuffle is given in a int[] shuffle, in which element i gives the position after the shuffle of the card that was initially in position i (both 0-based). The positions in the deck of the cards the player will receive after they have been shuffled are given in cardsReceived (0-based). Before the cards are shuffled, the player can order them in any way he wishes. Determine the initial ordering that will maximize the expected number of the K desired cards that he will receive and return this expected number.

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

First of all, lets call all positions listed in cardsReceived good, and all positions not in cardsReceived will be bad. Lets start from the easiest possible case - K = 1, when the player is interested in only one card. We need to determine which position we should place that card before shuffling. The most natural brute-force way to do that is to check all possible positions, do maxShuffle shuffles for each position. The quality of position X will be equal to the number of times that the card from position X will appear at good positions after one of those maxShuffle shuffles. Obviously, if we are interested in only one card, we place it at the position with the highest quality. The probability of getting this card will be equal to Q / maxShuffle, where Q is the respective quality.

The situation is very similar when we have two, three, or more cards - since the quality of each position is independent from qualities of other positions, we just pick two (three, or more) positions with highest qualities and place the cards we are interested in on those positions. The expected number of cards we get will be equal to the sum of all qualities divided by maxShuffle:

    public double stackDeck(int[] shuffle, int maxShuffles, int[] cardsReceived, int K) {
        int N = shuffle.length;
        int[] total = new int[N];
        int[] order = new int[N];
        for (int i = 0; i < N; i++)
            order[i] = i;
        for (int i = 0; i < maxShuffles; i++) {
            int[] cpy = order.clone();
            for (int j = 0; j < N; j++)
                order[shuffle[j]] = cpy[j];
            for (int j = 0; j < cardsReceived.length; j++)
                total[order[cardsReceived[j]]]++;
        }
        Arrays.sort(total);
        int sum = 0;
        for (int i = N - K; i < N; i++)
            sum += total[i];
        return sum / (double)maxShuffles;
    }
My code
class ShufflingMachine {
public:
  double stackDeck(vector <int> shuffle, int maxShuffles, vector <int> cardsReceived, int K) {
    double result = 0;

	int init[50];
	int cnt[50];


	for(int i=0 ; i<shuffle.size() ; i++){
		init[i] = i;
		cnt[i] = 0;
	}

	for(int i=0 ; i<maxShuffles ; i++){
		for(int j=0 ; j<shuffle.size() ; j++){
			init[j] = shuffle[init[j]];

			for(int k=0 ; k<cardsReceived.size() ; k++){
				if(init[j] == cardsReceived[k]) cnt[j]++;
			}
		}
	}

	int a=0;
	for(int i=0 ; i<K ; i++){
		int maxtmp = 0;
		int maxp = -1;
		for(int j=0 ; j<shuffle.size() ; j++){
			if(maxtmp < cnt[j]){
				maxtmp = cnt[j];
				maxp = j;
			}
		}
		a += maxtmp;
		cnt[maxp] = 0;
	}

    return (double)a/(double)maxShuffles;
  }
};

Problem 1000 DistinctDigits

問題

Consider the set of numbers formed by taking every number between low and high, inclusive, and sorting the digits of each number in non-increasing order (the numbers are initially written without any extra leading zeros). Return the number of distinct numbers in this new set.

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

This problem looks quite scary at the first glance. Fortunately, one may notice the answer for example 5 (1000, 10000000) is only 19 thousands, so the maximum total number of distinct numbers shouldn't be much bigger. This means we can easily check all possible non-increasing sequences and check whether each of them can represent a number between low and high. Note: Unlike in many similar problems, the answer in this one is not equal to the total number of distinct numbers between 1 and high minus the total number of distinct numbers between 1 and low.

To go through all possible sequences we can use a DFS on a graph, where each vertex is a pair (sequence S, digit D). You start from a pair (empty string, digit 0), and on each step we have 3 options: stop and check the current sequence S, append the digit to the sequence and continue to state (S + D, D), or move to the next digit and continue with state (S, D + 1). Now we need to solve the harder part of the problem - to check whether a sequence S can be reordered to represent a number X between low and high.

First we take care of the most obvious cases - when the length of sequence is not equal to lengths of low and high. Having done that, the problem is down to one of the following three subproblems:

Subproblem A1. Given a sequence of digits S and a number X determine whether it is possible to reorder the sequence such that the result will be not less than X. This problem can be solved by greedy approach - build a number T by picking the biggest number in S as the first digit of T, the second-biggest number as the second digit, and so on. Since T is the biggest number we can build from S, then the subproblem A is solvable if and only if T >= X.

Subproblem A2. Given a sequence of digits S and a number X determine whether it is possible to reorder the sequence such that the result will be not greater than X. Can be solved similarly to A1, but we build the smallest possible number T and make sure to avoid leading zeroes in T.

Subproblem B. Given a sequence of digits S, numbers low and high of the length equal to S, determine whether it is possible to reorder the S to receive a number T, such that low <= T <= high. First we need to make sure that the first digits of low and high are distinct. If both low and high start from a digit d, then we discard d from S, low, and high, and continue solving the problem with the smaller params (for example, if low = 12345, high = 16177 and S = "22341" then we discard '1' and continue with low = 2345, high = 6177 and S = "2234"). Of course, if S does not contain d, then we already know that the answer to the subproblem is negative. So, when the first letters of low and high are distinct, we may meet one of three following possibilities (let x and y be the first digits of (low and high, respectively):

  1. S contains a digit d, x < d < y. Then we put d as the first character of a number T, appending it with all other chars of S in any order. Obviosly low < T < high, so the subproblem is solved, and the answer is positive.
  2. All chars of S are either less than x or greater than y. Obviously, the subproblem is solved as well, but the answer is now negative.
  3. S contains a digit d1 = x or / and digit d2 = y, with all other digits being either less than x or greater than y. In this case, we have two choices: use digit d1, discard it from S and from low, and continue with subproblem A1, or use d2 and continue with subproblem A2. Fortunately, we already can solve the subproblems A1 and A2 in a linear time, and the answer to this subproblem will be positive if answer to one of two cases is positive.
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm426