Guest User

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