Al Zimmermann's Programming Contests

Searchin' For Kurchan

Pandiagonal Multiplicative Squares

suggested by Dmitry Kamenetsky and Anurag Sahay
including an idea from Rodolfo Marcelo Kurchan

Introduction

Place the numbers 1, 2, 3, ..., N*N on a NxN square such that the products of its rows, columns, diagonals and broken diagonals have certain properties.

The Task

The contest is divided into 3 parts:
Let's take a 3x3 example:
5 1 8
3 9 4
7 2 6

The horizontals products are:
  • 5*1*8 = 40
  • 3*9*4 = 108
  • 7*2*6 = 84
5 1 8
3 9 4
7 2 6
The vertical products are:
  • 5*3*7 = 105
  • 1*9*2 = 18
  • 8*4*6 = 192
5 1 8
3 9 4
7 2 6
The diagonals (top-left to bottom right, diagonal + two broken diagonals) products are:
  • 5*9*6 = 270
  • 1*4*7 = 28
  • 8*3*2 = 48
5 1 8
3 9 4
7 2 6
The antidiagonals (top-right to bottom left, diagonal + two broken diagonals) products are:
  • 8*9*7 = 504
  • 1*3*6 = 18
  • 5*4*2 = 40
5 1 8
3 9 4
7 2 6
The sum of all the products is: 40+108+84+105+18+192+270+28+48+504+18+40=1455
The smallest product is 18, and the largest is 504, thus its Kurchan score is 504-18=486

Your result has to be submitted as a list of numbers from 1 to N*N separated by spaces.
The above square could be submitted as: 
5 1 8 3 9 4 7 2 6
Note: all characters other than digits are translated into spaces.

The Scoring System

When you submit a N*N square, the scorer computes two numbers: If your submission establishes a new record or if it matches the existing record, you'll get a score of 1.0.
Otherwise, if your submission for a particular N improves your previous result for any of the three problem classes, its corresponding score(s) will be:

R = the current record for the considered part

Part 1 (maximal square) Q=log10(1-(S/R))
Score = Q/(Q-1)
Part 2 (minimal square) Q=log10(1-(R/S))
Score = Q/(Q-1)
Part 3 (Kurchan square) Score = R/D

Total Scoring

Your score for every part is the sum of all single problem scores.
Since there are 17 problems for each part, the best total score you can get is 17 for each part.
If you do not submit for a particular square N*N, you will receive a 0 for that square.
Each submission will be considered in all 3 problem classes.
The first submission for one N will produce 3 scores, one in each problem class.
Apart from these first submissions, a single submission will normally only lead to a score improvement in the one class to which it is targeted.
A minimum of 51 submissions is thus required to properly address all problems.

Prizes

First prize for every part is $90, second prize is $45.
In case of a tie, the entrant who reached the tied score first wins.

At the end of every week for the first 10 weeks, the contestant who has the highest cumulated sum of the 3 parts will win $10.

Five special prizes of $20 each will be awarded to the winners of those of the 51 problems that have only one record holder at the end of the contest. The 5 prizes will be allocated to the problems in the order of increasing N.

All prizes will be paid via Paypal when possible, or via Western Union in the other cases.

Organization

As the organizers, we may change the rules during this contest.

Thanks

Special thanks to:

Questions ?
Return to the index