JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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:
XorGame
Method:
play
Parameters:
String, String
Returns:
int
Method 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'.
Examples
0)

    
"10101"
"11011"
Returns: 1
Player A can win in the first turn by flipping characters 1 through 3 (0-based indices).
1)

    
"001100"
"001100"
Returns: 0
Player A wins immediately after the game begins.
2)

    
"110"
"011"
Returns: 2
In 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: -1

4)

    
"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:
PeriodicTiling
Method:
minBlock
Parameters:
String[]
Returns:
int
Method 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 '#'.
Examples
0)

    
{"#-#-#",
"-----",
"#-#-#",
"-----"}
Returns: 4
There are many valid blocks of 4 tiles, for example:
#-
--
1)

    
{"#",
"#",
"-",
"#"}
Returns: 3

2)

    
{"-#----#----#----",
"---#----#----#--",
"#----#----#----#",
"--#----#----#---",
"----#----#----#-",
"-#----#----#----",
"---#----#----#--",
"#----#----#----#",
"--#----#----#---",
"----#----#----#-",
"-#----#----#----",
"---#----#----#--",
"#----#----#----#",
"--#----#----#---",
"----#----#----#-",
"-#----#----#----"}
Returns: 5

3)

    
{"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------",
"----------------"}
Returns: 1

4)

    
{"-#-#--#-##----#-",
"#----#-#--#-##--",
"-#-##----#-#--#-",
"#-#--#-##----#-#",
"----#-#--#-##---",
"#-##----#-#--#-#",
"-#--#-##----#-#-",
"---#-#--#-##----",
"-##----#-#--#-##",
"#--#-##----#-#--",
"--#-#--#-##----#",
"##----#-#--#-##-",
"--#-##----#-#--#",
"-#-#--#-##----#-",
"#----#-#--#-##--",
"-#-##----#-#--#-"}
Returns: 13
Example 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:
DistanceGraph
Method:
countArrangements
Parameters:
int, int, String[]
Returns:
int
Method 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.
Examples
0)

    
5
2
{"NY", "YN"}
Returns: 14
There 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)

    
58
1
{"NYYY", "YNNN", "YNNN", "YNNN"}
Returns: 0
Cat 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)

    
5
2
{"NNYY", "NNNY", "YNNY", "YYYN"}
Returns: 4

3)

    
10
4
{"NYYY", "YNYY", "YYNY", "YYYN"}
Returns: 600

4)

    
20
6
{"NYYYN", "YNYNN", "YYNYN", "YNYNY", "NNNYN"}
Returns: 2940

5)

    
100
8
{"NYNY", "YNYN", "NYNY", "YNYN"}
Returns: 0

6)

    
100
8
{"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.png
http://www.topcoder.com/contest/problem/PeriodicTiling/pic2.png
RSS