JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 53
Problem: TilesMatching

Problem Statement

    TilesMatching is a game played by placing tiles on cells of a square board. On each turn, you are given a randomly generated tile and must either place it on the board or discard it. There are three basic types of tiles:
  • A regular tile is a tile with fixed color and shape. The tile must be placed on an empty cell which is vertically or horizontally adjacent to at least one already placed tile. The tile being placed must match the color or the shape (or both) for each tile which is vertically or horizontally adjacent to the cell where the tile is being placed.
  • A wildcard tile must be placed adjacent to at least one already placed tile, but it matches the color and the shape of any tile, and any tile can be placed adjacent to the already placed wildcard tile.
  • A "remove" tile is placed over any other tile to remove both of them from the board.
If the board has no tiles on it, the next tile will be wildcard, and it can be placed on any cell of the board. If the placed tiles fill a row or a column (or both), they are removed from the board.

The number of tiles you can discard is limited. The game starts with the counter of discarded tiles set to zero. Discarding a tile increments the counter by 1, while placing a tile on the board or using "remove" tile decrements it by 1, unless it is zero. At any moment the value of the counter must be not greater than D.

If you can neither place the tile on the board nor discard it, you have to end the game. If you never end the game, it will stop after 10000 moves. Your goal is to use as many tiles as possible before ending the game.

Implementation Details

Your code should implement two methods, as described below:
  • init (int N, int S, int D). This method is called once per test case to give you the number of colors and shapes N, width (= height) of the board S and the maximal possible value of the counter of the discarded tiles D.
  • placeTile (String tile). This method is called once per turn. tile gives you the tile you'll have to place and will be "W" for wildcard tile, "R" for "remove" tile and "CS" for a regular tile, C and S being '0'-'9' characters denoting color and shape of the tile. You must return a String formatted as "R C" to denote placing the tile on the cell in row R and column C of the board (indices are 0-based), "DISCARD" to discard the tile or "GIVE UP" to stop the game.

Scoring

Your score for a test case will be the number of tiles you have used before you give up or the simulation ends, plus 3*S multiplied by the number of times a row and a column were cleared simultaneously, plus S multiplied by the number of times a row or a column (but not both) were cleared. Placing a tile on the board and using "remove" tile to remove another tile are counted as "using" a tile, while discarding a tile of any type is not. Invalid return of any kind will result in zero absolute score for that test case.

Your overall score will be calculated in the following way: for each test case you get 1 point for each competitor you beat on this test case and 0.5 points for each competitor you tie with (a tie with yourself is not counted); finally, the sum of points is divided by (the number of competitors - 1).

Visualizer

A visualizer is avaliable for offline testing.
 

Definition

    
Class:TilesMatching
Method:init
Parameters:int, int, int
Returns:int
Method signature:int init(int N, int S, int D)
 
Method:placeTile
Parameters:String
Returns:String
Method signature:String placeTile(String tile)
(be sure your methods are public)
    
 

Notes

-You must return "GIVE UP" if you cannot make a move and have already reached the discard limit. Trying to discard beyond the limit will result in a score of 0.
-A "R" tile must be placed over an existing tile.
-If there are any tiles on the board, the next one has 1/(32-N) probability of being a wildcard and 1/(32-N) probability of being a "remove" tile. Color and shape of regular tile are chosen uniformly and independently from 0..(N-1).
-For more implementation details see the visualizer source.
-You may return any integer from init, it will be ignored.
-The memory limit is 1024 MB and the time limit is 20 seconds (which includes only time spent in your code).
-There are 10 example test cases and 100 full submission test cases.
 

Constraints

-N will be between 4 and 10, inclusive.
-S will be between 8 and 12, inclusive.
-D will be between 2 and 4, inclusive.
 

Examples

0)
    
seed = 1
N = 6
S = 11
D = 3
1)
    
seed = 2
N = 10
S = 8
D = 2
2)
    
seed = 3
N = 9
S = 9
D = 4
3)
    
seed = 4
N = 4
S = 10
D = 3
4)
    
seed = 5
N = 7
S = 10
D = 2
5)
    
seed = 6
N = 7
S = 9
D = 4
6)
    
seed = 7
N = 8
S = 10
D = 2
7)
    
seed = 8
N = 8
S = 12
D = 4
8)
    
seed = 9
N = 7
S = 8
D = 2
9)
    
seed = 10
N = 8
S = 8
D = 2

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)2010, TopCoder, Inc. All rights reserved.