Page 1 of 1

USACO All latin squares

Posted: Wed Dec 06, 2006 5:42 pm
by Guardian_Shadow
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;
}

Posted: Wed Dec 06, 2006 10:09 pm
by Darko
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?

Posted: Wed Dec 06, 2006 10:45 pm
by Guardian_Shadow
Wouldn't that be cheating?
And btw, on usaco it runs regretably 1.56s or something so...

Posted: Wed Dec 06, 2006 10:53 pm
by Darko
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.

Posted: Wed Dec 06, 2006 11:13 pm
by Guardian_Shadow
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...

Posted: Sun Dec 10, 2006 2:05 pm
by Guardian_Shadow
So, no one can help?

Posted: Mon Dec 11, 2006 3:36 pm
by misof
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.

Posted: Tue Dec 12, 2006 1:00 am
by Guardian_Shadow
Well, actually, that is already implemented.