JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: 2007 TopCoder Open Online Round 3
Problem: LumberjackExam

Problem Statement

    

You are a lumberjack, and it is your job to inspect the forest before harvesting, to mark any trees that have been infected with a wood rotting disease. You only have a limited amount of daylight left, and therefore must work as efficiently as possible to mark off as many such trees as possible, while still having time to return to your starting point. (Otherwise, you would risk becoming hopelessly lost in the forest under the dark of night.) The trees are all arranged in a rectangular grid, so when standing in the middle of four surrounding trees, it is possible to look in any of the four cardinal directions, and attempt to determine visually if any of the trees are infected. Unfortunately, as trees are further away from you, it becomes more difficult to accurately determine whether or not they are infected.

You start at (0,0), the Northwest corner of the forest. At any given moment, you can move in a series of steps East/West/North/South, or look in any of the same four directions. Moving takes one unit of time per step. Looking in any of the four directions also takes one unit of time. Unfortunately, company policy forbids you from looking while moving, as you might trip as a result of not watching where you are going.

Your code must implement a method examineForest. You are given ints height and width describing the size of the forest, an int time indicating the maximum amount of time available before you run out of daylight, and a double density describing how thick the forest is. Your method should make use of the two available library functions, look and move, in order to move throughout the forest in search of infected trees. Your method should return 0 after you have returned to the point of origin.

Library Methods

look: This method should be called with a single String parameter ("E", "W", "S" or "N") indicating the direction you want to look. The method will return a String[] containing exactly two elements. The first element represents your assessment of the row of trees to your left, and the second element your assessment of the row of trees to your right (where left and right are relative to the direction you are looking, and the row extends away from you). Each character of each element represents your assessment of a single tree, and is either 'Y' or 'N', indicating that the tree does or does not appear to be infected. The first character is the tree directly in front of you, the next character is the tree behind it (relative to the direction you are looking), etc. The two trees directly in front of you are always assessed correctly, and are immediately marked when applicable. The probability of assessing a tree in the distance as being infected is described by: baseline * (1 - (1 - density)distance) + (1 - density)distance * I, where I is 0 for uninfected trees and 1 for infected trees, baseline is the proportion of infected trees throughout the whole forest, and distance is 0 for the trees directly in front of you, 1 for the next pair, and so on. If there are no trees in one of the rows (for example, if looking east from (0,0)) that element of the return will be the empty string.

move: This method should be called to move through the forest. The single String parameter should indicate the direction(s) you wish to move (in order), where each character is 'E', 'W', 'N' or 'S'. The return will be a int[], indicating your coordinates after moving. (ret[0] = x, ret[1] = y)

Scoring

Your raw score for each test case will simply be the number of infected trees you mark during your travel through the forest, presuming you make it back out within the given time. Any invalid parameters passed to the library methods will result in scoring a 0 for that test case. Any calls to the move method that would cause you to go outside the region from (0,0) to (width,height) will result in a 0 for that test case. If your method makes too many calls, such that your lumberjack is still in the forest after nightfall, you will score a 0 for that test case.

Your total score will be calculated by adding up your relative score for each test case. The relative score for a test case is given by the formula:

(my score for this test case) / (max score by anyone for this test case)

Test Case Generation

width, height, time, and density will be chosen uniformly at random.

We then select, all uniformly at random, M between 40 and 60, P between 10 and 15, q0 between 0.30 and 0.34, and q between 0.45 and 0.49.

We start with a width * height grid of trees. K = (width * height / 200) of them are chosen at random. Those K are the seeds. Each of those K start spreading disease at a random time -t, where t in [0..M - 1]. When spreading, each tree that is infected has an incubation period of P, after which it starts spreading the disease. That is to say, if a tree is infected at time t, then at time t + P it will infect other trees. A tree that has incubated immediately spreads disease to all other (not yet infected) trees, with probability q0 * q^dist (where dist is the Manhattan distance between the two trees). The disease spreading continues until time 0, when you enter the forest. At this point, the disease spreading process stops, (imagine that the disease spreading timescale is much longer than the timescale used for walking around). In pseudocode:

