JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Semifinal 2 problems | Reply
[275]


Problem Statement
    
You have N balls, where N is odd. The balls are numbered from 0 to N-1. In that order, they are arranged into a row going from the left to the right.

In addition to the number, each ball has either the word "left" or the word "right" written on it. For simplicity, we will use the character '<' instead of "left", and the character '>' instead of "right". You are given the labels on all balls as the String label. For each i, character i of label represents the word on ball i.

You will now repeat the following procedure:
Choose a ball that is not at either end of the row of balls.
If the chosen ball has the label '<', remove the chosen ball and also the ball immediately to the left of it. Otherwise, remove the chosen ball and also the ball to the right of it.
Without reordering the remaining balls, push them together to get rid of the gap created in the previous step.
The process ends when only one ball remains in the row. That ball is called the survivor. Note that the numbers on the balls do not change during the process.

Find all possible survivors. Your method must return a String containing exactly N characters. If ball i can be the survivor, character i of the return value must be 'o' (lowercase oh). Otherwise, the corresponding character must be '.' (a period).
Definition
    
Class:
BallRemoval
Method:
canLeave
Parameters:
String
Returns:
String
Method signature:
String canLeave(String label)
(be sure your method is public)
    

Constraints
-
label will contain between 3 and 49 characters, inclusive.
-
label will contain an odd number of characters.
-
Each character of label will be either '>' or '<'.
Examples
0)

    
"<<>"
Returns: "..o"
Initially, you have three balls. Since you cannot choose balls at the ends of the row, you have to choose ball 1. As its label is '<', you remove balls 0 and 1. Hence the only possible survivor is ball 2.
1)

    
">>><<"
Returns: "o...o"
If you choose ball 2 or ball 3 first, you have to choose ball 1 next, and the survivor will be ball 0. If you choose ball 1 first, you have to choose ball 3 next, and the survivor will be ball 4.
2)

    
"<<><<"
Returns: "....o"

3)

    
"<><<><>"
Returns: "o.....o"

4)

    
">>><<<>>>>><<<>"
Returns: "o.....o.o.....o"


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Re: Semifinal 2 problems (response to post by [[rng_58]]) | Reply
[950]


Problem Statement
    
Cat Taro and rabbit Hanako are running the animal programming competitions in a forest. John and Brus are invited as judges. Each team that takes part in the competitions consists of exactly four members. Each team member is either a cat or a rabbit. You are given a int[] rabbits. The number of teams that take part in the competitions is equal to the number of elements in rabbits. For each i, team number i (0-based index) consists of rabbits[i] rabbits and 4-rabbits[i] cats. According to the best traditions of the animal programming competitions, each rabbit brings one carrot at the opening ceremony and presents it to some participant (either a cat or a rabbit) from a different team. The rabbits always coordinate their choices in order to make sure that no participant receives more than one carrot as a present. It seems this task is not that easy for the rabbits, so they asked the judges (John and Brus) to help them. Now John and Brus are thinking of a carrot distribution plan. All the carrots are considered pairwise distinct. Hence, two distribution plans are considered distinct if and only if there is at least one participant that receives a different present (i.e., either a different carrot in each plan, or a carrot in one plan and no carrot in the other). Return the number of different distribution plans, modulo 1,234,567,891.
Definition
    
Class:
TheAnimalProgrammingCompetitions
Method:
find
Parameters:
int[]
Returns:
int
Method signature:
int find(int[] rabbits)
(be sure your method is public)
    

Constraints
-
rabbits will contain between 1 and 47 elements, inclusive.
-
Each element of rabbits will be between 0 and 4, inclusive.
Examples
0)

    
{0, 1, 0}
Returns: 8
There are eight options for the only rabbit in the competitions.
1)

    
{4}
Returns: 0
Rabbits can't present carrots to their teammates.
2)

    
{1, 1, 0}
Returns: 60
If the first rabbit presents their carrot to somebody from the second rabbit's team then there are eight options for the second rabbit, if not - only seven. Thus the total number of different plans is 4*8 + 4*7 = 60.
3)

    
{0, 1, 2, 3, 4}
Returns: 644027397


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Re: Semifinal 2 problems (response to post by [[rng_58]]) | Reply
[500]


Problem Statement
    
Let S be a set containing k non-negative integers: { S[0], ..., S[k-1] }. We define OR(S) to be the bitwise "or" of all elements of S. Formally: OR(S) = S[0] or S[1] or ... or S[k-1]. For consistency, if S is the empty set, then OR(S) is defined to be 0. A set T is called "independent with respect to OR" if no two subsets of T produce the same value when OR is applied to them. Formally, T should have the following property: | { OR(S) : S is a subset of T } | = 2^|T|. In words: the set of all values OR(S), where S is a subset of T, contains exactly (2 to the size of T) distinct values. You are given a int[] A that describes a set of integers. Your goal is to select a subset B of the set described by A. The subset B has to be independent with respect to OR, and the sum of its elements has to be as large as possible. Return the largest possible sum of elements of the set B.
Definition
    
Class:
IndependentOfOR
Method:
maxSum
Parameters:
int[]
Returns:
int
Method signature:
int maxSum(int[] A)
(be sure your method is public)
    

Constraints
-
A will contain between 1 and 50 elements, inclusive.
-
All elements of A will be pairwise distinct.
-
Each element in A will be between 1 and 1,000,000, inclusive.
Examples
0)

    
{2, 3}
Returns: 3
The optimal solution is: {3}. Note that {2, 3} is not a valid solution, since |OR({2, 3})| = |{0, 2, 3}| = 3 < 2^2 = 4.
1)

    
{1, 2, 3, 4, 5, 6}
Returns: 11
This time the optimal solution is {5, 6}.
2)

    
{2, 3, 5, 7, 11, 13, 17, 19}
Returns: 41

3)

    
{8, 9, 13, 45, 47, 111, 127}
Returns: 127

4)

    
{5, 8, 55, 58, 85, 88, 555, 558, 585, 588, 855, 858, 885, 888}
Returns: 2919

5)

    
{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288}
Returns: 1048575


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Re: Semifinal 2 problems (response to post by [[rng_58]]) | Reply
Modulo 1,234,567,891 is so evil. :)
I'm just so used to modulo 1,000,000,007 and the fact that adding two numbers doesn't overflow in that case.
Re: Semifinal 2 problems (response to post by [[rng_58]]) | Reply
ignore, double post
RSS