I guess i too have same complexity but still three tests gave LTE . Help appreciated 
https://www.codechef.com/viewsolution/26412472
You are getting TLE because of using mod too many times use
if(val > mod) val -= mod;
instead
1 Like
I knew that the % operator is slow but never knew that it could be the difference between a TLE and AC & I have never seen it happen on any other site.
TLE: CodeChef: Practical coding for everyone
AC: CodeChef: Practical coding for everyone
why discriminant should be negative and why imaginary roots??
def func2(A, B, C):
s = 0
for b in range(1, B+1):
x = b**2
if A>b and C>b:
s+=(A-b)*(C-b)-1
for a in range(1, min(A, b)):
s+= max(0, C - (x/a)-1)
for a in range(1, min(C, b)):
s+= max(0, A - (x/a)-1)
#print s,
return s
for _ in range(input()):
A, B, C = map(int, raw_input().split())
#print brute(A, B, C),'\t'
print func2(A, B, C)
how is this code not working???
PLEASE HELP
can you check my approach its bit similar :https://discuss.codechef.com/t/how-codechef-test-the-programme-because-its-tuff-for-me-to-debug-my-code/38270
its giving WA for large cases
Time Complexity can be decreased further : O(B^2 + T*B).
Using DP is the key to decrease the Time Complexity.
Here’s the solution
https://www.codechef.com/viewsolution/26606903
It will work only when ans<2m.
If ans>2m:
ans-m>m
But , ans%m must be less than m.
1 Like
because the value quadratic equation is always positive so It does not cut the x-axis so roots should be imaginary , hence b^2<ac
Why using modulo operator is slower ? It does the same thing.
My solution is of O(T.B^2) . But I got TLE. I don’t know why.
https://www.codechef.com/viewsolution/26594355
Here’s some C++ code, where a \geq 0:
#include <iostream>
int main (void ) {
int MOD = 1'000'000'007;
int a;
std::cin >> a;
int res = a % MOD;
return 0;
}
--------------------------(1)
There are 2 cases:
Case 1
a<MOD
Here, res should store a.
Case 2
a\geqMOD
Here, res should store a \% MOD.
Here is the assembly generated for main of code (1):
_main:
leal 4(%esp), %ecx
andl $-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
pushl %ecx
subl $36, %esp
call ___main
movl $1000000007, -12(%ebp)
leal -20(%ebp), %eax
movl %eax, (%esp)
movl $__ZSt3cin, %ecx
call __ZNSirsERi
subl $4, %esp
movl -20(%ebp), %eax
cltd
idivl -12(%ebp)
movl %edx, -16(%ebp)
movl $0, %eax
movl -4(%ebp), %ecx
leave
leal -4(%ecx), %esp
ret
Let’s see what happens for the so-called better code:
#include <iostream>
int main (void ) {
int MOD = 1'000'000'007;
int a;
std::cin >> a;
int res = a < MOD ? a : a % MOD;
return 0;
}
--------------------------(2)
Let’s look at the assembly generated for the main of code (2):
_main:
leal 4(%esp), %ecx
andl $-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
pushl %ecx
subl $36, %esp
call ___main
movl $1000000007, -12(%ebp)
leal -20(%ebp), %eax
movl %eax, (%esp)
movl $__ZSt3cin, %ecx
call __ZNSirsERi
subl $4, %esp
movl -20(%ebp), %eax
cmpl -12(%ebp), %eax
jl L2
movl -20(%ebp), %eax
cltd
idivl -12(%ebp)
movl %edx, %eax
jmp L3
We can clearly see that the compiler isn’t doing any optimization for us if we are not using the conditional. In the assembly of code (1), line 17 and 18, we have:
cltd
idivl -12(%ebp)
But, in the other one, lines 17 to 21, we have:
cmpl -12(%ebp)
jl L2
movl -20(%ebp), %eax
cltd
idivl -12(%ebp)
Where,
L2:
movl -20(%ebp), %eax
Clearly, these are both different. Important instructions: cltd, idivl and cmpl. First, try to find out the time taken to run these instructions on the machine your code is running on when it’s being submitted. By simply comparing the times taken by these instructions, you can find out which one is faster. My bets are on code (2). 
5 Likes
This one is your second case and still not working
https://www.codechef.com/viewsolution/26643425
But in this one (CodeChef: Practical coding for everyone) I did
count -= mod
instead of
count = count%mod
It can be done in O(B^2 + T*B) Time much faster than all other codes. See the link
my code complexity is also O(T*B^2). But I got TLE
#include <stdio.h>
#include
#define int long long
using namespace std;
int mod=1e9+7;
int32_t main()
{
int t;
scanf("%lld",&t);
while(t–){
int A,B,C,ans=0;
scanf("%lld%lld%lld",&A,&B,&C);
for(int b=1;b<=B;b++){
//bb>=ac;
ans+=(A-1)(C-1) - min(b,A-1)min(b,C-1);
//cout<<ans << " \n";
int sz1=min(b,A),sz2=min(b,C);
if(sz1<=sz2){
for(int i = 1 ; i < sz1 ; ++i){
if (C-1 > b ) {
ans-=min((bb)/i,C-1)-b ;
}
if (A-1 > b) {
ans-= min((bb)/i,A-1)-b;
}
}
for(int i=sz1;i<sz2;i++){
if (A-1 > b) {
ans-= min((bb)/i,A-1)-b;
}
}
}
else{
for(int i = 1 ; i < sz2 ; ++i){
if (C-1 > b ) {
ans-=min((bb)/i,C-1)-b ;
}
if (A-1 > b) {
ans-= min((bb)/i,A-1)-b;
}
}
for(int i=sz2;i<sz1;i++){
if (C-1 > b ) {
ans-=min((bb)/i,C-1)-b ;
}
}
}
//cout<<ans << " \n";
ans%=mod;
}
printf("%lld\n",ans);
}
return 0;
}
My solution complexity is O(T.B^2). But its still getting tle at two test cases
https://www.codechef.com/viewsolution/26645132
Please once check my code[CodeChef: Practical coding for everyone](http://My Code).
I am following same approach as per you mentioned.let me know what is the mistake with this solution.
The % operation requires division which is slow. performance - Why is division more expensive than multiplication? - Stack Overflow
In case of doing something like if(val > mod) val -= mod;, you’re using subtraction which is a lot faster than division.
1 Like
In setter’s code, code gives TLE when I replace 1.0 with 1LL in function named ‘f’. What is the reason?
int main()
{
int t,a,b,c,x,k,p,count;
cin>>t;
while(t–)
{cin>>a>>b>>c;
count=0;
k=min(a,c);
p=max(a,c);
for(int i=1;i<=b;i++)
{if(k-i-1>0)
count=(count+((k-(i+1))1LL(p-(i+1)))%1000000007)%1000000007;
for(int j=2;j<=min(k,i+1);j++)
{x=((int)((i1.0i)/(j-1))+2)%1000000007;
if((p-x+1)>0)
count=(count+(p-x+1)%1000000007)%1000000007;
if((k-x+1)>0)
count=(count+(k-x+1)%1000000007)%1000000007;
}
}
cout<<count<<endl;
}
return 0;
}
THIS CODE SHOWS TLE.
#include
using namespace std;
int main()
{
int t,a,b,c,x,k,p,count;
cin>>t;
while(t–)
{cin>>a>>b>>c;
count=0;
k=min(a,c);
p=max(a,c);
for(int i=1;i<=b;i++)
{if(k-i-1>0)
count=(count+((k-(i+1))1LL(p-(i+1))))%1000000007;
for(int j=2;j<=min(k,i+1);j++)
{x=(((i*i)/(j-1))+2);
if((p-x+1)>0)
count=(count+(p-x+1))%1000000007;
if((k-x+1)>0)
count=(count+(k-x+1))%1000000007;
}
}
cout<<count<<endl;
}
return 0;
}
BUT THIS CODE PASSES ALL TEST CASES. DOES REMOVING 1-2 MOD MAKE SUCH A SIGNIFICANT DIFFERENCE?? PLEASE CLEAR MY DOUBT.