ANARC07C - Rotating Rings


Any square grid can be viewed as one or more rings, one inside the other. For example, as shown in figure (a), a 5 × 5 grid is made of three rings, numbered 1, 2 and 3 (from outside to inside.) A square grid of size N is said to be sorted, if it includes the values from 1 to N^2 in a row-major order, as shown in figure (b) for N = 4. We would like to determine if a given square grid can be sorted by only rotating its rings. For example, the grid in figure (c) can be sorted by rotating the first ring two places counter-clockwise, and rotating the second ring one place in the clockwise direction.

Input

Your program will be tested on one or more test cases. The first input line of a test case is an integer N which is the size of the grid. N input lines will follow, each line made of N integer values specifying the values in the grid in a row-major order. Note than 0

The end of the test cases is identified with a dummy test case with N = 0.

Output

For each test case, output the result on a single line using the following format:

k. result

Where k is the test case number (starting at 1,) and result is "YES" or "NO" (without the double quotes.) and single space between "." and "result".

Sample

Input:
4
9 5 1 2
13 7 11 3
14 6 10 4
15 16 12 8
3
1 2 3
5 6 7
8 9 4
0

Output:
1. YES
2. NO

hide comments
nadstratosfer: 2019-12-08 03:34:07

Unexpected AC in PyPy despite ridiculous TL. Some nasty suprises on the way but nothing that contradicts the statement so I guess the problem is OK.

Regarding the confusion in the comments, the fact that grid may be already sorted should have no effect on your algorithm.

Edit 2021-10-13: With the new TL pure Python can pass too.

Last edit: 2021-10-13 00:34:42
ahmed Ibrahim: 2016-08-20 01:27:17

Finally AC wooooooooooooooooooooooooow

randomguywithoutaname: 2014-09-16 03:27:04

@vr_geeks: It's the I/O that constrains this problem for Java. Even code that isn't fully optimized will pass with a fast enough input parser.

vr_geeks: 2013-02-09 02:48:21

Can this problem be solved using java??Myself always getting a TLE...even though my code is optimum

beginner :(: 2012-06-15 13:35:21

so if the matrix is already sorted row wise and column wise ,is the ans "NO" as no rotations are required ????

Last edit: 2012-06-15 13:38:32
Balasubramanian: 2011-11-23 17:36:51

For those solving this problem,
Well, the answer for n=1 is not always "NO".
Read the problem statement carefully(specially the first paragraph).

Last edit: 2011-11-23 17:37:34
Santiago Palacio: 2011-06-09 00:43:40

What I/O should you use instead of scanf? (in c++) as, by rajeshamal comment, it may not work.

Gurpreet Singh: 2011-03-25 20:19:09

OK!!!!
for n=1 ans is NO!!!!

:D: 2011-03-12 19:12:04

A how many rotations do you need to sort 1x1 grid of single element '1' ?

Dunno: 2011-03-12 13:41:38

uhmm, What answer should be when N equals with 1.. ?


Added by:psetter
Date:2009-07-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ANARC 2007