You are not logged in. Please login at www.codechef.com to post your questions!

×

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

15
9

Difficulty : Medium
Prerequisites : Segment Tree
Problem : Given n sides,there are two types of queries: Update one of the sides or Find the maximum possible perimeter of a non-degenerate triangle whose sides are in a[l]...a[r]

Approach for subtask-1 and subtask-2 (Brute Force) :
For query of type 1, simply change the value of the element at the required position

For query of type 2, copy the elements a[l]...a[r] (both inclusive) into a temporary array, say S. Sort this array in descending order. Starting from the first element, find the first three consecutive elements which can form a valid triangle i.e. if the three sides are a,b and c, then,
(a+b > c) and (b+c > a) and (a+c > b)
If such a triangle exists, print the sum of the three sides. Else print $0$ if no triangle can be formed.

Time Complexity : $O(N^2\log_{2}N)$

Analysis for subtask-3 :
Here, we will use a segment tree which will appear exactly same as a Merge-Sort tree. We will keep only those elements which form the largest valid triangle and those greater than these sides. First, lets analize the number of elements in each node of the tree.

For a list of sides to not form a valid triangle, the side length must be such that when the sides are sorted, every element is atleast the sum of previous two elements. In the worst case, the values may be of the form:
1, 2, 3, 5, 8, 13, 21, and so on...
This is nothing but the Fibonacci Series. In this series, the $44th$ number is $1134903170$ which is greater than $10^9$. This is an important conclusion as this means that if a node contains NO valid triangle, than it will AT MAX hold Just 43 values
Thus, any node in the segment tree will hold at max 45 values where the sides are of the form:
$1, 1, 1, 2, 3, 5, 8, 13...$ and so on till $701408733$

Approach :
Building the Segment Tree: Each node of the segment tree will store a vector which is built as follows. Starting from the root, travel through to the leaf. Store the value of the corresponding array element in the leaf. Now for each parent, first create a temporary array and store the elements of its children in sorted merge way.

For example, say there are two vectors, v1 and v2, for the two children. Keep two pointers p1 and p2, one for each vector, initialized to $0$. Add the smaller element out of v1[p1] and v2[p2] to our temporary array and increment the corresponding pointer. If one of the list exhausts, add the remaining elements of the other list to the temporary array. It's important to know that the total number of elements in the temporary array will not be greater than 90.

Now, starting from the third element from the last, travel linearly to find the first set of three consecutive elements which form a valid triangle. Say elements T[i],T[i+1] and T[i+2] form a valid triangle. Store the elements from T[i] till the end of array in the node. It's safe to say that the side lengths smaller than T[i] will never contribute to the triangle of the largest perimeter.
If no valid triangle exists, store all the elements from the temporary array.

For query of type 1, starting from the root, traverse through to the leaf, change the value of the lone element in the leaf to the new value. Now, when travelling backwards, for each parent, perform sorted merge of the vectors of the children nodes in exactly the same manner as that in building the tree.

For query of type 2, there can be three cases for each node:
The span of current node is completely outside the query range: Return an empty vector.

The span of current node is completely inside the query range: Return the vector present in the node.

The span of current node intersects partially with the query range: Make a call to each of its children. Merge the two vectors it has got from its children in the same manner as dpne during building, and return the Merged-Sorted Vector.

Now, in the main method, linearly travel from the third element from the last in the vector received to find three consecutive elements which can form a valid triangle. The sum of these three elements is our required answer. If no such trio exists, then $0$ is our answer.

Time Complexity: For either type of query, in the worst case, we may have to travel to a leaf and return.
So, complexity is $O(90\log_{2}N)$ per query.
Overall Complexity: $O(90*Q\log_{2}N) \approx O(Q\log_{2}N) $

This is the link to my code.
Hope this editorial helps. I'll be glad to clear doubts and hear other solutions.

This question is marked "community wiki".

asked 12 Mar, 23:36

harshmmodi's gravatar image

