TopcoderArchiveVisit Topcoder
Archive
Algorithm problem

DeLaLoubere

Problem statement, definition, constraints, and public examples.

Problem Statement

Given an odd number size, you will fill a size-by-size square with values using de la Loubere's method. The method works as follows:
  • 1) Place a 1 at the middle of the top row.
  • 2) Successive integers should be added, moving up and to the right in a diagonal line.
  • 3) When the top row is reached, the next integer should be placed as if the bottom row came above the top row.
  • 4) When the rightmost column is reached, the next integer should be placed as if the leftmost column came to the right of the rightmost column. Note that both rules 3 and 4 can be applied simultaneously.
  • 5) When a square is reached that already contains a number, use the square below the last square filled.
Let's try this method on a 3x3 square. Spaces will be denoted by '.' characters.
.1.  .1.  .1.  .1.  .1.  .16  .16  816  816
...  ...  3..  3..  35.  35.  357  357  357
...  ..2  ..2  4.2  4.2  4.2  4.2  4.2  492

 1    2    3    4    5    6    7    8    9      Step Number
In addition to the size of the square to be built, you will be given two int[]s rows and cols. They are 0-based values that, together, specify spots in the filled square. You will return a int[] with the same number of elements as rows. The ith element of the returned int[] will be the number whose row and column are specified by the ith elements of rows and cols, respectively. Row 0 is the topmost row and col 0 is the leftmost column.

Definition

Class:
DeLaLoubere
Method:
getValue
Parameters:
int, int[], int[]
Returns:
int[]
Method signature:
int[] getValue(int size, int[] rows, int[] cols)
(be sure your method is public)

Notes

  • size will be between 3 and 40001 inclusive.
  • size will be odd.
  • rows will contain between 1 and 50 elements inclusive.
  • cols will contain the same number of elements as rows.
  • Each element of rows will be between 0 and size-1 inclusive.
  • Each element of cols will be between 0 and size-1 inclusive.

Constraints

    Examples

    1. 3
      {0,0,0,1,1,1,2,2,2}
      {0,1,2,0,1,2,0,1,2}
      Returns: { 8,  1,  6,  3,  5,  7,  4,  9,  2 }
      As above.
    2. 11
      {0}
      {5}
      Returns: { 1 }
    3. 5
      {1,2,3}
      {1,0,4}
      Returns: { 5,  4,  3 }
    Back to all problems