# Yandex Algorithms 2017 Marathon

a guest
May 8th, 2017
431
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. using System;
2. using System.Linq;
3. using System.Collections.Generic;
4. using System.Diagnostics;
5.
6. class Solution
7. {
8.     static int width;
9.     static int height;
10.     static int k;
11.     static Point[] life;
12.     static Point[] magic;
13.     static Random random = new Random();
14.     static bool[,] fountain;
15.
16.     static int[,] dirRandom = new int[,] {
17.         {0,1,2,3},
18.         {0,1,3,2},
19.         {0,2,1,3},
20.         {0,2,3,1},
21.         {0,3,1,2},
22.         {0,3,2,1},
23.         {1,0,2,3},
24.         {1,0,3,2},
25.         {1,2,0,3},
26.         {1,2,3,0},
27.         {1,3,0,2},
28.         {1,3,2,0},
29.         {2,1,0,3},
30.         {2,1,3,0},
31.         {2,0,1,3},
32.         {2,0,3,1},
33.         {2,3,1,0},
34.         {2,3,0,1},
35.         {3,1,2,0},
36.         {3,1,0,2},
37.         {3,2,1,0},
38.         {3,2,0,1},
39.         {3,0,1,2},
40.         {3,0,2,1},
41.     };
42.
43.     static void Main(string[] args)
44.     {
45.         int[] nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
46.         height = nums [0];
47.         width = nums [1];
48.         k = nums [2];
49.         life = new Point[k];
50.         fountain = new bool[width, height];
51.         for (int i = 0; i < k; i++) {
52.             nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
53.             life [i] = new Point (nums [1], nums [0]);
54.             fountain [nums [1], nums [0]] = true;
55.         }
56.         magic = new Point[k];
57.         for (int i = 0; i < k; i++) {
58.             nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
59.             magic [i] = new Point (nums [1], nums [0]);
60.             fountain [nums [1], nums [0]] = true;
61.         }
62.
63.         double bestScore = -1;
64.         int counter = 0;
65.         int[,] solution = new int[width, height];
66.         Stopwatch sw = Stopwatch.StartNew ();
67.
68.
69.         while (sw.ElapsedMilliseconds < 1000 || solution == null) {
70.             int[,] grid = GenerateGrid ();
71.             if (grid == null)
72.                 continue;
73.             counter++;
74.             double score = ScoreGrid (grid);
75.             if (score > bestScore) {
76.                 bestScore = score;
77.                 solution = grid;
78.             }
79.         }
80.         Console.Error.WriteLine ("sims: " + counter);
81.         Console.Error.WriteLine ("score: " + (int)(bestScore * 160000 / k));
82.
83.         counter = 0;
84.         while (sw.ElapsedMilliseconds < 1950) {
85.             int[,] grid = ExpandGrid (solution);
86.             if (grid == null)
87.                 continue;
88.             counter++;
89.             double score = ScoreGrid(grid);
90.             if (score > bestScore) {
91.                 solution = grid;
92.                 bestScore = score;
93.             }
94.         }
95.
96.         Console.Error.WriteLine ("expand sims: " + counter);
97.         Console.Error.WriteLine ("expand score: " + (int)(bestScore * 160000 / k));
98.         Print (solution);
99.     }
100.
101.     static bool ExpandEdge(int[,] grid) {
102.         int x, y, dir, value;
103.         int x_, y_;
104.         while (true) {
105.             x = random.Next (width);
106.             y = random.Next (height);
107.             dir = random.Next (4);
108.             value = grid [x, y];
109.             x_ = x + offset [dir, 0];
110.             y_ = y + offset [dir, 1];
111.             if (x_ >= 0 && x_ < width && y_ >= 0 && y_ < height && grid [x_, y_] != value && !fountain [x_, y_])
112.                 break;
113.         }
114.
115.         List<Point> change = new List<Point> { new Point (x_, y_) };
116.         foreach (int newDir in new int[] {(dir+1)%4, (dir+3)%4}) {
117.             for (int dist = 1;; dist++) {
118.                 int myX = x + dist * offset [newDir, 0];
119.                 int myY = y + dist * offset [newDir, 1];
120.                 int otherX = x + dist * offset [newDir, 0] + offset [dir, 0];
121.                 int otherY = y + dist * offset [newDir, 1] + offset [dir, 1];
122.                 if (myX < 0 || myX >= width || myY < 0 || myY >= height || grid [myX, myY] != value || fountain [otherX, otherY])
123.                     break;
124.                 change.Add (new Point (otherX, otherY));
125.             }
126.         }
127.         foreach (Point p in change) {
128.             grid [p.X, p.Y] = value;
129.         }
130.         return true;
131.     }
132.
133.     static int[,] ExpandGrid(int[,] oldGrid) {
134.         int[,] grid = (int[,])oldGrid.Clone ();
135.         do {
136.             if (!ExpandEdge (grid)) return null;
137.         } while (random.NextDouble () < 0.25);
138.         if (!CheckConnected ((int[,])grid.Clone ()))
139.             return null;
140.
141.         return grid;
142.     }
143.
144.     static Point[] stack = new Point[50 * 50];
145.     static int stackIndex = 0;
146.     static bool CheckConnected(int[,] grid) {
147.         int components = 0;
148.         for (int x = 0; x < width; x++) {
149.             for (int y = 0; y < height; y++) {
150.                 if (grid [x, y] == 0)
151.                     continue;
152.                 components++;
153.                 stack [stackIndex++] = new Point (x, y);
154.                 while (stackIndex > 0) {
155.                     Point p = stack [--stackIndex];
156.                     int value = grid [p.X, p.Y];
157.                     if (value == 0)
158.                         continue;
159.                     grid [p.X, p.Y] = 0;
160.                     if (p.X > 0 && grid [p.X - 1, p.Y] == value)
161.                         stack [stackIndex++] = new Point (p.X - 1, p.Y);
162.                     if (p.X + 1 < width && grid [p.X + 1, p.Y] == value)
163.                         stack [stackIndex++] = new Point (p.X + 1, p.Y);
164.                     if (p.Y > 0 && grid [p.X, p.Y - 1] == value)
165.                         stack [stackIndex++] = new Point (p.X, p.Y - 1);
166.                     if (p.Y + 1 < height && grid [p.X, p.Y + 1] == value)
167.                         stack [stackIndex++] = new Point (p.X, p.Y + 1);
168.                 }
169.             }
170.         }
171.         return components == k;
172.     }
173.
174.     static void Print(int[,] grid) {
175.         for (int y = 0; y < height; y++) {
176.             for (int x = 0; x < width; x++) {
177.                 Console.Write ((char)('a' + grid [x, y] - 1));
178.             }
179.             Console.WriteLine ();
180.         }
181.     }
182.
183.     static int[,] GenerateGrid() {
184.         int[,] result = new int[width,height];
185.         MapPairs (result);
186.
187.         //sort mappings by manhattan distance
188.         int[] indices = Enumerable.Range(0,k).ToArray();
189.         int[] dist = new int[k];
190.         for (int i = 0; i < k; i++) {
191.             dist [i] = Math.Abs (life [i].X - magic [i].X) + Math.Abs (life [i].Y - magic [i].Y);
192.         }
193.         Array.Sort (dist, indices);
194.
195.         foreach(int i in indices) {
196.             if (!ConnectPair (result, life [i], magic [i], i + 1))
197.                 return null;
198.         }
199.
200.         FillGaps (result);
201.         return result;
202.     }
203.
204.     static void MapPairs(int[,] grid) {
205.         int index1 = random.Next (k);
206.         int index2 = random.Next (k);
207.         Point tmp = magic [index1];
208.         magic [index1] = magic [index2];
209.         magic [index2] = tmp;
210.
211.         for (int index = 0; index < k; index++) {
212.             double[] prob = new double[k - index];
213.             int probIndex = 0;
214.             for (int partner = index; partner < k; partner++) {
215.                 int dx = Math.Abs (magic [index].X - life [partner].X);
216.                 int dy = Math.Abs (magic [index].Y - life [partner].Y);
217.                 prob [probIndex++] = 1.0 / (dx * dx + dy * dy);
218.             }
219.             for (int i = 1; i < k-index; i++) {
220.                 prob [i] += prob [i - 1];
221.             }
222.             double randVal = prob [k - index - 1] * random.NextDouble ();
223.             int takeIndex = 0;
224.             while (prob [takeIndex] < randVal)
225.                 takeIndex++;
226.             tmp = life [index];
227.             life [index] = life [index + takeIndex];
228.             life [index + takeIndex] = tmp;
229.             grid [life [index].X, life [index].Y] = index + 1;
230.             grid [magic [index].X, magic [index].Y] = index + 1;
231.         }
232.     }
233.
234.     static Point[] queue = new Point[50 * 50];
235.     static bool ConnectPair(int[,] grid, Point p1, Point p2, int value) {
236.         int[,] dist = new int[width, height];
237.         dist [p1.X, p1.Y] = 1;
238.         int queueFirst = 0;
239.         int queueLast = 0;
240.         queue [queueLast++] = p1;
241.         while (queueFirst < queueLast && dist [p2.X, p2.Y] == 0) {
242.             Point p = queue [queueFirst++];
243.             for (int dir = 0; dir < 4; dir++) {
244.                 Point q = new Point (p.X + offset [dir, 0], p.Y + offset [dir, 1]);
245.                 if (q.X < 0 || q.X >= width || q.Y < 0 || q.Y >= height || dist [q.X, q.Y] > 0 || grid [q.X, q.Y] != 0 && grid [q.X, q.Y] != value)
246.                     continue;
247.                 dist [q.X, q.Y] = dist [p.X, p.Y] + 1;
248.                 queue [queueLast++] = q;
249.             }
250.         }
251.         if (dist [p2.X, p2.Y] == 0)
252.             return false;
253.         Point tmp = new Point (p2.X, p2.Y);
254.         grid [tmp.X, tmp.Y] = value;
255.         for (int next = dist [tmp.X, tmp.Y] - 1; next > 0; next--) {
256.             int dirIndex = random.Next (24);
257.             for (int i = 0; i < 4; i++) {
258.                 int dir = dirRandom [dirIndex, i];
259.                 Point neighbor = new Point (tmp.X + offset [dir, 0], tmp.Y + offset [dir, 1]);
260.                 if (neighbor.X < 0 || neighbor.X >= width || neighbor.Y < 0 || neighbor.Y >= height || dist [neighbor.X, neighbor.Y] != next)
261.                     continue;
262.                 tmp = neighbor;
263.                 grid [tmp.X, tmp.Y] = value;
264.                 break;
265.             }
266.         }
267.         return true;
268.     }
269.
270.     static void FillGaps(int[,] grid) {
271.         List<Point> missing = new List<Point> ();
272.         bool[,] inList = new bool[width, height];
273.         for (int x = 0; x < width; x++) {
274.             for (int y = 0; y < height; y++) {
275.                 if (grid [x, y] == 0 && !FillDoubleNeighbor (grid, x, y, missing, inList) && GetNeighborValues (grid, x, y) > 0 && !inList [x, y]) {
276.                     missing.Add (new Point (x, y));
277.                     inList [x, y] = true;
278.                 }
279.             }
280.         }
281.
282.         while (missing.Count > 0) {
283.             bool forceBorder = true;
284.             for (int i = missing.Count - 1; i >= 0; i--) {
285.                 Point p = missing [i];
286.                 if (grid [p.X, p.Y] != 0)
287.                     missing.RemoveAt (i);
288.                 else {
289.                     int neighborValuesCount = GetNeighborValues (grid, p.X, p.Y);
290.                     if (neighborValuesCount == 1) {
291.                         grid [p.X, p.Y] = neighborValues [0];
292.
293.                         if (p.X > 0 && grid [p.X - 1, p.Y] == 0 && !FillDoubleNeighbor (grid, p.X - 1, p.Y, missing, inList) && !inList [p.X - 1, p.Y]) {
294.                             missing.Add (new Point (p.X - 1, p.Y));
295.                             inList [p.X - 1, p.Y] = true;
296.                         }
297.                         if (p.X + 1 < width && grid [p.X + 1, p.Y] == 0 && !FillDoubleNeighbor (grid, p.X + 1, p.Y, missing, inList) && !inList [p.X + 1, p.Y]) {
298.                             missing.Add (new Point (p.X + 1, p.Y));
299.                             inList [p.X + 1, p.Y] = true;
300.                         }
301.                         if (p.Y > 0 && grid [p.X, p.Y - 1] == 0 && !FillDoubleNeighbor (grid, p.X, p.Y - 1, missing, inList) && !inList [p.X, p.Y - 1]) {
302.                             missing.Add (new Point (p.X, p.Y -+ 1));
303.                             inList [p.X, p.Y - 1] = true;
304.                         }
305.                         if (p.Y + 1 < height && grid [p.X, p.Y + 1] == 0 && !FillDoubleNeighbor (grid, p.X, p.Y + 1, missing, inList) && !inList [p.X, p.Y + 1]) {
306.                             missing.Add (new Point (p.X, p.Y + 1));
307.                             inList [p.X, p.Y + 1] = true;
308.                         }
309.                         forceBorder = false;
310.                     }
311.                 }
312.             }
313.             if (forceBorder) {
314.                 for (int i = missing.Count - 1; i >= 0; i--) {
315.                     Point p = missing [i];
316.                     if (grid [p.X, p.Y] != 0)
317.                         missing.RemoveAt (i);
318.                     else {
319.                         int neighborValuesCount = GetNeighborValues (grid, p.X, p.Y);
320.                         if (neighborValuesCount > 1) {
321.                             grid [p.X, p.Y] = neighborValues [random.Next (neighborValuesCount)];
322.
323.                             if (p.X > 0 && grid [p.X - 1, p.Y] == 0 && !FillDoubleNeighbor (grid, p.X - 1, p.Y, missing, inList) && !inList [p.X - 1, p.Y]) {
324.                                 missing.Add (new Point (p.X - 1, p.Y));
325.                                 inList [p.X - 1, p.Y] = true;
326.                             }
327.                             if (p.X + 1 < width && grid [p.X + 1, p.Y] == 0 && !FillDoubleNeighbor (grid, p.X + 1, p.Y, missing, inList) && !inList [p.X + 1, p.Y]) {
328.                                 missing.Add (new Point (p.X + 1, p.Y));
329.                                 inList [p.X + 1, p.Y] = true;
330.                             }
331.                             if (p.Y > 0 && grid [p.X, p.Y - 1] == 0 && !FillDoubleNeighbor (grid, p.X, p.Y - 1, missing, inList) && !inList [p.X, p.Y - 1]) {
332.                                 missing.Add (new Point (p.X, p.Y -+ 1));
333.                                 inList [p.X, p.Y - 1] = true;
334.                             }
335.                             if (p.Y + 1 < height && grid [p.X, p.Y + 1] == 0 && !FillDoubleNeighbor (grid, p.X, p.Y + 1, missing, inList) && !inList [p.X, p.Y + 1]) {
336.                                 missing.Add (new Point (p.X, p.Y + 1));
337.                                 inList [p.X, p.Y + 1] = true;
338.                             }
339.                             break;
340.                         }
341.                     }
342.                 }
343.             }
344.         }
345.     }
346.
347.     static bool FillDoubleNeighbor(int[,] grid, int x, int y, List<Point> missing, bool[,] inList) {
348.         int neighborValuesCount = GetNeighborValues (grid, x, y);
349.         if (neighborValuesCount > 1) {
350.             for (int i = 0; i < neighborValuesCount; i++) {
351.                 for (int j = i + 1; j < neighborValuesCount; j++) {
352.                     if (neighborValues [i] == neighborValues [j]) {
353.                         grid [x, y] = neighborValues [i];
354.                         for (int dir = 0; dir < 4; dir++) {
355.                             int x_ = x + offset [dir, 0];
356.                             int y_ = y + offset [dir, 1];
357.                             if (x_ >= 0 && x_ < width && y_ >= 0 && y_ < height && grid [x_, y_] == 0 && !FillDoubleNeighbor (grid, x_, y_, missing, inList) && !inList [x_, y_]) {
358.                                 missing.Add (new Point (x_, y_));
359.                                 inList [x_, y_] = true;
360.                             }
361.                         }
362.                         return true;
363.                     }
364.                 }
365.             }
366.         }
367.         return false;
368.     }
369.
370.     static int[] neighborValues = new int[4];
371.     static int GetNeighborValues(int[,] grid, int x, int y) {
372.         int index = 0;
373.         if (x > 0 && grid [x - 1, y] != 0)
374.             neighborValues [index++] = grid [x - 1, y];
375.         if (x + 1 < width && grid [x + 1, y] != 0)
376.             neighborValues [index++] = grid [x + 1, y];
377.         if (y > 0 && grid [x, y - 1] != 0)
378.             neighborValues [index++] = grid [x, y - 1];
379.         if (y + 1 < height && grid [x, y + 1] != 0)
380.             neighborValues [index++] = grid [x, y + 1];
381.         return index;
382.     }
383.
384.     static int[,] offset = new int[,] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
385.     static double ScoreGrid(int[,] grid) {
386.         double[] area = new double[k];
387.         double[] perimeter = new double[k];
388.
389.         for (int x = 0; x < width; x++) {
390.             perimeter [grid [x, 0] - 1]++;
391.             perimeter [grid [x, height - 1] - 1]++;
392.             for (int y = 0; y < height; y++) {
393.                 area [grid [x, y] - 1]++;
394.                 if (x + 1 < width && grid [x, y] != grid [x + 1, y]) {
395.                     perimeter [grid [x, y] - 1]++;
396.                     perimeter [grid [x + 1, y] - 1]++;
397.                 }
398.                 if (y + 1 < height && grid [x, y] != grid [x, y + 1]) {
399.                     perimeter [grid [x, y] - 1]++;
400.                     perimeter [grid [x, y + 1] - 1]++;
401.                 }
402.             }
403.         }
404.         for (int y = 0; y < height; y++) {
405.             perimeter [grid [0, y] - 1]++;
406.             perimeter [grid [width - 1, y] - 1]++;
407.         }
408.
409.         double score = 0;
410.         for (int i = 0; i < k; i++) {
411.             score += area [i] / (perimeter [i] * perimeter [i]);
412.         }
413.         return score;
414.     }
415.
416.     struct Point {
417.         public int X;
418.         public int Y;
419.
420.         public Point(int x, int y) {
421.             this.X = x;
422.             this.Y = y;
423.         }
424.
425.         public override string ToString ()
426.         {
427.             return X + "/" + Y;
428.         }
429.     }
430. }
RAW Paste Data