5★harshmmodi
4117
accept rate: 0%

edited 13 Mar, 19:23

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

(22 Mar, 06:50) sumitjha43213★

Will surely try to do that :)

(23 Mar, 22:08) harshmmodi5★

My solution: https://www.codechef.com/viewsolution/17653578

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.

link

answered 17 Mar, 12:32

sarthakmanna's gravatar image

5★sarthakmanna
606112
accept rate: 40%

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

(19 Mar, 14:35) lifecoder_10★

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 Mar, 22:57) sarthakmanna5★

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

TreeMap is used for that purpose.

(20 Mar, 23:00) sarthakmanna5★

For a list of sides to not form a valid triangle, the side length must be such that when the sides are sorted, every element is atleast the sum of previous two elements. In the worst case, the values may be of the form: 1, 2, 3, 5, 8, 13, 21, and so on... This is nothing but the Fibonacci Series. In this series, the 44th number is 1134903170 which is greater than 109. This is an important conclusion as this means that if a node contains NO valid triangle, than it will AT MAX hold Just 43 values Thus, any node in the segment tree will hold at max 45 values where the sides are of the form: 1,1,1,2,3,5,8,13... and so on till 701408733 @awesome conclusion @harshmmodi bhaiya thanks for editorial

link
This answer is marked "community wiki".

answered 12 Mar, 23:51

prince367's gravatar image

4★prince367
612
accept rate: 0%

Happy to hear that it helped :)

(13 Mar, 20:26) harshmmodi5★

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

link

answered 16 Mar, 18:47

rajarshi_basu's gravatar image

5★rajarshi_basu
4877
accept rate: 10%

My solution

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

link

answered 22 Mar, 16:08

kaushala's gravatar image

4★kaushala
272
accept rate: 0%

can u explain the get function in your solution?

(22 Mar, 16:30) beginner_11113★

@beginner_1111 if you follow the link I provided above, you can find a function named query() in the beginning of the blog. It gives the result of a segment tree range query for range $[l,r)$. Similar implementation is get() which solves for range $[l,r]$. Notice that the whole blog follows 0-indexing.

(02 Apr, 16:15) kaushala4★

Anybody tell me why its showing WA for this solution:link text

link

answered 13 Mar, 13:28

doramon's gravatar image

1★doramon
765
accept rate: 5%

@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:https://www.codechef.com/viewsolution/17822566

(13 Mar, 14:59) beginner_11113★

@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

(13 Mar, 20:30) harshmmodi5★

Runtime can be further improved by the fact that you dont have to create a tmp array, directly do the idea of merge sort tree in reverse.

U need max 45 values out of 90 values, right.

U merge the nodes such that elements in a node are stored in decreasing order, because it will save the time to create tmp array first. Also, do the work of 2nd loop inside and as soon as u find a triangle, or run out of lists, break the loop.

Another thing, Minimum value of K is 40, since 40th term of fibonacci series exceed 1e9.

Btw, nice detailed editorial..

link

answered 13 Mar, 20:44

taran_1407's gravatar image

5★taran_1407
3.3k1236
accept rate: 23%

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.

(13 Mar, 22:05) harshmmodi5★

Oh.. Miscounted digits...

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

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

(13 Mar, 22:24) taran_14075★

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

link

answered 15 Mar, 08:52

cjdjsaini97's gravatar image

4★cjdjsaini97
1
accept rate: 0%

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

(16 Mar, 12:53) harshmmodi5★

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.

link

answered 15 Mar, 22:40

manish3749's gravatar image

5★manish3749
12
accept rate: 0%

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.

(22 Mar, 16:11) kaushala4★

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

link

answered 17 Mar, 21:30

c_jain's gravatar image

2★c_jain
1
accept rate: 0%

Happy to hear that :)

(18 Mar, 16:46) harshmmodi5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,565
×1,049
×264
×64

question asked: 12 Mar, 23:36

question was seen: 5,104 times

last updated: 02 Apr, 16:15