JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 78
Problem: FixTheFence

Problem Statement

    

Fences (also known as Slitherlink) is a classic type of diagram puzzles.

The rules of Fences are as follows:

  • You're given a rectangular grid of lattice points.
  • Your task is to create a loop. The loop consists of segments connecting the neighboring points and those segments can only go vertically or horizontally.
  • Some of the cells (squares formed by 4 neighboring points) can contain numbers. Each number represents the amount of loop's segments that must touch this number.
  • The loop cannot cross or touch itself - this means that you cannot visit the same point twice.

In this problem your task is to create a program that gets a fences puzzle as an input and finds a valid loop that satisfies as many clues (numbers) as possible. Please note that those puzzles are most probably not valid. This means that in most cases it won't be possible to satisfy all of the numbers and even if it's possible, most likely there will be several ways of doing it.

Test case generation:

  • size is randomly generated in [15, 100] range.
  • fillRatio is randomly generated in [0.1, 1.0) range.
  • weights[4] array is created as 4 independent random numbers. The weights for numbers 0, 1 and 2 are in [0.0, 1.0) range, and the weight for number 3 is in [0.0, 0.5) range.
  • size x size diagram is generated as follows. The probability that a cell contains a number is fillRatio. If a cell contains a number then it's chosen as 0, 1, 2 or 3, where the probability of choosing number X is proportional to weights[X].
  • In a rare case, where the generated diagram contains no numbers, the whole process is restarted from scratch.

Implementation and Scoring:

You have to implement findLoop method, that takes a String[] diagram and returns a valid loop as a String. The diagram is formatted as follows. Each element describes one row of cells. And each character in a row describes one cell. That means that diagram[r][c] describes the cell at row r and column c. Empty cells are represented by "-" (dash) character and numbers are represented by "0", "1", "2" and "3".

Your return value should be formatted as "Row Column Loop". Row and Column describe the 0-indexed position of some lattice point on your loop, where (0, 0) corresponds to the upper-left corner. Loop should describe the path that traverses your loop around (in any direction) starting from (Row, Column) point. Loop should be a string that consists only of "U", "D", "L" and "R" characters, which stand for Up, Down, Left and Right. Since the task is to find a closed loop, your path should end in the same place where it started.

Raw score for each test case is simply the number of correct (satisfied) clues divided by the total number of clues. This is the score you will see in the example submission and in the visualizer. If your return was invalid or you exceeded time limit then your raw score for that test case is 0.

In this contest we are using relative scoring. This means that your score for each test case will be divided by the current best solution for this test case (among all competitors). So normalizedScore = rawScore / bestRawScore. 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

The offline tester/visualizer is available. You can use it to test your solution locally.

 

Definition

    
Class:FixTheFence
Method:findLoop
Parameters:String[]
Returns:String
Method signature:String findLoop(String[] diagram)
(be sure your method is public)
    
 

Notes

-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.
-By default all random variables are generated from uniform distribution.
 

Examples

0)
    
