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 TCO 2012 Finals problems
 TCO 2012 Finals problems | Reply [250]Problem Statement    You are given two Strings: the start string S and the end string E. Both strings have the same length, and each of their characters is either '0' or '1'. Two players A and B play the game that starts with the string S. Player A and player B take alternating turns, with player A going first. In each of her turns, player A picks a contiguous subsequence of the current string and flips it - changing all '0's to '1's and vice versa. (She is allowed to pick an empty subsequence, which results in her not changing the current string.) In each of his turns, player B may pick a character of the current string and flip it. (He is allowed not to pick any character and keep the current string unchanged.) When the string turns into E, player A wins. If player A can win the game, return the minimum possible number of turns A has to take. (We assume that if player A can ensure a win, then player B uses a strategy that postpones his loss for as long as possible.) If player A cannot win the game, return -1 instead.Definition    Class:XorGameMethod:playParameters:String, StringReturns:intMethod signature:int play(String S, String E)(be sure your method is public)    Constraints-S will contain between 1 and 50 characters, inclusive.-S and E will contain the same number of characters.-Each character in S and E will be '0' or '1'.Examples0)    "10101""11011"Returns: 1Player A can win in the first turn by flipping characters 1 through 3 (0-based indices).1)    "001100""001100"Returns: 0Player A wins immediately after the game begins.2)    "110""011"Returns: 2In this case, player A cannot win in her first turn. However, she can start by flipping characters 1 and 2, producing the string "101". Regardless of what player B does (and even if he chooses not to flip anything), she will then have winning move in her second turn.3)    "10101010""11111111"Returns: -14)    "001011010101101""001000101101101"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.
 Re: TCO 2012 Finals problems (response to post by [[rng_58]]) | Reply [500]Problem Statement    This problem statement contains images that may not display properly outside the applet. Cucumberman went to a theme park. The floor of the park was interesting: It was tiled with black tiles and white tiles. The tiling was systematic: the floor consisted exclusively of repeated copies of a single block of tiles. For the purpose of this problem, we will assume that the floor was infinitely large. The following picture shows an example: a finite rectangular part of one possible floor. This tiling pattern can be made of disjoint copies of a block that consists of 13 tiles. The picture on the left shows one block, and the picture on the right shows how blocks are placed to form the tiling. Let's call this tiling a 13-tiling. Formally, a tiling is a way to represent the entire infinite floor as a union of infinitely many blocks, each containing a finite number of tiles. A tiling is called a k-tiling if the following conditions are all satisfied:Each tile is contained in exactly one block.Each block contains exactly k tiles.Each block must be 4-connected.All blocks have exactly the same shape. Formally, for any pair of blocks X and Y, there is a translation (no rotations or reflections) of the entire floor that moves block X to exactly cover the current position of block Y.The tiling is periodic. Formally, for any three blocks X, Y, and Z, there is a block W such that if we take the translation that moves block X to block Y, this translation would move block Z to exactly cover the current position of block W.You are given a String[] part that represents a rectangular part of the infinite floor. Return the minimal possible integer k such that the floor can be a k-tiling.Definition    Class:PeriodicTilingMethod:minBlockParameters:String[]Returns:intMethod signature:int minBlock(String[] part)(be sure your method is public)    Constraints-part will contain between 1 and 16 elements, inclusive.-Each element of part will contain between 1 and 16 characters, inclusive.-All elements of part will contain the same number of characters.-Each character in part will be either '-' or '#'.Examples0)    {"#-#-#", "-----", "#-#-#", "-----"}Returns: 4There are many valid blocks of 4 tiles, for example:#---1)    {"#", "#", "-", "#"}Returns: 32)    {"-#----#----#----", "---#----#----#--", "#----#----#----#", "--#----#----#---", "----#----#----#-", "-#----#----#----", "---#----#----#--", "#----#----#----#", "--#----#----#---", "----#----#----#-", "-#----#----#----", "---#----#----#--", "#----#----#----#", "--#----#----#---", "----#----#----#-", "-#----#----#----"}Returns: 53)    {"----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------", "----------------"}Returns: 14)    {"-#-#--#-##----#-", "#----#-#--#-##--", "-#-##----#-#--#-", "#-#--#-##----#-#", "----#-#--#-##---", "#-##----#-#--#-#", "-#--#-##----#-#-", "---#-#--#-##----", "-##----#-#--#-##", "#--#-##----#-#--", "--#-#--#-##----#", "##----#-#--#-##-", "--#-##----#-#--#", "-#-#--#-##----#-", "#----#-#--#-##--", "-#-##----#-#--#-"}Returns: 13Example from the statement.5)    {"###-###-###", "-#--#---#-#", "-#--###-###"}Returns: 26 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: TCO 2012 Finals problems (response to post by [[rng_58]]) | Reply [1000]Problem Statement    Fox Ciel is the owner of a hotel. In her hotel, there are N rooms numbered from 0 to N-1. The distance between room i and room j is |i-j|. M cats, conveniently numbered from 0 to M-1, want to stay in this hotel. You are given a String[] friendship with M elements, containing M characters each. These describe the friendship between those M cats. In particular, character j of element i of friendship is 'Y' if cats i and j are friends, and 'N' if they are not. Additionally, friendship has the following properties:It is symmetric. Cats i and j are friends if and only if cats j and i are friends.It is anti-reflexive. No cat is friends with itself.The graph of friendships is connected. In other words, for any two cats i and j we can form a sequence of cats starting with cat i and ending with cat j, such that all pairs of adjacent cats are friends. Ciel wants to assign rooms to the cats. The cats made the following requests:Each cat must be assigned a single room.No two cats can be assigned the same room.For each distinct i and j, if cat i and cat j are friends, the distance between their rooms must be less than or equal to D.For each distinct i and j, if cat i and cat j are not friends, the distance between their rooms room must be strictly more than D. You are given the ints N and D and the String[] friendship. Let X be the number of ways in which Ciel can assign rooms to the cats, while satisfying all their requests. Compute and return the value (X modulo 1,000,000,007).Definition    Class:DistanceGraphMethod:countArrangementsParameters:int, int, String[]Returns:intMethod signature:int countArrangements(int N, int D, String[] friendship)(be sure your method is public)    Notes-In the statement, |x| denotes the absolute value of x.Constraints-N will be between 1 and 100, inclusive.-D will be between 1 and 8, inclusive.-friendship will contain between 1 and 50 elements, inclusive.-friendship will contain at most N elements.-Each element of friendship will contain exactly M characters, where M is the number of elements of friendship.-Each character in friendship will be either 'Y' or 'N'.-For each i and j, the j-th character of the i-th element of friendship and the i-th character of the j-th element of friendship will be the same.-For each i, the i-th character of the i-th element of friendship will be 'N'.-For each i and j, you can reach cat j from cat i by a sequence of friends, as explained in the problem statement.Examples0)    52{"NY", "YN"}Returns: 14There are two cats. As they are friends, their rooms must be at most 2 apart. There are 14 possible assignments (cat 0's room, cat 1's room): (0,1), (0,2), (1,0), (1,2), (1,3), (2,0), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,2), and (4,3).1)    581{"NYYY", "YNNN", "YNNN", "YNNN"}Returns: 0Cat 0 is friends with each of the other three cats. As D=1, each of the three cats should receive a room that is next to cat 0's room. This is impossible.2)    52{"NNYY", "NNNY", "YNNY", "YYYN"}Returns: 43)    104{"NYYY", "YNYY", "YYNY", "YYYN"}Returns: 6004)    206{"NYYYN", "YNYNN", "YYNYN", "YNYNY", "NNNYN"}Returns: 29405)    1008{"NYNY", "YNYN", "NYNY", "YNYN"}Returns: 06)    1008{"NNNNNNNNNNNNNNYNNNNNNNNNNNNYNNNNNNNNNNYNNYNNNNNNNN","NNNNYYYNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNYNNNNNNNNNYNY","NNNNNNNNNNYYNYNNNNNNNYNNNNNNNNNYNNNNNNNNNNNYNNYNNN","NNNNNNNNNNNNNNNNNYNNNNNYNNNNYNNNNYYNNNNYNNYNNNNNNN","NYNNNNYNNNNNYNNNYNYNYNYNNNNNNNNNNNNNYNNNNNNNNNNYNY","NYNNNNNNNNNNNNYNNNNYNNNNNNNNNNNNNNNNNYYNNNNNNNNNNY","NYNNYNNNNNNNNNNNYNYNYNNNNNNNNNNNNNNNYYNNNNNNNNNYNY","NNNNNNNNNNNNNNNYNYNNNNNNNNNNNNYNNNNYNNNNYNNNYNNNNN","NNNNNNNNNNNNNNNNNNNNNNNNYYYNNYNNNNNNNNNNNNNNNNNNNN","NNNNNNNNNNNNYNNNYNYNNNYNNNNNNNNNYNNNYNNNNNNNNYNYYN","NNYNNNNNNNNYNNNNNNNNNYNNNNNNNNNYNNNNNNNNNNNYNNYNNN","NNYNNNNNNNYNNNNNNNNNNYNNNNNNNNNYNNNNNNNNNNNYNNYNNN","NNNNYNNNNYNNNNNNYNYNYNYNNNNNNNNNYNNNYNNNNNNNNYNYYN","NNYNNNNNNNNNNNNNNNNNNYNNNNNNNNNYNNNNNNNNNNNNNYYNYN","YNNNNYNNNNNNNNNNNNNYNNNNNNNYNNNNNNNNNNYNNYNNNNNNNN","NNNNNNNYNNNNNNNNNYNNNNNNNNNNNNYNNYNNNNNNYNYNYNNNNN","NNNNYNYNNYNNYNNNNNYNYNYNNNNNNNNNYNNNYNNNNNNNNYNYYN","NNNYNNNYNNNNNNNYNNNNNNNYNNNNNNYNNYYNNNNYYNYNNNNNNN","NNNNYNYNNYNNYNNNYNNNYNYNNNNNNNNNYNNNYNNNNNNNNYNYNN","NYNNNYNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNYYNNNNNNNNNNY","NYNNYNYNNNNNYNNNYNYNNNNNNNNNNNNNNNNNYYNNNNNNNNNYNY","NNYNNNNNNNYYNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNNYNNYNNN","NNNNYNNNNYNNYNNNYNYNNNNNNNNNNNNNYNNNYNNNNNNNNYNYYN","NNNYNNNNNNNNNNNNNYNNNNNNNNNNYNYNNYYNNNNYNNYNNNNNNN","NNNNNNNNYNNNNNNNNNNNNNNNNYYNNYNNNNNYNNNNNNNNYNNNNN","NNNNNNNNYNNNNNNNNNNNNNNNYNYNNYNNNNNYNNNNNNNNNNNNNN","NNNNNNNNYNNNNNNNNNNNNNNNYYNNNYNNNNNYNNNNNNNNYNNNNN","YNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNYNNYNNNNNNNN","NNNYNNNNNNNNNNNNNNNNNNNYNNNNNNNNNYYNNNNYNNYYNNNNNN","NNNNNNNNYNNNNNNNNNNNNNNNYYYNNNNNNNNNNNNNNNNNNNNNNN","NNNNNNNYNNNNNNNYNYNNNNNYNNNNNNNNNYNNNNNNYNYNNNNNNN","NNYNNNNNNNYYNYNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNN","NNNNNNNNNYNNYNNNYNYNNNYNNNNNNNNNNNNNYNNNNNNNNYNNYN","NNNYNNNNNNNNNNNYNYNNNNNYNNNNYNYNNNYNNNNYYNYNNNNNNN","NNNYNNNNNNNNNNNNNYNNNNNYNNNNYNNNNYNNNNNYNNYNNNNNNN","NNNNNNNYNNNNNNNNNNNNNNNNYYYNNNNNNNNNNNNNNNNNYNNNNN","NNNNYNYNNYNNYNNNYNYNYNYNNNNNNNNNYNNNNNNNNNNNNNNYNY","NYNNNYYNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNNNNNNNNNNNNY","YNNNNYNNNNNNNNYNNNNYNNNNNNNYNNNNNNNNNNNNNYNNNNNNNN","NNNYNNNNNNNNNNNNNYNNNNNYNNNNYNNNNYYNNNNNNNYNNNNNNN","NNNNNNNYNNNNNNNYNYNNNNNNNNNNNNYNNYNNNNNNNNYNYNNNNN","YNNNNNNNNNNNNNYNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNNNNNN","NNNYNNNNNNNNNNNYNYNNNNNYNNNNYNYNNYYNNNNYYNNNNNNNNN","NNYNNNNNNNYYNNNNNNNNNYNNNNNNYNNNNNNNNNNNNNNNNNNNNN","NNNNNNNYNNNNNNNYNNNNNNNNYNYNNNNNNNNYNNNNYNNNNNNNNN","NNNNNNNNNYNNYYNNYNYNNNYNNNNNNNNNYNNNNNNNNNNNNNNNYN","NNYNNNNNNNYYNYNNNNNNNYNNNNNNNNNYNNNNNNNNNNNNNNNNNN","NYNNYNYNNYNNYNNNYNYNYNYNNNNNNNNNNNNNYNNNNNNNNNNNNY","NNNNNNNNNYNNYYNNYNNNNNYNNNNNNNNNYNNNNNNNNNNNNYNNNN","NYNNYYYNNNNNNNNNNNNYYNNNNNNNNNNNNNNNYYNNNNNNNNNYNN"}Returns: 448127799 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: TCO 2012 Finals problems (response to post by [[rng_58]]) | Reply Pictures of 500:http://www.topcoder.com/contest/problem/PeriodicTiling/pic1.pnghttp://www.topcoder.com/contest/problem/PeriodicTiling/pic2.png
 Forums News, Programs & Events Discussions 2012 TopCoder Open TCO 2012 Finals problems Previous Thread  |  Next Thread