fork(2) download
copy 
  1. namespace GridWits
  2. {
  3.     using System;
  4.     using System.Linq;
  5.  
  6.     /// <summary>
  7.     /// Class for solving the 'Square Fields' problem.
  8.     /// </summary>
  9.     public class SquareFields
  10.     {
  11.         /// <summary>
  12.         /// Whether to output what is going on during the algorithm.
  13.         /// </summary>
  14.         private readonly bool verbose;
  15.  
  16.         /// <summary>
  17.         /// The parameter N (number of points) (n in the original code)
  18.         /// </summary>
  19.         private int parameterN; 
  20.  
  21.         /// <summary>
  22.         /// The parameter K (number of squares required) (kk in the original code)
  23.         /// </summary>
  24.         private int parameterK;
  25.  
  26.         /// <summary>
  27.         /// The current best found solution (res in the original code)
  28.         /// </summary>
  29.         private int bestFoundSolution;
  30.  
  31.         /// <summary>
  32.         /// The x coordinates read from the problem (x[100] in the original code)
  33.         /// </summary>
  34.         private int[] xCoordinates;
  35.  
  36.         /// <summary>
  37.         /// The y coordinates read from the problem (y[100] in the original code)
  38.         /// </summary>
  39.         private int[] yCoordinates;
  40.  
  41.         /// <summary>
  42.         /// The left bounds for the squares so far (mnx[100] in the original code)
  43.         /// </summary>
  44.         private int[] leftBounds;
  45.  
  46.         /// <summary>
  47.         /// The left bounds for the squares so far (mxx[100] in the original code)
  48.         /// </summary>
  49.         private int[] rightBounds;
  50.  
  51.         /// <summary>
  52.         /// The left bounds for the squares so far (mny[100] in the original code)
  53.         /// </summary>
  54.         private int[] lowerBounds;
  55.  
  56.         /// <summary>
  57.         /// The left bounds for the squares so far (mxy[100] in the original code)
  58.         /// </summary>
  59.         private int[] upperBounds;
  60.  
  61.         /// <summary>
  62.         /// Initializes a new instance of the <see cref="GridWits.SquareFields"/> class.
  63.         /// </summary>
  64.         /// <param name="verbose">If set to <c>true</c>, be verbose.</param>
  65.         public SquareFields(bool verbose)
  66.         {
  67.             this.verbose = verbose;
  68.         }
  69.  
  70.         /// <summary>
  71.         /// Goes through all possible partitions recursively, finding the smallest possible size.
  72.         /// We stop the recursion when we have used too many squares or are already bigger than the smallest size we have found so far.
  73.         /// (Rec(i, k, sz) in the original code)
  74.         /// </summary>
  75.         /// <param name="nextPointToPlace">Next point to place. (i in the original code)</param>
  76.         /// <param name="numberOfNonemptySquares">Number of nonempty squares. (k in the original code)</param>
  77.         /// <param name="currentLargestSquareSize">Current largest square size. (sz in the original code)</param>
  78.         private void SolveRecursively(int nextPointToPlace, int numberOfNonemptySquares, int currentLargestSquareSize)
  79.         {
  80.             /* Only continue if the numberOfNonemptySquares is no larger than the final required number of squares
  81.              * and the current size is no larger than the best size found so far
  82.              */
  83.             if (numberOfNonemptySquares <= parameterK && currentLargestSquareSize <= bestFoundSolution)
  84.             {
  85.                 // If we have placed all of the points so far, see if our current size improves on the best found solution
  86.                 if (nextPointToPlace == parameterN)
  87.                 {
  88.                     if (verbose && (bestFoundSolution > currentLargestSquareSize))
  89.                         Console.WriteLine("New solution is an improvement: setting bestFoundSolution to {0}", currentLargestSquareSize);
  90.                     bestFoundSolution = Math.Min(bestFoundSolution, currentLargestSquareSize);
  91.                 } 
  92.                 else
  93.                 {
  94.                     /* Otherwise, we have a new point to place in one of our squares.
  95.                      * Since all of the empty squares are equivalent, we need only try placing our point in any of the nonempty ones 
  96.                      * (index 0 to numberOfNonEmptySquares-1) and the first empty one (index numberOfNonEmptySquares)
  97.                      */
  98.                     for (int squareIndex = 0; squareIndex <= numberOfNonemptySquares; ++squareIndex)
  99.                     {
  100.                         // store the original bounds to return to the original state after we've tried putting the point in this square;
  101.                         int originalLeftBound = leftBounds[squareIndex];
  102.                         int originalRightBound = rightBounds[squareIndex];
  103.                         int originalLowerBound = lowerBounds[squareIndex];
  104.                         int originalUpperBound = upperBounds[squareIndex];
  105.  
  106.                         // Now put the point in the square
  107.                         leftBounds[squareIndex] = Math.Min(leftBounds[squareIndex], xCoordinates[nextPointToPlace]);
  108.                         rightBounds[squareIndex] = Math.Max(rightBounds[squareIndex], xCoordinates[nextPointToPlace]);
  109.                         lowerBounds[squareIndex] = Math.Min(lowerBounds[squareIndex], yCoordinates[nextPointToPlace]);
  110.                         upperBounds[squareIndex] = Math.Max(upperBounds[squareIndex], yCoordinates[nextPointToPlace]);
  111.  
  112.                         /* Now recursively attempt to place the next point, incrementing numberOfNonemptySquares if we
  113.                          * placed our point in the first empty one.
  114.                          */
  115.                         int newSizeOfSquare = 
  116.                             Math.Max(rightBounds[squareIndex] - leftBounds[squareIndex], upperBounds[squareIndex] - lowerBounds[squareIndex]);
  117.  
  118.                         if (verbose)
  119.                         {
  120.                             Console.WriteLine(
  121.                                 "Have put point ({0},{1}) in square {2}",
  122.                                 xCoordinates[nextPointToPlace],
  123.                                 yCoordinates[nextPointToPlace],
  124.                                 squareIndex);
  125.                             Console.WriteLine(
  126.                                 "Bounds for square {0} are now ({1} to {2}, {3} to {4}), so it is of size at least {5}",
  127.                                 squareIndex,
  128.                                 leftBounds[squareIndex],
  129.                                 rightBounds[squareIndex],
  130.                                 lowerBounds[squareIndex],
  131.                                 upperBounds[squareIndex],
  132.                                 newSizeOfSquare);
  133.                         }
  134.  
  135.                         SolveRecursively(
  136.                             nextPointToPlace + 1, 
  137.                             Math.Max(numberOfNonemptySquares, squareIndex + 1),
  138.                             Math.Max(currentLargestSquareSize, newSizeOfSquare));
  139.  
  140.                         if (verbose)
  141.                         {
  142.                             Console.WriteLine(
  143.                                 "Backtracking, removing point ({0},{1}) in square {2}",
  144.                                 xCoordinates[nextPointToPlace],
  145.                                 yCoordinates[nextPointToPlace],
  146.                                 squareIndex);
  147.                             newSizeOfSquare = 
  148.                                 Math.Max(originalRightBound - originalLeftBound, originalUpperBound - originalLowerBound);
  149.                             if (originalLeftBound < 1000000)
  150.                                 Console.WriteLine(
  151.                                     "Bounds for square {0} are now ({1} to {2}, {3} to {4}), so it is of size at least {5}",
  152.                                     squareIndex,
  153.                                     originalLeftBound,
  154.                                     originalRightBound,
  155.                                     originalLowerBound,
  156.                                     originalUpperBound,
  157.                                     newSizeOfSquare);
  158.                             else
  159.                                 Console.WriteLine("Square {0} is now empty.", squareIndex);
  160.                         }
  161.  
  162.                         // now return the bounds of this square to what they were before you put the point in
  163.                         leftBounds[squareIndex] = originalLeftBound;
  164.                         rightBounds[squareIndex] = originalRightBound;
  165.                         lowerBounds[squareIndex] = originalLowerBound;
  166.                         upperBounds[squareIndex] = originalUpperBound;
  167.                     }
  168.                 }
  169.             }
  170.         }
  171.  
  172.         /// <summary>
  173.         /// Read the data, run the recursive algorithm and output the answer.
  174.         /// </summary>
  175.         public void Main()
  176.         {
  177.             int numberOfCases = int.Parse(Console.ReadLine());
  178.             for (int caseIndex = 1; caseIndex <= numberOfCases; ++caseIndex)
  179.             {
  180.                 int[] parameters = Console.ReadLine().Split(' ').Select(_ => int.Parse(_)).ToArray();
  181.                 parameterN = parameters[0];
  182.                 parameterK = parameters[1];
  183.  
  184.                 xCoordinates = new int[parameterN];
  185.                 yCoordinates = new int[parameterN];
  186.                 for (int ptIndex = 0; ptIndex < parameterN; ++ptIndex)
  187.                 {
  188.                     int[] coordinates = Console.ReadLine().Split(' ').Select(_ => int.Parse(_)).ToArray();
  189.                     xCoordinates[ptIndex] = coordinates[0];
  190.                     yCoordinates[ptIndex] = coordinates[1];
  191.                 }
  192.  
  193.                 leftBounds = new int[parameterK + 1];
  194.                 rightBounds = new int[parameterK + 1];
  195.                 lowerBounds = new int[parameterK + 1];
  196.                 upperBounds = new int[parameterK + 1];
  197.                 for (int i = 0; i <= parameterK; ++i)
  198.                 {
  199.                     lowerBounds[i] = 1000000; // 64000 would do since the coordinates are supposed to be in the range 0-64000
  200.                     upperBounds[i] = -1000000; // 0 would do since the coordinates are supposed to be in the range 0-64000
  201.                     leftBounds[i] = 1000000; // 64000 would do since the coordinates are supposed to be in the range 0-64000
  202.                     rightBounds[i] = -1000000; // 0 would do since the coordinates are supposed to be in the range 0-64000
  203.                 }
  204.  
  205.                 bestFoundSolution = 1000000; // 64000 would do
  206.                 SolveRecursively(0, 0, 0);
  207.                 Console.WriteLine(@"Case #{0}: {1}", caseIndex, bestFoundSolution);
  208.             }
  209.         }
  210.     }
  211.  
  212.     /// <summary>
  213.     /// Example solution to Code Jam Problem B
  214.     /// </summary>
  215.     public class CodeJamProblemB
  216.     {
  217.         /// <summary>
  218.         /// The entry point of the program, where the program control starts and ends.
  219.         /// </summary>
  220.         /// <param name="args">The command-line arguments.</param>
  221.         static void Main(string[] args)
  222.         {
  223.             var sf = new SquareFields(false);
  224.             sf.Main();
  225.         }
  226.     }
  227. }
  228.  
  229.  
Success #stdin #stdout 0.04s 24264KB
comments (?)
stdin
copy 
2
5 2
1 1
2 2
3 3
6 6
7 8
3 2
3 3
3 6
6 9
stdout
copy 
Case #1: 2
Case #2: 3
https://ideone.com/TNrdFO
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!