Seed = 1
Diagram size = 77
Diagram =
3--------01-2-3-011-0311-00--3-20--213032110--2-2-00---0-230-0--1023230-12033
-10-221--23332303--0-3103-12-11--12--022-2--3-3223-221-0-2-2210--00202-3310--
10-----233----010--0-0011---32-003313-3-122----3-22-1--002013321-2-3-1-010--1
---0-33-2300210---130-13-233---21-11-22--31-200-0-2-11-3-3--1-2---3--1--02131
--1-3-3233--230-310002-22-0-32-3030021--332-2331-30-2203-2232-1--30-01-33---0
30223--20--323-12313-02-20-3--2202-1-11--1-1-32330-00-2--1--3-2--320--31321-1
02-102--2332132-322-3----3000-20-2-3003---02233--21--0--13-203-0112-30-1-13-1
1201---2033-3220-1-3-11-3-0-3---0--02001--3-0112-1------03001--02-330--111-00
20021-2-2-1-12-3-----0----3--1103-2022-01-133013032-0--300--213--0--2-31231-0
--1230--2130020-0-1231-333-1-3-----0--00-0-21-2-10-11012213230021-01-3-023233
-3--3---0-3311------1-100-23-0312-1--1-2202-0----311-2----32-1-110012--3-----
0----2--2-0-30-23-----03-320-3-1--31-1313223--13-31--012--3231-01---2-231-11-
-3---3211333130-212--213-1-022103102---0123-12213232-300-020-2--31122202201--
-0321---22-2-1000-322-3-00-0-232-20131---231-02213130130----002-0222001-03-0-
-0-33203----103-21012---0--20--2012-2-1023-30330-3--1---02--30-1003-2--0-20--
103-2-0-02122-2-22310-23023013120-203-0--203131-0013----10-1-13-21----3-3221-
-000-1--0-3--2-0-003-23103-0-313---02-12233--232-2000--3---22-3---1-2---3031-
30-2-32113-0130-21-3--02---1-23-0--211---2--3-02--303-323030-1211--3-11-1222-
23202----1--0-1-0-3----00--323030-33---00300-1-10-02-1-3-033-3133-03-3-001--3
0033-3001---312-02033202---120330-1--0-2--0323-000-232103-0-2033-2322--2---32
-13322121------232033-0-1312--101--10--12323012002-23331-201--200-120--32--11
0-10-1213303-1233-21332331-3----0-0120-11-3101313-20-0--12300222-23-13-0--120
-12202-1----120-0-30-23-2---1-2-2---0-11---30232-1-0--1110-30-13--1-3--021121
--02-10---0203-3111--0--23132123-01-1120-300-3-1103-0-022-00----2101-0---0--2
--333232-3--03013--1000-1003220-22-01-001331-0--33-02-22-1-0-2-13011030--3303
3-01-22223--31233----1-3-3--03-1-3003--3-01--3-1103-20----0-12-03---2-2-0-31-
31----3--2133212-03-0-2-2-3-33-021-213-3---3--3---0333-3-232-0----23-33--110-
-----0-03233-02-0020-1-032-3-3---021---321-3101-20002-103-32-3-230-2320-0-2-3
3-11---012--33-1--03112--20201-01--1313---3--------33311-0-----22---3-0-20--3
---02-0320-0-1-0322-00-1-20----2--2-001--332-0---2-31-10-13-3-2-0--22--0--133
23-32-3210-1-20-2---0--22-1123-00--32020-1-1-1-233-3323-002-1-2--2-0--20-2--0
31--21-3--3-0033110102-----3-10--03302-0---22-10-0------1330301-2-23-30-230--
220-3-2030032021333-12132-3312--1---0-213---22-2-10--2-0--0-03-2-222113-13-2-
2-222-2-2303333-33-03-23--0-2-3123--32322010320-30011--3--220210--3-1131313--
3---3-22--012-------1-0--32---32000033-10-10---013--0---22-02012133---2022---
-3-2-001--20333-3-1-1-31---0-0-30-2-----001-001-32-20---103---1-030-11-----1-
03-3-1-0--2032--1-13100-20133-23-21-023-0-133001-33-1-22-32-1-23-0131321333--
03-22--00-3-111--10-011-0233130-3--212-321----3311-0--31-1-1-3-0020--3330-131
--0-20-0---0132--302-2----03113013-231-0--23-01011322-02-00-----322-3301-3--0
202--2-2020-----30-02---30000310223----1-30030---33-1--203313-3---03-01300131
1012--021--01-0--23-----3-233--------23---232--1-3-3333-1-2-2-23-33--010-3---
-222-33-30-232--3300------2-2213-1---32-2-10-2-13--200110--13-2-0-32-2-1---2-
3--3--2033---33-21--1--1-13131-30030-33-01-3013----1--3-23-3303233222-232----
-1-2--------3-0-0-03---2---0--2-3-2233-1-----0-322--211--20--11211-130-32-031
1001-1310-232103-0002-01002-2231-113--33--2---320203-0-32--3--302101-1-1-3-33
23032-0012--10---2-2032-02--23-13--3--012-2--2-11--00--0-1033--3-11003--0---2
2-123---13--3---3--0313--2---213-02-113-223121--22023--0-02002-0-1--2-0-2102-
0---3-30--323-032001-3--313-102002-21-1--3--3--2122001-13-3-3-331-23--2-333--
0-3-0-1201-02--331002233-133-21-02-2-2-11----302102-2032-32--21-20-11-1--3003
-13-3--0----21-1-13-0-12321-0-0--00-03--13-1-1203-1302-3-0300--033-2--33--10-
1010-3-32----1-2300-20-1--1--00332-033-30----2-12020111210201-0-3--3-0-210--2
--133-1-13003-233112---0--3---2-10220-0233-0122-030-----0-000-130--23-2310222
-302-3222-1-301-3---30-2-1-0-2-1122031---1-323-023-00--03--03-2-331113-0-1301
1320013002---00-33-21-12-031323102-0030311102---0-030-0-000-102-2-1223-123-11
03-0-23-1-100-12-0-2--201232--3-3-31-3-32--1--11303-20--0---0231---3113-2-02-
2-0-23-3-2-1-2--3-21-331-0-121-111000---31--000233203---30213-301100-01033310
3--2202-1-1-332-321-31-1-310-3311--3-3321-1303-1--30---03-23-0330--1--2-23220
-10-132-2322323200-23-3---22--3211-3-03-0-32-3-3-1-03-0---03-103-23-2300--2-3
03-20011103130--2-202--02323-0-1-3220--3203--3-03-2-301--00110-1---2-3-132030
-2---30-123--313-23-33-210-02-0-0--212331--30130230223--21--23----1202131--3-
3-2313-1---0-3---32-0-11------22-00-3-31--2--31-000--0-2---02022--233-1-31221
2110-1-33-03202210001332-1-21312-12-223---20-02332-3111-030-11131101201-2--32
-1-0-10-033-13303-202023----0223-131-1---13--3-23---1----0210-3---020-1213--1
3-0--3020---01-10-0013-0-0-3--2-000--0--222-33--2201-200300-00-0-0-0323-33-30
--213--332-203-222---23-003-01-2-33202-0--1----0-10--1--111-2201--321--02-0--
020330-1-2131-1--311-010-2---03213113--2-2-30-30-2302-01-33-3-3310221----3---
---2-01--11-2-20---233330-1-2--22-3----31-2-330112322113320-23-2---2-233-1--2
3--01-2-3-22-0232213---02-3-31-2100300-1323313-31-0-3--30-30-0-3-3-31-321-010
02-02-3-2-0--30321--30--010221-3011320--032-111-323--12302302000013130----231
202-31---1-00---1-20-20--31-33-3--030-10332----33-2300133221-3-3-01203331102-
11031-23-0030-3--2-32--320-1--0-30-13-202-0332-33--320-0---03-0-330321-----20
--12-----230-020--03-12-0-0-30-3123-032012---0---023----01033-1300-23110200--
-1003-3-1030-23-20112-1-33-232-1301-231---100-200-1-3002---001-2300-3-3233-33
-020102-0-0103-21--32323-002--01-0--303032233-02221---20-3-31-0-2-131-21--0--
3330-03030--00--3-03--300-2303103-2---2-20331-2-1--231--303022--32----30-110-
330-2130---21---3100223--3--333--1302-13--21303-311013-0-0-333-3----12-0---23
23010-1-10301-13013--33130333--31110-23001-2--101-221---3---32231--2-1-2-2013
1)
    
