We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. NP Complete
  4. Spies, Revised

Spies, Revised

Problem
Submissions
Leaderboard
Discussions

Two spies in a grid will have their covers blown if:

  1. They are both in the same row.
  2. They are both in the same column.
  3. They can see each other diagonally (i.e., lie in a line inclined ° or ° to the base of the grid).

The level of danger is now increased! In addition to the conditions above, no spies may lie in any straight line. This line need not be aligned ° or ° to the base of grid.

Write a program in the language of your choice to place spies (one spy per row) on an grid without blowing anyone's cover. Your program must then print the following lines describing a valid configuration:

  1. The value of .
  2. A space-separated list of -indexed column numbers, where each value is the column number of the spy in row (where ).

Solve this problem for as large as possible, up to (and including) .

Note: Run and Custom Input are not available for this challenge; you must click Submit Code for your submission to be scored. Your score for this challenge will always be the maximum value scored by any of your submissions.

Examples
In the examples below, denotes a spy and * denotes an empty cell.

Sample Configuration 0

A valid configuration for :  

* S * * * * * * * * * 
* * * S * * * * * * * 
* * * * * * S * * * * 
S * * * * * * * * * * 
* * * * * * * S * * * 
* * * * * * * * * * S 
* * * * S * * * * * * 
* * S * * * * * * * * 
* * * * * * * * S * * 
* * * * * S * * * * * 
* * * * * * * * * S * 

Sample Output 0

This C++ code:

#include <stdio>  
using namespace std;  

int main(){  
    cout << "11\n" ;  
    cout << "2 4 7 1 8 11 5 3 9 6 10" ;  
    return 0 ;  
}  

Produces this output:

11
2 4 7 1 8 11 5 3 9 6 10 

This configuration will earn a score of .

Sample Configuration 1

A valid configuration for :

S * * * * * * * * * * * * 
* * S * * * * * * * * * * 
* * * * * * * * * * * S * 
* * * * * * * * * S * * * 
* * * * * * S * * * * * * 
* S * * * * * * * * * * * 
* * * * * * * * * * S * * 
* * * * S * * * * * * * * 
* * * * * * * S * * * * * 
* * * * * * * * * * * * S 
* * * * * * * * S * * * * 
* * * S * * * * * * * * * 
* * * * * S * * * * * * *

Sample Output 1

This Python code:

print "13"  
print "1 3 12 10 7 2 11 5 8 13 9 4 6"

Produces this output:

13
1 3 12 10 7 2 11 5 8 13 9 4 6

This configuration will earn a score of .

Sample Configuration 2

An invalid configuration for :

S * * * * * * 
* * S * * * * 
* * * * S * * 
* * * * * * S 
* S * * * * * 
* * * S * * * 
* * * * * S * 

Sample Output 2

The following output:

7
1 3 5 7 2 4 6 

will earn a score of because the spies in the first rows are in a straight line as are the spies in the next rows.

Input Format

There is no input for this challenge.

Constraints

  • is odd.
  • (Do not submit for any value of larger than )

Scoring
A correct configuration will get a score of .

Output Format

Print the following lines of output:

  1. The first line should be a single integer denoting the value of .
  2. The second line should contain a space-separated list of integers. Each integer (where ) should be the -indexed column number where the spy in row is located.

Author

HackerRank

Difficulty

Expert

Cutoff Score

99.90

Max Score

100

Submitted By

3827

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature