kunal12libra →
-
You can use the “code sample” feature it will make your code printed correctly.
-
You can use pastebin, I find it a good way to share code.
I’ll directly discuss an approach for full points here.
F(X,Y,Z)=(X+Y)*(Y+Z) and condition to be satisfied is that Y>=X and Y>=Z as well. So now, You have Three arrays A,B,C. X will be from array A, Y will be from Array B and Z from array C. So, Suppose Array A contains a,b,c,d,e. Array B contains f,g,h,i and Array C contains j,k,l,m. First thing to do is to sort the Array A and C. By doing so, we will get to know how many elements in array A and Array C are less than particular B[i]. This will be done applying binary search for each value of B[i]. For example if after sorting A contains a,b,c,d,e and values in A which are less than or equal to B[0] are a,b,c(I’m discussing here for B[0],rest will be done in the same way) and after sorting if C contains j,k,l,m and j,k are the values which are less than B[0]. Now,
let B[0]=X then we have
(a+X)(X+j)+(a+X)(X+k)+(b+X)(X+j)+(b+X)(X+k)+(c+X)(X+j)+(c+X)(X+k)
After simplifying above calculation the formula which we get is
(( 3 * X)+(a+b+c) ) * ((2 * X)+(j+k))
In general manner :
((Number of elements in A less than or equal to B[i] multiplied by B[i] )+(sum of all the elements in A less than or equal to B[i])) * ((Number of elements in C less than or equal to B[i] multiplied by B[i])+(sum of all the elements in C less than or equal to B[i]))
This step should be done for all B[i]'s and sum of all will be our answer.
Note: Here number of elements <= B[i] can be found out by simple binary search and sum of all the elements <= B[i] can be found out by maintaining a Presum array.
AC Code: CodeChef: Practical coding for everyone
C++ users: please use scanf and printf
6 Likes
https://www.codechef.com/viewsolution/14068767
I am getting tle in one of the testcases. Can someone explain me why?
Complexity I calculated appears to be: O( q*(log p + log r) )
What I really did was sorted the A and C arrays, calculated cumulative sums of array A and C and then found the upper bound of A and C for every element in B.
I also did sort B in decreasing order so that once any element returns first element in either A or C as upper bound I just stop (since upper bound is first element aka 0th element I have none elements before it).
1 Like
The biggest mistake you are doing is sorting the b array which is wrong altogether because you need to answer the query as it is asked.
Look at my approach I did almost similar to you - link text
Ok listen…here is my approach…I first sort the x and z array using sort() function, then from given test case, I derived a formula for this problem which is (countx * y+sumx)*(countz * y+sumz) for every y where the countx = number of element in X array <= Y and similarly for countz. Sumx and Sumz represent the sum of all element which is <= Y.To find all these elements if you use linear search you will get tle , so instead of using linear search you can use binary search.that’s all and you are good to go!!
Here is link to my code…CodeChef: Practical coding for everyone
hey can anybody upvote me. I want to share my code which was executed in nlogn time
Here is my solution with 0.66sec. To solve this question You need to first solve the function and derive a simple relation which can give you the answer.For every element in B you need 4 things:
- Number of elements upto which the element in B is greater than elements in array A(sizeA)
- Number of elements upto which the element in B is greater than elements in array C(sizeC)
- Sum of all those elements in point 1.(sumA)
- Sum of all those elements in point 2.(sumC)
So I sorted all the 3 arrays in increasing order.Most people sorted only A and C but by sorting B you only need to traverse Array A and array C only once because the elements which are less than B[0] will always be lesser than B1,B[2]…B[q].
Here you go!
Observations:
- Mod in the sum also
- Make sure you have your exception of no numbers greater than B[i] taken care of
- More Mod.
P.S. Giff Karma ;-;
1 Like
this is what i tried but i am getting tle in 2 cases. Please help.
https://www.codechef.com/viewsolution/14219608
I think its complexity is O(n ln n) but i don’t know why it is giving tle. I have seen other solutions and their complexities is same.
my approach was:
1)take A elements
2)take B elements and store max element of B
3)take only those elements from C which are less than max of B
4)sort C
5)Now i for A ,j for B ,k for C
run loop till j<sizeof B
if condition satisfied if k has not reached limit and the next element is less than of B[j] increment k, otherwise if j has not reached its limit increment j, otherwise increment i.
still i got TLE please help!!!
Hey everyone ! Thanks for your awesome responses and solution links.
I learnt a lot from different approaches also realised the lame mistake I did -_-
Cheers !
1 Like
THe code which i have submitted use all the approaches discussed by you @sidhartp538 but still it is giving wrong answer in some of the cases I have applied mod after each operation , used quick sort and binary search too.I also derived the formula which seems correct to me . first the code was giving wa later it gave tle despite of the fact that the complexity of the code was same in both the cases . if anyone could precisely figure out what is the issue it will be highly appreciated . thanks!
@godslayer12 one more thing which no one pointed it is that you using lower_bound while you should be using upper_bound since you the last occurrence of element
Inspite of BinarySearch anyone can use upper_bound also.
CodeChef: Practical coding for everyone Can anyone help me with optimizing my solution? I’m getting TLE in sub-task #4 and 0.91s execution time for sub-task #5. Upvotes will be appreciated since I don’t have permission to post any new questions.
Can any one please tell me what is wrong with my code i have first sorted A and C array and then i have used upper bound stl function to determine the contribution of each element of B in the answer.This is what i tried
https://www.codechef.com/viewsolution/14196681