Seed = 2
Diagram size = 28
Diagram =
12-----231--12--1232----2---
2222----2-3-2122--1132-221-2
2---1-3-32-11-112-11----22-2
-21--2--0---2-1---12-0----2-
12--3132-----2-22-0--221-21-
232-1-1-----21-2--22121--3--
2-11-1-11-1-222-3-102---1-21
-22-1---3-12---22-1-3--121--
32332-22-1-2--2------1-----1
1-1212---2-1-2122-12--132122
--2-12-01-2-2--1-2--2--21---
-2-1232-----2-1---2-22-23-2-
22---2-10-122--0-31----1--22
-1-0-2211------12--2---12--1
21222-2----1--1---02-2---111
-3--1--12-2--13---1222-22211
2-22-2--11-2-3--112-----2---
2131-2122--22-21-21----21---
-1-2--1-----2-1---12----2-13
1---3-2--2-222121--2---1---3
221-2--12-1---2-2--2-----1--
-2---2112-32-11-21---13-2--1
-2112-2--312-2--22-2--11122-
--22--212-11222-2-12222-2-11
1---2221--------3-12--2-1---
-2--121-232--23231-21122211-
1--23----2332--21-1----1-2--
3---2122-1--1-222222---21--1
2)
    
Seed = 3
Diagram size = 67
Diagram =
203-13232122221113-332111-2231-2212230-22331112120212212--202332-22
-221--1-0-2322112--3220222-202322322120-22132122-0222103-012222111-
1022-11--2302-111033331210122-31-11-1-12112-3-22-2213033-2331121221
32202032-333322112-023-22-1312332211-1222--232213312212-21101332231
-3120-33-22313321-3211-13120-32131221321321132-3-32211213--21122121
02103-12-0-212211311221121223220-2--23-12--20301-2212-002313223-221
-322221212-33133123-202-321211-12223321233312102322113123-322-032-2
1-31023-3-2-32-22222-3210221-21211011113120132-1222222220221121---2
123-2-33-30211121321113132132222032232223-3222-1--222322-22020-1212
121111--32-3301-0-3221202232212022--32221222--32331-2133-3201122--2
222020-22-2221-122211332---22-2232211-111213223-31213122-2233-02113
22--3221231202121-233-3-1213211231222-2222-312112132132120221-21121
13-31-231-2--02210321033-32-1103-0-1212013332212022-3323-22311321-0
111-2-11231121122--2-3-230-32110232222122-2232233-233-113-212211202
221213212032-332-2-322-222-2231222321322123121-0231111312-121203-22
11-131-323-222123-11322-221--2-223100312120-322-01-11023233123-1202
21211321222-11-1-313121122231332--212--3131321-23122332222232232312
3131112232-221213332220311-12-220111111220232-11-1232222002121--121
21122321-102322-1-1032-203-2111123320211-2212-0122-1-32-1--12231302
1-322222-22222111103-222-221--1-21---233112-3101322133223312-21-212
1--2231023102-3203-2222-32-22221201112-1-1--2122122112--22232232--2
21-231222202-2221--022--111-23322122123112321310-222223111222221023
22212231121-1030-11211033321212--2112-32-2232-3211-222122113-311112
131322221321202-1--0302312-13312212212-21221231122-122211122210-222
-0111011-22213232213331203-22-32321112-21-133--333132202-32-21-2-3-
3113122-21-22222021-32-3-221322201-1112302313-2123---33312022233-01
2221211212223132312211-12-222-3133331-221212212--2021-32321-1232--1
11122121223211213231-321-132131221111111302222012122333312-2210212-
213332-323-11111-1232312232213-222231121-2-212-2213-031331-222-1-22
211120--11-223311232231323222123121112323-11--2-221212-2-322--013--
22122-022221220222210-322112221--3-1--313332--01--1-13-23212131133-
-332-31223321321122322110021-22123222--222-011112212-21223---12-202
2222-12-00-1-12-12330111-22313221220102213321211--31132232322303112
2113212-00-122-1-2233223302320-02223222--13121-22-2221-1--3-2311232
3311-13--1221121-3222-112121221-3121332221-33121322-221312231223323
-2-2313-3-22332211122-113-21-1-20-32223131322---311222-321301331213
322221022202023-2220-121212321--2213-1322--33--22-211--322-32--2222
312122-1-23-22-131031122113022213-122222--2310223312332112322232212
2-202223-211-2-32-322-1110-1-111202121312233222-230--3-31333222-132
2-2221222-32-2031121222-22202-2-311-12202----1-1103121122-3313-3231
132121321030231223--222222202-11-322-3222220232120302322122212-2112
212211-211-102221-111323-212221223222-21222103132323112013122-22--0
11212312131222-1233233222--3233132123210-222-31--322-312122-22-1321
1232122-21-2331--221321313231--212212-30222220222-1-23212233-122122
122-1222222112-1111322232-22322--1-2-31---31-230222311212-22112-331
021113031211032222132222302120211012-122-023221221231-22-232112-130
-222-2212312-3-222--212221321322020--3-22122122031232-122-021--3113
12-222-101-212-2221322-2-2-21323123-0-01233222332-33-3-121322---31-
23133-230-212-12-121100112312223212--32---1103-12211222211--02-3121
2323-23--10331332-23223-2132323-112--01232-022232--22312-1-332-2202
32--10021221123321221-0023101-21323-23-2-003320-100121-03321302332-
-1311023321-131--0-0212323-122---2313123-112-2331-3-2111223-2011--1
321-122-211-23332223-132222-123231311023--1212213012221112312332330
232-002122-1-3-2-113223332022-2-2-11-2-202-23133213222123332102-121
-1-221310232221-31-121211-223-123120-2233-231102-110222121223132302
-1223221--21121-21231322321213132-1-11202232323212-22-3212221313-32
2-02-212-1132221-2-2-1323122-0213133221322221211-3-22231231302-3222
-2321--302-2--2331223213-3-3222132-3-122-10---1-11211-3-3333-312221
111121012133-21332231222--112122213121133-0-2221322222122322222212-
32312-23122-112-2-12--1121-013221123322123223222-2-20212-23112232-3
13221130212-33211233--021123--2223223112-22212012-2-2-1-131--13-12-
2-1132122223112-121133112-3213--32002323032323033121021122230-321-1
0-3-3121232121113-3-332222-1-123323232-213133303311-33-211333220331
11231111022--223121-21202-31322-23-3--12120-22-22110-23322202111122
23132-0312-22--1233222112232321-2223-10-31332-1----1121112232-22131
21--3--2-321213-31231122-2113122120223-21202212123-22122-2-2212212-
22311013-321032110323-3-122231122202-1-22112-1322-222121222321-233-
3)
    
