Can anyone help me with SUMQ from JUNE17 ?

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.

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

@siddharthp538 Hey I understood the approach and followed it, still getting a TLE for larger inputs.
Pls help me out.

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

1 Like

I keep getting WA in some test cases, and i am not able to identify the case.

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

Thank you.

help needed !!
donno y im getting WA and TLE !!
pls help me out !!
link to my code : CodeChef: Practical coding for everyone

a far more simple approach will br just twist the formula …
lets go with the test case given …
sort the 1st and 3rd arrays!
store their presums in two different arrays,sum1 and sum2

now just transverse in the 2nd array from 1st elemnt to lst elmnt … and suppse in the tst case we get 1st elemnt as 5 then using upper bound find the uppr bound of 5 in the 1st array and then the upper bound in the 3rd array … you get the elemnts as (1,2,3) and (4,5) ,use binary srch to do rther then linear search ,…
now twick the formula to ((1+2+3)+(3 * 5)) * ( (4+5)+(2 * 5))
do it for every elemnt in the 2ND ARRAY… here 3 * 5 (3 refers to the count of elemnts less then equals 5) and 2 * 5 , 2 the no of elemnts less then equals 5 .
keep doing it for all elemnts and then just simply print the answer…

do use modulo in every summation steps carefully.else u may get a wrng answer …
here’s my code for reference !
https://www.codechef.com/viewsolution/14087847

What’s wrong with my implementation ?? I know it’s not optimized but is should work for small subtask
any help would be appreciated.
https://www.codechef.com/viewsolution/14059882

Sorry for posting this here(lack of karma points :|) ; I had adopted a similar approach to the one mentioned in the comments; however I got a WA for all my testcases. I would be thankful if anyone could take a look (nSLdfk - Online C++ Compiler & Debugging Tool - Ideone.com). Regards.

This is my code : CodeChef: Practical coding for everyone
i think my approach is ok. but somehow I can’t realise the cause of WA. please help!!

Thanks btw.

I did try that, but it didn’t work.
I think the formula i wrote needs some modifications and adjustments to handle the overflow.

Okay thanks lemme try that.

got my mistake, will try in practice section

Enjoy the karma.

1 Like

U’re doing the same mistake i mid, break down your formula, use modulus properties and take modulus at each step

Just a link to ideone could have helped…

3 Likes