JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: ColorLinker
Problem: ColorLinker

Problem Statement

    

Overview:

In this problem you're given an N by N grid, where each cell is either empty or colored in a certain color. Your task is to color some of the cells, so that each of the colors forms a single 4-connected region of cells. Since we don't have to restrict ourselves to real-world limitations, it is allowed to color the same cell into more than one color. In particular, it is allowed to color cells which are already colored in the initial grid.

Test case generation:

Unless specified otherwise, all random variables are sampled from uniform distribution.
  • N is randomly generated in [20, 60] range.
  • colorsSize is randomly generated in [2, 5] range.
  • coloredCellsSize is randomly generated in [N / 2 (integer division), 4 * N] range.
  • colorWeights is an array of doubles with a size of equal to colorsSize. Each element of the array is generated independently and it is equal to rand() * rand(), where rand() function generates a random double in [0.0, 1.0) range.
  • penalty is randomly generated in [N, 8 * N] range.

After all of the above variables are generated, we generate the grid. The grid is N by N and exactly coloredCellsSize cells are colored. The cells to be colored are chosen randomly. The color of each cell is determined independently and the probability that a given cell gets colored into a specific color is proportional to the element of colorWeights corresponding to that color. Please note that some colors may turn to be not used at all.

Implementation:

You need to implement link method that takes String[] grid and int penalty and returns a valid coloring. The grid is formatted as follows: each element describes one row of cells and each character describes a single cell. That means that grid[r][c] describes the cell at row r and column c. Empty cells are represented by '-' (dash) character and digits from '0' to '4' represent different colors.

You should return an array of integers. For each cell that you want to color, you have to return 3 integers (all 0-based) describing its row, column and color. More formally, if you want to color X cells, your return should contain 3 * X integers and elements 3 * k + 0, 3 * k + 1, 3 * k + 2, 0 <= k < X, must describe one of the colored cells. Remember that you can color one cell into many colors. In this case you need to include a separate triple for each of the colors you use for that cell. You are also required to include triples for the initially colored cells that are given to you in grid parameter.

Scoring:

Raw score for a test case is equal to the sum of scores for each cells. Score for each cell is equal to colors_used + colors_used * (colors_used - 1) * penalty, where colors_used is the number of colors used in that particular cell. If we fail to get your return value (time limit, memory limit, crash, etc.) or if it does not define a valid coloring, then your raw score for that test case will be 0.

In this contest we use relative scoring and your task is to minimize the score. This means that your score for each test will be equal to best score (lowest positive score among all of the competitors) divided by your score: normalizedScore = bestRawScore / rawScore. The small exception is, when your rawScore is 0 then your normalizedScore will also be 0. Your overall score will be equal to 1000000 * (the arithmetic average of your normalized scores for all test cases). This is the score you will see on the standings page.

Tools:

An offline tester/visualizer tool is available.

 

Definition

    
Class:ColorLinker
Method:link
Parameters:String[], int
Returns:int[]
Method signature:int[] link(String[] grid, int penalty)
(be sure your method is public)
    
 

Notes

-Formally, a set S of cells is 4-connected if: for any two cells A and B from S, there exists a path from A to B such all intermediate cells in the path also belong to S and any two consecutive cells in the path share a common side.
-The memory limit is 1024 MB and the time limit is 10 seconds (which includes only time spent in your code).
-There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-There are 10 example test cases and 100 full submission test cases.
 

Examples

0)
    
Seed = 1
Grid size = 60
Colors = 5
Penalty = 328
Grid =
-------------------------------------------------3---------2
--------------2---------------2-----------------------------
-----------------------------------0----------------------2-
------------------------------------------------2-----------
----------------2-------------------3----------------1------
-------------2-------------------------------------1--------
-----------------------------------------------------2------
3------------------------------2----------------------------
-3-------------0----2-------------------------2----2--------
--------------2---------------------0-----------------------
------------------------------------------------------------
-------------------1----------------------------------------
------------------------------------------------------------
---------3--------2-----------------------------------------
---------------------1--------------------------------------
1------------------3-----------2------------2---------------
------------------------------------------------------------
---------1--------------------------------------------------
------0-----------------------------------------------------
3----------------------------------------------------------0
--------1-2-------------------------------------------------
------------------------------------------------------------
--------1-------------3-------------------------------------
--------------------------------------------------2----3----
----------------------------------------------3-------------
------------------------------------------------------------
-----------------------------------1------------------------
------1-----------------------------------------------------
------------------------------------------------------3-----
---------------------------------------------2------------3-
------------------------------2-----------------------------
-----------------1-----------------------------2------------
----------------2---0---------------------------------------
------------------------------------------------------------
-------------------3---------2------------------------------
----------3-----------------------------------------2--1--0-
----------------1-----------------2-------------------------
--------------------------------------------------------2---
------------------0------------------------------3----------
-------------2----------------------------------------------
------------------------------------------------------------
------------------------------------------------------------
---------------------4------2-------1-----------------------
------------------------------------------------------------
---------------------------------------1--------------------
---------------------------2-------------------3------------
----------------------3-------------------------------------
-----------2---------------------------------------2--------
------------------------------------------------------------
------------------4----------------------------4-----1------
-------3-3-------0------------------------------------------
---------------------------------------1-------3------------
--------------0---------------------------------------------
---------------------2--------------------------------------
------------------------------------------------------------
------------------------------------------------------------
------------0-----------------------------------------------
---------------------------------------------------1--------
------------------------3-----------------------------------
---------------------22-------------------------------------
1)
    