Seed = 4
Diagram size = 47
Diagram =
1110-13311-13-01113113231313-1-3002132303033333
1121312121-312330122111103332-11131312110113-33
3-3-1321113232031--311-33123013--1--0-2121-2-11
1012233131112310312313332331-1311312--1-1--0301
3311121-1-233122110313321002211010---011303--22
0312-31111131233211-32111-231022123-13113311011
1011131112123111301-121-3121033300320-12133212-
130312033311310111122-300311210321201-333110011
-323311301331131011032011133-11-210123-31301313
113113-121313313-33-131-0-12133211-211132133-10
331303013113113-3330333331333013-311013-3110312
33-00312311111331303021131123011120131301233033
201323231313133013001212333-232103-303213333130
3013-13121113113333123331-21-30103-320022111333
13012-2133121123112111311-22113233-32111-11-133
1312033332-101222--3-3331313211133011131132-202
2133-01013-3-133-333131113-310011112312231301-1
-1--33031-13203310101313030-1311233131303231-23
13-1322333010233-003301111011203333311-30330-1-
112233331131302103020-1-311-3002113313113010103
311--120131023-3322312030-1-3003-231-0--3-31133
3311012203111011310311111213331-311310331011-32
3011-032-32113310111031123331113333311211313-33
3-230010131131333--111113-103-131213311-3003133
3-2--2021331310211132232221323233131013103-23-1
1111333311323-03301-111-223312311-333331-110101
320-33110111113123133213--301-1001101-2110113-1
11031130320302002131-303222113-133123-113333-11
3210-03323-13100-3133110--3321-233131-3212133-1
0200311-23-1313111323113221313131110120311-0301
3333200131312-133123-3-230133210202133103111331
113-33331003111-10310331111-131-13330111-132100
21103213030131111201111112113-12-330200011-1--3
-321321-33113010133110-11133-332333-2-113111322
11313322333-33331113321113311--3-0--10132--1013
12331301000321-302-33031-311010210312-130313-31
3233323113-323120313-1311-0120331311123311-331-
-32110-131313131332-32-2-3311131-131--1-3201203
031131-111-1031131011013332-13313-22213233-130-
-13310-311133-2213-3111113-12-2312003121-23-011
313330303333311131-112-31-31112-112323101331111
322-13231301-022122112121323331331133001-331311
2-02-13211333-13-3021132-122311-130-131323131-1
03131-2-133301-1313121331121133-31133231133013-
1-103311232103-110-132312033011-33233330033133-
11110303231223-1-33311133333013-113202310302313
123111-33133-3231-11331130130331-33111101133032
4)
    
