problem link:---->LAPD
BEFORE MOVING ON COOL and try it yourself first it is strictly advised…
NOW THE MOST TRICKY PART IS THAT It involved a lot of maths so if you are a matheatical geek then you can easily arrive at the equation (a-1)*(c-1)>b^2
DERIVATION CAN BE OBTAINED FROM OFFICIAL EDITORIAL ALSO …
BUT GETTING THAT EQUATION WAS NOT ENOUGH TO SOLVE THE PROBLEM IT INVOLVED A LOT OF TRICKY PART OF CODING.
Naive approach:- (Brute Force)
/* Traversing a loop from 1 to a-1 and from 1 to c-1 and from 1 to b and at each step checking for the condition that (a-1)(c-1)> b^2 and incrementing the counter but this approach would work only for first subtask of 30 marks .
c++ code snippet :-
l=0;
cin>>a>>b>>c;
for(i=1;i<=a;i++)
{
for(j=1;j<=b;j++)
{
for(k=1;k<=c;k++)
{
p=(i-1)(k-1);
q=j*j;
if(p>q)
l++;
}
}
}
cout<<l<<endl;
full code see
30 marks code
YOU CAN OPTIMISE IT SOMEWHAT TO GET CLEAR THE SECOND SUBTASK OF 50 MARKS.
FURTHER OPTIMISATION SEE IF YOU WANT TO MAKE (a-1)*(c-1)>b^2
THEN YOU NEED NOT COMPUTE ALL NUMBERS WHICH ARE GREATER THAN B IN BETWEEN 1 TO A-1
AND
ALSO ALL NUMBERS GREATER THAN B FROM 1 TO C-1 AS THESE NUMBERS WHEN MULTIPLIED WILL ALWAYS BE GREATER THSN B^2.
THUS we can finally have all such numbers as
let final answer be ans=0;
n=max(0,(a-b-1)*(c-b-1))
now we need to map all numbers less than b in a with all c and all numbers less than b in c
with a
but how for 50 points you can traverse a loop i,j,from 1 to min(a-1,b) and 1 to min(c-1,b) and for
and for each and every number i see how many numbers in c will satisfy the property (a*c)>b^2;
lets say the number a is 5 b is 2 and c is 8
since a>b and c>b too then
so if we pick i=2 in the way we are traversing bove from 1 to b then lets say
i represents values between 1 to(min(b,a-1)) and j from (1 to b)
k=(j*j)/i+1;
k is threshold(boundary of all numbers in c gretater than k when multiplied with i will give a number greater than j^2(j is b here) OK COOL.
so all numbers
which will satisfy the property will be incremented as
ans+=(max(0,c-k));
OK NICE NOW SAME THING WE DO FOR ALL NUMBERS IN C LESS THAN B NOW BE COOL AND THINK OF THE OVERALL COMPLEXITY WITH THIS APPROACH.
we are traversing a loop in every test case of size (b^2)
so every test case will not pass it will take around three seconds when b is upto 5000 for all the test cases
COOL WE CAN OPTIMISE IT AGAIN BUT BEFORE THAT LET US CHECK WE ARE HAVING RIGHT LOGIC ON CODE IMPLEMENT IT.
CODE LINK IS GIVEN BELOW FOR FIFTY POINTS.
COOL…
NOW OPTIMISATION OF ABOVE STEP IS THAT WE CAN GO FOR b^2 complexity exactly once and after that we can compute every value in O(T*B) time let us see the implementation or coding part of it.
problem link:---->LAPD
BEFORE MOVING ON COOL and try it yourself first it is strictly advised…
NOW THE MOST TRICKY PART IS THAT It involved a lot of maths so if you are a matheatical geek then you can easily arrive at the equation (a-1)*(c-1)>b^2
DERIVATION CAN BE OBTAINED FROM OFFICIAL EDITORIAL ALSO …
BUT GETTING THAT EQUATION WAS NOT ENOUGH TO SOLVE THE PROBLEM IT INVOLVED A LOT OF TRICKY PART OF CODING.
Naive approach:- (Brute Force)
/* Traversing a loop from 1 to a-1 and from 1 to c-1 and from 1 to b and at each step checking for the condition that (a-1)(c-1)> b^2 and incrementing the counter but this approach would work only for first subtask of 30 marks .
c++ code snippet :-
l=0;
cin>>a>>b>>c;
for(i=1;i<=a;i++)
{
for(j=1;j<=b;j++)
{
for(k=1;k<=c;k++)
{
p=(i-1)(k-1);
q=j*j;
if(p>q)
l++;
}
}
}
cout<<l<<endl;
full code see
30 marks code
YOU CAN OPTIMISE IT SOMEWHAT TO GET CLEAR THE SECOND SUBTASK OF 50 MARKS.
FURTHER OPTIMISATION SEE IF YOU WANT TO MAKE (a-1)*(c-1)>b^2
THEN YOU NEED NOT COMPUTE ALL NUMBERS WHICH ARE GREATER THAN B IN BETWEEN 1 TO A-1
AND
ALSO ALL NUMBERS GREATER THAN B FROM 1 TO C-1 AS THESE NUMBERS WHEN MULTIPLIED WILL ALWAYS BE GREATER THSN B^2.
THUS we can finally have all such numbers as
let final answer be ans=0;
n=max(0,(a-b-1)*(c-b-1))
now we need to map all numbers less than b in a with all c and all numbers less than b in c
with a
but how for 50 points you can traverse a loop i,j,from 1 to min(a-1,b) and 1 to min(c-1,b) and for
and for each and every number i see how many numbers in c will satisfy the property (a*c)>b^2;
lets say the number a is 5 b is 2 and c is 8
since a>b and c>b too then
so if we pick i=2 in the way we are traversing bove from 1 to b then lets say
i represents values between 1 to(min(b,a-1)) and j from (1 to b)
k=(j*j)/i+1;
k is threshold(boundary of all numbers in c gretater than k when multiplied with i will give a number greater than j^2(j is b here) OK COOL.
so all numbers
which will satisfy the property will be incremented as
ans+=(max(0,c-k));
OK NICE NOW SAME THING WE DO FOR ALL NUMBERS IN C LESS THAN B NOW BE COOL AND THINK OF THE OVERALL COMPLEXITY WITH THIS APPROACH.
we are traversing a loop in every test case of size (b^2)
so every test case will not pass it will take around three seconds when b is upto 5000 for all the test cases
COOL WE CAN OPTIMISE IT AGAIN BUT BEFORE THAT LET US CHECK WE ARE HAVING RIGHT LOGIC ON CODE IMPLEMENT IT.
CODE LINK IS GIVEN BELOW FOR FIFTY POINTS.
COOL…
NOW OPTIMISATION OF ABOVE STEP IS THAT WE CAN GO FOR b^2 complexity exactly once and after that we can compute every value in O(T*B) time let us see the implementation or coding part of it.
ACTUALLY FOR EVERY NUMBER LESS THAN B IN A OR C WHAT WE ARE computing . We are computing :-
let us say i be number between 1 to b in a then always we are evaluating iteratively the one statement given below as
j =(1 to b)
c-(j^2)/1-1+c-(j^2)/2-1+c-(j^2)/3-1 upto … c-(j^2)/j-1
this can be further simplified as
k*(c-1)-(summation of this harmonic progression of floor values that is ((j^2)/1 +(j^2)/2 +(j^20/j);
ACTUALLY FOR EVERY NUMBER LESS THAN B IN A OR C WHAT WE ARE computing . We are computing :-
let us say i be number between 1 to b in a then always we are evaluating iteratively the one statement given below as
j =(1 to b)
c-(j^2)/1-1+c-(j^2)/2-1+c-(j^2)/3-1 upto … c-(j^2)/j-1
this can be further simplified as
k*(c-1)-(summation of this harmonic progression of floor values that is ((j^2)/1 +(j^2)/2 +(j^2/j);
similarly we can acheive it for every b and every c
if you carefully analyse the things then why we are repeating for every b doing same thing in every test case we can already compute the given hp for every b in 1 to 5000 in a 5001 *5001 matrix //
and precompute the values
cool
so each entry i ,j of a matrix will give summation of
(ii/1+(ii/2)+(ii/3)…(ii)/j;
you can easily acheive this by applying prefix sum while computing the things and all this stuff can be done once only for O(B^2) time where B=b;
Now in every test case T we will not go for actual B^2 algorithm we can just compute our values with the obtained matrix and apply different cases for a,c values and remember not to add the final values with tricky part of our algo (a-j-1)*(c-j-1) for every b in 1 to b…
NOW SAY THE OVERALL TIME COMPLEXITY WILL BE O(B^2+T*B) where T is number of test cases which can be done in 10^8 computations bound in one seconds only
bE
cool dont panic just realise the idea yourself for further query see the code
and if I will get time I will reply to your doubts also…