JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums News, Programs & Events Discussions 2012 TopCoder Open Semifinal 1 problems
 Semifinal 1 problems | Reply [250]Problem Statement    There is a 3-dimensional grid that consists of N*M*L cells. Each of the cells has three integer coordinates (i,j,k), where 0 <= i < N, 0 <= j < M, and 0 <= k < L. Initially, the cells are colorless. You are now going to color each of the cells either white or black.You will be given three strings: S, T, and U. Each of these strings only contains the characters 'o' and 'x'. The lengths of these strings are N, M, and L, respectively.The coloring of cells will consist of two steps. The first step looks as follows: For each i,j,k: you color the cell (i,j,k) white if the three characters S[i], T[j], and U[k] are all the same. Otherwise, you color the cell black.Once the first step is done, the white cells will form some connected components. (Two cells belong to the same component if they share a common face. Belonging to the same component is transitive.) A white component is said to be on the boundary, if at least one of its cells has a face that is on the boundary of the grid.In the second step, the white components that are on the boundary will remain white, and the color of all remaining white components is changed to black.You are given three vector s: SArray, TArray, and UArray. Concatenate all elements of SArray to get S. In the same way, TArray yields T and UArray yields U. Your method must return the number of black cells after the second step.Definition    Class:FloodFill3DMethod:countBlackParameters:vector , vector , vector Returns:long longMethod signature:long long countBlack(vector SArray, vector TArray, vector UArray)(be sure your method is public)    Constraints-SArray, TArray and UArray will each contain between 1 and 50 elements, inclusive.-Each element of SArray, TArray and UArray will contain between 1 and 50 elements, inclusive.-Each character of SArray, TArray and UArray will be either 'o' or 'x'.Examples0)    {"oxo"}{"oxo"}{"oxo"}Returns: 19The figure below shows how the coloring is done. After the first step, 9 cells are white and the other 18 are black. In the second step, the cell (1,1,1) changes color to black. So there are 18+1 = 19 black cells after the second step. 1)    {"ooo"}{"oo"}{"o"}Returns: 0There are 3*2*1=6 cells and all of those are colored in white in the first step. Since this connected component shares at least one face with the boundary of the cells, it is not recolored. Therefore, the resulting number of black cells are 0.2)    {"xxo", "oox", "o"}{"x", "o", "x", "o"}{"ooo", "xxxoo", "oxx"}Returns: 242Do not forget to concatenate all elements of the vector s to get S, T, and U.3)    {"xxxxxxxxxxxxxxxxxxxx","xxooooooooooooooooxx","xxooooooooooooooooxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxooooxxxxxxxx","xxxxxxxxxxxxxxxxxxxx"}{"xxxxxxxxxxxxxxxxxxxx","xxxxxxxoooooooxxxxxx","xxxxxoooooooooooxxxx","xxxxooooooooooooxxxx","xxxxooooxxxxxoooxxxx","xxxxoooxxxxxxxxxxxxx","xxxxoooxxxxxxxxxxxxx","xxxxoooxxxxxxxxxxxxx","xxxxooooxxxxoooxxxxx","xxxxoooooooooooxxxxx","xxxxxooooooooooxxxxx","xxxxxxoooooooxxxxxxx","xxxxxxxxxxxxxxxxxxxx"}{"xxxxxxxxxxxxxxxxxxxx","xxxxxxxoooooxxxxxxxx","xxxxoooooooooooxxxxx","xxoooooooooooooooxxx","xxoooooxxxxxoooooxxx","xxooooxxxxxxxooooxxx","xxooooxxxxxxxooooxxx","xxooooxxxxxxxooooxxx","xxooooxxxxxxxooooxxx","xxoooooxxxxxoooooxxx","xxxxoooooooooooxxxxx","xxxxxxxoooooxxxxxxxx","xxxxxxxxxxxxxxxxxxxx"}Returns: 15027148 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 1 problems (response to post by [[rng_58]]) | Reply [1000]Problem Statement    Alice and Bob are playing a famous game called Nim. In this game, they first set up n piles of stones. The piles are labeled 1 through n. For each i, the number of stones on the i-th pile is between 1 and m, inclusive. Once the piles are set up, Alice and Bob alternate in taking turns. In their turn, each player chooses one of the piles and removes some stones from the pile (at least one, possibly all of them). The game ends when all piles are empty. The player unable to make a valid move loses. (In other words, the player who removed the very last stone wins.)Since Alice and Bob are both brilliant, they soon learned how to play Nim and both started playing it optimally. Nowadays, they don't even need to play the game. They simply look at the initial setup of piles and compute who will win the game. It is no surprise that this gets a bit boring after some time.Therefore they came up with an improved version of the game. The new version looks as follows:They both agree on the values n, m (with meanings as mentioned above), and k (explained below). For convenience, m+1 will always be a power of 2.Alice picks the sizes of the n piles.Bob selects exactly k consecutive piles and throws the remaining piles away. That is, for some i, Bob selects the piles i through i+k-1.Alice may remove some of the piles. (She is allowed to remove as many as she wants, but not all of them. She is allowed to remove no piles. The piles she removes do not have to be consecutive.)With the remaining piles Bob and Alice play a game of Nim. In this game, Bob takes the first turn.Alice wants to win the game. Clearly, the key to winning the game is picking a good sequence of pile sizes in the second step of the above description. You are given the ints n, m, and k. Your goal is to count all sequences of pile sizes with the following property: If Alice picks the sequence in step 2, and then both Alice and Bob play the rest of the game optimally, Alice will win. As this count can be a huge number, return its remainder modulo 1,000,000,007.Definition    Class:YetAnotherNimMethod:solveParameters:int, int, intReturns:intMethod signature:int solve(int n, int m, int k)(be sure your method is public)    Notes-Two sequences of pile sizes are considered different if there is some i such that the number of stones on the i-th pile differs. For example, the sequences (2,5,7) and (2,7,5) are considered different.Constraints-n will be between 1 and 1,000,000,000 (10^9), inclusive.-m will be between 1 and 1,000,000,000 (10^9), inclusive.-m + 1 will be a power of 2.-k will be between 1 and n, inclusive.Examples0)    100130Returns: 1There is only one valid setup: 100 piles with one stone each. In step 3, Bob will select exactly 30 of these piles. (It does not matter which 30, as they all look the same.) In step 4, Alice will remove 28 of them, leaving Bob with two piles, each with one stone. In the game of Nim, Bob takes one of the stones, Alice the other one, and she wins. Hence there is one setup such that Alice wins the game.1)    100151Returns: 0Regardless of what Alice does in step 2, after step 3 there will only be one pile of stones. Nothing will happen in step 4, as Alice has to leave at least one pile of stones. In the game of Nim, Bob will simply take all the stones from that pile and win the game. So there are no setups such that Alice wins.2)    100152Returns: 15In step 3, Bob will pick two of the 100 piles. Alice cannot throw anything away in step 4, because if she does, only one pile will remain and Bob easily wins the game of Nim. So the game of Nim will be played with the two piles Bob selected. Bob wins the game of Nim if and only if the piles have different sizes. So in order to win the game, Alice has to make sure that Bob picks two equal piles in step 3. The only way to force this is by choosing the same size for each of the 100 piles in step 2. As the maximal pile size is 15, there are exactly 15 winning setups.3)    111Returns: 04)    1003110Returns: 908629681 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 1 problems (response to post by [[rng_58]]) | Reply [500]Problem Statement    This problem statement contains images that may not display properly outside the applet. There are N characters in the Ninja language. As the number of different characters can be very large, we will use numbers from 1 to N to represent the individual characters in Ninja language. The characters are numbered in alphabetical order. That is, whenever i < j, character i is earlier in the alphabet than character j. Each string in Ninja language can now be seen as a sequence of integers. When comparing two different strings of the same length, the lexicographically smaller one is the one with a smaller integer on the first place where they differ. Ninja Ren has a string R of length N that contains each character exactly once. Then she converted the string R to the string S using the following method: First, Ren takes her string R and writes it onto a circular piece of paper. The paper can now be cut at one of N possible positions, each time producing a different string of length N. Ren takes those N different strings and sorts them into lexicographical order (starting with the lexicographically smallest one). The string S is obtained by taking the last characters of the N sorted strings, in order. In other words, Ren takes the N cyclic rotations of R, sorts them, and then only looks at their last letters. For example, when R is "2 4 5 1 3", S will be "5 3 1 2 4". The following picture shows how the conversion works. You are given the int N and a vector first. containing a prefix of the string S. More precisely, for each valid index i, element i of first is the i-th character of S. (Both indices are 0-based.) Find the lexicographically smallest possible string S. If N is less than or equal to 50, return the entire string S. If N is greater than 50, return just the last 50 characters of S. If there is no such S, return an empty vector instead.Definition    Class:StRingsMethod:getSmallestParameters:int, vector Returns:vector Method signature:vector getSmallest(int N, vector first)(be sure your method is public)    Constraints-N will be between 1 and 100,000 inclusive.-first will contain between 1 and 50 elements, inclusive.-Each element of first will be between 1 and N, inclusive.-Elements of first will be pairwise distinct.-The constraints above guarantee that the number of elements of first will be less than or equal to N.Examples0)    5{2, 4}Returns: {2, 4, 1, 5, 3 }{2, 4, 1, 5, 3} is the lexicographically smallest possible string S.1)    5{1}Returns: { }There is no S that starts with 1.2)    10{3, 8, 6}Returns: {3, 8, 6, 1, 2, 5, 4, 9, 10, 7 }3)    100{34, 68, 97, 87, 47, 39, 50, 59, 4, 7, 29, 91, 1, 80, 90, 95, 60, 40, 43, 73, 54, 69, 32, 31, 53, 11, 84, 3, 28, 77, 44, 86, 2, 75, 85, 52, 93, 81, 70, 89, 19, 67, 98, 100, 41, 65, 57, 27, 33, 49}Returns: {5, 6, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 30, 35, 36, 37, 38, 42, 45, 46, 48, 51, 55, 56, 58, 61, 62, 63, 64, 71, 66, 72, 74, 76, 78, 79, 82, 88, 83, 94, 96, 92, 99 }If N is greater than 50, return just the last 50 characters of S.4)    1{1}Returns: {1 } 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.
 Forums News, Programs & Events Discussions 2012 TopCoder Open Semifinal 1 problems Previous Thread  |  Next Thread