Seed = 5
Diagram size = 17
Diagram =
1--321-21----12-1
-21-23--3-2--1---
-2-------12---213
323-1111--31---33
----1--01--2121--
322-13-0-1-12-1--
1--123322--1-2-2-
21-33-1-32-3--22-
-2---1131-2---3--
1--3-----3-2---22
---2-1--231-3-213
-11-21---2-3121--
2-2-22-2------33-
-21-12-2----1-2--
2--0-1---1-21--2-
----1-12111-22122
12-2---30-2-13-1-
5)
    
Seed = 6
Diagram size = 59
Diagram =
122202100102000002220000101-12221001000003221223012-0110331
12000110020-0112010222110020213223120010-220001000301000010
22021200231102022200220212210-030030000022-222222102-200022
0-202112120022200220002202100022010202222000211212001200301
20001010001200003000023201221202032022121002001300310021320
03032000231010211000211200200-00001110120220210122223003211
30201132301100020102220000020122220212031221201302001112020
30210-01012200002103012320-123222002000-0201000010210000020
200220122001200200223110100000112112221-0021221132202321010
02001101200110230010210-12033200033321021022300222011100201
00012020102200302100221011-002001200010201001-2103220120210
002210021200010210100010102000222021102301200220002221-1121
100020200101200120121002002110022222022-0010022111221001201
12223102222001003000012221000010112010021012200300031203102
03103022000112302200220100020230001202111201022210022101020
21032110110211200130032220122121200013110100121010102001000
021221321230111100203321020020022121-2011222000002222120120
00222122003210021322112220001100222212003112000022020020020
20120211221100200001221020113010021022111020000233022201020
0-220020301201120220112220000030120002201021200202100201313
130-12030321100-220000000302-0000101000120003202002-3000202
11002012221111222030121000220002131201222001210120102220200
0111000120020002-021001220110210220202220120110020120030000
203310032030020210200113202021213001010200200200200-0000120
00021200012211211211030121101112121031122012100100012122300
10020222221311100020101100002100032000020032210102122112012
0001002020021120002-30022122102201021230-2-0311002200011021
11000200010002223002231212212100111211210022210310020121222
21020122212012031210020222-2021300321020230001-033000020000
00000102020-222322230212-0200300023020020012102111000023200
102101-0122112210010021120021302010200202023200000101011020
021010001-0202012201212220110033123232100020220100100220200
21112111000212201122010-1000221110000110101100-101000100232
011132021112001-0000210000011002201021201221220213000311100
20221211200002002100100011012001001001200232200000121020032
222200000102021102001012023211301011100020021212-1-002021-0
02-21000112000200221020201222111000112021021002011220122230
32222002000000132002002010-1223220000-202030200012102-10130
210200-0120000000220002002-10001200010222220020011211102310
03120203222110100020310020222320010100222121021221200-23201
10022011111102222100121000001220120021322102000101202020020
01222221012000121100220020102-00012020100211000000310002000
00200-2302301-001020021010020020010200010020200022000101222
02020221100110311212132120203200021000231002322032-21000200
2002212000012-023100010120102030030200010002102320121200002
1021011-3021032012010001221112101200121000012200-2120032001
00-220222202002031002002200120211001003020302-1002200021003
-3021200002201021200201200300200102013231001010021022020120
12011303002100022200200210122-2000202101112312000202010320-
03202020120320000020200001010120022002023202120010202113101
20220210003202032-001201-0122202002000001001200210301020101
0010201221020202012111020-11201122-201120100121010210012310
01212-2220202010002201102212020211-102100113202022200203221
0000020022103322110122221120200030030222021002-102320220000
12311102201021120002012100020200100220200211120020-02001200
1222110303200220002211112022211010-100021001120022220202110
10211211301102023010122002002322121300230311222010210100121
02210002100002220202000233321033102021211022001200010101202
0211100200201101022222001200310222213-002221010220111101220
6)
    