for K seeds 
	(x,y) = a random, uninfected tree
	t = -Random[0...M - 1]
	Mark(x, y) as infected
	Add (x, y) to incubation list at time t


While incubation list has trees 	
	currentTree = take earliest incubated tree from list
	for each tree in forest
		if tree is not already infected and Random < q0 * q^(man dist) then
			set tree as infected
			if (t + P <= 0) then
				add this tree to incubation list for time t + P
		

Visualizer

A visualizer is provided to help you develop your solution. The seeds for the examples are 1-10.
 

Definition

    
Class:LumberjackExam
Method:examineForest
Parameters:int, int, int, double
Returns:int
Method signature:int examineForest(int height, int width, int time, double density)
(be sure your method is public)
 

Available Libraries

    
Class:Lumberjack
Method:move
Parameters:String
Returns:int[]
Sample Call:val = Lumberjack.move(movements);
Method:look
Parameters:String
Returns:String[]
Sample Call:val = Lumberjack.look(direction);
    
 

Notes

-The time limit is 20 seconds, and the memory limit is 64M.
-The trees themselves are in between the coordinate points along which you move. That is to say that you can move between (0, 0) and (width, height), while the trees are located at points from (0.5, 0.5) to (width - 0.5, height - 0.5).
-If nobody scores higher than a 0 for a given test case, then all relative scores will be 0 for that case.
-The first four examples have been specially constructed outside of the normal constraints, to facilitate testing. The remaining examples follow the generation described in the problem statement.
-There are 10 example cases and 40 non-example cases.
 

Constraints

-width and height will be between 50 and 100, inclusive.
-time will be between 200 and 2500, inclusive.
-density will be between 0.05 and 0.30, inclusive.
 

Examples

0)
    
20 x 20 grid, density = 0.15186, time = 1026
K = 2
M = 53
P = 12
q = 0.47843
q0 = 0.32635
baseline = 0.085

....................
....................
....................
....................
....................
....................
....................
....................
....................
......X.............
.....X..............
.....XX.............
..XX.X..............
..XXXXX.............
XXXX..X.X.......X...
....X..X............
.....XX.X...........
..X..XXX....XX......
.X..XX..............
...X................
 
Here, the '.' represents a clean tree, and 'X' an infected tree. Note that you start above and to the left of the upper-leftmost '.'.
1)
    
30 x 30 grid, density = 0.05104, time = 1435
K = 4
M = 55
P = 10
q = 0.48692
q0 = 0.30133
baseline = 0.06778

..............................
..............................
.........................X....
..........................X...
.........................XX...
.........................XX...
.........................X..X.
...........................X..
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..................X.X.........
................X...X.........
.........X.....XX..XXX........
...............X..XX..X.......
.........X.....X.X..X..X......
...........X..X.XXXX.XX.......
.............X.X.XX...........
...........X..XX.X...X........
...........X..X.XXXX..........
...........XX...X.X...........
..........XXX.....X...........
.........X.......X............
 
2)
    
40 x 40 grid, density = 0.25131, time = 1655
K = 8
M = 55
P = 13
q = 0.48409
q0 = 0.32301
baseline = 0.075

........................................
...X...........X..X.....................
.................X......................
..........X..X.XX.......................
...XX...X.......X...X...................
...............XX.XXX...................
...X............XXXX.X..................
.............XX.XXXXX.X.................
..X..........X..XX.X.X.X................
..............XXX..X..X......X..........
..X.X.........XX.XX.XX..................
.............X.X.X..XX.X................
.........X...X.X........XX.....X..X.....
................X....X..X...........X...
.X......................X...............
......................XX...........X.XX.
.......................XX...........X...
.................................X.....X
......................X.........X....XX.
.....................................X..
......................................X.
.......................................X
........................................
........................................
........................................
........................................
......................................X.
....................................X...
.................................X....X.
...................................X..X.
...................................X....
........................................
........................................
........................................
X..X...............................X....
....X............................X.X....
....X...........................XX.XXX..
..X.X..........................X...XX...
..............................X.XX.XX...
..................................X.X...
 
3)
    
50 x 50 grid, density = 0.25268, time = 2384
K = 12
M = 52
P = 11
q = 0.46993
q0 = 0.31138
baseline = 0.0328

