01Tiles - i am getting "Time exceeded"

[Jayaganesh]

Hi All,

I am new to this site and also new to c++ programing . Currently in learning stage. Recently i have appeared in Zonal informatics olympiad and have cleared and shortlisted for 2nd level (Indian computing olympiad) where i have to write programes for 2 problems.I am trying this following problem and every time it is coming as "Time exceeded" . I am not able to debug it. Pls help me out, where i am going wrong. This problem is from IARCS.org

Problem:
To help Lavanya learn all about binary numbers and binary sequences, her father has bought her a collection of square tiles, each of which has either a 0 or a 1 written on it. Her brother Nikhil has played a rather nasty prank. He has glued together pairs of tiles with 0 written on them. Lavanya now has square tiles with 1 on them and rectangular tiles with two 0's on them, made up of two square tiles with 0 stuck together). Thus, she can no longer make all possible binary sequences using these tiles.

To amuse herself, Lavanya has decided to pick a number N and try and construct as many binary sequences of length N as possible using her collection of tiles. For example if N = 1, she can only make the sequence 1. For N=2, she can make 11 and 00. For N=4, there are 5 possiblities: 0011, 0000, 1001, 1100 and 1111.

Lavanya would like you to write a program to compute the number of arrangements possible with N tiles so that she can verify that she has generated all of them. Since she cannot count beyond 15746, it is sufficient to report this number modulo 15746.

Input format

A single line with a single integer N.

Output format

A single integer indicating the number of binary sequences of length N, modulo 15746, that Lavanya can make using her tiles.

Test data

You may assume that N ≤ 1000000.

Example

Here is a sample input and output corresponding to the example discussed above.

Sample input

4
Sample output

5

CPU Timelimit: 3 seconds
Memory limit: 64M
Grading style: ioi

My coding :

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int fac(int a)
{int i,p=1;
if(a==0)
{return 1;
}
for(i=a;i>0;i++)
{p=p*i;
}
return p;
}
int tot(int n,int m)
{int i;
i=fac(n-m)/fac(m)/fac(n-m-m);
return i;
}



int main()
{
int n;
cin>>n;
int a;
a=floor(n/2);
int m,l,c,s=0;
for(m=0;m<=a;m++)
{l=tot(n,m);
s=s+l;
}
c=s%15746;
cout<<c;
}

[ne555]

[code]"Please use code tags"[/code]

> "Time exceeded"
Usually means that the order of your algorithm is too big.
For every number you do a loop from 0 to n/2, that's O(n)
Inside the loop you call the tot() function.
__ there you execute the factorial. That's O(n) because either `n-m' or `m' are as big as `n'

Total time O(n^2)
Considering that n could be as big as 1e6, the order should be around O(n lg n).


Apart. Integers have a limit in the number they can store, the operations that you're doing will likely overflow.

[Jayaganesh]

Thx for your response. As i am totally new and now only started understanding the programes, it would be helpful to me if you can explain me in little bit more detail, and also debug the above code exactly where it is to be changed, so that by seeing the corrected program, i will understand your inputs better. Please support me.

[ne555]

You need to change the algorithm, so go back to the drawing board.


About the overflow, the answer have to be modulo 15746, so apply the rules of modulo to your operations to avoid the overflow.
By instance:

(a+b) mod m = (a mod m + b mod m) mod m
(a*b) mod m = (a mod m * b mod m) mod m