### USACO All latin squares

Posted:

**Wed Dec 06, 2006 5:42 pm**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;
}
```