............X.X...................................
...............................................X..
...X...XX...X.....................................
...XX.............................................
.............................................X....
..................................................
............................................X.....
..................................................
...........................................X..X...
...........................................X.XX...
............................................X.X...
........................X......................XX.
.........................XX...................X...
........................XX........................
........................X.X.......................
..................X..XX...........................
..................X.XXX.X.........................
........................X.X.......................
..................................................
.....................X...XX.......................
........................X.........................
..................................................
.................X................................
.................................X................
.......................X..........................
..................................................
..................................................
..................................................
..................................................
..................................................
........................................X.X.......
.................................X.......X.X......
.....................................XX..X........
.................................XX..X.X..........
................................XX................
..............................XX.X................
..............................X...................
..................................................
..................................................
...X..............................................
..................................................
..................................................
..........XX......................................
..............X...................................
..................................................
.........X......XX................................
.........XXX.X.....X..............................
.........XX.XX....................................
.............X....X...............................
.........X........................................
 
4)
    
66 x 55 grid, density = 0.20295, time = 304
K = 18
M = 54
P = 14
q = 0.4671
q0 = 0.33305
baseline = 0.04298

..................................................................
..................................X.X.............................
..................................................................
.....X......XX......................X.X......X....................
..........X.X.........................X......X....................
..X.........X.X....................X.......XXX....................
..........X......................X......X...XX....................
.XXX.......X..............................XX.X....................
...........................................X......................
X.XX.XX...........................................................
X.....X.........................................XX................
..X..X............................................................
......X...........................................................
..........................XX.....................X................
........................X.........................................
........................XX........................................
.....................X....X.......................................
.......................XX.X.......................................
...............X..................................................
..................................................................
..................................................................
..........................X.......................................
........................XX.X......................................
..................................................................
..................................................................
.................X...XX...........................................
.....................X................................X.X.........
...............X..................................................
...............X..................................................
...............X..................................................
...............X..................................................
..................................................................
......................XX..X.......................................
...................X..XX..........................................
......................XX..........................................
..............XX..XX..............................................
...............X..X....................................X..........
..............X...................................................
..................................................................
..............X.XX.....................................X...XX.....
......................................................XX..........
.......................XX..............................X....X.....
.......................X...............................X..........
......................XX.X...................X....................
....................X..............................X..XX.X...XX...
.....................X...X..................X.....................
...........................................XX.X...XXX.XX..........
.......................................XXXXX......................
..........................................XX..X..X.X...X..........
..............................................X.X.................
.........................................XX..XX..XX...............
.......................................X.......X.X................
.........................................XX....X..................
.....................X....................X.X.XX..................
...........................................X.X.XX.................
 
5)
    
68 x 63 grid, density = 0.10213, time = 712
K = 21
M = 54
P = 15
q = 0.4756
q0 = 0.30803
baseline = 0.04505

....................................................X.X.............
...................................................XXXX.............
................................................X..X.X..XX..........
.........X..........................................X...X...........
................................................X..............X....
...........................................................X........
....................................................X.............X.
....................................................................
..................................................XXX..XX...........
.....................................................X...X..........
.....................................................X..X........X..
...................................................XX...X.......XX..
...................................................XX...........XX.X
...................................................X.X...........X.X
.....................................................XX........X.XX.
.....................................................X..........X.XX
..............................................................X.XXX.
...................................................................X
.X...........................................................X......
...X.............................................X..................
.X.X...............................................................X
..................................................X.X...............
......X...........................................XX................
....................................................................
.....................................................XX.X...........
.......................................................X............
....................................................................
....................X...............................................
............X.......................................................
....................................................................
...............XXX..................................................
.............X...X..................................................
...........X..X.....................X...............................
........X..XX.......................................................
.........X.XX.X.X.X.................................................
.......XX..X.X..X..........................X.X......................
.......XXXX.XX.X......................X....X............X...........
.....X.XX..XXXXX......X....................XX..........X.X..........
............X.XX............X.................XX........XX.X........
X.X..X.X..........................XX.......X........................
X.X.X..X....X...............X.....X........XXX...X..................
X.X..........X..X.......................X...XX.X....................
...X......................X.X.......X........X......................
...........................X..........XXX.X.........................
....X......................X........................................
....................................................................
....................................................................
........X.......................................X...................
.........X....................................X.....................
.........X.X........................................................
....................................................................
........X...........................................................
....X...X..X........................................................
...XXXX.X.X.........................................................
....X.X.............................................................
....X.XX............................................................
....XX..............................................................
.....X..............................................................
....................................................................
....................................................................
....................................................................
....................................................................
....................................................................
 
