The link to my code is: http://www.codechef.com/viewsolution/5963384
My loop is running for n*m times and the time limit is 1 second. So, why am I getting a tle??
n*m*t is your complexity…a definite TLE!!!
1 Like
Yes, your code’s complexity is nmt. For optimizing it, try thinking the way that for all possible values of n and m, you’ll get the same probability array except the last row (nth) and last coloumn(mth) as per the input. The rest of the cells will have the same probabilities. So don’t you think you are computing something again and again, repeatedly?
Assuming 1-indexed, Just compute the probabilities of all the cells. For the last row, cells from a[n][2] to a[n][m] will have the increased probabilities by the way we have computed. What needs to be done here is :
for(j=2;j<n;j++)
prob[n][j]= prob[n-1][j] *0.5 + prob[n][j-1] // cell to its left in the same row will have its full contribution as it is the last row and cell above it in row n-1 will have contribution of 0.5.
Similarly, do for the last coloumn. Also, sum of probabilities for general n,m grid will remain same. So, maintain a 2-d sum grid and update the sum of last row and last coloumn.
You may like to have a look at my solution here.
PS: The soltuion if u’ll see very nearly is just n+m-1, cuz sum of every diagonal in the n*m grid after you’ll calculate the above prob[][] array comes out to be 1. So, the solution above is just for helping you improve your approach. Even I did this way only during the contest 
1 Like
How it is n-m+1 ???
Please explain a little bit more. Please
#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
float n,m;
scanf("%f %f",&n,&m);
float k=m*n;
if(n==1 || m==1)
{
if(n>m)
{
printf("%f\n",n);
}
else
{
printf("%f\n",m);
}
}
else
{
float p;
p=2+(k-2)*0.5;
printf("%f\n",p);
}
}
}
I am submitting this code but it is giving wrong answer