Seed = 7
Diagram size = 29
Diagram =
-2-1--0--120---2---32----1---
-10--000----1--2--1-2----1322
0-----1--1----2-0-1-----2-133
1-121-1--12-2002----21-1--21-
2222---1-0-------0-----2--210
---2211-0-21----2-030-----231
1--2--1---3----12--20--------
2-------1---21-3----2-2---2--
-01--3-30--2--2---0-----220-0
20--3-222---2--0----2--0-1-11
--2--0--221-2---102220---22--
01-2-0-0-22--20--1--0--311---
------1-22-----11----121-1---
-1222--2---1--1-1-3-1-11-2112
-00-1----21-0-12---202--1300-
11-02--211-2--02-01-22--0221-
----12----1------02--211---2-
---1--0-202---21-----123-21-3
-20--30---1----122-----1---12
2----2----102-----1--20-11--1
-12--2011--1-1--22---2-32-2--
2-2-0--1-----202--0--11-2--1-
----------0--2----1--22--0---
--1012221-1211-21-2---1------
-021--------------1---1--122-
2-1---02-2---2-2112---110---2
----1--2-------21-221---3--2-
--0-2-23---221--1-1-01--1110-
1---2---13-12-2------1--12--2
7)
    
Seed = 8
Diagram size = 33
Diagram =
----0------------0-3--220-3-0--3-
0--------3----1-3-03-----130---22
3-10-0----1---1---010-------033--
-0-0-0--1----003110210--023--223-
-----1---0-0--132-0--3--210-21--1
0--1-0--0000-0-----0-3-1-0--0----
-2-123030000-003-----13-320-1----
0----0-1-3-30-0--2-000--03-2--00-
--0-2---33-2---0--210-3-002-1-000
--32-10-0--10-0----130--0------2-
-0-331301---0030-----0-2--01--01-
100-20-2-102----3012--0---002----
02230103---1-32-----0---03---32--
0--00120---2-2-1-130-0102032-21-1
-3-----0310--130020113----1-23-00
3--2--003--0--22---02--0--0-2-00-
--23--3-223--13-313-3-3--1-3-201-
--010---0----0---0-0--2-03-30-0--
-1--3-031-1-0-030-02-0-0--0-123--
----0--33003--00--0--000-3-------
---03030000--0-3-030-2-01-0-3----
0-0-2----3-30-3---0021--203-----3
---2-0--200-----200----0-3101-3--
0-2----2--00-----1-2-0-00-3-2--00
0100-00--1---3--00-----0130-3-002
----1-3-03----1-03--2--001-11--30
-3000-013---0------3-30----102201
--01--3-0-----01--3----01021-000-
31--3---20--3-1-2-------31-0----0
-3220----0--31-331-20---3-----031
2--0-----33--1-0-3-0-30-2--0-3---
--2-1--02---1--0000--0---1-------
---0101320---02000-0-0---032110-0
8)
    
Seed = 9
Diagram size = 41
Diagram =
1020-0-021-1-110-01--0110--1110011-222011
22-001-0312-111101110013120-00--01-1--103
03-3110012-0211---1221122-1----3--10011--
1-131-----1-101---2-000-111-1---101--2-11
10133020--1--101--10-1332001011--1201201-
131110-01-2-100-101231--0-1-0-012--100-20
-21131--320--2101-1-10--0001-100011-03013
112-011101213020121133101-11102-10-0-2101
11---0-0101-0000-2-1-21--201111-00---1-11
01-010121-2-1--101--31110--010-1121-3-1--
---21011300112111-0111300-1001-103001----
-20100010200010-1-0210000-0-0-0-02-103330
11-12011--21--0110--311-103--11011-00103-
113223--121-0-1--011111-10-0----0-11-010-
0110011--01-20-1--1-021301000-022-1001103
1120201203-0111---1-1--1312300-102021-230
110-00--11311--120-303300110--0111-0--1--
1013131021221123031--21---00010-10-103---
1231--301--300-0210331---031---1201-0--11
101-03111-1-00000-00--321--1---11102-12-0
11210-10--001111-011010--1211---00-0-2311
31--00000000-00-----22--1-11---2---3-1100
10-30-0-2-1-32-1-000132--0-31-01-21-2101-
11-000-100---31003132001101-11030--1-1-3-
--22101-211--0-0-00--01001-11-00--3-131--
-0--03-1-10--0-1-0-0232-3-0002220011110-2
00102--00-01-10-1021-01--1---100-1--10--1
210000--011--13123-221--10020110-03001111
1-01-0302--1--0321-1200--302-12-0-00-3110
0-10---10-11------03-00-1000-11-2-01-1-21
1---3-01-111-30-1-00002-2-103130-11-1-121
-0--1101231-121-00-101312--11----00301-10
0--00330-01113--13210111-000000012-1---01
10-21-0-10-1003011-30111010-1--2-20-1-3--
11-0011020-100-23---1-0100-1-00--111-0311
1100-1002---31-1-100-1-00-01-030-0-01310-
313--023-00113--03000--12--03202-130-31-1
30--1-111--3-121--013--10120213-3000-100-
1-010--2--31-11-1030-21---110-200-300-1--
32--1-1-10-00202-11200-1-012-110---01011-
--1-1001-01211-1---110013-02101---01-2111
9)
    
