Key Information

Register
Submit
The challenge is finished.

Challenge Overview

Important Links

  • Submission-Review You can find your submissions artifacts here  Artifacts will contain output.txt's for both example test cases and provisional test cases with stdout/stderr and individual test case scores. 
  • Other Details For other details like Processing Server Specifications, Submission Queue, Example Test Cases Execution
  • Sample Submissions/ Tester / Source Files are now also available in the Download Section on the top right. This section will only be visible once you have registered for the match.

Problem Statement

Given an NxN grid of numbers your task is to move the numbers to their target locations. A number n at row r and column c (both 0-based) is in its target location if n = r*N + c + 1. A move consists of selecting a square subgrid and rotating all its numbers by 90 degrees clockwise or counter clockwise. Rotating a subgrid of size S (2 <= S <= N) incurs a penalty of floor((S-1)^1.5). A number that does not finish in its target location is penalized by P*dist, where P is a weighting input parameter and dist is the Manhattan distance to its target location. Your task is to minimize the total penalty.

Here is an example solution for seed=1 and N=4. The subgrid currently being rotated is highlighted in blue for clockwise rotations and in red for counter clockwise rotations. The cells are painted green based on how close their number is to the target location.

Implementation

Your code will receive as input the following values, each on a separate line:

  • N, the size of the grid.
  • P, the weighting parameter.
  • N*N lines, each with a single integer representing the numbers in the grid. The number in the cell with row r and column c (both 0-based) will be on line r*N+c.

Your code should write to output the following:

  • On the first line, the number of moves M.
  • M lines, each representing a single move. A move is formatted as 4 space-separated terms [r c s dir] (without the brackets), where r is the top row of the subgrid (0-based), c is the left column of the subgrid (0-based), s is the size of the subgrid and dir is the rotation direction: "R" for clockwise and "L" for counter clockwise.

Scoring

Rotating a subgrid of size S incurs a penalty of floor((S-1)^1.5). A number that does not finish in its target location incurs a penalty of P*dist, where P is a weighting input parameter and dist is the Manhattan distance to its target location. Your raw score for a test case is the total of all penalties. If your return was invalid then your raw score on this test case will be -1. Possible reasons include:

  • Illegally formatted moves or moves that are out of bounds.
  • Using more than 100,000 moves.

If your raw score for a test case is negative then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is MIN/YOUR, where YOUR is your raw score and MIN is the smallest positive raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, the sum of all your test scores is normalised to 100.

Test Case Generation

Please look at the visualizer's source code for the exact details about test case generation. Each test case is generated as follows:

  • Generate the size of the grid N, randomly chosen between 4 and 40, inclusive.
  • Generate the weighting parameter P, randomly chosen between 1 and 10, inclusive.
  • Generate the grid. This is a random permutation of numbers between 1 and N*N, inclusive.
  • All values are chosen uniformly at random.

Notes

  • The Manhattan distance between locations (r1,c1) and (r2,c2) is abs(r1-r2) + abs(c1-c2).
  • The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
  • The compilation time limit is 30 seconds.
  • There are 10 example test cases and 100 full submission (provisional) test cases. There will be 2000 test cases in the final testing.
  • The match is rated.

Languages Supported

C#, Java, C++ and Python

Submission Format

Your submission must be a single ZIP file not larger than 500 MB, with your Source Code only:
Please Note: Please zip only the file. Do not put it inside a folder before zipping, you should directly zip the file.

Make sure you name your Source Code file as RotatingNumbers.<appropriate extension>

  • Java Source Code - RotatingNumbers.java
  • C++ Source Code - RotatingNumbers.cpp
  • Python3.6 Source Code - RotatingNumbers.py
  • C# Source Code - RotatingNumbers.cs

Tools

An offline tester is available below. You can use it to test/debug your solution locally. You can also check its source code for an exact implementation of test case generation and score calculation. You can also find links to useful information and sample solutions in several languages.

Sample Submissions

Here are example solutions for different languages, modified to be executed with the visualizer. You may modify and submit these example solutions.

Offline Tester / Visualizer

In order to use the offline tester/visualizer tool for testing your solution locally, you'll have to modify your solution by adding the main method that interacts with the tester/visualizer via reading data from standard input and writing data to standard output.

To run the tester with your solution, you should run:

java -jar tester.jar -exec "<command>" -seed <seed>

Here, <command> is the command to execute your program, and <seed> is seed for test case generation. If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\solution.exe" or "~/topcoder/solution". In case your compiled solution is to be run with the help of an interpreter, for example, if you program in Java, the command will be something like "java -cp C:\TopCoder Solution".

Additionally you can use the following options:

  • -seed <seed>. Sets the seed used for test case generation, default is seed 1.
  • -novis. Turn off visualization.
  • -debug. Print debug information.
  • -sz <cell size>. Use custom grid size, default is 20 pixels. If size is set to 0 then the full screen is used.
  • -delay <delay>. Sets the delay (in milliseconds) between visualizing consecutive simulation steps, default is 500. If the delay is less than 20 then rotations are not shown.
  • -N <N>. Sets a custom size of the grid.
  • -P <P>. Sets a custom weighting parameter.
  • -pause. Starts visualizer in paused mode. See more information below.

The visualizer works in two modes. In regular mode, steps are visualized one after another with a delay specified with the -delay parameter. In paused mode, the next move will be visualized only when you press any key. The space key can be used to switch between regular and paused modes. The default starting mode is regular. You can use the -pause parameter to start in paused mode.

Finally, you can print any debug information of your solution to standard error, and it will be forwarded to the standard out of the tester.

Helpful Information

ELIGIBLE EVENTS:

2020 Topcoder(R) Open

SHARE:

ID: 30122730