Seed = 2
Grid size = 34
Colors = 4
Penalty = 131
Grid =
--------------------1-------------
------------2---------------------
----------------------------------
------2---------------------------
-2--------------------------------
----------------------------------
---------------------------2------
------------1------------------2--
1--------------------1-----------1
----------------------------------
----------------------------------
----------------------------------
-----------1-----------------1----
----------------------------------
----------------------------------
--1----------------------1--------
-------------------------2--------
----------------------------------
----------------------------------
----------------------------------
---------------1------------------
------1---------------------------
-1--1-----------------------------
----------------------------------
----------------------------------
-------------1--------------------
------------------------------1---
---------------------2------------
------------------1---------------
------------1---------------------
----------------------------------
----------------------------------
----------------------------------
------------------1-----1---------
2)
    
Seed = 3
Grid size = 28
Colors = 3
Penalty = 102
Grid =
--1----1---2---------1--1---
---------2---1--2------1----
-1----1---------------------
-----------2----21-0----1---
---------------212-----21---
--------------1-------------
------------------22--------
---2-----1---------------2--
------2---------------1-----
-----------------1-2--------
-------------------1---1--1-
---------21------------11---
--------1----1-----1--------
----------------------------
-----2--------1-------2-----
--------2----1-----------2--
--1------2-------1----------
--2----------1-------2-2--2-
---2---1-------------------1
---------11-2--------------1
-----1----1-1--------------1
--2---------------------2-1-
----------11-----2-2--------
----------1-------------2---
--0------------2----1--2----
0-----------0-0-----1-------
-1------0--0-------1------1-
---1-----1----1-211-----2---
3)
    
Seed = 4
Grid size = 31
Colors = 3
Penalty = 58
Grid =
------------------------1------
-------------------------------
-1-1---------------------------
--1-----------------1----------
----2--------------------------
-----------------------1-------
---0----------1----------------
-0--1------2-----2-------------
-------------11--0--1---------1
----0-1---------1--------------
-------1-----------------------
---1------------------------0--
-----------1-0-1---------------
----------------------------0--
----------1----------------1--2
-------0------------------1----
-------------1-----------------
---0--------------1------------
------------1-1---1------------
-----------------------------1-
-0--------------0-------1------
-1-1-----1---------2-----------
2-1----1-1---0-----------------
----------------0--------------
--------------------------1----
--0------------------------1-1-
----------------------1-------1
---------------------1------1--
--------0----------------------
-0---2--1--1------1-------1----
-------------------------------
4)
    
Seed = 5
Grid size = 49
Colors = 2
Penalty = 292
Grid =
-------------------------------------------------
-------------------------------------------------
-------------------1-----------------------------
-------------------------------------------------
------------------------------------------1------
-------------------------------------------------
-------------------------------------------------
-------------------------------------------------
-------------------------------------------------
--------------------------1----------------------
--------------------1----------------------------
-------------------------------------------------
-------------------------------------------------
-1-----------------------------------------0-1--1
------------------1------------------------------
-1-----------------------------------------------
--1-----------------------------1----------------
-------------------------------------------------
------------------1------------------------------
----1--------------------------------------------
----------------------------------1--------------
-------------------------------------------------
----------------------------------------1-----1--
---1---------------------------------------------
-----------------------------------------------1-
-------1-------1---------------------------------
-------------------------------------------------
-------------------------------------------------
-------------------------------------------------
-------------------------------------------------
-------------------------------------------------
--------1----------------------------------------
-------------------------------------------------
-----------------------1-------------------------
-------------------------------------------------
-------------------------------------------------
----------------1--------------------------------
-------------------------------1-----------------
-----1-------------------------------------------
------------------------------------------------1
-------------------------------------------------
-------------------------------------------------
-------------------------------------------------
---------1---------------------------------------
-------------------------------------------------
-------------------------1------------------1----
-------------------------------------------------
1------------11--------1-------------------------
------------------------------------------11-----
5)
    