Seed = 10
Diagram size = 53
Diagram =
--11212--3-1-1--11-1--13201--1-2321-2-----------1-2-1
------2-----3-----22222-2-11---1-3--2-2----1--2-1222-
-----22--1----1-13------1-11--11-----1132-112-----2--
------1----2--13---222-----12---2-21--1--22-1-21----3
221-----1-----2------1---2-222---1-3-1--1--2-1---3--2
--311-1-2-13-03-12------3-1-1-3---31-2---2--1---2-2-2
22--0----122-----0--21--1-------1-----221--1---11---2
--1-11-112-1---------1-----10-23-12-2-1-1-2---01-2--2
-2--21---1--1--2--1---22-12-2----12--3---2----2122-2-
--1--1------2--22---------12---3--112--21-----2--1--2
---2-2---21---1--1-112--1--31------2-2-3----1-1--13-2
2--111--2---2-1------11--2--1-20--2-----11--2------22
--221--2----2---2------1-------22-2--1--21------111-1
----121-----21---3---2--3--1-1--------------1-2-----1
--221----2---1-1-1-1-----11-23--21--3-------1-----1--
------2---21------3-------22-213--2----113--1--11---2
-2--2----023------1--12----1---2-------3-3-----2-1-1-
3-----2------1-2------2-3-31--122---1---1---33-2----1
--1-1-3---3-2--2-2---1-2-------1-----2-2---1-2-------
---3-----12------12-----------1-----11222--------1---
11--21-2211---3---0-22----2-----231--2----11--2-11-2-
----2--0-1---21--2----21-3-----21---2-2-1--1-1112-1-2
--22----------2---1--2--2---2----3-----11-----2-2-1--
3-2-2-1112321332---------3------1----22------22--2--2
3-22---2---2--21--2-----3-1-12-1-1-2---1----3--1311-2
22--1-31--132--231---2---2---12111-1121-21----1-2----
1---2--23-11----------2-2-111----12-3-31------------2
-133----1--3-----3--2-1-------1-1-----1---------2---1
-12-2-12------1--121---311---1--2---1-------12--1----
2-23-----2111-2133----11--2---2-2--2-----1------2--2-
2--2----3---2-1----3---------1------1---1-----1---2--
---31-20-22-31-2------2---3--2---2---21--2--2--2-3-2-
----1-1---1---31--2---12---11-2-1-32--3------1---112-
------223-----------2-----2-3----2--12----231-2-2----
2-32---1-----2--1---2----2--1-----1------111---2-----
-------2-2------2--1--1-------1--1---11-2121--23---33
-2---2-1-2---3----11-1-2-33-2-2-2--1-23-2--2---3-2---
-2---------1--------2----23-3-3--12-1--313-1-----2--1
-1-221-----22---2-------3--111------1--13-------1-22-
2----1-1-----22-----2-----------2-21------21----212-1
--1---21------1-0--1---1-----13-221-----21-22-2---221
-2---1--1-2--2-----1--1------1-1-23--12------21---132
-212-----2-232--1--------21--2-----1----2--1-----222-
-2--3-1---112-21------1--12---1--------1-----1-22-22-
3-------1--2------3--1-2-32--------1-011-22-1--1--2-1
11-2-1---1-----3----1--2---33---2----2--1---1--2-2-1-
-12---332-2-23--32--1-11-121-1----1--12--1--1-------2
---3------2--3-22-12--221--1---11--322-1-3-------1-2-
--2-22-------1-211-1----3-21-1------1-------1121---3-
-2---2---2--2---212-----1----3---1----2111-2----112--
1--2-----1-1-----1-1-1-2--12--1-12-2---2----1--1-3--1
-22---32-1-1--131----11---22--1331--2-----0---1--1---
1--13132------211-----1---2-1-2--1-111---211-12-2--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.