JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 62
Problem: CellularAutomaton

Problem Statement

    In this problem you will be exploring the evolution of cellular automaton depending on its initial configuration. The cellular automaton consists of a two-dimensional rectangular grid of cells and a rules string. Each cell of the grid can exist in one of two states: live or dead.



The evolution of the automaton happens step-by-step in the following way. On each step, for each cell we calculate the number L of live cells which are adjacent to it (vertically, horizontally or diagonally). The cells of leftmost and rightmost columns are considered to be adjacent, as well as cells of topmost and bottommost rows. Once L is calculated, the state of the cell changes accordingly to the L-th element of the rules:
  • if it is '=', the state of the cell doesn't change;
  • if it is '-'('+'), the cell becomes dead (live) regardless of its previous state;
  • if it is 'X', the state of cell changes to its opposite.
Thus, the rules string for Conway's Game of Life is "--=+-----". All cells change their states simultaneously, so for each cell the number of live neighbors is calculated before any changes are performed.



Your task is: given the rules string of the automaton and its initial configuration, change the states of some cells to obtain a new initial configuration so that the quantity of live cells after a certain number of iterations is maximized.

Implementation Details

Your code should implement one method configure(String[] grid, String rules, int N, int K). grid gives you the initial configuration of the grid: grid[i][j] is the state of cell in row i and column j and is '1' (one) for live or '0' (zero) for dead. rules is the string of automata rules, N is the number of cells that can be changed and K is the number of evolution steps that will be done.



You have to return a String[] of same dimensions as grid which contains new initial configuration of the automaton (with states of at most N cells changed).

Scoring

Your score for a test case is calculated as number of live cells after K iterations (starting with the configuration you've returned), divided by the total number of cells on the grid. Your overall score is a sum of individual scores over all test cases. Invalid return of any kind (invalid dimensions of grid, character other than '0' and '1', changing states of more than N cells etc.) results in zero score for that test case.

Tools

A visualization tool is provided for offline testing. It also allows manual play as well as manual fixing of your program's return.
 

Definition

    
Class:CellularAutomaton
Method:configure
Parameters:String[], String, int, int
Returns:String[]
Method signature:String[] configure(String[] grid, String rules, int N, int K)
(be sure your method is public)
    
 

Notes

-Parameters R, C, N and K are chosen randomly and uniformly (except for the first test case). All cells of grid are generated independently, the probability of a cell being live is chosen as a parameter as 0.3..0.7. The rules are generated as follows: first two and last two characters are set to '-', the rest of characters are chosen randomly with equal probabilities.
-The memory limit is 1024 MB and the time limit is 10 seconds per test case (which includes only time spent in your code). There is no explicit code size limit.
-There are 10 example test cases and 100 full submission test cases.
 

Constraints

-The numbers of rows R and columns C in grid will be between 10 and 100, inclusive.
-N will be between 5 and (R*C)/16, inclusive (integer division used).
-K will be between 2 and 20, inclusive.
-Your return must have the same dimensions as grid and differ from it in at most N characters.
 

Examples

0)
    
seed = 1
R = 12
C = 12
rules = --=+-----
N = 9
K = 2
1)
    
seed = 2
R = 23
C = 50
rules = ----X=X--
N = 23
K = 11
2)
    
seed = 3
R = 99
C = 29
rules = --X+X=X--
N = 28
K = 6
3)
    
seed = 4
R = 52
C = 83
rules = ----+-X--
N = 124
K = 14
4)
    
seed = 5
R = 83
C = 59
rules = --X=+X---
N = 92
K = 5
5)
    
seed = 6
R = 34
C = 36
rules = --X++++--
N = 40
K = 13
6)
    
seed = 7
R = 98
C = 54
rules = --+--X+--
N = 292
K = 17
7)
    
seed = 8
R = 49
C = 30
rules = --XX=----
N = 90
K = 6
8)
    
seed = 9
R = 55
C = 74
rules = --=-+-X--
N = 197
K = 5
9)
    
seed = 10
R = 84
C = 41
rules = --=XX==--
N = 179
K = 8

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.