Can anyone help me with SUMQ from JUNE17?

help
, ,
21

Haha, exactly my point. :stuck_out_tongue:

22

link text

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:

  1. Number of elements upto which the element in B is greater than elements in array A(sizeA)
  2. Number of elements upto which the element in B is greater than elements in array C(sizeC)
  3. Sum of all those elements in point 1.(sumA)
  4. 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].

23

Here you go!
:smiley:

Observations:

  1. Mod in the sum also
  2. Make sure you have your exception of no numbers greater than B[i] taken care of
  3. More Mod.

P.S. Giff Karma ;-;

1 Like
24

PLZZ tell whats wrong in my solution.
https://www.codechef.com/viewsolution/14119092

25

Simple Implementation:
https://www.codechef.com/viewsolution/14059356

26

Here is my solution hope this will help you.
https://www.codechef.com/viewsolution/14219395

27

Image of code is worse. What do we do to that image? We can atleast copy paste code to debug it.

28

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.

29

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!!!

30 
After simplifying above calculation the formula which we get is
(( 3 * X)+(a+b+c) ) * ((2 * X)+(j+k))

How did you arrive at this result? I will appreciate hints on the thought process since i tried hard but couldnt simplify the function.

2 Likes
31

@vijju123 thanks !

1 Like
32

Enjoy the karma and thanks !

33

Step 1: (a+X)(X+j)+(a+X)(X+k)+
(b+X)(X+j)+(b+X)(X+k)+
(c+X)(X+j)+(c+X)(X+k)
Step 2: (a+X)(X+j+X+k)+
(b+X)(X+j+X+k)+
(c+X)(X+j+X+k)
Step 3: (a+X+b+X+c+X)(X+j+X+k)
Step 4: (3X+a+b+c)(2X+j+k)

1 Like
34

Damn, it was quite simple. I just opened the bracket and lmao…XD Utter Disaster XD

35

looks good

2 Likes
36

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
37

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!

38

Don’t use quicksort, its worst case tuns till On2, try some inline sort or merge sort.

39

@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

40

Inspite of BinarySearch anyone can use upper_bound also.