TCO 2010 Marathon Match Round2 - CellularAutomaton

Submission 1 - 35.16

No idea, just return the given configuration.

Note. The best submission over all competitor is 46.91.

Example scores:
0) 0.2361111111111111
1) 0.0
2) 0.5262974573319401
3) 0.0
4) 0.4849908107004288
5) 0.6650326797385621
6) 0.3459939531368103
7) 0.4034013605442177
8) 0.07321867321867322
9) 0.42770034843205573

Submission 2 - 36.92

SA

Select random point and toggle the state of the cell. 

Restore best method - when N cells have been changed:

- Calculate gains by changing states of some changed cell to its original states.

- Select best of them and restore.

Too few iterations. (less than 1000 for many cases)

Example scores:
0) 0.625
1) 0.0
2) 0.6137234413096482
3) 0.0
4) 0.5895446191545844
5) 0.7867647058823529
6) 0.36054421768707484
7) 0.4741496598639456
8) 0.18968058968058968
9) 0.5150987224157956

Submission 3 - 47.27

Modify the formula for temperature.

Fix bug in submission2 .

- The number of iterations has increased tenfold by above two modification.

- There might be many TLEs in submission 2.

Example scores:
0) 0.6597222222222222
1) 0.0
2) 0.6610936955764541
3) 0.0
4) 0.6702062487237084
5) 0.8586601307189542
6) 0.3934240362811791
7) 0.5469387755102041
8) 0.341031941031941
9) 0.5638792102206737

Submission 4 - 47.11

2-change method - when N cells have been changed:

- Toggle two cells(one is changed and another one is unchanged)

Example scores:
0) 0.6597222222222222
1) 0.0
2) 0.6628352490421456
3) 0.0
4) 0.6724525219522156
5) 0.8700980392156863
6) 0.38945578231292516
7) 0.5496598639455782
8) 0.3385749385749386
9) 0.5722996515679443

Submission 5 - 47.29

Optimize memory use.

Local Test: 44.94593

Submission 6 - 47.25

Use restore best method when K <=10, and use 2-change method when K > 10.

Local Test: 45.11850

Submission 7 - 47.39

Remove some unnecessary computations.

- The number of iterations has increased by about 50%.

Local Test: 45.13912

Submission 8 - 49.02

Remove redundant computations by memoization

- The number of iterations has increased about 4 times.

Use 2-change method used in submission 5 when K <= 7, and use restore best method used in submission 2 elsewhere.

Local Test: 46.45118

Submission 9 - 49.15

Fix a bug: The temperature for SA never decreases.

Temperature: sqrt(min(K, sqrt(R*C))) / 2 - min(0.5, 3/K) + (1 - currrentTime / timeLimit)

Local Test: 46.36277

Submission 10 - 49.19

Run restore best method together with 2-change method every 10 updates.

Local Test: 46.61858

Submission 11 - 49.22

Run restore best method every 5 updates.

Local Test: 46.65548

Introduce new heuristic

Accept best negative move: If there were no updates for some period. accept the best try among the period.

Unfortunately ABH doesn't seem to work

Submission 12 - 49.20

Apply ABH with parameter 3.0

Psyho has reached 50.26

Local Test: 46.88371

Submission 13 - 49.49

Remove unnecessary computations that prepare a data structure for simulation.

Local Test: 46.80152

Submission 14 - 49.19

Remove redundant simulation (by memoization)

Use 2-change method  when K <= 6, and use restore best method  elsewhere.

No restore best heuristic when K <= 6.

Multi-start SA for small K.

Local Test: 46.71543

Submission 15 - 49.29

Fix a bug in submission 14. (Memoization had not been used)

Submission 16 - 49.55

Use Monte Carlo method to choose best restore cell with check ratio 0.3 ~ 0.9

Use 2-change method  when K <= 3, and use restore best method  elsewhere.

Multi-start SA for when K <= 3

No restore best heuristic.

Local Test: 47.00399

Submission 17 - 49.75

Remove unnecessary simulation

- There are many cells in the grid that are not effected by previous updates.

Local Test(100set): 47.19683

Local Test(200set): 49.80420

Submission 18 - 49.88

Reduce memory to use cache memory more efficiently.

Local Test(200set): 49.88934

Submission 19 - 49.92

Use restore best method for all K.

No multi start.

Increase the maximum number of changed cell gradually.

- N_limit = ( N + N * progress * (2-progress) ) / 2 + 1. (parabola)

Local Test(200set): 49.97555

Submission 20 - 49.93

The same code with the submission 19.

Submission 21 - 49.93

Increase the maximum number of changed cell gradually.

- N_limit = N*sqrt(1-(progress-1)*(progress-1))+1. (circle)

ainu7 reached 50.65

Local Test(200set): 50.02681

Submission 22 - 50.17

Test points near by the last updated point.

- The distance between testing point and the last update point is decreased gradually.

- upper bound of the distance: max(R/2, C/2)

- lower bound of the distance: min(2*K+1, max(R/2, C/2))

- dist = (lower_bound - upper_bound) * progress + upper_bound + 0.5

Local Test(200set): 50.25089

Submission 23 - 49.38

Speed up about 10~15%

- Maintain the number of live neighbor cells.

Test points near by the last updated point.

- the distance limit is min(2K+1, R/2 or C/2)

Local Test(200set): 50.29451

Submission 24 - 50.14

Fix a bug in the last submission

Local Test(200set): 50.21529

Submission 25 - 50.32

Lower Temperature

Local Test(200set): 50.47068

Submission 26 - 50.34

Lower Temperature

Local Test(200set): 50.50701

Submission 27 - 50.40

Remove "if" states in mainly working loop by simple pre-processing.

Local Test(200set): 50.55063

Submission 28 - 50.37

Just a little bit of adjustment of the temperature

Local Test(200set): 50.615629

Submission 29 - 50.36

The same code with the submission 27. Just to check the deviation.

Submission 30 - 50.57

Temperature: (sqrt(min(K, sqrt(R*C))) / 2 - min(0.5, 3/K)) / 2.5 + 0.5 * (1 - currrentTime / timeLimit)

Use Monte Carlo method to choose best restore cell with check ratio 0.4 ~ 1.0

Local Test(200set): 50.742574