Answers to: PSHTRG - Editorialhttps://discuss.codechef.com/questions/124012/pshtrg-editorial<h1>PROBLEM LINK:</h1>
<p>
<a href="http://www.codechef.com/MARCH18A/problems/PSHTRG">Div1</a>, <a href="http://www.codechef.com/MARCH18B/problems/PSHTRG">Div2</a><br>
<a href="http://www.codechef.com/problems/PSHTRG">Practice</a>
</p>
<p>
<strong>Author:</strong> <a href="http://www.codechef.com/users/fekete">Ivan Fekete</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/triveni">Triveni Mahatha</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/adkroxx">Adarsh Kumar</a>
</p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Segment tree</p>
<h1>PROBLEM:</h1>
<p>You are given an array with $N$ elements. You need to support two types of operations on this array. First one is point update. For the second operation, you will be given query range $l,r$ and you need to find the maximum possible perimeter of a triangle with non-zero area whose sides are $A_x, A_y, A_z$, where $l \le x < y < z \le r$. If no triangle can be formed, you just need to output $0$.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Build a segment tree where each node stores largest $K$ elements from the interval. Value of $K$ for given constraint will be around $50$. Update function on the tree can now be supported in $O(KlogN)$.</p>
<p><strong>Claim:</strong> For a given range, triangle with maximum perimeter can be formed using largest $K$ elements from that interval. Answer will be 0, only for the case, when there will be less than $K$ elements in the interval and no triangle formation is possible.</p>
<p>You can query for largest $K$ elements in $O(KlogN)$. Finding the triangle with maximum perimeter afterward is relatively easy and procedure for the same can be found in detailed explanation.</p>
<h1>EXPLANATION:</h1>
<p>Let's try to solve a simpler version first.</p>
<h3>Solve a simple version first:</h3>
<p>In this version, you are given an array of $N$ integers and you need to find the maximum possible perimeter of a triangle.<br>
To solve this problem, first, we sort our array in non-ascending order. Next, we iterate over each $ A[i] $ (where $ 1 \le i < N-1 $ ) and fix the longest side, $ c = A[i] $. To satisfy the condition $ a+b>c $ and maximize $ a+b+c $, we must choose $ b = A[i+1] $ and $ a = A[i+2] $. $a+b+c$ will be the largest perimeter for minimal $i$ satisfying the condition $a+b>c$. The answer will be $0$ if no such $i$ exist.<br></p>
<p><strong>Claim:</strong> If $N>K$, answer always exist and can be found using largest $K$ elements, i.e. $ i \le K $. Here $ K = O(log_{\phi}(\sqrt{5}.MAX))$, where $\phi = \frac{1+\sqrt{5}}{2}$ and $MAX$ is the maximum value which can be present in the array.<br>
<strong>Proof:</strong> Lets say you keep adding elements in an array in increasing order such that no triangle formation is possible at any instant. Say there are $r$ elements currently in the array, when you add $(r+1)^{th}$ element, it must not satisy triangle inequality with any elements already present in the array. Hence we can write,<br>
</p><center>$A[r+1] \ge A[r]+A[r-1]$</center><br>
If we keep on adding elements in this manner, we will end up on <a href="https://en.wikipedia.org/wiki/Fibonacci_number">fibonacci sequence</a>. Fibonacci numbers grows very fast and soon they will exceed the maximum value that can be present in the array. If we do not exceed the maximum value that can be present in the array, triangle can definitely be formed using $K$ elements. You can compute the exact value of $K$, but we will just use approximation here for our purpose:<br><br>
<center>$fib(K) > MAX$<br>
$\Rightarrow \frac{\phi^K}{\sqrt{5}} > MAX$ (Using approximation)<br>
$\Rightarrow K > log_{\phi}(\sqrt{5}.MAX)$</center><p></p>
<p><strong>Conclusion:</strong> For our original purpose, we will only need largest $K$ elements from the query range. We need a Data Structure that can support point update and can report largest $K$ elements from any query range in logarithmic time complexity or similar. For current constraints $K = 50$.</p>
<h3>Using segment tree for our purpose</h3>
<p>We can perform our required operation with the help of segment tree. In each node of segment tree, you need to store largest $K$ elements from that interval. If size of interval is less than $K$ then store all elements from that interval.</p>
<p>Merge function for two nodes can be implemented in a manner similar to merge sort algorithm. Merging of two nodes can be done in $O(K)$. For each update/query, you will need to change/visit atmax $logN$ nodes. Hence the time complexity for each update/query will be $O(KlogN)$. For more implementation details, you can have a look at attached solutions.</p>
<h1>Time Complexity:</h1>
<p>$O(Q.K.logN)$ </p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS</h1>
<p><a href="http://www.codechef.com/download/Solutions/MARCH18/Setter/PSHTRG.cpp">Setter's solution</a><br>
<a href="http://www.codechef.com/download/Solutions/MARCH18/Tester/PSHTRG.cpp">Tester's solution</a><br>
</p>enMon, 14 May 2018 00:55:11 +0530Answer by pavitra_aghttps://discuss.codechef.com/questions/124012/pshtrg-editorial/126634<p><a href="/users/112228/ista2000">@ista2000</a> can you please explain your approach. I am new to segment trees.
Thanks in Advance:)</p>pavitra_agMon, 14 May 2018 00:55:11 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/126634Answer by jha_gaurav98https://discuss.codechef.com/questions/124012/pshtrg-editorial/124986<p>Please can someone help me in improving my solution. I have understood the concept and written a code but it is giving TLE.The complexity is Q.K.log n where k = 45. <a href="https://www.codechef.com/viewsolution/17965123">here is my code</a> Thanks </p>jha_gaurav98Mon, 26 Mar 2018 22:31:26 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124986Answer by gyanendra371https://discuss.codechef.com/questions/124012/pshtrg-editorial/124508<p>can anyone just tell me how setter is doing without sorting nodes.</p>gyanendra371Sat, 17 Mar 2018 23:51:01 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124508Answer by soumen2252https://discuss.codechef.com/questions/124012/pshtrg-editorial/124472<p>Can anyone help me. Why <a href="https://www.codechef.com/viewsolution/17862222">this</a> code is giving TLE?</p>soumen2252Sat, 17 Mar 2018 11:15:39 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124472Answer by namanjain007https://discuss.codechef.com/questions/124012/pshtrg-editorial/124407<p><a href="https://discuss.codechef.com/users/183523/harrypotter0">harrypotter0 </a>For mathematical calculations ,refer to <a href="https://en.wikipedia.org/wiki/Fibonacci_number">this</a> </p>namanjain007Thu, 15 Mar 2018 20:11:01 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124407Answer by harrypotter0https://discuss.codechef.com/questions/124012/pshtrg-editorial/124380<p>Please can someone explain to me the math involved behind the limiting the value of K to 50 ? </p>harrypotter0Thu, 15 Mar 2018 00:35:09 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124380Comment by aryanc403 on aryanc403's answerhttps://discuss.codechef.com/questions/124012/pshtrg-editorial#124368<p><a href="https://www.codechef.com/viewsolution/17834749">https://www.codechef.com/viewsolution/17834749</a>
<a href="/users/156623/kailashnath199">@kailashnath199</a> Thank you Man. Now, i am able to do this question using segment tree.
Thank You.</p>aryanc403Wed, 14 Mar 2018 22:35:19 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial#124368Comment by ista2000 on ista2000's answerhttps://discuss.codechef.com/questions/124012/pshtrg-editorial#124367<p>Ah, yes the intended solution uses something different too. Its a cross between a segtree and a merge sort tree. Thanks for describing the intended one. :D</p>ista2000Wed, 14 Mar 2018 22:30:01 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial#124367Comment by shawnbam_96 on saurabh18213's answerhttps://discuss.codechef.com/questions/124012/pshtrg-editorial#124330<p>The only reason I can think of -
<br>
Weak test cases (lengths of required(valid) triangle were very close to r) i.e. <b>number of queries giving required triangle in less number of iterations >> number of queries giving required triangle in more number of iterations <b></b></b></p>shawnbam_96Wed, 14 Mar 2018 05:05:24 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial#124330Comment by namanjain007 on tarunnpvs's answerhttps://discuss.codechef.com/questions/124012/pshtrg-editorial#124287<p>Editorial just correctly explained that if there are more than 50 nos in the range l to r then as if a plus b is less than c for all (c>b>a) then c should be greater than Fibonacci nos series having elements a b c etc. So c would exceed your upper limit</p>namanjain007Tue, 13 Mar 2018 16:31:41 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial#124287Answer by tarunnpvshttps://discuss.codechef.com/questions/124012/pshtrg-editorial/124284<p>Is there any reason to choose k=50? If Yes can some one explain?</p>tarunnpvsTue, 13 Mar 2018 15:25:28 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124284Answer by doramonhttps://discuss.codechef.com/questions/124012/pshtrg-editorial/124264<p>Anybody tell me why its showing WA for this solution:<a href="https://www.codechef.com/viewsolution/17822034">solution</a></p>doramonTue, 13 Mar 2018 11:43:21 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124264Answer by akibkhan12345https://discuss.codechef.com/questions/124012/pshtrg-editorial/124263<p>neither tester nor setter's solution are opening.. showing the error "This XML file does not appear to have any style information associated with it. The document tree is shown below." fix it <a href="/users/1/admin">@admin</a></p>akibkhan12345Tue, 13 Mar 2018 11:18:35 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124263Answer by rj25https://discuss.codechef.com/questions/124012/pshtrg-editorial/124242<p>I got AC with full 100 points using Square root decomposition, should have got WA, but test cases were weak. <a href="https://www.codechef.com/viewsolution/17731209">Slution</a></p>rj25Tue, 13 Mar 2018 03:56:48 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124242Comment by adkroxx on ista2000's answerhttps://discuss.codechef.com/questions/124012/pshtrg-editorial#124223<p>I knew about this solution too. But for me something else was simpler, hence I decided to describe that solution. But anyway good job. :)</p>adkroxxMon, 12 Mar 2018 23:26:14 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial#124223Answer by saurabh18213https://discuss.codechef.com/questions/124012/pshtrg-editorial/124222<p>I am not getting how <a href="https://www.codechef.com/viewsolution/17665748">this</a> O(Q*N) submission of mine is getting 100 points.
My approach :
First I created a vector of pair in which i stored every element's value and index. Then I sorted this vector.
For first query I used an algorithm similar to one used in insertion sort. And for query 2 I just traversed
the array from backward and checked the conditions for an element, whether its index is between l and r .</p>saurabh18213Mon, 12 Mar 2018 23:06:34 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124222Comment by kailashnath199 on aryanc403's answerhttps://discuss.codechef.com/questions/124012/pshtrg-editorial#124214<p><a href="http://codeforces.com/blog/entry/15890">http://codeforces.com/blog/entry/15890</a></p>kailashnath199Mon, 12 Mar 2018 21:40:47 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial#124214Answer by l_returnshttps://discuss.codechef.com/questions/124012/pshtrg-editorial/124211<p>No need to store 50 points.. while merging two arrays from child nodes.. we can break adding points when we get a triangle and by fibonacci it is clear that no. of points would be less than 50 always.. so it would be more optimized....
sample code for merging could be..
<code>s1=size of v1 , s2 = size of v2....
while(i<s1 && j<s2)
{
if( v[k-1] + v[k-2] > v[k-3]) /// breaking condition
return ;
if(v1[i] > v2[j])
v.push_back(v1[i++]);
else
v.push_back(v2[j++]);
k++;
}</code></p>l_returnsMon, 12 Mar 2018 21:26:53 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124211Comment by sdssudhu on ista2000's answerhttps://discuss.codechef.com/questions/124012/pshtrg-editorial#124206<p>Wow such a different idea . Never thought of this.</p>sdssudhuMon, 12 Mar 2018 20:18:28 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial#124206Answer by aryanc403https://discuss.codechef.com/questions/124012/pshtrg-editorial/124203<p>Can I get a link to nice tutorial on Segment tree ?
Btw I passes this question using sqrt decomposition. <a href="https://www.codechef.com/viewsolution/17743850">https://www.codechef.com/viewsolution/17743850</a>
With little optimisation.</p>aryanc403Mon, 12 Mar 2018 19:25:56 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124203Answer by praveenkumar12https://discuss.codechef.com/questions/124012/pshtrg-editorial/124196<p><a href="/users/290734/kayak">@kayak</a> 2^31 is less than 3*10^9.</p>praveenkumar12Mon, 12 Mar 2018 19:08:47 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124196Answer by nilmadhab1https://discuss.codechef.com/questions/124012/pshtrg-editorial/124194<p>I have used square root decomposition for the problem.
<a href="https://www.codechef.com/viewsolution/17760397">https://www.codechef.com/viewsolution/17760397</a></p>nilmadhab1Mon, 12 Mar 2018 18:59:15 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124194Comment by droy0528 on adkroxx's questionhttps://discuss.codechef.com/questions/124012/pshtrg-editorial#124189<p>very nice editorial <a href="/users/77774/adkroxx">@adkroxx</a></p>droy0528Mon, 12 Mar 2018 18:07:36 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial#124189Answer by ista2000https://discuss.codechef.com/questions/124012/pshtrg-editorial/124188<p>Wouldn't a much simpler solution be to just make a segtree which returns the index of the max element in a range? After extracting the max index, we can save it and then point update it to 0 and then do the max query again to get the second largest. This is $O(KlogN)$ query and $O(logN)$ update but is much simpler.</p>ista2000Mon, 12 Mar 2018 18:07:04 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124188Answer by b123eginnerhttps://discuss.codechef.com/questions/124012/pshtrg-editorial/124173<p>Solutions are not visible :( </p>b123eginnerMon, 12 Mar 2018 17:15:23 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124173Answer by bhishmahttps://discuss.codechef.com/questions/124012/pshtrg-editorial/124169<p>Having a priority queue at each node of the segment tree would be easier I guess, my <a href="https://www.codechef.com/viewsolution/17634490">solution</a> . Also $K = 45$ worked fine.</p>bhishmaMon, 12 Mar 2018 16:46:16 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124169Answer by saurabh18213https://discuss.codechef.com/questions/124012/pshtrg-editorial/124166<p><a href="/users/290734/kayak">@kayak</a> use long long for calculating answer as the answer can be the sum of three maximum integers, which will result in overflow. </p>saurabh18213Mon, 12 Mar 2018 16:28:37 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial/124166Comment by gdisastery1 on adkroxx's questionhttps://discuss.codechef.com/questions/124012/pshtrg-editorial#124162<p>You can also simply use Max Segment Tree: Query for the largest element, remove it (by setting the value to -infinity), and repeat it K times. Afterwards you just restore the values. This is also $O(K \log n)$ per query.</p>gdisastery1Mon, 12 Mar 2018 15:54:47 +0530https://discuss.codechef.com/questions/124012/pshtrg-editorial#124162