## USACO All latin squares

Moderator: Board moderators

New poster
Posts: 19
Joined: Thu Oct 12, 2006 6:04 pm

### USACO All latin squares

A square arrangement of numbers

1 2 3 4 5
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4

is a 5 x 5 Latin Square because each whole number from 1 to 5 appears once and only once in each row and column.

Write a program that will compute the number of NxN Latin Squares whose first row is:

1 2 3 4 5.......N

Your program should work for any N from 2 to 7.
PROGRAM NAME: latin
INPUT FORMAT
One line containing the integer N.
SAMPLE INPUT (file latin.in)

5

OUTPUT FORMAT
A single integer telling the number of latin squares whose first row is 1 2 3 . . . N.
SAMPLE OUTPUT (file latin.out)

1344

I was wondering if anyone can tell me what can I do with this code to get the program to run less than 1s. I think I made all the necessary optimisations.

Code: Select all

``````#include<stdio.h>
int imar[8][8],imak[8][8],n,nf=1;

int smesti(int i,int j);
FILE *fin,*fout;
main()
{
int i,bbr;

fin=fopen("latin.in","r");
fscanf(fin,"%d",&n);
fclose(fin);
nf=1;
for(i=1;i<n;i++)
nf=nf*i;

for(i=1;i<=n;i++)
{
imar[i][i]=1;
imak[i][i]=1;
}

fout=fopen("latin.out","w");
bbr=smesti(2,2);
fprintf(fout,"%.0lf\n",(double)bbr*(double)nf);
fclose(fout);
return 0;
}

int smesti(int i,int j)
{
register int k,l,s=-1,priv;
register int brres=0;

if(j>n)
{
i++;
j=2;
}

if(i==n)
return 1;

for(k=1;k<=n;k++)
{
if(imar[i][k] || imak[j][k])
continue;

if(i==2 && k>=j && s!=-1)
brres+=s;
else
{
imar[i][k]=1;
imak[j][k]=1;
priv=smesti(i,j+1);
brres+=priv;
if(k>j)
s=priv;
}

imar[i][k]=0;
imak[j][k]=0;
}

return brres;
}
``````

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
I don't know, it runs under a second on my computer.

You can probably count them without actually filling the grid, but why not just calculate and hard code the answers?

New poster
Posts: 19
Joined: Thu Oct 12, 2006 6:04 pm
Wouldn't that be cheating?
And btw, on usaco it runs regretably 1.56s or something so...

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Is it in the rules or something? I don't consider it cheating, especially because you didn't just copy a sequence from somewhere, you actually calculated it. But I don't know what they think about it.

New poster
Posts: 19
Joined: Thu Oct 12, 2006 6:04 pm
Well, the way I see it, the answers should be calculated within the time limit. If you hardcode something, that means it cannot be calculated within the proposed 1 s...

New poster
Posts: 19
Joined: Thu Oct 12, 2006 6:04 pm
So, no one can help?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Use the fact that the number of latin squares of the form

Code: Select all

``````1234567
2X
3
4
5
6
7
``````
is equal for all X in {3,4,5,6,7}. I.e., instead of trying X from {1,3,4,5,6,7} here it is enough to try X=1 and X=3. This should bring your runtime under 1s.