6)
    
76 x 60 grid, density = 0.05241, time = 398
K = 22
M = 53
P = 14
q = 0.47277
q0 = 0.3297
baseline = 0.08684

..........................X.X...............................................
.............................X.........................................X....
........................X.X..X.........................................X.X..
............................XXX.......................................XXX...
..............................XX.......................................X.X..
.......................................................................X.X..
..................................X.........................................
............................................................................
..................................X.............X......X....................
......................................X.X.................X.................
..................................XX....XX......X...........................
....................................X...X.....X......X.X....................
....................................XX.X.......X............................
..................................X..XX.......X...X..X......................
..................................X.X.X........XX......X....................
..................................XXX........X.XX.XX..X.....................
...................................X.XXX.....XX.XXXXXXXX....................
......................................XX.X...XX.XXXX.X.X....................
..............................................XX.XXX........................
..........................X..............X...XXXXXX...X.....................
.........................X.........X.X.X.............X.............X........
...............X........................X...X...X................X..........
............XXXX............X........X.X.........................X.X........
..........X.XXX......................X.....X..X....................X........
...........XXXX...X........................X..X....X........................
................X.....................................................XX....
......XX.X.X.XXX.................................................XX......X..
.......X..XX..XXX...........................................................
...........XX.X...X.........................................................
............X.X.............................................................
.......................................................................XXXXX
...........X...X...............X....................X.......................
......X........................XX.......................................XX..
..............................X.....................X.X.X...............XX..
..............................X.X..................XXXX................XXXXX
....................................................XXX...............X....X
......X.......................X.X................X......X.X..........X......
...................................................XXX...............X......
.....X.X.X......................XXX..................................XX.X...
.......X.........................X............X.............XX.......XX.....
...............................................X...X.....XXX.........X......
...............................................X...........X.X..............
.......................................................XX.X...XX.XX.........
.................................X.X....................X....XX.............
.................................XX.................X..XX.X....XX...........
..............................X...................X.....XXX..XX.XX..........
....................................................XXXXXXXX.XXXXXXX..XX....
.................................X..................XX.XX.X.XXXX...XXX......
X.X.............................XX..XX...............XXX.X..X.....X.........
X.XX...X...........X............X....X.............X.XX.X.........XXXX......
..XX.X......XX.......................................X.........X.X.XXXX.....
X.X.........XX.X.X.................................................X...X....
..........X.X.XX...................................................XXXX.....
...........XXXXX..................................................X.........
.......X..X.X...XXX................................................XX.......
..........X.XXX...................................................XXX.......
.....XX...XXXX.............................X.....................XXX........
.........XXXX..X............................X......................XXX......
..........XXX...............................X........................X......
..........X.X...............................................................
 
7)
    
90 x 99 grid, density = 0.05378, time = 1662
K = 44
M = 51
P = 13
q = 0.45861
q0 = 0.31808
baseline = 0.05713

..................X.....................................X.................................
................................................X.........................................
..................X..............................X.XX...X........................X........
...................................................X...X..................................
....................................X.............................................X.......
..................................X......................................X......X.........
..................................X............................................XXX...X....
........................................................................X........XXX......
......................................................................X..X......XXX.X.....
......................................................................X..X.X..............
...........X.........................................................X...XX........X......
........XX.X......................................................................XX......
.........XX.......X..X................................................X...................
.........X................................................................................
....................X.....................................................................
.......X..XX........XX..X.................................................................
.....XX..X.XX....XX..X....................................................................
.........XXXX......XXX.X..................................................................
.....X...XXX......XX......................................X...............................
.....X....XXXXX.....X.....................................................................
....X...XXXXX.X....X..XXX.........................................X.......................
..........XXXX.X......X..........................................X........................
...........X.XX...................................................X.......................
.............X..X.X...X.................................................................X.
.............X........................................................................XX.X
........................................................................................X.
......................................................................................XX..
....................................................................................X.X...
..........................................................................................
............................................X..................................X....X.XX..
....................................................................................XX....
......................................................X.....X....................X..XXXXXX
............................XX.............X.........................................XXXXX
..........................X.XX....................................................X..XX...
.......................X...XX...............................XX.X....................XX....
.........................XX.X.............................................................
.........................XXX..............................X...........................X...
......................X.......X..........................X...........................X....
............................................XX...........X.XXX.......................XXX..
......................X.XX...X..........................X...........................X...X.
.........................X..X.........................XXX.XX..............................
..............................X..............................X............................
.................X.X.X..X.X..X........................X..X.XX.............................
...................X..XXXX.X..X............................X..............................
...................X...X.X....X...........................XX..............................
.................XX.XXX..X................................................................
......................X...X.X.............................................................
....................X.......X.............................................................
..........................XXX.............................................................
............................X......................X.X....................................
..........................X...............................................................
.....................................................X....................................
..........................................................................................
....................................................X..XX.................X...............
........................................................X.X...............................
......................................................X......X............................
.......................................................X.....XX...........................
.X.........................................................XXX............................
..........................................X...............X.XXXX..........................
...............................................................X..........................
...............................................................X..X.......................
......................................................X.....X.............................
......................................................XXXXXXXX............................
.............................................................XX..X........................
.............................X..............................XXX.X.........................
...................................................................X.....................X
.................X.........X.X.........................................................XXX
............................X..........................X..X.X.X........................X..
.......................................................XX.X.X.............................
.................X.X..................................X...X.XXX...........................
.................X.....................................X..XXXXXXX.X.......................
...............X.....................................X.......XXXX.........................
............................X............................X..XXX.X..X......................
............................................X.............X...X.XX......X...............X.
........................................................X.XXXX.XXXX.XX.XXX................
................................................................X...XXX.X.................
.....................................................................X....................
.........................................X...............X..XX............................
......XX.................................X................................................
........X..X............................XX...................X.......X....................
.......................................X.......X..........................................
........................................X.....X...........................................
..........X..............................XX.X..XX.........................................
.........X................................X...........................X...................
.........X.......................................................X..................X.....
.......XXXXXX..X....X.......................X......................XX.....................
.X..........X..........X..................X..........................XXX..................
..X.......X.......X......................XX...................X.X.XX...X............XXXXX.
.XX.X..................X.....................................X..XXX.X...X............XX...
....X..X.X......................................................X............X..X....XX...
.X.X.X.X.X.......................................................XX...................X...
........X.X....................................................X.X.....X.X..........X..XX.
.X......X........................................................X.X...XX......X...X.XXX..
...XXX..................................................................X.........X.......
..XX.X...........................................................XX.................X.X.X.
...X.X...................X....X..................................XX....X.............XXXX.
..............................X......................................X......X.........X...
................................X...................................X.XX.X...........X....
..................................................................X.X.XXX...X.............
 
8)
    
72 x 96 grid, density = 0.25405, time = 1347
K = 34
M = 52
P = 15
q = 0.45578
q0 = 0.33975
baseline = 0.0515