Seed = 6
Grid size = 53
Colors = 2
Penalty = 266
Grid =
0----------------------------------------------------
-----------------------------------------------------
1----------------------------0-----------------------
-----0-----0-0------------------------------------0--
--0-----------------------------------0-----0--------
---------------01--0---------------------------------
----------------------------------------------0------
----------0--------------0----------------1----------
------------------0-----0----------------------------
-----------------0-----------------------------------
-----------------1-------------0---------------------
-1-0-----------------------------------0-------------
-----------------------------------------------------
------------------------------------1----------------
-----------------------------------------------------
--------------------------------0--------------------
------------1----------------------------------------
----------------------0---0--------------------------
--------------------------0--------------------------
---0----------------1--0--------------0--------------
-----------------------------------------------------
------------------1----------------------------------
-----------------0-----------------------------------
---------------------------------------1------------1
-----------1---------------------0--------------0----
---------------0-------------0-------------------1---
-----0---------1----------------------01-------------
-----------------------------------------------------
----------------------------0----------0-------------
--------------------------0---------0----------------
-----------1----------------------------------------0
----------------------1---0--------------------------
----------------------0------------------------------
----------------------1-------------------0----------
---------------------------------------------------0-
-------------------1---------0-----------------------
------------------------------------0--------------10
-----------------------------------1-----------------
--------------------------------0--------------------
---------1-------------------------------------------
----------------------------1----------------------0-
---11----0---------------------------0-------0-0-----
-----------------------------------0-----------------
---------0------------------1------------0---------0-
---------0-------------------------------------------
--------------0---------1----------------------------
--------------------------------0--------------------
----------------------------------0-0----------------
--0--------------------------------------------------
-----------------------------------------------------
----1---------00---------------------1---------------
---------------------------------------------------0-
---------------0-------------------------------------
6)
    
Seed = 7
Grid size = 24
Colors = 5
Penalty = 83
Grid =
0------4------------4-40
--------3-4------4------
-------1-4-----4----3---
4-----------------43----
-4--------1-------------
---------------4-------1
-----------------4-----1
---------3-3-4---1------
--------4--4------1-----
----4----------4--------
-1-----------4----------
---4-----3---------4----
--3-----------3-11--4---
----------------------4-
--------------4---------
--1--0------------------
------------------------
---4----------4---------
-----1------------------
---------3-1--------0---
--4---------------3-11--
----34---------------4--
----4-------------------
--1-----------------3---
7)
    
Seed = 8
Grid size = 37
Colors = 4
Penalty = 115
Grid =
---------------002-------------------
--2-0-----------------2---2------2---
-------12---02--2----------------22--
-------------------------------------
------2--------------2-2-------------
---------------------------2---------
---------2----------02-----3----0----
---2---------2-----3------2--2-------
-------------------------------------
--------1--------------2-------1-----
-1------0------------2----2-2--------
----2-------------------1------------
--2------2--------1-2--------2-------
---------0---------------------------
1--2----3-2----2----------2----------
0-------2-------------2------3-------
------0---1-2---2--------------02--0-
----0-------------------------2-2--2-
-----------------------2-------------
-2--------2------22-2----------------
---2---------------------------------
-------------0----2----------2-------
-------------------------------------
-------------------------------------
-----------------2-----------12-2----
--------------------------2----------
22----0----------------1--2----------
----------------2-------1-------0--2-
-2--------------2-----------1-23-----
-----------------------------3-------
----------------3--2--------2---2----
------2----2-----2--------2---------2
--2----------------2----------------1
---------2---2-----------------------
---------022---------2--------------2
-----------------------2-2----2------
-----0--------22------2--2-----------
8)
    
Seed = 9
Grid size = 40
Colors = 2
Penalty = 172
Grid =
------------0--------------------0------
-----------------------------0----------
---------0----------------1-------------
----0-----------------1-------0---------
---------------------1---------------0--
-----------------------------0----------
----------------------------------------
----------------0-----------------------
-----------------------------------0----
----------------------------------------
----------------------------------------
-------------------------------0-----0--
---------------0-1----------------------
--------------0-------------------------
-----------0-------0--------------------
----------------------------------------
----------------1------------------0----
-------0----------------------------0---
-------------------0--------------------
---------------------0----0-------------
-0------------------------0-------------
----------------------------------------
-----------------------0----------------
----------------------------------------
---------0---------------0---0-0--------
---------------------------------------0
-----------0-------------------------0--
----------------------------------------
---0--------------------------0---------
------------------------------------0---
----------------------------------------
---0------------------------------------
-----------------------------0----------
----------------------------------------
------------------------------------0---
----------------------------------------
----------------------------------------
----------------------------------------
--------------0-------------------------
----------------------------------------
9)
    
Seed = 10
Grid size = 35
Colors = 2
Penalty = 57
Grid =
--------10-------1-----------------
1----------------------------------
----------------------------1------
----------------11-----------------
-1-------1-------------------------
------------------------------11---
----------11----------1------------
---------------------------1-------
-----------------------------------
-----------------------------------
---1-------------------------------
----------1------------------------
----------------------1-----------1
1----------------------------------
-------------1---------------------
-----------1-----11-1--------------
-------------------------1---------
--1------------------1-------------
------1----------------------------
-----------------------------------
-----------------11-1-----1--------
-----------------0----------1-1----
--------------------1--------------
-------------------1----------1----
-----------------1-----------1-----
----------------------------1------
---------1-------------------------
-----1-----------------------------
-----------------------------1-----
---00----------1--1----------------
----------------------1------------
--------------------------------1--
----------------------------------1
---------------------1-------------
-----------------1---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)2010, TopCoder, Inc. All rights reserved.