PSHTRG [Unofficial Editorial] (Pishty and Triangles) MARCH LONG

general
, , ,
5

Anybody plz tell me why i am getting TLE for this solution : link text

6

Heyy… Can anyone provide the editorial for the problem Chef And GCD queries(GCDCNT). I tried to solve the problem and my complexity for each query was around O(2^6 log(n)) but still it gave TLE. Here is the link to my soln.

7

Nice Editorial. For similar problems, check out yandex problem D(the last round ie (waitt… last or the second last… i forgot XD)). Also, Polish informatics Olympiad’s problem : triangles and triangles2

1 Like
8

My solution: CodeChef: Practical coding for everyone

I have used square root decomposition. Each segment is sorted using TreeSet for logarithmic time complexity.Each query in √n log n time using heap.

2 Likes
9

thanks, @harshmmodi Now I understand the reason behind the value of K = 45 or 50 in the official editorial.

10

My solution

I used iterative segment tree as described here. Very efficient and easy to implement/debug/personalise.

1 Like
11

@doramon u r getting wrong because of the size of temporary array which is b[60] set the size to 90 because u can have 45 +45 from the fibonacci series
But suprisingly the last test case is timing out

Link:CodeChef: Practical coding for everyone

12

Happy to hear that it helped :slight_smile:

13

@doramon change all those 30’s to 50’s , 29’s to 49’s and 60’s to 100’s and run… it may work then

14

Yes, you are completely correct that the temp array is not required. I included it just so that its easier for others to understand. (But, should’ve mentioned that it’s not necessary :’) )

And as far as that 40th number is concerned, I think there’s some confusion. 40th number is 102334155 which is less than 1e9.

15

Oh… Miscounted digits…

I guess i miscounted digits of 40th fib number :stuck_out_tongue:

TCs didnt include a failing test case, because my soln passed with 40.

16

In every node of the tree, you are storing all the elements in its span. This is giving TLE. Store only those elements which form the largest valid triangle and those greater than these sides. You may read the Approach for building the segment tree written above

17

Happy to hear that :slight_smile:

18

Can you please explain your solution. What are you storing in bucket of n^(1/2) and how are u handling the queries.

19

For query, I have used a PriorityQueue (Heap). In this heap, I have inserted the max value from each bucket (and their bucket index). Complexity: √(N).log N

Now, the tricky part. I have 'poll’ed the maximum value from the heap and inserted the next largest value in that bucket

Suppose the heap contains [9,5,4]. 9 is polled. The next largest value from the bucket containing the ‘9’ is added to the heap, say 3. So, the heap becomes [5,4,3]. Again 5 is polled and so on…

The last tricky part: handling multiple occurrence of the same value.
For this, TreeMap is used all over instead of TreeSet

20

Each bucket is just a frequency record, containing the frequency of each value in that segment.

TreeMap is used for that purpose.

21

thank you sir for the editorial :slight_smile: please keep posting such awesome contents for us to learn :slight_smile:

22

I need some reputation points… Please upvote this comment /\

Official editorial is out… and here’s my solution which breaks the range in blocks of 60 and solves the problem.

23

can u explain the get function in your solution?

24

can u please explain the approach?