...................X...X..X................................XXX..........
...................XXX..................................................
......................XX................................................
........................................................................
..........XX............................................................
...........XX...........................................................
...........X.......X....................................................
.........X.X....XXX.X...................................................
.................XX....XX...............................................
.............X....X.X...................................................
..............XX.X.XX...................................................
..................X.....................................................
..................X.....................................................
...............X........................................................
...............................................................X........
........................................................................
...................................................................X....
...............................................................X........
........................................................................
.................................X............................XX.X.X....
..............................XX........................X.X....X..XXX.XX
...............................................................X..X.....
........................................X.......................X.X.....
...............................X........XX...........X.........XX...X...
...........XX..............................X..................XXXX......
......X.......X...........................X.............................
.........X..X..X...........................X....................X.......
........XXXXXX.............................X.X..........................
.....X..XX.XXX...........................X.XXXX.........................
.........XX.XX..X..........................XX.X.........................
.........X.XXX............................XXXXX.........................
.........X...XX...........................XXXX.X........................
..........X..X...........................XXXXX..........................
...........X............................................................
.............X...........................X..............................
..X.....................................................................
........................................................................
........................................................................
........................................................................
........................................................................
........................................................................
........................................................................
........................................................................
......................................................X.................
........................X.............................X.................
........................X.............................XX.XX.............
.......................XX...................X...XXX.X..X..X.XXX.........
........................X........................XX....XX....XXX...X....
.......................................................X.X..XX.X........
........................................................XXX.X..XXXX.....
...........................X.........................X..XX.....XX.X.....
.........................XX.............X.........XX.X..X...............
...................X.....................XX......X.....X.X..............
..................XXX....X..X.............XXX............X..............
...................X.....XXX............X.XX......X.....................
.........................X..............X.X..X......................X...
.........................XXX..............X.....................XX.XX...
..........................X......................X..................X...
...................................................................X..X.
....................X................................................XX.
...............................X...................................XX.X.
.......................................................................X
...........................X............................................
................................X.......................................
.........................X..............................................
........................X.XXXXXX.XX.....................................
.......................XX..XX.XXX.......................................
..X...................X....X..X.........................................
............................XX.X.X......................................
.............................X..........................................
...............................X........................................
..............................X.........................................
........................X....X................................XX........
........................XX....X.............................XXXX........
...................X.....X....................................X.........
...................X....XX.....................................X........
...................X.X..........................X...........XXX.........
.............................XXX.X.............X..X...X......XX.........
..............................X..X.............X.X....X.................
.............................XXXX.X...........XXXX......................
.....X..........................X...........XX...X......................
.....X.....X................X....X........X.............................
....X.......................XXX.X.............X.........................
.............................XX.XX......................................
...............................X........................................
........................................................................
........................................................................
..............................X.........................................
........................X.....XX........................................
........................................................................
..............................X.........X...............................
........................................................................
........................................................................
........................................................................
............XXX.........................X...............................
............X.X.........................XXX.............................
 
9)
    
74 x 53 grid, density = 0.15323, time = 2291
K = 19
M = 53
P = 11
q = 0.46427
q0 = 0.31473
baseline = 0.06451

......................................................................X..X
.......X.......XX.....................................................XX..
...............X.XX..X.............................................XXXXXXX
.................XXX..X........................................X..XX.XX.X.
..................XXX..............................................X..XXXX
...............X.XX.X.....................X..X......................X..XXX
............X...XX.....X.X................X........................X...X.X
.............X.XX....X.XX...............XXX.........................X....X
............XXXXXX.X.....................XX.........................X..X..
............XXX.X.....X................X...X.........................X....
............XX.XX......................X.X..............................XX
........XX...XXX.........................XX........................X.X..XX
.........XXXXXXX........................X...........................XX....
...........X.XXX.........................X.........................X......
........X..XXXX..........................................................X
.......XX.XXXXXXXX........................XX..............X...............
.......XX..XXX.XX.........................XXXXX...........X...X...........
..........XXX...XX....................X...XX.X............X..XX...........
.........X...X..XX....................XX....X..............X.X............
XX...X..X...X..XXX........................................................
....X.XXX........X........................................................
....XX..........XX........................................................
..........................................................................
.....X................................X.XX................................
..........................................................................
...................................X......................................
..........................................................................
..................X.....................X.................................
..........................................................................
...................................X................................X...X.
..........................................................................
....................................................................XX.X..
..........................................................................
.....................................................................X....
X...................................................................X.....
.X...................................................................X....
...................................................................XXX....
....................................................................XXX...
..................................................................XX......
..................X.X.................................................XX..
...................................................................X......
.X..................X..............X............X..................X..XX.X
......................................X................X..........X...XX..
.X...............................................X.X................XX....
..................X.X........................X......................X.....
..................X.............................X..................XXXX...
..............X........................................................X..
..........................................................................
......................................................................X...
..........................................................................
..........................................................................
..........................................................................
..........................................................................
 

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.