LAPD - Editorial

editorial
, , , , , ,
24

My solution is of O(T.B^2) . But I got TLE. I don’t know why.
https://www.codechef.com/viewsolution/26594355

25

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 \geq MOD

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). :slightly_smiling_face:

5 Likes
26

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

27

It can be done in O(B^2 + T*B) Time much faster than all other codes. See the link

https://www.codechef.com/viewsolution/26495543

28

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;

}

29

My solution complexity is O(T.B^2). But its still getting tle at two test cases
https://www.codechef.com/viewsolution/26645132

30

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.

31

@adsk3003

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
32

In setter’s code, code gives TLE when I replace 1.0 with 1LL in function named ‘f’. What is the reason?

33

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.

34

Setter name: Kochekov Kerim(not Karim) :slight_smile:

1 Like
36

changed , sorry :stuck_out_tongue:.

37

Yes, as the mod uses division and division uses more computation than subtraction.