tag:blogger.com,1999:blog-23874254290384490022024-03-21T15:59:29.992-07:00Codaholic.cppConcepts of competitive programming !Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-2387425429038449002.post-17633785710966161022018-05-10T22:42:00.001-07:002018-05-11T04:09:10.061-07:00Euler Totient Function<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
Hello Coders,<br />
<br />
I am writing this blogpost after a very long time. I am really sorry for that. :(<br />
<br />
This blogpost is related to a mathematical topic which is <b>Euler Totient function</b> and there are many problems which are based on this mathematical concept.<br />
<br />
<b>What is Euler Totient Function?</b><br />
It is a function which takes the input an integer <b>n </b>and in return it gives the number of relatively prime numbers to <b>n</b> which are smaller than it.<br />
<br />
<a name='more'></a><br />
<br />
<b>What is a relatively prime number?</b><br />
A number <b>X </b>is relatively prime to another number say <b>Y </b>if <b>GCD(X, Y) </b>is <b>1. </b>Here GCD(X, Y) is greatest common factor of X and Y.<br />
<br />
<b></b> Let's take some examples and find their relatively smaller prime numbers(RSPN):<br />
N = 2,<br />
RSPN(2) = {1}<br />
--------------------<br />
N = 3<br />
RSPN(3) = {1, 2}<br />
--------------------<br />
N = 4<br />
RSPN(4) = {1, 3}<br />
--------------------<br />
N = 5<br />
RSPN(5) = {1, 2, 3, 4}<br />
--------------------<br />
N = 6<br />
RSPN(6) = {1, 5}<br />
<br />
and so on.....<br />
<br />
Now let's see how euler totient give the number of relatively prime numbers to N which are smaller than it.<br />
<br />
<b>Formula:</b><br />
<b>EulerTotient(N) = N * (1 - 1/p1) * (1 - 1/p2) * (1 - 1/p3) .........</b><br />
<i>Note: </i>Here p1, p2, p3.... are the prime factors of N.<br />
<br />
Let's validate the formula now:<br />
EulerTotient(<b>6</b>) = 6 * (1 - 1 / 2) * (1 - 1 / 3) = 6 * (1/2) * (2/3) = 2<br />
Wow! You can see that 6 has only 2 RSPN which are {1, 5}.<br />
<br />
Similarly you can test for other numbers also.<br />
<br />
<b>Proof of the formula:</b><br />
For proof you can visit <a href="https://en.wikipedia.org/wiki/Euler%27s_totient_function" target="_blank">Wikipedia Page.</a><b> </b><br />
Proof is very simple and it uses <b>multiplicative property</b> of Euler Totient Function<b>, </b>which means that: <b>EulerTotient(X*Y) = EulerTotient(X) * EulerTotient(Y).</b><br />
<br />
<b>C++ Implementation of Euler Totient Function:</b> <script src="https://gist.github.com/ma5terdrag0n/9b7ec20827b839e1c015c296169e2d79.js"></script>
</div>
<div>
<b>Problems for practice:</b><br />
<b><a href="https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1120&mosmsg=Submission+received+with+ID+19608548" target="_blank">Problem1</a> </b><br />
<b><a href="https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1240&mosmsg=Submission+received+with+ID+19608655" target="_blank">Problem2</a> </b><br />
<b><a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1761&mosmsg=Submission+received+with+ID+19609050" target="_blank">Problem3</a> </b><br />
You can see the solutions for above 3 problems on my another blog:<b> <a href="https://gocodergo.wordpress.com/2017/07/05/uva-10179-irreducable-basic-fractions/" target="_blank">Link</a></b><br />
<b><br /></b> <b>Thanks for reading this post!</b><br />
<b>Happy Coding!!</b><br />
<b><br /></b> <b><br /></b> <b><i>PS: </i></b><i>You can comment if you find anything wrong or you have any doubt regarding this topic</i><b><br /></b></div>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-45078090916450197012018-02-12T01:32:00.001-08:002018-02-12T01:32:32.733-08:00Code Chef: February Challenge First Five<div dir="ltr" style="text-align: left;" trbidi="on">
<h1>
Chef And His Characters:</h1>
<div style="text-align: left;">
This problem is straight-forward. Check every substring of length four and find if the 4 characters of string are 'c', 'h', 'e' and 'f'. </div>
<div style="text-align: left;">
<i><b>Complexity: </b>Linear per case.</i> <br />
<a href="https://www.codechef.com/viewsolution/17215649" target="_blank">Link to my C++ code!</a> <br />
<a name='more'></a></div>
<hr />
<h1>
Chef And The Patents: </h1>
<div style="text-align: left;">
Simple implementation problem. Just calculate the maximum number of patents that can be finished in the given time and finally compare it with the required patents to print the answer.</div>
<div style="text-align: left;">
<i><b>Complexity: </b>Linear per case</i> <br />
<a href="https://www.codechef.com/viewsolution/17216321" target="_blank">Link to my C++ code!</a></div>
<hr />
<h1>
Permutation and Palindrome:</h1>
<div style="text-align: left;">
First of all make a 2D-Array or Array of vectors <b>v</b>(let).</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
v['a'] = {indices where <b>a</b> occurs in the string}</div>
<div style="text-align: left;">
v['b'] = {indices where <b>b</b> occurs in the string}</div>
<div style="text-align: left;">
...</div>
<div style="text-align: left;">
...</div>
<div style="text-align: left;">
v['z'] = {indices where <b>z</b> occurs in the string}</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Now check where frequency of each of the character in the string. </div>
<div style="text-align: left;">
<b>If</b> there are more than one character which have odd count: </div>
<div style="text-align: left;">
then, print -1.</div>
<div style="text-align: left;">
<b>else:</b></div>
<div style="text-align: left;">
First see all those characters which have even count.</div>
<div style="text-align: left;">
Print half of the stored indices of those characters from 'a' to 'z'.</div>
<div style="text-align: left;">
Now see if there is a character with odd count.</div>
<div style="text-align: left;">
If Yes, then print all the indices of that character.</div>
<div style="text-align: left;">
Now print remaining half of the indices but this time in reverse order i.e from 'z' to 'a'.<br />
<i><b>Complexity : </b>Linear per case</i> </div>
<div style="text-align: left;">
<a href="https://www.codechef.com/viewsolution/17262055" target="_blank">Link to my C++ code!</a></div>
<hr />
<h1>
Car-pal Tunnel:</h1>
<div style="text-align: left;">
Let <b>t</b>(i) denotes the time taken to pass from ith tunnel.<b> </b></div>
<div style="text-align: left;">
<b>Observation:</b></div>
<div style="text-align: left;">
If t(i - 1) > t(i): </div>
<div style="text-align: left;">
Then there will be no delay when passing from ith tunnel. So simple ignore </div>
<div style="text-align: left;">
the ith tunnel.</div>
<div style="text-align: left;">
</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<i><b>Note:</b> Starting from first tunnel consider only those tunnels which have t(i) > t(i-1).</i> </div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Must use paper and pen !!</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Now note the delay at each tunnel. At each tunnel delay between first and last car will be (t(i) - t(i-1)) * (c-1).</div>
<div style="text-align: left;">
Add all the delays and print the answer.<br />
<i><b>Complexity : </b>Linear per case.</i> </div>
<div style="text-align: left;">
<a href="https://www.codechef.com/FEB18/status/CARPTUN,solo_loser" target="_blank">Link to my C++ code!</a> </div>
<hr />
<h1>
Broken Clock:</h1>
<div style="text-align: left;">
<b>Pre-requisite: </b></div>
<div style="text-align: left;">
Trigonometric formula: 2*cos(a)*cos(b) = cos(a+b) + cos(a-b)</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Let <b>cos(theta) = d / l, </b>where theta is angle moved in 1 second.</div>
<div style="text-align: left;">
Clearly, after <b>t </b>seconds:</div>
<div style="text-align: left;">
Angle moved, <b>$</b> <b>= t * theta</b></div>
<div style="text-align: left;">
So <b>y-coordinate </b>after t-seconds will be <b>l * cos($).</b></div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<i>Note:</i> We need to calculate <b>cos(t * theta) </b>using already known <b>cos(theta).</b> </div>
<div style="text-align: left;">
<br />
Let see the calculation:<br />
Let t = 12<br />
t is even, so divide t into 2 equal parts:<br />
2 * cos(6*theta) * cos(6*theta) = cos(12 * theta) + cos(0)<br />
or<br />
cos(12 * theta) = 2 * cos(6*theta) * cos(6*theta) - cos(0)<br />
<br />
We know that cos(0) = 1. So only thing we need to calculate is cos(6*theta)<br />
<br />
Now Lets calculate cos(6 * theta) using the same formula:<br />
cos(6 * theta) = 2 * cos(3 * theta) * cos(3 * theta) - cos(0)<br />
<br />
Again we need to calculate cos(3 * theta):<br />
<i>Note: Here t is odd, so divide t into 2 parts: (t/2+1) and (t/2)</i><br />
cos(3*theta) = 2*cos(2*theta)*cos(theta) - cos(theta)<br />
<i> </i><br />
We know cos(theta), but we need t calculate cos(2*theta).<br />
<br />
So cos(2*theta) = 2*cos(theta)*cos(theta) - cos(0)<br />
<br />
I hope you observed the <i><b>Recursion.</b></i></div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #000000; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #cccccc;">typedef</span> <span style="color: #cd00cd;">long</span> <span style="color: #cd00cd;">long</span> <span style="color: #cccccc;">ll;</span>
<span style="color: #cd00cd;">map</span><span style="color: #3399cc;"><</span><span style="color: #cccccc;">ll,ll</span><span style="color: #3399cc;">></span> <span style="color: #cccccc;">cos;</span>
<span style="color: #cccccc;">ll</span> <span style="color: #cccccc;">funcos(ll</span> <span style="color: #cccccc;">l,</span> <span style="color: #cccccc;">ll</span> <span style="color: #cccccc;">d,</span> <span style="color: #cccccc;">ll</span> <span style="color: #cccccc;">t){</span>
<span style="color: #cccccc;">ll</span> <span style="color: #cccccc;">mod</span> <span style="color: #3399cc;">=</span> <span style="color: #cd00cd;">1e9</span><span style="color: #3399cc;">+</span><span style="color: #cd00cd;">7</span><span style="color: #cccccc;">;</span>
<span style="color: #cdcd00;">if</span><span style="color: #cccccc;">(t</span> <span style="color: #3399cc;">==</span> <span style="color: #cd00cd;">0</span><span style="color: #cccccc;">){</span>
<span style="color: #cccccc;">cos[</span><span style="color: #cd00cd;">0</span><span style="color: #cccccc;">]</span> <span style="color: #3399cc;">=</span> <span style="color: #cd00cd;">1</span><span style="color: #cccccc;">;</span>
<span style="color: #cdcd00;">return</span> <span style="color: #cd00cd;">1</span><span style="color: #cccccc;">;</span>
<span style="color: #cccccc;">}</span>
<span style="color: #cdcd00;">if</span><span style="color: #cccccc;">(t</span> <span style="color: #3399cc;">==</span> <span style="color: #cd00cd;">1</span><span style="color: #cccccc;">){</span>
<span style="color: #cccccc;">cos[t]</span> <span style="color: #3399cc;">=</span> <span style="color: #cccccc;">(d</span> <span style="color: #3399cc;">*</span> <span style="color: #cccccc;">inverseModulo(l,</span> <span style="color: #cccccc;">mod</span><span style="color: #3399cc;">-</span><span style="color: #cd00cd;">2</span><span style="color: #cccccc;">,</span> <span style="color: #cccccc;">mod))</span><span style="color: #3399cc;">%</span><span style="color: #cccccc;">mod;</span>
<span style="color: #cdcd00;">return</span> <span style="color: #cccccc;">cos[t];</span>
<span style="color: #cccccc;">}</span>
<span style="color: #cdcd00;">if</span><span style="color: #cccccc;">(cos</span><span style="color: #3399cc;">.</span><span style="color: #cccccc;">count(t))</span><span style="color: #cdcd00;">return</span> <span style="color: #cccccc;">cos[t];</span>
<span style="color: #cdcd00;">if</span><span style="color: #cccccc;">(t</span> <span style="color: #cdcd00;">is</span> <span style="color: #cccccc;">odd){</span>
<span style="color: #cccccc;">cos[t]</span> <span style="color: #3399cc;">=</span> <span style="color: #cccccc;">(</span><span style="color: #cd00cd;">2</span><span style="color: #3399cc;">*</span><span style="color: #cccccc;">funcos(l,</span> <span style="color: #cccccc;">d,</span> <span style="color: #cccccc;">t</span><span style="color: #3399cc;">/</span><span style="color: #cd00cd;">2</span><span style="color: #3399cc;">+</span><span style="color: #cd00cd;">1</span><span style="color: #cccccc;">)</span><span style="color: #3399cc;">%</span><span style="color: #cccccc;">mod</span><span style="color: #3399cc;">*</span><span style="color: #cccccc;">funcos(l,</span> <span style="color: #cccccc;">d,</span> <span style="color: #cccccc;">t</span><span style="color: #3399cc;">/</span><span style="color: #cd00cd;">2</span><span style="color: #cccccc;">)</span><span style="color: #3399cc;">%</span><span style="color: #cccccc;">mod</span> <span style="color: #3399cc;">+</span> <span style="color: #cccccc;">mod</span> <span style="color: #3399cc;">-</span> <span style="color: #cccccc;">funcos(l,</span> <span style="color: #cccccc;">d,</span> <span style="color: #cd00cd;">1L</span><span style="color: #cccccc;">L)</span><span style="color: #3399cc;">%</span><span style="color: #cccccc;">mod)</span> <span style="color: #3399cc;">%</span> <span style="color: #cccccc;">mod;</span>
<span style="color: #cccccc;">}</span><span style="color: #cdcd00;">else</span><span style="color: #cccccc;">{</span>
<span style="color: #cccccc;">cos[t]</span> <span style="color: #3399cc;">=</span> <span style="color: #cccccc;">(</span><span style="color: #cd00cd;">2</span><span style="color: #3399cc;">*</span><span style="color: #cccccc;">powerModulo(funcos(l,</span> <span style="color: #cccccc;">d,</span> <span style="color: #cccccc;">t</span><span style="color: #3399cc;">/</span><span style="color: #cd00cd;">2</span><span style="color: #cccccc;">),</span> <span style="color: #cd00cd;">2L</span><span style="color: #cccccc;">L,</span> <span style="color: #cccccc;">mod)</span> <span style="color: #3399cc;">+</span> <span style="color: #cccccc;">mod</span> <span style="color: #3399cc;">-</span> <span style="color: #cd00cd;">1</span><span style="color: #cccccc;">)</span> <span style="color: #3399cc;">%</span> <span style="color: #cccccc;">mod;</span>
<span style="color: #cccccc;">}</span>
<span style="color: #cdcd00;">return</span> <span style="color: #cccccc;">cos[t]</span><span style="color: #3399cc;">%</span><span style="color: #cccccc;">mod;</span>
<span style="color: #cccccc;">}</span>
</pre>
</td></tr>
</tbody></table>
</div>
<div>
<br />
<i>Note: </i><br />
<i>1. powerModulo calculates base^exponent modulo mod.</i><br />
<i>2. inverseModulo calculates base^(-1) modulo mod. </i><br />
<i><b>Complexity : </b>log(n) per case. </i><br />
<a href="https://www.codechef.com/viewsolution/17376238" target="_blank">Link to my C++ code!</a><br />
<br />
Thanks for reading this post!<br />
Happy Coding! </div>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-17933233338338767182018-01-15T01:32:00.000-08:002018-01-15T01:32:31.116-08:00Code Chef january challenge unofficial editorial for first 5 problems<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: left;" trbidi="on">
<h1>
Rectangle:</h1>
<div style="text-align: left;">
This is the easiest problem of the contest. Opposite sides of a rectangle are equal. So use this property to see if there are 2 pairs of equal sides.<br />
<a name='more'></a></div>
</div>
<div style="background: #111111; border-color: black; border-radius: 0%; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="background-color: #0f140f; color: #008800; font-style: italic;">//inside int main()</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">t;</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">t;</span>
<span style="color: #fb660a; font-weight: bold;">while</span><span style="color: white;">(t--){</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">a[</span><span style="color: #0086f7; font-weight: bold;">4</span><span style="color: white;">];</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: #0086f7; font-weight: bold;">4</span> <span style="color: white;">;</span> <span style="color: white;">i++)cin</span> <span style="color: white;">>></span> <span style="color: white;">a[i];</span>
<span style="color: white;">sort(a,a</span> <span style="color: white;">+</span> <span style="color: #0086f7; font-weight: bold;">4</span><span style="color: white;">);</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(a[</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">]</span> <span style="color: white;">==</span> <span style="color: white;">a[</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">]</span> <span style="color: white;">and</span> <span style="color: white;">a[</span><span style="color: #0086f7; font-weight: bold;">2</span><span style="color: white;">]</span> <span style="color: white;">==</span> <span style="color: white;">a[</span><span style="color: #0086f7; font-weight: bold;">3</span><span style="color: white;">])</span>
<span style="color: white;">cout</span> <span style="color: white;"><<</span> <span style="color: #0086d2;">"YES\n"</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">else</span>
<span style="color: white;">cout</span> <span style="color: white;"><<</span> <span style="color: #0086d2;">"NO\n"</span><span style="color: white;">;</span>
<span style="color: white;">}</span>
</pre>
</div>
<div>
<br />
<hr />
<h1>
Maximum Score:</h1>
<div style="text-align: left;">
Start solving the problem from last list instead of first list, because in order to get the maximum sum we must select the maximum element from the last list. Obviously sorting makes the task easier. So sort all the lists and let our variable<b> ans </b>be 0 initially. First select the maximum value from last list and store it in a variable(say <b>last</b>) and add it to <b>ans</b>, then find the maximum value from second last list which is less than<b> last, </b>let it be <b>val</b> and then set <b>last = val</b> and add <b>val</b> to the <b>ans. </b>Similarly do for other lists. Finally <b>ans </b>will be our final answer.<br />
<b>Complexity : </b><br />
<i>using sorting: O(n*n*log(n)) per test-case</i><br />
<i>without sorting: O(n*n) per test-case</i> </div>
<div style="text-align: left;">
<i><a href="https://www.codechef.com/viewsolution/16760211" target="_blank">Link to my solution</a></i><b> </b></div>
</div>
</div>
<hr />
<div>
<h1>
K-Concatenation:</h1>
<div style="text-align: left;">
<i><b>Pre-requisites: Kadane's Algorithm or maximum sum sub-array problem</b>.</i></div>
<div style="text-align: left;">
Let <b>a </b>be the given array of <b>n </b>elements and <b>k </b>is the number of arrays. </div>
<div style="text-align: left;">
Let <b>sum </b>be the sum of elements of array a[n].</div>
<div style="text-align: left;">
There are 3 cases:</div>
<div style="text-align: left;">
<i>ans1 = maximum sum sub-array from array <b>a[]</b> and ignoring all the (k-1) arrays.</i></div>
<div style="text-align: left;">
<i>ans2 = max_suffix_sum_of_a + (k-2)*<b>sum</b>+ max_prefix_sum_of_a.</i></div>
<div style="text-align: left;">
<i>ans3 = maximum sum sub-array from joining array <b>a[]</b> 2 times.</i><br />
Final answer will be equal to maximum of ans1, ans2, and ans3.<i> </i><br />
Don't forget to make a different case when k = 1, because ans2 and ans3 are not valid when k = 1.<i> </i></div>
<div style="text-align: left;">
<b>Complexity: </b><i>O(n) per test-case</i><br />
<i><a href="https://www.codechef.com/viewsolution/16812542" target="_blank">Link to my solution in C++</a></i></div>
</div>
<hr />
<div>
<h1>
String Merging:</h1>
<div style="text-align: left;">
<b><i>Pre-requisites: Longest common sub-sequence</i></b><br />
We know that our answer counts only<i><b> </b></i>when there are 2 unequal characters. So first of all get rid of continuous equal characters by replacing them with a single occurrence because they are not going to add anything to the answer. <b><i>Eg.</i></b> If string s = "piikkkaachhu" then make s = "pikachu". So after shortening both the given strings <b>a </b>and <b>b</b>, we can see that, we can merge them in such a way that the<b> </b>characters of their <b>longest common sub-sequence </b>collides, so that most of the characters can be made continuous in the merged string and final answer can be minimized.<br />
Let <b>n</b> be the length of shortened <b>a </b>string.<br />
Let <b>m</b> be the length of shortened <b>b </b>string.<br />
Then our final answer will be <b>n + m - lcs(a,b),</b> where lcs(string1, string2) returns the length of lcs of string1 and string2.<br />
<i><b>Complexiy: </b>O(n*m) per case</i><br />
<i><a href="https://www.codechef.com/viewsolution/16776101" target="_blank">Link to my solution in C++</a> </i><b><i> </i></b> </div>
</div>
<hr />
<div>
<h1>
Partition the numbers: </h1>
<h3 style="text-align: left;">
<i>Observations:<b> </b></i></h3>
<div style="text-align: left;">
Sum of first <b>n </b>natural<b> </b>numbers, <b>sum </b>= (n*(n+1)) / 2.</div>
<div style="text-align: left;">
Let's remove x(1<=x<=n) from sequence. So, sum = (n*(n+1)) / 2 - x.</div>
<div style="text-align: left;">
Now if sum is odd, we can never divide the remaining numbers into 2 sets.</div>
<div style="text-align: left;">
When n = 2 or n = 3, answer is "impossible", no matter what is the value of x. <i><br /></i></div>
<h3 style="text-align: left;">
<i>Approach:</i></h3>
<div style="text-align: left;">
We need to find if sum/2 can be formed from the remaining numbers. If yes! then what are those numbers which sums to sum/2.</div>
<div style="text-align: left;">
Let <b>req</b> = sum/2</div>
<div style="text-align: left;">
Make an array <b>color[n]</b> to represent the partitions.</div>
<div style="text-align: left;">
Color 0 represents the first partition and Color 1 represents another partition and Color 2 represents the <b>x</b>.</div>
<div style="text-align: left;">
Initially color all numbers with color 0. It means all numbers are initially in partition 1.</div>
<div style="text-align: left;">
It's obvious that req is always greater then n.</div>
<div style="text-align: left;">
So, start a loop, counter <b>i</b> from <b>n</b> to <b>1 </b>and if color[i] == 0, subtract <b>i </b>from req and change color[i] to 1. Break the loop once you get that after next addition req will be < 0. </div>
<div style="text-align: left;">
So now we have 2 cases:<br />
<i>Case 1:</i> </div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">if</span>(color[req] <span style="color: #333333;">==</span> <span style="color: #0000dd; font-weight: bold;">0</span>){
color[req] <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">return</span>;
}
</pre>
</div>
<div>
<i>Case 2:</i><br />
Now if(color[req] != 0)<i> </i>we need to make req from addition of some numbers which are in first partition(i.e. having color[i] = 0).<br />
<i></i><br />
We can make req in 2 ways from given numbers:</div>
<div>
<b>Way 1:</b></div>
<div>
Eg: 1, 2, 3, 4, 5. How can you make 6 from these numbers(1 to (6-1 = 5)).</div>
<div>
1 + 4 = 2 + 4. So yep, we have 2 ways to make 6(see the pattern: one number from start and one number from end).</div>
<div>
Similarly req can be formed from one of the combinations(1 to (req-1)).</div>
<div>
<i>Conditions:</i> color[first] = 0 and color[second] = 0 and first < second, where first and second are the first and second numbers respectively.</div>
<div>
If you find a combination make color[first]=1 and color[second]=1, and then return<br />
<b>Way 2:</b><br />
Eg: 6, 7, 8, 9, 10, 11, 12<b>........</b><br />
Let 12 be already in second partition(color[12] = 1 and is the last element from last which has color = 1), and we need to make req = 6 from numbers greater than 6. What rubbish? xD. Yep we can!π€, by the following steps.<br />
Now remove 12 from second partition and add it in first partition<b> </b>and add 12 to req.<i> </i><br />
Now req = 12+6 = 18. Now, How can you make 18 from numbers from 7 to 11 (lets say color[7] = ... = color[11] = 0)?<br />
7 + 11 = 8 + 10 = 18. Now we have 2 ways.(Again! observe the pattern.)<br />
<i>In this way find the 2 numbers whose sum equals req and color them with 1 finally.</i><br />
Finally after coloring all the numbers, check if the really are divided into partitions. If yes then print the colors, else print "impossible".<br />
<i><b>Complexity:</b> Linear per case </i><br />
<i><a href="https://www.codechef.com/viewsolution/16802270" target="_blank">Link to my solution in C++</a></i><br />
<br />
<i>Thank you !</i><br />
<i>Keep coding!</i><br />
<br />
PS: If you find anything wrong in the post, please feel free to mention it in comment section.<i> </i></div>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com10tag:blogger.com,1999:blog-2387425429038449002.post-10090854447760585752018-01-01T00:40:00.002-08:002018-01-06T19:27:57.701-08:00Longest increasing subsequence<div dir="ltr" style="text-align: left;" trbidi="on">
<br />
<div style="text-align: left;">
<h2 style="text-align: left;">
<i>Contents:</i></h2>
</div>
<ol style="text-align: left;">
<li><i>Wtf is Longest increasing subsequence?</i></li>
<li><i>Dynamic programming approach to find the length.</i></li>
<li><i>O(nlog(n)) solution to find length using binary search.</i></li>
</ol>
<a name='more'></a><h2>
Longest Increasing Subsequence:</h2>
<div style="text-align: left;">
Suppose we are given an array of integers and a subsequence is a sequence of numbers we get after removing some elements from the array. So as the name suggests a longest increasing subsequence(LIS) is the longest sequence of array elements that we can get after removing some integers from the array and remaining elements must be in increasing order.</div>
<div style="text-align: left;">
Eg. Array a[] = {1, 2, 4, 3, 6}</div>
<div style="text-align: left;">
Here, we can get longest increasing subsequence by removing <b>4 </b>from the array.</div>
<div style="text-align: left;">
LIS = {1, 2, 3, 6}.</div>
<h2 style="text-align: left;">
Dynamic Programming Solution:</h2>
<div style="text-align: left;">
<b>Problem:</b> Given an array of integers, find the length of LIS?</div>
Let a[] is the given array of integers.<br />
<div style="text-align: left;">
Let dp[] be the new array, where dp[i] gives the length of LIS considering the <b>ith </b>element of array a[] as the last element of LIS. Initialize this dp[] with 1 because the length of LIS is obviously at least 1.</div>
<div style="text-align: left;">
Now suppose we already calculated dp[] from index <b>0</b> to <b>i-1</b>. Now we need to calculate dp[i].</div>
<div style="text-align: left;">
To calculate dp[i] we need to see if there is some a[j] < a[i] where j ranges from (0, i-1).</div>
<div style="text-align: left;">
If some a[j] < a[i] then we can say that dp[i] = max(dp[i], dp[j]+1). <b>Why?</b></div>
<div style="text-align: left;">
Because dp[j] gives us the length of LIS considering a[j] as last element of LIS and we know that a[j] < a[i], so that's why if we consider a[i] as last element of LIS and a[j] as second last element then clearly dp[i] can be maximum of dp[i] or dp[j]+1. Before doing dp[i] = max(dp[i], dp[j]+1), dp[i] gives the length of LIS considering a[i] as last element of LIS and 2nd last element of LIS is something other than a[j].</div>
<div style="text-align: left;">
In this way, we calculate dp[] and the maximum value of this array gives the length of LIS.</div>
<div style="text-align: left;">
<b>Implementation in C++:</b></div>
<br />
<div style="background: #111111; border-color: black; border-radius: 0%; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="background-color: #0f140f; color: #ff0007; font-style: italic; font-weight: bold;">#include<bits/stdc++.h></span>
<span style="color: #fb660a; font-weight: bold;">using</span> <span style="color: #fb660a; font-weight: bold;">namespace</span> <span style="color: white;">std;</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: #ff0086; font-weight: bold;">main</span><span style="color: white;">(){</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">n;</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// length of array a</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">n;</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">a[n];</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// input array</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n</span> <span style="color: white;">;</span> <span style="color: white;">i++){</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">a[i];</span>
<span style="color: white;">}</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">dp[n];</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// dp array</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n;</span> <span style="color: white;">i++)</span>
<span style="color: white;">dp[i]</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// initializing dp[] with 1</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">answer</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">1</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n</span> <span style="color: white;">;</span> <span style="color: white;">i++){</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// considering ith element as last element of LIS</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">j</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">j</span> <span style="color: white;"><</span> <span style="color: white;">i</span> <span style="color: white;">;</span> <span style="color: white;">j++){</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(a[j]</span> <span style="color: white;"><</span> <span style="color: white;">a[i]){</span>
<span style="color: white;">dp[i]</span> <span style="color: white;">=</span> <span style="color: white;">max(dp[i],</span> <span style="color: white;">dp[j]</span> <span style="color: white;">+</span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">);</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="color: white;">answer</span> <span style="color: white;">=</span> <span style="color: white;">max(answer,</span> <span style="color: white;">dp[i]);</span>
<span style="color: white;">}</span>
<span style="color: white;">cout</span> <span style="color: white;"><<</span> <span style="color: #0086d2;">"Length of LIS is : "</span> <span style="color: white;"><<</span> <span style="color: white;">answer</span> <span style="color: white;"><<</span> <span style="color: white;">endl;</span>
<span style="color: white;">}</span>
</pre>
</div>
<div>
<br />
<b>Time Complexity: </b><i>O(n*n)</i><br />
<h2 style="text-align: left;">
<b>O(nlog(n)) Solution:</b> </h2>
<div style="text-align: left;">
We can also find the length of LIS in O(nlog(n)) using binary search and a temporary array.</div>
<div style="text-align: left;">
We will use a temporary vector <b>v[]</b> which will always be sorted and its last element gives the last element of LIS.</div>
<div style="text-align: left;">
So let's iterate the given array a[] <b>from the index 0</b> <b>to </b><b>(n-1).</b> </div>
<div style="text-align: left;">
If v[] is empty directly push the a[i] to <b>v.</b></div>
<div style="text-align: left;">
If last element of LIS till now i.e. <b>v[last_idx]</b> is smaller than current element i.e. a[i], push a[i] into the vector <b>v.</b></div>
<div style="text-align: left;">
Otherwise we need to search the position where a[i] can be placed in vector v, in such a way that it does not disturb the current length of LIS which is length of vector <b>v</b>. We can find the suitable position by doing binary search over the vector v or using <b>upper_bound(). </b><br />
Finally length of vector v will give the length of LIS.<br />
Let's take an <b>example.</b></div>
<div style="text-align: left;">
a[] = {12, 13, 2, 15, 4, 5, 6}</div>
<div style="text-align: left;">
v[] = {}</div>
<div style="text-align: left;">
- - - - - - - - - - </div>
<div style="text-align: left;">
idx = 0 // index of current iteration</div>
<div style="text-align: left;">
v is empty so push a[idx] in v.</div>
<div style="text-align: left;">
v[] = {12}</div>
<div style="text-align: left;">
last_idx = 0 // last index of v</div>
<div style="text-align: left;">
- - - - - - - - - -</div>
<div style="text-align: left;">
idx = 1</div>
<div style="text-align: left;">
v[last_idx] < a[idx]</div>
<div style="text-align: left;">
push a[idx] in v.</div>
<div style="text-align: left;">
v[] = {12, 13}</div>
<div style="text-align: left;">
last_idx = 1</div>
<div style="text-align: left;">
Till now we have maximum length LIS is 2.</div>
<div style="text-align: left;">
- - - - - - - - - -</div>
<div style="text-align: left;">
idx = 2</div>
<div style="text-align: left;">
v[last_idx] > a[idx] (13 > 2)</div>
<div style="text-align: left;">
Find the first position in v[] where v[pos] > a[idx]</div>
<div style="text-align: left;">
clearly, pos = 0</div>
<div style="text-align: left;">
v[] = {2, 13}</div>
<div style="text-align: left;">
last_idx = 1</div>
<div style="text-align: left;">
- - - - - - - - - -</div>
<div style="text-align: left;">
idx = 3</div>
<div style="text-align: left;">
v[last_idx] < a[idx] (13 < 15)</div>
<div style="text-align: left;">
push a[idx] in v.</div>
<div style="text-align: left;">
v[] = {2, 13, 15}</div>
<div style="text-align: left;">
last_idx = 2</div>
<div style="text-align: left;">
Till now we have maximum length LIS is 3.</div>
<div style="text-align: left;">
- - - - - - - - - -</div>
<div style="text-align: left;">
idx = 4</div>
<div style="text-align: left;">
v[last_idx] > a[idx] (15 > 4)</div>
<div style="text-align: left;">
Find the first position in v[] where v[pos] > a[idx]</div>
<div style="text-align: left;">
clearly, pos =1</div>
<div style="text-align: left;">
v[] = {2, 4, 15}</div>
<div style="text-align: left;">
last_idx = 2</div>
<div style="text-align: left;">
- - - - - - - - - -</div>
<div style="text-align: left;">
idx = 5</div>
<div style="text-align: left;">
v[last_idx] > a[idx] (15 > 5)</div>
<div style="text-align: left;">
Find the first position in v[] where v[pos] > a[idx]</div>
<div style="text-align: left;">
clearly, pos =2</div>
<div style="text-align: left;">
v[] = {2, 4, 5}</div>
<div style="text-align: left;">
last_idx = 2</div>
- - - - - - - - - -</div>
<div>
<div style="text-align: left;">
idx = 6</div>
<div style="text-align: left;">
v[last_idx] < a[idx] (5 < 6)</div>
<div style="text-align: left;">
push a[i] in v.</div>
<div style="text-align: left;">
v[] = {2, 4, 5, 6}</div>
<div style="text-align: left;">
last_idx = 3</div>
<div style="text-align: left;">
Till now we have maximum length LIS is 4.</div>
<div style="text-align: left;">
<br />
<b>Length of LIS = 4</b></div>
<div style="text-align: left;">
Bravo !! This is like magic. xD</div>
<div style="text-align: left;">
<i><br /></i></div>
<div style="text-align: left;">
<i>Note : If there are many LIS of same size then the last element of vector v, will always give the last element of that LIS which has the smallest last element.</i></div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<b>Implementation in C++</b><b>:</b></div>
<div style="text-align: left;">
<br /></div>
</div>
<div style="background: #111111; border-color: black; border-radius: 0%; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="background-color: #0f140f; color: #ff0007; font-style: italic; font-weight: bold;">#include<bits/stdc++.h></span>
<span style="color: #fb660a; font-weight: bold;">using</span> <span style="color: #fb660a; font-weight: bold;">namespace</span> <span style="color: white;">std;</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: #ff0086; font-weight: bold;">main</span><span style="color: white;">(){</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">n;</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// length of array a</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">n;</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">a[n];</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// input array</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n</span> <span style="color: white;">;</span> <span style="color: white;">i++){</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">a[i];</span>
<span style="color: white;">}</span>
<span style="color: white;">vector<</span><span style="color: #cdcaa9; font-weight: bold;">int</span><span style="color: white;">></span> <span style="color: white;">v;</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;">++){</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// push if v is empty of v[last_idx] < a[i]</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(v.empty()</span> <span style="color: white;">or</span> <span style="color: white;">v.back()</span> <span style="color: white;"><</span> <span style="color: white;">a[i]){</span>
<span style="color: white;">v.push_back(a[i]);</span>
<span style="color: white;">}</span><span style="color: #fb660a; font-weight: bold;">else</span><span style="color: white;">{</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// binary search the position</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">pos</span> <span style="color: white;">=</span> <span style="color: white;">upper_bound(v.begin(),</span> <span style="color: white;">v.end(),</span> <span style="color: white;">a[i]-1)</span> <span style="color: white;">-</span> <span style="color: white;">v.begin();</span>
<span style="color: white;">v[pos]</span> <span style="color: white;">=</span> <span style="color: white;">a[i];</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// size of vector v will give the length of LIS</span>
<span style="color: white;">cout</span> <span style="color: white;"><<</span> <span style="color: #0086d2;">"Length of LIS : "</span> <span style="color: white;"><<</span> <span style="color: white;">v.size()</span> <span style="color: white;"><<</span> <span style="color: white;">endl;</span>
<span style="color: white;">}</span>
</pre>
</div>
<div>
<br />
Problem for practice: Try to find the length of longest non-decreasing subsequence. (Hint : note the difference, xD)<br />
<br />
<i>Thank You!</i><br />
<i>Happy Coding. </i></div>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com2tag:blogger.com,1999:blog-2387425429038449002.post-46962917161116162042017-12-22T23:03:00.001-08:002018-01-01T01:22:09.253-08:00Heaps and Priority Queue<div dir="ltr" style="text-align: left;" trbidi="on">
<h2 style="text-align: left;">
Contents:</h2>
<ol style="text-align: left;">
<li><i>Heaps and Priority Queue</i></li>
<li><i>Types of Heap </i></li>
<ol>
<li><i>Min-heap</i></li>
<li><i>Max-heap</i></li>
</ol>
<li><i> Some uses of heap with their complexities.</i></li>
<li><i> Problem from Hackerearth:</i></li>
<ol>
<li><i>Brute Force solution</i></li>
<li><i>Solution using priority_queue<a name='more'></a></i></li>
</ol>
</ol>
<div>
<h2 style="text-align: left;">
Heaps and Priority Queue:</h2>
Heap is a tree-based data structure , in which all the nodes are in specific order whith respect to<br />
their children.Most commonly used heap is binary heap in which each node has atmost 2 children.<br />
In a complete binary tree with n nodes, height will be log2(n).<br />
<h2 style="text-align: left;">
Types of Heap:</h2>
<h3 style="text-align: left;">
<i>Max_heap:</i> <span style="font-weight: normal;"><i>In this the nodes are arranges in such a way that parent node is greater than all its child nodes.</i></span></h3>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuqEEaMYnngekWBjQDp2oPv2ktv1TfA07lqDKw8XgZCzN8mYT-E6C-H_ON2dKFnJ_L1w1ZcSQXK5qh7EOzwvlCMHAQ-YP-jiJbyarHjn1ZBJ2z8L7L0fSsouDpgM3yCGgufx8Lib7XKoKQ/s1600/max.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="256" data-original-width="780" height="209" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuqEEaMYnngekWBjQDp2oPv2ktv1TfA07lqDKw8XgZCzN8mYT-E6C-H_ON2dKFnJ_L1w1ZcSQXK5qh7EOzwvlCMHAQ-YP-jiJbyarHjn1ZBJ2z8L7L0fSsouDpgM3yCGgufx8Lib7XKoKQ/s640/max.jpg" width="640" /></a></div>
<br />
Have a close look at the above picture. Node 6 is greater than its child nodes-4 & 5 , and similarly for other nodes.<br />
<br />
<h3 style="text-align: left;">
<i>Min_heap: <span style="font-weight: normal;">Based on the same concept we have</span> <span style="font-weight: normal;">min heap in which parent node is less than its child nodes.</span></i></h3>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhd86hv2daOLFSh5ARL05JxexxqrChF7P6l-BdPTpdpDcoCy-QmDEM5BsjVAe7x6B1_B2xtF0MDwocX6oKAeOQhvsXpbIlLDLK2W9Np62R6gKARnVLkmkvqwcyzNJXJgwK_IY9OGZwET0jb/s1600/min.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="155" data-original-width="240" height="258" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhd86hv2daOLFSh5ARL05JxexxqrChF7P6l-BdPTpdpDcoCy-QmDEM5BsjVAe7x6B1_B2xtF0MDwocX6oKAeOQhvsXpbIlLDLK2W9Np62R6gKARnVLkmkvqwcyzNJXJgwK_IY9OGZwET0jb/s400/min.png" width="400" /></a></div>
<br />
Closely observe the above picture, each parent node is less than its child nodes.<br />
<br />
NOTE:-Root node of min heap gives us the smallest element and Root of max heap gives us the largest element.<br />
<h2 style="text-align: left;">
Benifits of using heap:</h2>
<ol style="text-align: left;">
<li>Extract min/max - O(log n)</li>
<li>Get min/max - O(1)</li>
<li>BuildHeap - O(n)</li>
<li>Heapify - O(logn)</li>
</ol>
<h2 style="text-align: left;">
Solution of a Hackerearth Problem:</h2>
Lets discuss the implementation with the help of question given <a href="https://www.hackerearth.com/practice/data-structures/trees/heapspriority-queues/practice-problems/algorithm/little-monk-and-virat/">HERE</a><br />
<br />
<i><b>Brute-force:</b></i><br />
Use sorting and find the element at the kth position.<br />
But sorting takes O(nlogn).<br />
indexing kth element O(1) but removing it takes O(n).<br />
<br />
<b><i>Optimal approach using heap</i>:</b><br />
<i>Note: here we use <b>priority queue</b> which is an implementation of heap data structure.</i><br />
<div style="background: #111111; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="background-color: #0f140f; color: #ff0007; font-style: italic; font-weight: bold;">#include<bits/stdc++.h></span>
<span style="color: #fb660a; font-weight: bold;">using</span> <span style="color: #fb660a; font-weight: bold;">namespace</span> <span style="color: white;">std;</span>
<span style="color: white;">main()</span>
<span style="color: white;">{</span>
<span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">n,i;</span>
<span style="color: white;">scanf(</span><span style="color: #0086d2;">"%lld"</span><span style="color: white;">,&n);</span>
<span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">sum[n];</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(i=</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;i<n;i++)</span>
<span style="color: white;">{</span>
<span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">a;</span>
<span style="color: white;">scanf(</span><span style="color: #0086d2;">"%lld"</span><span style="color: white;">,&a);</span>
<span style="color: white;">sum[i]=a;</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(i=</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;i<n;i++)</span>
<span style="color: white;">{</span>
<span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">a;</span>
<span style="color: white;">scanf(</span><span style="color: #0086d2;">"%lld"</span><span style="color: white;">,&a);</span>
<span style="color: white;">sum[i]+=a;</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(i=</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;i<n;i++)</span>
<span style="color: white;">{</span>
<span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">a;</span>
<span style="color: white;">scanf(</span><span style="color: #0086d2;">"%lld"</span><span style="color: white;">,&a);</span>
<span style="color: white;">sum[i]+=a;</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">//sum of three categories</span>
<span style="color: white;">}</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">/*priority queue in ascending order</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> helps to extract the minimum element</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> similar to min heap*/</span>
<span style="color: white;">priority_queue<</span><span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span><span style="color: white;">,vector<</span><span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span><span style="color: white;">>,greater<</span><span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span><span style="color: white;">></span> <span style="color: white;">>min_heap;</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(i=</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;i<n;i++)</span>
<span style="color: white;">{</span>
<span style="color: white;">min_heap.push(sum[i]);</span>
<span style="color: white;">}</span>
<span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">q;</span>
<span style="color: white;">scanf(</span><span style="color: #0086d2;">"%lld"</span><span style="color: white;">,&q);</span>
<span style="color: #fb660a; font-weight: bold;">while</span><span style="color: white;">(q--)</span>
<span style="color: white;">{</span>
<span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">k,t;</span>
<span style="color: white;">scanf(</span><span style="color: #0086d2;">"%lld"</span><span style="color: white;">,&k);</span>
<span style="color: white;">vector<</span><span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">int</span><span style="color: white;">>v;</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(k>min_heap.size())</span>
<span style="color: white;">{</span>
<span style="color: white;">printf(</span><span style="color: #0086d2;">"-1\n"</span><span style="color: white;">);</span>
<span style="color: #fb660a; font-weight: bold;">continue</span><span style="color: white;">;</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(i=</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;i<k;i++)</span>
<span style="color: white;">{</span>
<span style="color: white;">t=</span> <span style="color: white;">min_heap.top();</span><span style="background-color: #0f140f; color: #008800; font-style: italic;">/*extract the first k minimum elements*/</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> </span><span style="background-color: #0f140f; color: white;">v.push_back(t);</span><span style="background-color: #0f140f; color: #008800; font-style: italic;"> /*and get the kth minimum*/</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;"> </span><span style="background-color: #0f140f; color: white;">min_heap.pop(); </span><span style="background-color: #0f140f; color: #008800; font-style: italic;"> /*and insert back in heap the rest*/</span>
<span style="color: white;">}</span>
<span style="color: white;">printf(</span><span style="color: #0086d2;">"%lld\n"</span><span style="color: white;">,v[k-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">]);</span>
<span style="color: white;">v.pop_back();</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(i=k-</span><span style="color: #0086f7; font-weight: bold;">2</span><span style="color: white;">;i>=</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;i--)</span>
<span style="color: white;">{</span>
<span style="color: white;">t=v[i];</span>
<span style="color: white;">min_heap.push(t);</span>
<span style="color: white;">v.pop_back();</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
The <b>Time complexity</b> of above implementation is <b>O(q*klog(n)).</b><br />
<br />
There is another method of finding kth smallest/largest element using order statistics which can be done in O(n). This will be discussed in next post.<br />
Till then<br />
<i>HAPPY CODING! :)</i><br />
<i><br /></i> <i><br /></i> <i>Contributed by Sunpriya Kaur Bhatia</i></div>
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-41038380893516691922017-12-13T00:19:00.003-08:002017-12-13T00:31:13.210-08:00Square Root Decomposition with range updates<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
Hello guys! Hope you all are doing well.</div>
In Codechef December challenge I came across a very interesting problem which can be solved using square root decomposition. So i am gonna explain the algorithm using that particular problem. <a href="https://www.codechef.com/DEC17/problems/CHEFEXQ/" target="_blank">Link to problem.</a><br />
<br />
<b>Pre-requisites: </b><i>properties of XOR operation.</i><br />
<a name='more'></a><b>Problem</b>:<br />
There is an array and we have to solve 2 types of queries on it:<br />
<ul>
<li><b>type 1:</b> Given two numbers <b>i</b> and <b>x</b>, the value at index <b>i</b> should be updated to <b>x</b>.</li>
<li><b>type 2:</b> Given two numbers <b>i</b> and <b>k</b>, your program should output the total number of <i>magical</i> subarrays with the last index β€ <b>i</b> in which the xor of all elements is equal to <b>k</b>.</li>
</ul>
<div>
<b>Solution for 50 marks: </b><br />
For type 1 query just update the given array in O(1) time.<br />
For type 2 query we can use dp. Make prefix_xor array for the given array. Now we can check where prefix_xor[i] = k in <b>linear time</b>.<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #111111; border-color: black; border-radius: 0%; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="background-color: #0f140f; color: #008800; font-style: italic;">// For type-2 query</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// a[] is the given array</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">ans</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;</span>
<span style="color: white;">prefix_xor[</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">]</span> <span style="color: white;">=</span> <span style="color: white;">a[</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">]</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(a[</span><span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">]</span> <span style="color: white;">==</span> <span style="color: white;">k){</span>
<span style="color: white;">ans++;</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">1</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n</span> <span style="color: white;">;</span> <span style="color: white;">i++){</span>
<span style="color: white;">prefix_xor[i]</span> <span style="color: white;">=</span> <span style="color: white;">prefix_xor[i-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">]</span> <span style="color: white;">^</span> <span style="color: white;">a[i];</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(prefix_xor[i]</span> <span style="color: white;">==</span> <span style="color: white;">k){</span>
<span style="color: white;">ans++;</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
</pre>
</div>
</div>
Linear time for each query is not sufficient to solve this problem, we need to reduce the complexity further. Let's see how can we do that.<br />
<br />
<b>Solution for 100 marks:</b><br />
First of all we will make a prefix_xor array similar to the one made above but only once. After this we will divide the prefix array into buckets each of size sqrt(n). Each bucket is sorted so that for query of type2 we can use binary search. We are also saving our original array(which is given) in b[]. <!-- HTML generated using hilite.me --><br />
<div style="background: #111111; border-color: black; border-radius: 0%; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #fb660a; font-weight: bold;">typedef</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: #cdcaa9; font-weight: bold;">long</span> <span style="color: white;">ll;</span>
<span style="color: #fb660a; font-weight: bold;">const</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">N</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">100010</span><span style="color: white;">;</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// inside main()</span>
<span style="color: white;">ll</span> <span style="color: white;">b[n],</span> <span style="color: white;">a[n];</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n;</span> <span style="color: white;">i++){</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">a[i];</span>
<span style="color: white;">b[i]</span> <span style="color: white;">=</span> <span style="color: white;">a[i];</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(i){</span>
<span style="color: white;">a[i]</span> <span style="color: white;">=</span> <span style="color: white;">(a[i]</span> <span style="color: white;">^</span> <span style="color: white;">a[i-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">]);</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// a[] is prefix_xor array</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="color: white;">vector<ll></span> <span style="color: white;">buckets[N];</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">num</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// num is number of buckets</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n;</span> <span style="color: white;">i</span> <span style="color: white;">+=</span> <span style="color: white;">(ll)sqrt(n),</span> <span style="color: white;">num++){</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">j</span> <span style="color: white;">=</span> <span style="color: white;">i</span> <span style="color: white;">;</span> <span style="color: white;">j</span> <span style="color: white;"><</span> <span style="color: white;">i</span> <span style="color: white;">+</span> <span style="color: white;">(ll)sqrt(n)</span> <span style="color: white;">&&</span> <span style="color: white;">j</span> <span style="color: white;"><</span> <span style="color: white;">n;</span> <span style="color: white;">j++){</span>
<span style="color: white;">buckets[num].push_back(a[j]);</span>
<span style="color: white;">}</span>
<span style="color: white;">sort(all(buckets[num]));</span>
<span style="color: white;">}</span>
</pre>
</div>
<br />
<b>For</b> <b>type-1 query</b> (i, x) in which we need to change only one element and we know that we are storing prefix xor in our buckets, so all the elements after this element needs to be updated also. Here we will use a lazy array which will update all buckets in sqrt(n) time. For each query of type 1 we need to update only one bucket (lets say <b>B</b>) in which given index <b>i </b>lies. Buckets which are after <b>B</b> are the ones in which all elements needs to be updated so, we just update the lazy[] with <b>(lazy[bucket_idx] ^ original_value_at_i ^ new_value_for_i).</b><br />
<b>Time Complexity:</b> O(sqrt(n)) for each query of type-1. <b> </b><br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #111111; border-color: black; border-radius: 0%; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i,</span> <span style="color: white;">new_val;</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">i</span> <span style="color: white;">>></span> <span style="color: white;">new_val;</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(type</span> <span style="color: white;">==</span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">){</span>
<span style="color: white;">ll</span> <span style="color: white;">lowest_bucket_index;</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// consider 0-based indexing</span>
<span style="color: white;">lowest_bucket_index</span> <span style="color: white;">=</span> <span style="color: white;">(i-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">)</span> <span style="color: white;">/</span> <span style="color: white;">(ll)sqrt(n);</span>
<span style="color: white;">ll</span> <span style="color: white;">buffer</span> <span style="color: white;">=</span> <span style="color: white;">(b[i-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">]</span> <span style="color: white;">^</span> <span style="color: white;">new_val);</span>
<span style="color: white;">b[idx-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">]</span> <span style="color: white;">=</span> <span style="color: white;">y;</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// update given index with new value</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// Empty the bucket 'B' which contain element at index i</span>
<span style="color: white;">buckets[lowest_bucket_index].clear();</span>
<span style="color: white;">ll</span> <span style="color: white;">lastidx</span> <span style="color: white;">=</span> <span style="color: white;">(lowest_bucket_index</span> <span style="color: white;">+</span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">)</span> <span style="color: white;">*</span> <span style="color: white;">(ll)sqrt(n);</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">//------- Update the first bucket 'B'--------</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: white;">idx</span> <span style="color: white;">-</span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">lastidx</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;">++){</span>
<span style="color: white;">a[i]</span> <span style="color: white;">=</span> <span style="color: white;">(a[i]</span> <span style="color: white;">^</span> <span style="color: white;">buffer);</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: white;">lowest_bucket_index</span> <span style="color: white;">*</span> <span style="color: white;">(ll)sqrt(n);</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">lastidx</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;">++){</span>
<span style="color: white;">buckets[lo_buck_num].pb(a[i]);</span>
<span style="color: white;">}</span>
<span style="color: white;">sort(all(buckets[lo_buck_num]));</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">//--------------------------------------------</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">//****** Update remaining buckets ************</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: white;">lo_buck_num+</span><span style="color: #0086f7; font-weight: bold;">1</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">num</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;">++){</span>
<span style="color: white;">lazy[i]</span> <span style="color: white;">=</span> <span style="color: white;">(lazy[i]</span> <span style="color: white;">^</span> <span style="color: white;">buffer);</span>
<span style="color: white;">}</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">//********************************************</span>
<span style="color: white;">}</span>
</pre>
</div>
<div>
<br />
<b>For type-2 Query(idx, y) </b>we need to find the number of indices < idx where prefix xor equals <b>y.</b> For this query we also search one bucket completely(upto index idx) in which idx lies. Buckets before this bucket, contain prefix xor in sorted order, so in each bucket we can do binary search 2 times to look for upper index for <b>y </b>and lower index for <b>y. </b>Finally add (<b>upper_idx - lower_idx + 1</b>) in the final answer for each bucket.<br />
<b>Note: </b>Buckets can be updated only when <b>XORred </b>with lazy[]. So is idea of binary search on the buckets is wrong? No it's not because we will update our search element <b>y</b> instead of updating each element of bucket by XORring it with lazy[bucket_idx].</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #111111; border-color: black; border-radius: 0%; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: white;">ll</span> <span style="color: white;">idx,</span> <span style="color: white;">y;</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">idx</span> <span style="color: white;">>></span> <span style="color: white;">y;</span>
<span style="color: white;">ll</span> <span style="color: white;">hi</span> <span style="color: white;">=</span> <span style="color: white;">idx-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: white;">hi_bucket_idx</span> <span style="color: white;">=</span> <span style="color: white;">hi</span> <span style="color: white;">/</span> <span style="color: white;">(ll)sqrt(n);</span>
<span style="color: white;">ll</span> <span style="color: white;">startidx</span> <span style="color: white;">=</span> <span style="color: white;">hi_bucket_idx</span> <span style="color: white;">*</span> <span style="color: white;">(ll)sqrt(n);</span>
<span style="color: white;">ll</span> <span style="color: white;">ans</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: white;">startidx;</span> <span style="color: white;">i</span> <span style="color: white;"><=</span> <span style="color: white;">hi</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;">++){</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">((a[i]^lazy[hi_bucket_idx])</span> <span style="color: white;">==</span> <span style="color: white;">y){</span>
<span style="color: white;">ans++;</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="background-color: #0f140f; color: #008800; font-style: italic;">// Binary search, for each bucket < hi_bucket_idx</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">hi_bucket_idx</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;">++){</span>
<span style="color: white;">ll</span> <span style="color: white;">foo;</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// upper index</span>
<span style="color: white;">ll</span> <span style="color: white;">bar;</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// lower index</span>
<span style="color: white;">foo</span> <span style="color: white;">=</span> <span style="color: white;">bar</span> <span style="color: white;">=</span> <span style="color: white;">-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: white;">ll</span> <span style="color: white;">left,</span> <span style="color: white;">right;</span>
<span style="color: white;">left</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;</span>
<span style="color: white;">ll</span> <span style="color: white;">x</span> <span style="color: white;">=</span> <span style="color: white;">(y</span> <span style="color: white;">^</span> <span style="color: white;">lazy[i]);</span> <span style="background-color: #0f140f; color: #008800; font-style: italic;">// update search element y</span>
<span style="color: white;">right</span> <span style="color: white;">=</span> <span style="color: white;">buckets[i].size()-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">while</span><span style="color: white;">(left</span> <span style="color: white;"><=</span> <span style="color: white;">right){</span>
<span style="color: white;">ll</span> <span style="color: white;">mid</span> <span style="color: white;">=</span> <span style="color: white;">(left</span> <span style="color: white;">+</span> <span style="color: white;">right)</span> <span style="color: white;">>></span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">((mid</span> <span style="color: white;">==</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">||</span> <span style="color: white;">(x</span> <span style="color: white;">></span> <span style="color: white;">buckets[i][mid-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">]))</span> <span style="color: white;">&&</span> <span style="color: white;">buckets[i][mid]</span> <span style="color: white;">==</span> <span style="color: white;">x){</span>
<span style="color: white;">bar</span> <span style="color: white;">=</span> <span style="color: white;">mid;</span><span style="color: #fb660a; font-weight: bold;">break</span><span style="color: white;">;</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">else</span> <span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(x</span> <span style="color: white;">></span> <span style="color: white;">buckets[i][mid]){</span>
<span style="color: white;">left</span> <span style="color: white;">=</span> <span style="color: white;">mid+</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">else</span><span style="color: white;">{</span>
<span style="color: white;">right</span> <span style="color: white;">=</span> <span style="color: white;">mid-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="color: white;">left</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;</span>
<span style="color: white;">right</span> <span style="color: white;">=</span> <span style="color: white;">buckets[i].size()-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">while</span><span style="color: white;">(left</span> <span style="color: white;"><=</span> <span style="color: white;">right){</span>
<span style="color: white;">ll</span> <span style="color: white;">mid</span> <span style="color: white;">=</span> <span style="color: white;">(left</span> <span style="color: white;">+</span> <span style="color: white;">right)</span> <span style="color: white;">>></span> <span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">((mid</span> <span style="color: white;">==</span> <span style="color: white;">sz(buckets[i])-</span><span style="color: #0086f7; font-weight: bold;">1</span> <span style="color: white;">||</span> <span style="color: white;">(x</span> <span style="color: white;"><</span> <span style="color: white;">buckets[i][mid+</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">]))</span> <span style="color: white;">&&</span> <span style="color: white;">buckets[i][mid]</span> <span style="color: white;">==</span> <span style="color: white;">x){</span>
<span style="color: white;">foo</span> <span style="color: white;">=</span> <span style="color: white;">mid;</span><span style="color: #fb660a; font-weight: bold;">break</span><span style="color: white;">;</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">else</span> <span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(x</span> <span style="color: white;"><</span> <span style="color: white;">buckets[i][mid])</span>
<span style="color: white;">right</span> <span style="color: white;">=</span> <span style="color: white;">mid-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">else</span>
<span style="color: white;">left</span> <span style="color: white;">=</span> <span style="color: white;">mid+</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">;</span>
<span style="color: white;">}</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(foo</span> <span style="color: white;">>=</span> <span style="color: white;">bar</span> <span style="color: white;">and</span> <span style="color: white;">foo</span> <span style="color: white;">!=</span> <span style="color: white;">-</span><span style="color: #0086f7; font-weight: bold;">1</span> <span style="color: white;">and</span> <span style="color: white;">bar</span> <span style="color: white;">!=</span> <span style="color: white;">-</span><span style="color: #0086f7; font-weight: bold;">1</span><span style="color: white;">){</span>
<span style="color: white;">ans</span> <span style="color: white;">+=</span> <span style="color: #0086f7; font-weight: bold;">1</span> <span style="color: white;">+</span> <span style="color: white;">foo</span> <span style="color: white;">-</span> <span style="color: white;">bar;</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="color: white;">cout</span> <span style="color: white;"><<</span> <span style="color: white;">ans</span> <span style="color: white;"><<</span> <span style="color: white;">endl;</span>
</pre>
</div>
<div>
<b>Time Complexity: </b>O(sqrt(n) * log(n)) for each query of type-2.<br />
<br />
Thank you guys for reading this post. If you find anything wrong in this post please comment below and i hope you learnt something usefull from this post.<br />
-<i> Happy Coding </i>
</div>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-6936988633068797642017-12-10T22:37:00.000-08:002017-12-15T23:09:18.299-08:00Lazy Propagation on segment tree<div dir="ltr" style="text-align: left;" trbidi="on">
<b><u>LAZY PROPAGATION</u></b><br />
<br />
This is for the update query in the minimum range query question.The brute force method involves<br />
various updates in the segment tree for just one query.However ,in lazy propogation,the update is<br />
only propogated to the child nodes as and when it is required i.e. we maintain another array which<br />
keeps the track of all the previous updates which have not been made yet in the segment tree and<br />
will update only when there is a query on that particular range.<br />
<br />
<a name='more'></a><br />
The main idea is to maintain an array lazy of the same size as that of segment tree,and initialize<br />
it to 0.A <i>zero</i> at any position indicates that there are no updates from previous queries and<br />
a <i>non-zero</i> value indicates that there are some updates which have yet not been made on that position<br />
and propagated.<br />
<br />
<b><u>Algorithm to update a range of values.</u></b><br />
<br />
update(l,r) //update in range [l-r)<br />
1.if the current segment of tree has any pending update,add that to current node.<br />
2.If current node's range lies completely in<br />
update query range.<br />
a) Update current node<br />
b) Postpone updates to children by setting<br />
lazy value for children nodes.<br />
3) If current node's range overlaps with update<br />
range, follow the same approach as above simple<br />
update.<br />
a) Recur for left and right children.<br />
b) Update current node using results of left<br />
and right calls.<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f0f0f0; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #902000;">void</span> <span style="color: #06287e;">updateLazy</span>(<span style="color: #902000;">int</span> segtree[],<span style="color: #902000;">int</span> lazy[],<span style="color: #902000;">int</span> l,<span style="color: #902000;">int</span> r,<span style="color: #902000;">int</span> low,<span style="color: #902000;">int</span> high,<span style="color: #902000;">int</span> pos,<span style="color: #902000;">int</span> k)
{
<span style="color: #007020; font-weight: bold;">if</span>(low<span style="color: #666666;">></span>high)
<span style="color: #007020; font-weight: bold;">return</span>;
<span style="color: #60a0b0; font-style: italic;">/*make sure all propogation is done at the pos</span>
<span style="color: #60a0b0; font-style: italic;"> if not update the pos and pass the update to its children*/</span>
<span style="color: #007020; font-weight: bold;">if</span>(lazy[pos]<span style="color: #666666;">!=</span><span style="color: #40a070;">0</span>)
{
segtree[pos]<span style="color: #666666;">+=</span>lazy[pos];
<span style="color: #007020; font-weight: bold;">if</span>(low<span style="color: #666666;">!=</span>high) <span style="color: #60a0b0; font-style: italic;">//if its not a leaf node</span>
{
lazy[<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>]<span style="color: #666666;">+=</span>lazy[pos];
lazy[<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">2</span>]<span style="color: #666666;">+=</span>lazy[pos];
}
lazy[pos]<span style="color: #666666;">=</span><span style="color: #40a070;">0</span>;
}
<span style="color: #60a0b0; font-style: italic;">//no overlap condition</span>
<span style="color: #007020; font-weight: bold;">if</span>(l<span style="color: #666666;">></span>high<span style="color: #666666;">||</span>r<span style="color: #666666;"><</span>low)
{
<span style="color: #007020; font-weight: bold;">return</span> ;
}
<span style="color: #60a0b0; font-style: italic;">//total overlap</span>
<span style="color: #007020; font-weight: bold;">else</span> <span style="color: #007020; font-weight: bold;">if</span>(l<span style="color: #666666;"><=</span>low<span style="color: #666666;">&&</span>r<span style="color: #666666;">>=</span>high)
{
segtree[pos]<span style="color: #666666;">+=</span>k;
<span style="color: #007020; font-weight: bold;">if</span>(low<span style="color: #666666;">!=</span>high) <span style="color: #60a0b0; font-style: italic;">//if its not leaf</span>
{
lazy[<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>]<span style="color: #666666;">+=</span>k;
lazy[<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">2</span>]<span style="color: #666666;">+=</span>k;
}
<span style="color: #007020; font-weight: bold;">return</span>;
}
<span style="color: #007020; font-weight: bold;">else </span><i><span style="color: #007020;"> </span><span style="color: #666666;">//partial overlap</span></i>
{
<span style="color: #902000;">int</span> mid<span style="color: #666666;">=</span>(low<span style="color: #666666;">+</span>high)<span style="color: #666666;">/</span><span style="color: #40a070;">2</span>;
updateLazy(segtree,lazy,l,r,low,mid,<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>,k);
updateLazy(segtree,lazy,l,r,mid<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>,high,<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">2</span>,k);
segtree[pos]<span style="color: #666666;">=</span>min(segtree[<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>],segtree[<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">2</span>]);
}
}</pre>
</td></tr>
</tbody></table>
</div>
<br />
<br />
The above code is for minimum range query question.<br />
Practice more problems on online platform..<br />
HAPPY CODING!</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-9121020968531537482017-12-09T02:20:00.000-08:002017-12-09T03:02:33.856-08:00Segment Trees and range minimum query<div dir="ltr" style="text-align: left;" trbidi="on">
<b><u>SEGMENTED TREES</u></b><br />
<br />
We generally come across question involving range queries and update queries which may or may not require to print output after each queries.<br />
For example:-we have an array arr[0.....n-1] and following two queries:<br />
1.find minimum in range [l,r] where 0<l<r<n and output it.<br />
2.upadate each value in range [l,r] and output the new array.<br />
<br />
<a name='more'></a><br />
<br />
<b><u>Brute force approach</u></b>:Run a loop for each query from l-r and find the minimum or update the array.<br />
This approach takes O(n) time for each query and if the number of queries is large,the total time<br />
would be of order O(m*n) {m being the number of queries} , which is not expected to be a good time<br />
complexity.<br />
<br />
<b><u>Segmented tree approach</u></b>:This approach takes O(log(n)) time to perform both the operations which is<br />
definitely way better than O(m*n).<br />
<br />
<b><u>Representation of segment tree:</u></b><br />
1.All the leaf nodes are the elements of the array<br />
2.Each internal node belong to an interval and root node belonging to interval [0,n).<br />
3.Each node will have two children ,left and right,each of whoes interval will be<br />
[l,mid) and [mid,r) respectively, mid=(l+r)/2.<br />
<br />
The above was a conceptual representation of a segmented tree.physically the tree is stored in the<br />
form of an array . Each element at an index i has its children at index 2*i+1 and 2*i+2 for left<br />
and right respectively. The tree will have atmost 4*n nodes.<br />
<br />
<b><u>In context to the minimum range query:</u></b><br />
1. Leaf nodes represent the elements of array<br />
2. The internal nodes will represent the minimum of all leaves below it.<br />
<br />
<b><u>How to answer range query?</u></b><br />
<br />
You are given a range [l,r).there are three possible cases<br />
1. <b>Partial overlap </b>-check both the children<br />
2. <b>Complete overlap</b> - we stop here and return the value of the node<br />
3. <b>No </b><b>overlap </b>- in this we stop there itself and return a large value<br />
<br />
<b>The code is as follows:</b><br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f0f0f0; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #007020;">#include<bits/stdc++.h></span>
<span style="color: #007020; font-weight: bold;">using</span> <span style="color: #007020; font-weight: bold;">namespace</span> std;
<span style="color: #902000;">void</span> <span style="color: #06287e;">buildTree</span>(<span style="color: #902000;">int</span> tree[],<span style="color: #902000;">int</span> arr[],<span style="color: #902000;">int</span> pos,<span style="color: #902000;">int</span> low,<span style="color: #902000;">int</span> high)
{
<span style="color: #007020; font-weight: bold;">if</span>(low<span style="color: #666666;">==</span>high)
{
tree[pos]<span style="color: #666666;">=</span>arr[low];
<span style="color: #007020; font-weight: bold;">return</span>;
}
<span style="color: #007020; font-weight: bold;">else</span>
{
<span style="color: #902000;">int</span> mid<span style="color: #666666;">=</span>(low<span style="color: #666666;">+</span>high)<span style="color: #666666;">/</span><span style="color: #40a070;">2</span>;
buildTree(tree,arr,<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>,low,mid);
buildTree(tree,arr,<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">2</span>,mid<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>,high);
tree[pos]<span style="color: #666666;">=</span>min(tree[<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>],tree[<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">2</span>]);
}
}
<span style="color: #902000;">int</span> <span style="color: #06287e;">rangeQuery</span> (<span style="color: #902000;">int</span> tree[],<span style="color: #902000;">int</span> pos, <span style="color: #902000;">int</span> low, <span style="color: #902000;">int</span> high, <span style="color: #902000;">int</span> l, <span style="color: #902000;">int</span> r)
{
<span style="color: #007020; font-weight: bold;">if</span>(l<span style="color: #666666;"><=</span>low<span style="color: #666666;">&&</span>r<span style="color: #666666;">>=</span>high)
<span style="color: #007020; font-weight: bold;">return</span> tree[pos]; <span style="color: #60a0b0; font-style: italic;">//total overlap</span>
<span style="color: #007020; font-weight: bold;">if</span>(l<span style="color: #666666;">></span>high<span style="color: #666666;">||</span>r<span style="color: #666666;"><</span>low)
<span style="color: #007020; font-weight: bold;">return</span> INT_MAX; <span style="color: #60a0b0; font-style: italic;">//no overlap</span>
<span style="color: #902000;">int</span> mid<span style="color: #666666;">=</span>(low<span style="color: #666666;">+</span>high)<span style="color: #666666;">/</span><span style="color: #40a070;">2</span>;
<span style="color: #007020; font-weight: bold;">return</span> min(rangeQuery(tree,<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>,low,mid,l,r),rangeQuery(tree,<span style="color: #40a070;">2</span><span style="color: #666666;">*</span>pos<span style="color: #666666;">+</span><span style="color: #40a070;">2</span>,mid<span style="color: #666666;">+</span><span style="color: #40a070;">1</span>,high,l,r));<span style="color: #60a0b0; font-style: italic;">//partial overlap</span>
}
main()
{
<span style="color: #902000;">int</span> arr[]<span style="color: #666666;">=</span>{<span style="color: #40a070;">1</span>,<span style="color: #40a070;">3</span>,<span style="color: #40a070;">5</span>,<span style="color: #40a070;">2</span>,<span style="color: #40a070;">6</span>,<span style="color: #40a070;">7</span>,<span style="color: #40a070;">8</span>};
<span style="color: #902000;">int</span> tree[<span style="color: #40a070;">10</span>];
buildTree(tree,arr,<span style="color: #40a070;">0</span>,<span style="color: #40a070;">0</span>,<span style="color: #40a070;">7</span>);
cout<span style="color: #666666;"><<</span>rangeQuery(tree,<span style="color: #40a070;">0</span>,<span style="color: #40a070;">0</span>,<span style="color: #40a070;">7</span>,<span style="color: #40a070;">3</span>,<span style="color: #40a070;">5</span>); <span style="color: #60a0b0; font-style: italic;">//min from 3-5</span>
cout<span style="color: #666666;"><<</span>rangeQuery(tree,<span style="color: #40a070;">0</span>,<span style="color: #40a070;">0</span>,<span style="color: #40a070;">7</span>,<span style="color: #40a070;">0</span>,<span style="color: #40a070;">5</span>); <span style="color: #60a0b0; font-style: italic;">//min from 0-5</span>
}
</pre>
</td></tr>
</tbody></table>
</div>
</div>
<div>
This article is contributed by Sunpriya Kaur Bhatia and i hope now you can implement segment tree without any problem. Lazy propagation will be discussed in next post. <br>
<i>Thanks,<br> Happy Coding !</i>
</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-86814459616843152502017-10-20T01:57:00.000-07:002017-10-20T02:09:34.778-07:00Selection Sort<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>Hey Everyone !</b><br />
In this article i am going to describe the <b> Selection Sort Algorithm</b> which has a complexity of <b>O(n^2)</b> and people don't prefer to use this algorithm in competitve programming contests, but i am writing this because it can be asked in viva or during exams in colleges. <br />
<a name='more'></a><hr />
<b> What is Selection Sort?</b><br />
Selection sort is just a sorting algorithm which sorts the given array in the ascending order order by selecting the minimum element(say M) from the array, and then selecting the next minimum element(say P) from the array and this time not considering the last minimum element(ignoring M this time)and this goes on until the whole array elements are covered by continuously ignoring the previous minimum elements. Similarly we can sort the array in reverse order by selcting the maximum element everytime instead of minimum. Lets have a look at the procedure. Observe how we are ignoring the previously selected minimum elements by using a variable start and method swap().<br />
<b> Procedure: </b><br />
<i>Note: Consider 0-based indexing of array elements!</i><br />
<ol>
<li>Let start = 0 and end = n where n is the size of the array.</li>
<li>Find the minimum element in the array from start to end.</li>
<li>Swap this minimum element with the element at the index represented by value of variable start.</li>
<li>Increment start by 1.</li>
<li>Repeat the procedure from step 2 to step 4 until (start != end).</li>
<li>Thats it !</li>
</ol>
<hr />
<b>Example</b><br />
let n = 5, Array a[ ] = {4, 2, 6, 3, 1}<br />
start = 0 and end = 4<br />
Minimum element from index 0 to 4 is 1. So swap 1 with 4.<br />
a[ ] = {1, 2, 6, 3, 4} and start = 0 + 1 = 1<br />
Minimum element from index 1 to 4 is 2. So swap 2 with 2.<br />
a[ ] = {1, 2, 6, 3, 4} and start = 1 + 1 = 2<br />
Minimum element from index 2 to 4 is 3. So swap 3 with 6.<br />
a[ ] = {1, 2, 3, 6, 4} and start = 2 + 1 = 3<br />
Minimum element from index 3 to 4 is 4. So swap 4 with 6.<br />
a[ ] = {1, 2, 3, 4, 6} and start = 3 + 1 = 4<br />
Minimum element from index 4 to 4 is 6. So swap 6 with 6.<br />
a[ ] = {1, 2, 3, 4, 6} and start = 4 + 1 = 5<br />
Now start becomes equal to n, so we stop at this point.<br />
<h3>
Implementation in C++</h3>
<!-- HTML generated using hilite.me --><br />
<div style="background: #111111; border-color: black; border-radius: 0%; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="background-color: #0f140f; color: #ff0007; font-style: italic; font-weight: bold;">#include<bits/stdc++.h></span>
<span style="color: #fb660a; font-weight: bold;">using</span> <span style="color: #fb660a; font-weight: bold;">namespace</span> <span style="color: white;">std;</span>
<span style="color: #cdcaa9; font-weight: bold;">void</span> <span style="color: #ff0086; font-weight: bold;">SelectionSort</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">*a,</span> <span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">n){</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">start</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span><span style="color: white;">;</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">end</span> <span style="color: white;">=</span> <span style="color: white;">n;</span>
<span style="color: #fb660a; font-weight: bold;">while</span><span style="color: white;">(start</span> <span style="color: white;">!=</span> <span style="color: white;">end){</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">mini</span> <span style="color: white;">=</span> <span style="color: white;">INT_MAX,</span> <span style="color: white;">idx</span> <span style="color: white;">=</span> <span style="color: white;">start;</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: white;">start</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">end;</span> <span style="color: white;">i</span> <span style="color: white;">++){</span>
<span style="color: #fb660a; font-weight: bold;">if</span><span style="color: white;">(mini</span> <span style="color: white;">></span> <span style="color: white;">a[i]){</span>
<span style="color: white;">mini</span> <span style="color: white;">=</span> <span style="color: white;">a[i];</span>
<span style="color: white;">idx</span> <span style="color: white;">=</span> <span style="color: white;">i;</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="color: white;">swap(a[start],</span> <span style="color: white;">a[idx]);</span>
<span style="color: white;">start++;</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: #ff0086; font-weight: bold;">main</span><span style="color: white;">(){</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">n;</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">n;</span>
<span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">a[n];</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;">++)</span> <span style="color: white;">{</span>
<span style="color: white;">cin</span> <span style="color: white;">>></span> <span style="color: white;">a[i];</span>
<span style="color: white;">}</span>
<span style="color: white;">SelectionSort(a,</span> <span style="color: white;">n);</span>
<span style="color: white;">cout</span> <span style="color: white;"><<</span> <span style="color: #0086d2;">"After Sorting:\n"</span><span style="color: white;">;</span>
<span style="color: #fb660a; font-weight: bold;">for</span><span style="color: white;">(</span><span style="color: #cdcaa9; font-weight: bold;">int</span> <span style="color: white;">i</span> <span style="color: white;">=</span> <span style="color: #0086f7; font-weight: bold;">0</span> <span style="color: white;">;</span> <span style="color: white;">i</span> <span style="color: white;"><</span> <span style="color: white;">n</span> <span style="color: white;">;</span> <span style="color: white;">i++){</span>
<span style="color: white;">cout</span> <span style="color: white;"><<</span> <span style="color: white;">a[i]</span> <span style="color: white;"><<</span> <span style="color: #0086d2;">" "</span><span style="color: white;">;</span>
<span style="color: white;">}</span>
<span style="color: white;">}</span>
</pre>
</div>
<hr />
<b> Complexity:</b>
Time Complexity is clearly O(n^2).
We used 2 nested loops and outer loop runs from 0 to n and inner loop runs from start to n where variable start increments by 1 in every step.<br />
Let counter = 0 (initially).<br />
initially start = 0, so inner loop runs from 0 to n. Counter = n<br />
now start = 1, so inner loop runs from 1 to n. Counter = n + (n - 1)<br />
....<br />
....<br />
....<br />
now start = n - 1, so inner loop runs from (n - 1) to n. Counter = n + (n - 1) + . . . . + 1.<br />
So Counter = n * ( n + 1 ) / 2.<br />
Hence complexity is O(n^2).<br />
Refer CLRS to know more abot complexity of algorithms.<br />
<hr />
<blockquote>
Thank You for reading this post !</blockquote>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-62987075802692971052017-08-06T10:02:00.000-07:002017-08-06T10:08:59.042-07:00Z-Algorithm<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>Contents :</b>
<br />
<ul>
<li><i>Objective of this post</i></li>
<li><i>An Awesome video tutorial on You Tube</i></li>
<li><i>Implementation in C++</i></li>
<li><i> Practice Problems <a name='more'></a></i></li>
</ul>
<hr />
<ol>
<li><b>Objective of this post :</b> In problems of string matching or searching we often try to apply library functions like find() in C++ or try to apply brute force, but most of the time we get TLE. Let N = length of the text and M = length of pattern which we need to search in the given text. We got TLE because in these cases our complexity is O(n*m). But we can reduce it to O(n + m) using some efficient string searching algorithms which requires some preprocessing like : <br />
<ol>
<li>KMP String search Algorithm
</li>
<li>Z Algorithm </li>
</ol>
Z-Algorithm can be used directly or as a subproblem in problems like :<br />
<ul>
<li>Find the all the occurrence of a string in the given text.</li>
<li>Find the long prefix which is also a suffix. </li>
<li> And many more. . .</li>
</ul>
</li>
<li><h3>
Z-Algorithm with implementation in JAVA</h3>
<iframe allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/CpZh4eF8QBw" width="560"></iframe>
</li>
<li><b>Implementation in C++ :</b>
<!-- HTML generated using hilite.me --><div style="background: #f8f8f8; border-color: green; border-radius: 5%; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800;">#include<bits/stdc++.h></span>
<span style="color: #aa22ff; font-weight: bold;">using</span> <span style="color: #aa22ff; font-weight: bold;">namespace</span> std;
<span style="color: #aa22ff; font-weight: bold;">typedef</span> <span style="color: #00bb00; font-weight: bold;">long</span> <span style="color: #00bb00; font-weight: bold;">long</span> ll;
<span style="color: #00bb00; font-weight: bold;">void</span> <span style="color: #00a000;">ZAlgorithm</span>(string text, string pattern){
string s <span style="color: #666666;">=</span> pattern <span style="color: #666666;">+</span> <span style="color: #bb4444;">"$"</span> <span style="color: #666666;">+</span> text;
<span style="color: #00bb00; font-weight: bold;"> int</span> n <span style="color: #666666;">=</span> s.size();
<span style="color: #00bb00; font-weight: bold;"> int</span> Z[n] <span style="color: #666666;">=</span> {<span style="color: #666666;">0</span>};
<span style="color: #00bb00; font-weight: bold;"> int</span> j <span style="color: #666666;">=</span> <span style="color: #666666;">0</span>, lo, hi;
lo <span style="color: #666666;">=</span> hi <span style="color: #666666;">=</span> <span style="color: #666666;">0</span>;
<span style="color: #aa22ff; font-weight: bold;">for</span>(<span style="color: #00bb00; font-weight: bold;">int</span> i <span style="color: #666666;">=</span> <span style="color: #666666;">1</span> ; i <span style="color: #666666;"><</span> n ; i <span style="color: #666666;">++</span>){
<span style="color: #aa22ff; font-weight: bold;"> if</span>(hi <span style="color: #666666;"><</span> i){
lo <span style="color: #666666;">=</span> hi <span style="color: #666666;">=</span> i;
<span style="color: #aa22ff; font-weight: bold;">while</span>(hi <span style="color: #666666;"><</span> n and s[hi <span style="color: #666666;">-</span> lo] <span style="color: #666666;">==</span> s[hi]){
hi<span style="color: #666666;">++</span>;
}
Z[i] <span style="color: #666666;">=</span> hi <span style="color: #666666;">-</span> lo;
hi<span style="color: #666666;">--</span>;
}<span style="color: #aa22ff; font-weight: bold;">else</span>{
<span style="color: #00bb00; font-weight: bold;"> int</span> x <span style="color: #666666;">=</span> i <span style="color: #666666;">-</span> lo;
<span style="color: #aa22ff; font-weight: bold;">if</span>(Z[x] <span style="color: #666666;"><</span> hi <span style="color: #666666;">-</span> i <span style="color: #666666;">+</span> <span style="color: #666666;">1</span>){
Z[i] <span style="color: #666666;">=</span> Z[x];
}<span style="color: #aa22ff; font-weight: bold;">else</span>{
lo <span style="color: #666666;">=</span> i;
<span style="color: #aa22ff; font-weight: bold;"> while</span>(hi <span style="color: #666666;"><</span> n and s[hi <span style="color: #666666;">-</span> lo] <span style="color: #666666;">==</span> s[hi]){
hi<span style="color: #666666;">++</span>;
}
Z[i] <span style="color: #666666;">=</span> hi <span style="color: #666666;">-</span> lo;
hi<span style="color: #666666;">--</span>;
}
}
}
cout <span style="color: #666666;"><<</span> <span style="color: #bb4444;">"Pattern found at following indices</span><span style="color: #bb6622; font-weight: bold;">\n</span><span style="color: #bb4444;">"</span>;
<span style="color: #aa22ff; font-weight: bold;"> for</span>(<span style="color: #00bb00; font-weight: bold;">int</span> i <span style="color: #666666;">=</span> <span style="color: #666666;">0</span> ; i <span style="color: #666666;"><</span> n ; i <span style="color: #666666;">++</span>){
<span style="color: #aa22ff; font-weight: bold;"> if</span>(Z[i] <span style="color: #666666;">==</span> pattern.size()){
cout <span style="color: #666666;"><<</span> i <span style="color: #666666;">-</span> pattern.size() <span style="color: #666666;"><<</span> endl;
}
}
}
<span style="color: #00bb00; font-weight: bold;">int</span> <span style="color: #00a000;">main</span>(){
string text, pattern;
cin <span style="color: #666666;">>></span> text <span style="color: #666666;">>></span> pattern;
ZAlgorithm(text, pattern);
}
</pre>
</td></tr>
</tbody></table>
</div>
</li>
<li><b>Practice Problems :</b><br />
<a href="https://www.hackerearth.com/practice/algorithms/string-algorithm/z-algorithm/practice-problems/">Link</a><br />
</li>
</ol>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-66874260658205903662017-07-27T00:46:00.001-07:002017-07-27T00:51:17.801-07:00All about Trie data structure !<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>Contents :</b>
<br />
<ol>
<li><i>Introduction to Trie</i></li>
<li><i>Insertion of a string in Trie</i> </li>
<li><i>Searching a string in a Trie</i></li>
<li><i>Application : <b>Auto-Complete the keyword<a name='more'></a></b></i></li>
</ol>
<hr />
<ul>
<li><b>Introduction to Trie :</b><br />
Trie is a data structure which is very efficient for information retrieval and in competitive programming it has many applications. Using tries we can search a keyword in O(n) time in a dictionary where <b>n</b> is the length of keyword.
To insert an element in a trie we also need O(n) time. But it is not memory efficient as each node of a trie consists of multiple branches where each branch represents a possible character of keys. We need to mark last node for every string so that when we search for a key in trie we must know its endpoint. Lets see how data is stored in a trie with the help of an example.<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgY6AWz0Ae_N1aDIxixDrcP028lJEIivW7r2clEefuTfvQuCfDPP4QLvWALdCUVbBCMQ7_6cz5xU4hh39GiMc2b-SmJBGwGlgbM5lEWHDFdW3nnpgG3Ypdlb25OTE06Rn_GTfeCu-Lii3KO/s1600/trie.png" imageanchor="1"><img border="0" data-original-height="426" data-original-width="521" height="521" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgY6AWz0Ae_N1aDIxixDrcP028lJEIivW7r2clEefuTfvQuCfDPP4QLvWALdCUVbBCMQ7_6cz5xU4hh39GiMc2b-SmJBGwGlgbM5lEWHDFdW3nnpgG3Ypdlb25OTE06Rn_GTfeCu-Lii3KO/s640/trie.png" width="640" /></a>
So this is how data is stored in a trie. Green nodes are the special nodes indicating the end of a particular string. Lets see the structure we need to make this trie. First of all we need a boolean variable which is true for special nodes. We need various pointers depending on type of data, lets consider our data consists of only lowercase alphabets. So we need 26 pointers.<br />
<!-- HTML generated using hilite.me --><div style="background: #ffffff; border-color: blue; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;">1
2
3
4</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-weight: bold;">struct</span> trie{
<span style="color: #333399; font-weight: bold;">bool</span> isleaf; <span style="color: #888888;">// True when special node</span>
trie <span style="color: #333333;">*</span> next[<span style="color: #0000dd; font-weight: bold;">26</span>]; <span style="color: #888888;">// Pointers to next possible charatcers</span>
};
</pre>
</td></tr>
</tbody></table>
</div>
<br />
So, now we know the structure of trie, lets move to insertion part.<br />
</li>
<li>
<b>Insertion of a string in Trie :</b><br />
We are given the string to insert in the trie and the root node of the trie. In order to insert the string in the trie we iterate through all the characters in the given string. Initially we are at root node. So we need to check if there is a pointer to node corresponding to the first character of the string. If found then just jump to that node and check the next character of the string. But if node is not found (i.e. NULL), at this point we need to create a new node and save the pointer to that node in the root node and jump to that node. Similarly do this for every character of the string. Once all the characters are found (corresponding pointers) or inserted in the trie mark the special variable of last node as true.<br />
<b>Implementation :</b>
<!-- HTML generated using hilite.me --><div style="background: #ffffff; border-color: blue; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26</pre>
</td><td><pre style="line-height: 125%; margin: 0;">trie <span style="color: #333333;">*</span> <span style="color: #0066bb; font-weight: bold;">getNode</span>(){
trie <span style="color: #333333;">*</span> node <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> trie();
node<span style="color: #333333;">-></span>isleaf <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> <span style="color: #0000dd; font-weight: bold;">26</span> ; i <span style="color: #333333;">++</span>){
node<span style="color: #333333;">-></span>next[i] <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>;
}
<span style="color: #008800; font-weight: bold;">return</span> node;
}
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">insert</span>(string s, trie <span style="color: #333333;">*</span>root){
trie <span style="color: #333333;">*</span> node <span style="color: #333333;">=</span> root;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> s.size() ; i <span style="color: #333333;">++</span>){
<span style="color: #333399; font-weight: bold;">int</span> index <span style="color: #333333;">=</span> s[i] <span style="color: #333333;">-</span> <span style="color: #0044dd;">'a'</span>; <span style="color: #888888;">// index of pointer corresponding to ith char of string </span>
<span style="color: #008800; font-weight: bold;">if</span>(node<span style="color: #333333;">-></span>next[index] <span style="color: #333333;">==</span> <span style="color: #007020;">NULL</span>){ <span style="color: #888888;">// if pointer does'nt exists</span>
trie <span style="color: #333333;">*</span> temp <span style="color: #333333;">=</span> getNode(); <span style="color: #888888;">// create a new node</span>
node<span style="color: #333333;">-></span>next[index] <span style="color: #333333;">=</span> temp; <span style="color: #888888;">// save the pointer to new node </span>
}
node <span style="color: #333333;">=</span> node<span style="color: #333333;">-></span>next[index]; <span style="color: #888888;">// jump to next node </span>
}
node<span style="color: #333333;">-></span>isleaf <span style="color: #333333;">=</span> <span style="color: #007020;">true</span>; <span style="color: #888888;">// mark special node : True</span>
}
<span style="color: #888888;">// inside int main()</span>move to
trie <span style="color: #333333;">*</span>root <span style="color: #333333;">=</span> getNode();
insert(<span style="background-color: #fff0f0;">"happy"</span> , root);
</pre>
</td></tr>
</tbody></table>
</div>
<b> Complexity : </b><br />
As we have only one loop for covering all the characters of the string (0 to size of keyword), so time complexity is of order n i.e. <b>O(n)</b>, where n is size of keyword.<br />
</li>
<li>
<b>
Searching a string in a Trie :</b><br />
Searching is also an easier task once you understand the insertion part clearly. We start from root node and look the next node corresponding to the first character of the string. If node is not found then return false as string is not present in the trie. If corresponding node is found we move to next character of the string and jump to the corresponding node. We do the same for all other characters of the string. Once we checked all the characters of the string, we need one final check which is to check the special variable of the last node. If special variable of last node is true it means that string exists in the trie otherwise the given string is one of the prefix of a bigger string that exists in the trie.
<br />
<b>Implementation :</b>
<!-- HTML generated using hilite.me --><div style="background: #ffffff; border-color: blue; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #333399; font-weight: bold;">bool</span> <span style="color: #0066bb; font-weight: bold;">search</span>(string s, trie <span style="color: #333333;">*</span> root){
trie <span style="color: #333333;">*</span> node <span style="color: #333333;">=</span> root;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> s.size() ; i <span style="color: #333333;">++</span>){
<span style="color: #333399; font-weight: bold;">int</span> index <span style="color: #333333;">=</span> s[i] <span style="color: #333333;">-</span> <span style="color: #0044dd;">'a'</span>;
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: #333333;">!</span>node<span style="color: #333333;">-></span>next[index]){ <span style="color: #888888;">// Checking the pointer corresponding to given string </span>
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>; <span style="color: #888888;">// Not Found</span>
}
node <span style="color: #333333;">=</span> node<span style="color: #333333;">-></span>next[index];
}
<span style="color: #008800; font-weight: bold;">return</span> (node<span style="color: #333333;">-></span>isleaf <span style="color: #333333;">==</span> <span style="color: #007020;">true</span>); <span style="color: #888888;">// Return true if special is true </span>
}
</pre>
</td></tr>
</tbody></table>
</div>
<b> Complexity : O(n), n = length of keyword</b><br />
</li>
<li> Application : <b>Auto-Complete the keyword</b><br />
This problem was asked in many coding interviews, so thats why i think it is important to discuss here.<br />
This is interesting because soon we will create our own program which provide suggestions for the entered keyword. This is similar to google suggestions when we type something in search box.<br />
<b>Problem : </b> Given a string s, print all the strings which are stored in a trie and have prefix s.<br />
<b>Solution : </b> Initially we are at root node. First of all we find the given string s in the trie. If it is not found then there could not be any other string with prefix s. But if it is found we reached to the node <b>N</b> corresponding the last character of the string s. Now we need to print all the words which can be formed from the nodes beneath the node <b>N</b>. For this we can apply DFS with a little modification. So DFS will print all the strings with prefix s. It will print only when it will reach the special node. We need 3 parameters for DFS which are :<br />
<ol>
<li>Pointer to current node</li>
<li>String s which is prefix for all the strings</li>
<li>Remaining string, lets call it suffix</li>
</ol>
Lets see the implementation part for this problem !<br />
<b> Implementation : </b><br />
<!-- HTML generated using hilite.me --><div style="background: #ffffff; border-color: blue; border-style: ridge; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93</pre>
</td><td><pre style="line-height: 125%; margin: 0;"> <span style="background-color: #ffaaaa; color: red;">#</span>include<span style="color: #333333;"><</span>bits<span style="color: #333333;">/</span>stdc<span style="color: #333333;">++</span>.h<span style="color: #333333;">></span>
<span style="color: #008800; font-weight: bold;">using</span> <span style="color: #008800; font-weight: bold;">namespace</span> std;
<span style="color: #008800; font-weight: bold;">typedef</span> <span style="color: #333399; font-weight: bold;">long</span> <span style="color: #333399; font-weight: bold;">long</span> ll ;
<span style="color: #008800; font-weight: bold;">struct</span> trie{
<span style="color: #333399; font-weight: bold;">bool</span> isleaf;
trie <span style="color: #333333;">*</span> next[<span style="color: #0000dd; font-weight: bold;">26</span>];
};
trie <span style="color: #333333;">*</span> <span style="color: #0066bb; font-weight: bold;">getNode</span>(){
trie <span style="color: #333333;">*</span> node <span style="color: #333333;">=</span> <span style="color: #008800; font-weight: bold;">new</span> trie();
node<span style="color: #333333;">-></span>isleaf <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> <span style="color: #0000dd; font-weight: bold;">26</span> ; i <span style="color: #333333;">++</span>){
node<span style="color: #333333;">-></span>next[i] <span style="color: #333333;">=</span> <span style="color: #007020;">NULL</span>;
}
<span style="color: #008800; font-weight: bold;">return</span> node;
}
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">insert</span>(string s, trie <span style="color: #333333;">*</span>root){
trie <span style="color: #333333;">*</span> node <span style="color: #333333;">=</span> root;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> s.size() ; i <span style="color: #333333;">++</span>){
<span style="color: #333399; font-weight: bold;">int</span> index <span style="color: #333333;">=</span> s[i] <span style="color: #333333;">-</span> <span style="color: #0044dd;">'a'</span>;
<span style="color: #008800; font-weight: bold;">if</span>(node<span style="color: #333333;">-></span>next[index] <span style="color: #333333;">==</span> <span style="color: #007020;">NULL</span>){
trie <span style="color: #333333;">*</span> temp <span style="color: #333333;">=</span> getNode();
node<span style="color: #333333;">-></span>next[index] <span style="color: #333333;">=</span> temp;
}
node <span style="color: #333333;">=</span> node<span style="color: #333333;">-></span>next[index];
}
node<span style="color: #333333;">-></span>isleaf <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">1</span>;
}
trie <span style="color: #333333;">*</span><span style="color: #0066bb; font-weight: bold;">search</span>(string s, trie <span style="color: #333333;">*</span> root){
trie <span style="color: #333333;">*</span> node <span style="color: #333333;">=</span> root;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> s.size() ; i <span style="color: #333333;">++</span>){
<span style="color: #333399; font-weight: bold;">int</span> index <span style="color: #333333;">=</span> s[i] <span style="color: #333333;">-</span> <span style="color: #0044dd;">'a'</span>;
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: #333333;">!</span>node<span style="color: #333333;">-></span>next[index]){
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #007020;">NULL</span>;
}
node <span style="color: #333333;">=</span> node<span style="color: #333333;">-></span>next[index];
}
<span style="color: #008800; font-weight: bold;">return</span> node;
}
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">dfs</span>(trie<span style="color: #333333;">*</span> root, string prefix, string suffix){
<span style="color: #888888;">// Print all the suggestions recursively</span>
<span style="color: #008800; font-weight: bold;">if</span>(root<span style="color: #333333;">-></span>isleaf <span style="color: #333333;">==</span> <span style="color: #0000dd; font-weight: bold;">1</span>){
cout <span style="color: #333333;"><<</span> prefix <span style="color: #333333;"><<</span> suffix <span style="color: #333333;"><<</span> endl;
}
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> <span style="color: #0000dd; font-weight: bold;">26</span> ; i <span style="color: #333333;">++</span>){
<span style="color: #008800; font-weight: bold;">if</span>(root<span style="color: #333333;">-></span>next[i]){
string newSuffix;
newSuffix <span style="color: #333333;">=</span> suffix;
newSuffix.push_back(i <span style="color: #333333;">+</span> <span style="color: #0044dd;">'a'</span>);
dfs(root<span style="color: #333333;">-></span>next[i], prefix, newSuffix);
}
}
}
<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">predict</span>(string s, trie <span style="color: #333333;">*</span> root){ <span style="color: #888888;">// Show suggestions</span>
trie <span style="color: #333333;">*</span> node <span style="color: #333333;">=</span> root;
<span style="color: #008800; font-weight: bold;">if</span>(<span style="color: #333333;">!</span>(node <span style="color: #333333;">=</span> search(s, root))){
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>;
}
dfs(node, s, <span style="background-color: #fff0f0;">""</span>);
}
<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">main</span>(){
<span style="color: #333399; font-weight: bold;">int</span> n;
cin <span style="color: #333333;">>></span> n;
trie <span style="color: #333333;">*</span>root <span style="color: #333333;">=</span> getNode();
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> n ; i <span style="color: #333333;">++</span>){
string s;
cin <span style="color: #333333;">>></span> s;
insert(s, root);
}
<span style="color: #333399; font-weight: bold;">int</span> Q;
cin <span style="color: #333333;">>></span> Q; <span style="color: #888888;">// Q : queries</span>
<span style="color: #008800; font-weight: bold;">while</span>(Q<span style="color: #333333;">--</span>){
string s;
cin <span style="color: #333333;">>></span> s; <span style="color: #888888;">// We need suggestions for string s.</span>
<span style="color: #333399; font-weight: bold;">int</span> x <span style="color: #333333;">=</span> predict(s, root);
<span style="color: #008800; font-weight: bold;">if</span>(x <span style="color: #333333;">==</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>){
cout <span style="color: #333333;"><<</span> <span style="background-color: #fff0f0;">"No keywords found"</span> <span style="color: #333333;"><<</span> endl;
}
}
}
</pre>
</td></tr>
</tbody></table>
</div>
<hr />
So after reading this post you get to know a lot about Trie data structure and if you have any doubt or you find some error or bug in the program please don't hesitate to write in the comment section.
<br /><b>
Thank You </b>
<b> </b></li>
</ul>
<b>THE END !!</b>
<br />
<ul>
</ul>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-59085758791140841462017-07-20T10:05:00.000-07:002017-07-20T10:25:01.975-07:00Understanding Binary Search and Linear Search <div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>Contents :</b><br />
<ul>
<i>
<li>Understanding Linear search and its time complexity</li>
<li>Understanding Binary search</li>
<li>Implementation of binary search in C++<a name='more'></a></li>
</i></ul>
</div>
<hr />
<ol>
<li>
<b>Understanding Linear search and its time complexity :</b><br />
Given an array and a key element and we need to check if the given key is in the array. If it is present then at what position it is located ?<br />
<b>Linear Search : </b> is comparing key element with each and every element of the array. If it is matched with some element, then whoa! we get the index of key element in the array.<br />
<b>Time Complexity :</b>O(n) because we are comparing key with each and every element of the array.<br />
<b>Implementation Hint:</b> Run a for loop from 0 to N and compare array[i] with key. If array[i] = key, then save the position in some variable and break the loop.<br />
</li>
<li>
<b>Understanding Binary search : </b><br />
We can apply binary search only on sorted values. If we are given a sorted array of <b>n<i></i></b> elements and we need to search an element in the array then we can search it in only log(n) time using binary search.<br />
In each iteration of binary search, we find the middle element of array and compare it with key element and if key is lesser than middle element then it also means that it is lesser than all the elements to the right of middle of element, since the array is sorted. So we ignore rightmost part of the array and our array shrinks to half the size.<br />
Similarly we ignore the leftmost part of the array if key is greater than middle element of the array.<br />
We stop this process on 2 conditions :
<ol>
<li><b>Found Condition : </b>If the middle element is equal to the key element.</li>
<li><b>Not Found Condition : </b>If the array shrinks to size zero.</li>
</ol>
<b> Example : </b><br />
<pre style="border-color: blue; border-style: ridge; border: solid-blue;">a[ 7 ] = 1 3 5 6 22 102 111
Key = 5
left = 0
right = n = 7
Iter 1: mid = (left + right) / 2 = 3
a[ 3 ] > key, So we now know that all elements
with index >= 3 are greater than Key and so
range 3 to 7 of the array are useless, hence
we change variable right to 2.
left = 0, right = 2
Iter 2: mid = (0 + 2) / 2 = 1
a[ 1 ] = 3 which is less than key, so we
change left variable to mid+1 i.e. left = 1+1 =2
left = 2, right = 2
Iter 3: mid = (2 + 2) / 2 = 2
a[ 2 ] = key = 5 ,
So key is present in array at index 2.
</pre>
</li>
<li>
<b>Implementation in C++ :</b>
<!-- HTML generated using hilite.me --><div style="background: #ffffff; border-width: 0.1em 0.1em 0.1em 0.1em; overflow: auto; padding: 1em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #557799;">#include <iostream></span>
<span style="color: #008800; font-weight: bold;">using</span> <span style="color: #008800; font-weight: bold;">namespace</span> std;
<span style="color: #888888;">// Binary Search Function</span>
<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">search</span>(<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #333333;">*</span>a, <span style="color: #333399; font-weight: bold;">int</span> n, <span style="color: #333399; font-weight: bold;">int</span> key){
<span style="color: #333399; font-weight: bold;">int</span> left <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #333399; font-weight: bold;">int</span> right <span style="color: #333333;">=</span> n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">while</span>(left <span style="color: #333333;"><=</span> right){
<span style="color: #333399; font-weight: bold;">int</span> mid <span style="color: #333333;">=</span> (left <span style="color: #333333;">+</span> right) <span style="color: #333333;">>></span> <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">if</span>(a[mid] <span style="color: #333333;">==</span> key){
<span style="color: #008800; font-weight: bold;">return</span> mid; <span style="color: #888888;">// Element found at index mid</span>
}<span style="color: #008800; font-weight: bold;">else</span> <span style="color: #008800; font-weight: bold;">if</span>(a[mid] <span style="color: #333333;"><</span> key){
left <span style="color: #333333;">=</span> mid <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span>;
}<span style="color: #008800; font-weight: bold;">else</span>{
right <span style="color: #333333;">=</span> mid <span style="color: #333333;">-</span> <span style="color: #0000dd; font-weight: bold;">1</span>;
}
}
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>; <span style="color: #888888;">// Element not found</span>
}
<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">main</span>() {
<span style="color: #333399; font-weight: bold;">int</span> n;
cin <span style="color: #333333;">>></span> n;
<span style="color: #333399; font-weight: bold;">int</span> a[n]; <span style="color: #888888;">// Sorted Array</span>
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> n ; i <span style="color: #333333;">++</span>){
cin <span style="color: #333333;">>></span> a[i];
}
<span style="color: #333399; font-weight: bold;">int</span> key;
cin <span style="color: #333333;">>></span> key; <span style="color: #888888;">// Key element</span>
cout <span style="color: #333333;"><<</span> search(a, n, key);
<span style="color: #008800; font-weight: bold;">return</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
}
</pre>
</td></tr>
</tbody></table>
</div>
<b>Complexity : </b>Lets consider the size of array be 2<sup>10</sup> = 1024. In each iteration we divide the array into 2 equal halves. So,<br />
<pre><b>Iteration Number : Size of array</b>
1 : 1024 / 2 = 512
2 : 512 / 2 = 256
3 : 256 / 2 = 128
4 : 128 / 2 = 64
5 : 64 / 2 = 32
6 : 32 / 2 = 16
7 : 16 / 2 = 8
8 : 8 / 2 = 4
9 : 4 / 2 = 2
10 : 2 / 2 = 1
</pre>
So from this we can see that we can search an element in a sorted array of size 1024 in just 10 iterations. <br />
Clearly 10 comes from log2(1024).<br />
Hence, <b>time complexity of binary search is log2(n)</b> where<b> n</b> is the size of the array.
</li>
</ol>
So we can say that if the given list is sorted we must apply binary search if we need to search an element in the list. Otherwise we have one more choice Linear Search whose complexity is <b>O(n)</b> which is far worst than binary search. <br />
<i>Don't do this <b>crazy</b> thing on an unsorted list :</i> Sort the list first and then apply binary search. Sorting a list takes<b> O(nlog(n)) </b>which is greater than <b>O(n)</b> linear search. In case of unsorted array linear search performs well.
<br />
Thank you buddies for reading this post !<br />
<b>The End !!</b>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-25845279209342465072017-07-19T01:40:00.002-07:002017-07-20T10:27:33.952-07:00Merge Sort Algorithm<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>Merge Sort Algorithm</b> is a sorting algorithm which has time complexity of O(nlog(n)) where n is number of elements in the unsorted list. In merge sort algorithm we divide the array in two halves and then sort those <br />
<a name='more'></a>two sub arrays recursively and after sorting them, the main thing is to merge them so that after merging them we get a sorted array. <br />
Lets understand merge sort with an example : <br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuR9m_tWIKY5BFxmXHQ_2gFL8ytzyVUXPGVvxaxE1fyfNO7A0aRx4WZp2fKtanqyqeabpBZKZTrLL9ZBc4kBQrVB7H9HkfWmfKbQ1QwkiPmVUOvITnxKNIx5nXE1_ueHOdIxA8ljGagG23/s1600/merge.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="418" data-original-width="536" height="311" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiuR9m_tWIKY5BFxmXHQ_2gFL8ytzyVUXPGVvxaxE1fyfNO7A0aRx4WZp2fKtanqyqeabpBZKZTrLL9ZBc4kBQrVB7H9HkfWmfKbQ1QwkiPmVUOvITnxKNIx5nXE1_ueHOdIxA8ljGagG23/s400/merge.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fig. 1</td></tr>
</tbody></table>
</div>
In fig. 1 we have an array a[ ] = {2, 6, 4, 5, 3} which is unsorted, so lets apply merge sort on this array to convert it into a sorted one. Follow the steps and observe the figure carefully. We divide the array into 2 sub arrays {2, 6, 4} and {5, 3}. As number of elements in main array are not even so one sub-array must contain one extra element.<br />
Now, first sort a1[ ] = {2, 6, 4} recursively. Divide again a1 into 2 halves {2, 6} and {4}. As set {2, 6} contain 2 elements, so we can divide it further into 2 equal parts i.e. {2} and {6}. Now comes the merging stage because we can't divide the array further.<br />
Merge {2} and {6} in such a way that the new array that formed is sorted. So after merging we should have {2, 6}.<br />
Now merge it again with {4}. We get {2, 4, 6}.<br />
Similarly, after sorting 2nd subarray of main subarray {5, 3} we get {3, 5}.<br />
Merging {2, 4, 6} and {3, 5}, we get {2, 3, 4, 5, 6}.<br />
So finally we can see that we get our sorted array. <br />
Now Lets see the <b>implementation part </b> and don't worry about merging, it is explained in the code itself !<br />
<b></b><br />
<h2>
<b>Code for Merge sort in C++ :</b></h2>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: 0.1em 0.1em 0.1em 0.1em; border: black; overflow: auto; padding: 1em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #557799;">#include<bits/stdc++.h></span>
<span style="color: #008800; font-weight: bold;">using</span> <span style="color: #008800; font-weight: bold;">namespace</span> std;
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">merge</span>(<span style="color: #333399; font-weight: bold;">int</span><span style="color: #333333;">*</span>,<span style="color: #333399; font-weight: bold;">int</span>,<span style="color: #333399; font-weight: bold;">int</span>,<span style="color: #333399; font-weight: bold;">int</span>);
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">mergeSort</span>(<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #333333;">*</span>a, <span style="color: #333399; font-weight: bold;">int</span> lo, <span style="color: #333399; font-weight: bold;">int</span> hi){
<span style="color: #333399; font-weight: bold;">int</span> mid <span style="color: #333333;">=</span> (lo <span style="color: #333333;">+</span> hi) <span style="color: #333333;">>></span> <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #008800; font-weight: bold;">if</span>(lo <span style="color: #333333;"><</span> hi){
mergeSort(a, lo, mid);
mergeSort(a, mid <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span>, hi);
merge(a, lo, mid, hi);
}
}
<span style="color: #333399; font-weight: bold;">void</span> <span style="color: #0066bb; font-weight: bold;">merge</span>(<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #333333;">*</span>a, <span style="color: #333399; font-weight: bold;">int</span> lo, <span style="color: #333399; font-weight: bold;">int</span> mid, <span style="color: #333399; font-weight: bold;">int</span> hi){
<span style="color: #333399; font-weight: bold;">int</span> i, j;
i <span style="color: #333333;">=</span> lo;
j <span style="color: #333333;">=</span> mid <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #333399; font-weight: bold;">int</span> newA[hi <span style="color: #333333;">-</span> lo <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span>]; <span style="color: #888888;">// New array will be our sorted merged array</span>
<span style="color: #333399; font-weight: bold;">int</span> counter <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #008800; font-weight: bold;">while</span>(i <span style="color: #333333;"><</span> mid <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span> <span style="color: #333333;">&&</span> j <span style="color: #333333;"><</span> hi <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span>){
<span style="color: #008800; font-weight: bold;">if</span>(a[i] <span style="color: #333333;">></span> a[j]){
newA[counter<span style="color: #333333;">++</span>] <span style="color: #333333;">=</span> a[j<span style="color: #333333;">++</span>];
}
<span style="color: #008800; font-weight: bold;">else</span>{
newA[counter<span style="color: #333333;">++</span>] <span style="color: #333333;">=</span> a[i<span style="color: #333333;">++</span>];
}
}
<span style="color: #008800; font-weight: bold;">while</span>(i <span style="color: #333333;"><</span> mid <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span>){
newA[counter<span style="color: #333333;">++</span>] <span style="color: #333333;">=</span> a[i<span style="color: #333333;">++</span>];
}
<span style="color: #008800; font-weight: bold;">while</span>(j <span style="color: #333333;"><</span> hi <span style="color: #333333;">+</span> <span style="color: #0000dd; font-weight: bold;">1</span>){
newA[counter<span style="color: #333333;">++</span>] <span style="color: #333333;">=</span> a[j<span style="color: #333333;">++</span>];
}
<span style="color: #008800; font-weight: bold;">for</span>(i <span style="color: #333333;">=</span> lo , j <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>; j <span style="color: #333333;"><</span> counter <span style="color: #333333;">&&</span> i <span style="color: #333333;"><=</span> hi ; i <span style="color: #333333;">++</span>, j <span style="color: #333333;">++</span>){
a[i] <span style="color: #333333;">=</span> newA[j];
}
<span style="color: #888888;">/*</span>
<span style="color: #888888;"> leftHalf = {3, 4, 7} , rightHalf = {2, 6}</span>
<span style="color: #888888;"> This example is in intermediate stage right now,</span>
<span style="color: #888888;"> so left and right halves are already sorted !</span>
<span style="color: #888888;"> newA[] = {} initially</span>
<span style="color: #888888;"> int i = 0 is pointer for leftHalf[]</span>
<span style="color: #888888;"> int j = 0 is pointer for rightHalf[]</span>
<span style="color: #888888;"> ***********************************************</span>
<span style="color: #888888;"> if leftHalf[i] < rightHalf[j]:</span>
<span style="color: #888888;"> add leftHalf[i] to newA[] and increment i</span>
<span style="color: #888888;"> else add rightHalf[j] to newA[] and increment j</span>
<span style="color: #888888;"> ***********************************************</span>
<span style="color: #888888;"> Clearly 3 > 2 so j = 1 and i = 0 and newA = {2, }</span>
<span style="color: #888888;"> 3 < 6, i = 1 and j = 1 and newA = {2, 3, }</span>
<span style="color: #888888;"> 4 < 6, i = 2 and j = 1 and newA = {2, 3, 4}</span>
<span style="color: #888888;"> ...</span>
<span style="color: #888888;"> newA = {2, 3, 4, 6, 7} </span>
<span style="color: #888888;"> */</span>
}
<span style="color: #333399; font-weight: bold;">int</span> <span style="color: #0066bb; font-weight: bold;">main</span>(){
<span style="color: #333399; font-weight: bold;">int</span> n;
cin <span style="color: #333333;">>></span> n;
<span style="color: #333399; font-weight: bold;">int</span> a[n];
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> n ; i <span style="color: #333333;">++</span>){
cin <span style="color: #333333;">>></span> a[i];
}
mergeSort(a, <span style="color: #0000dd; font-weight: bold;">0</span>, n<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>);
cout <span style="color: #333333;"><<</span> <span style="background-color: #fff0f0;">"Sorted Array : </span><span style="background-color: #fff0f0; color: #666666; font-weight: bold;">\n</span><span style="background-color: #fff0f0;">"</span>;
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> i <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span> ; i <span style="color: #333333;"><</span> n ; i <span style="color: #333333;">++</span>){
cout <span style="color: #333333;"><<</span> a[i] <span style="color: #333333;"><<</span> <span style="background-color: #fff0f0;">" "</span>;
}
cout <span style="color: #333333;"><<</span> <span style="background-color: #fff0f0;">"</span><span style="background-color: #fff0f0; color: #666666; font-weight: bold;">\n</span><span style="background-color: #fff0f0;">"</span>;
}
</pre>
</td></tr>
</tbody></table>
</div>
<b><u>Time Complexity : </u></b><br />
Dividing the array : O(log(n))<br />
Merging : O(n)<br />
Overall Complexity : O(n * log(n)) because we are dividing and merging simultaneously !<br />
<b></b><br />
<blockquote>
<b>The End !</b></blockquote>
Thanks for reading the post buddies !</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-84027266765892889882017-07-11T04:10:00.000-07:002017-07-17T02:49:10.195-07:00Breadth First Search in C++<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>Prerequisites :</b> <a href="http://sleepincode.blogspot.in/2017/07/graph-adjacency-list-using-stl-in-c-for.html"><i>Adjacency List, Queue data structure(FIFO)</i></a>
<br />
<b>
Breadth First Search :</b><br>
Like DFS, BFS is another form of Graph traversal Algorithm. Instead of going deeper and deeper, unlike DFS it goes in breadth first faishon which means that if it is on node u currently, then it first visits all the neighbours of node u and then the same thing happens with each of its neighbours. Lets understand how this algorithm works with the help of an example.<br />
<a name='more'></a><div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4mCuqsPfCovJb9_76qg10ZNN6BRi64CQEZyE2xC1Vkr19dZIyrwU1J20C8dX8Pgc6v_2T8kWnvMysWyODnsKuX1Zpldzm4whJ7GJoUCnyTKUpAve5JZtLf29i-9Ap2WSI0wkkAOqCR9Hd/s1600/graph.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="282" data-original-width="562" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg4mCuqsPfCovJb9_76qg10ZNN6BRi64CQEZyE2xC1Vkr19dZIyrwU1J20C8dX8Pgc6v_2T8kWnvMysWyODnsKuX1Zpldzm4whJ7GJoUCnyTKUpAve5JZtLf29i-9Ap2WSI0wkkAOqCR9Hd/s640/graph.png" width="640" /></a></div>
Consider this undirected graph G of 8 vertices and 8 edges and assume a Queue <b>q</b> which is initially empty. Let vertex 1 be our source vertex. So lets push the vertex 1 into the Queue q. Now push all the unvisited neighbouring vertices of 1 into q and pop vertex 1 from q.<br />
Queue q : 2, 3, 4<br />
Now front element of q is 2 so pop out 2 from q and push all the unvisited neighbouring vertices of 2 in the Queue.<br />
Queue q : 3, 4, 5, 6<br />
front element is 3, so pop it out and push all the unvisited neighbouring vertices of 3 in the Queue. <br />
Queue q : 4, 5, 6, 7<br />
Similarly pop 4 out and push all unvisited neighbouring vertices of 4<br />
Queue q : 5, 6, 7, 8<br />
Now every vertex of graph is visited so pop out every element from q until it is not empty.<br />
<b>Applications in competitive coding :</b><br />
<ul>
<li> <i>To test if a graph is Bipartite. </i></li>
<li><i>Minimum Spanning Tree for unweighted graph.</i></li>
<li>Single Source shortest path on unweighted graph.</li>
<li><i>Path Finding.</i></li>
</ul>
<b>Implementation in C++ :</b><br />
<i><b>Problem Statement :</b> </i> Given an unweighted graph G and the distance between any 2 directly connected nodes is 1. You are given a source node <b>s</b> and you have to find the distance of all other nodes from <b>s</b>. <br />
<i><b>Idea </b>:</i> We will apply BFS and we will maintain a distance vector which do 2 things for us. Firstly it stores distance of each node from source node and secondly it would tell us whether a particular node is already visited or not. Keep distance[source] = 0. <br />
When we are looping over the unvisited neighbours of front element of the queue we do just one extra thing i.e.<br />
<b>distance[unvisitedNeighbour(i)] = distance[q.front] + 1</b>. <br />
Rest of the procedure is same, popping out from queue and checking the unvisited neighbours of next element in the queue.<br />
<i><b>Code for this problem :</b></i>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; overflow: auto; padding: 0.49em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44</pre>
</td><td><pre style="line-height: 125%; margin: 0;"> <span style="border: 1px solid #FF0000;">#</span>include<span style="color: #666666;"><</span>bits<span style="color: #666666;">/</span>stdc<span style="color: #666666;">++</span>.h<span style="color: #666666;">></span>
<span style="color: #aa22ff; font-weight: bold;">using</span> <span style="color: #aa22ff; font-weight: bold;">namespace</span> std;
<span style="color: #00bb00; font-weight: bold;">int</span> n;
map<span style="color: #666666;"><</span><span style="color: #00bb00; font-weight: bold;">int</span>, vector<span style="color: #666666;"><</span><span style="color: #00bb00; font-weight: bold;">int</span><span style="color: #666666;">></span> <span style="color: #666666;">></span> adjList; <span style="color: #008800; font-style: italic;">// Considering unweighted graph</span>
<span style="color: #00bb00; font-weight: bold;">void</span> <span style="color: #00a000;">bfs</span>(<span style="color: #00bb00; font-weight: bold;">int</span> source){
<span style="color: #00bb00; font-weight: bold;">int</span> dist[n<span style="color: #666666;">+1</span>]; <span style="color: #008800; font-style: italic;">// distance vector</span>
memset(dist, <span style="color: #666666;">-1</span>, <span style="color: #aa22ff; font-weight: bold;">sizeof</span>(dist)); <span style="color: #008800; font-style: italic;">// dist[i] = -1; means node i is unvisited</span>
queue<span style="color: #666666;"><</span><span style="color: #00bb00; font-weight: bold;">int</span><span style="color: #666666;">></span> q;
q.push(source);
dist[source] <span style="color: #666666;">=</span> <span style="color: #666666;">0</span>;
<span style="color: #aa22ff; font-weight: bold;">while</span>(<span style="color: #666666;">!</span>q.empty()){
<span style="color: #00bb00; font-weight: bold;">int</span> u <span style="color: #666666;">=</span> q.front();
q.pop(); <span style="color: #008800; font-style: italic;">// Removing front element from queue</span>
<span style="color: #aa22ff; font-weight: bold;">for</span>(<span style="color: #00bb00; font-weight: bold;">int</span> i <span style="color: #666666;">=</span> <span style="color: #666666;">0</span> ; i <span style="color: #666666;"><</span> adjList[u].size() ; i <span style="color: #666666;">++</span>){
<span style="color: #00bb00; font-weight: bold;">int</span> v <span style="color: #666666;">=</span> adjList[u][i];
<span style="color: #aa22ff; font-weight: bold;">if</span>(dist[v] <span style="color: #666666;">==</span> <span style="color: #666666;">-1</span>){ <span style="color: #008800; font-style: italic;">// True if v is not visited earlier</span>
q.push(v);
dist[v] <span style="color: #666666;">=</span> dist[u] <span style="color: #666666;">+</span> <span style="color: #666666;">1</span>;
}
}
}
printf(<span style="color: #bb4444;">"Nodes Number | Distance </span><span style="color: #bb6622; font-weight: bold;">\n</span><span style="color: #bb4444;">"</span>);
<span style="color: #aa22ff; font-weight: bold;">for</span>(<span style="color: #00bb00; font-weight: bold;">int</span> i <span style="color: #666666;">=</span> <span style="color: #666666;">1</span> ; i <span style="color: #666666;"><=</span> n ; i <span style="color: #666666;">++</span>){
printf(<span style="color: #bb4444;">"%d</span><span style="color: #bb6622; font-weight: bold;">\t\t\t\t</span><span style="color: #bb4444;">|</span><span style="color: #bb6622; font-weight: bold;">\t\t</span><span style="color: #bb4444;">%d </span><span style="color: #bb6622; font-weight: bold;">\n</span><span style="color: #bb4444;">"</span>, i, dist[i] );
}
}
<span style="color: #00bb00; font-weight: bold;">int</span> <span style="color: #00a000;">main</span>(){
<span style="color: #00bb00; font-weight: bold;">int</span> edges; <span style="color: #008800; font-style: italic;">// n = number of nodes, edges = Number of edges</span>
scanf(<span style="color: #bb4444;">"%d%d"</span>,<span style="color: #666666;">&</span>n,<span style="color: #666666;">&</span>edges);
<span style="color: #aa22ff; font-weight: bold;">for</span>(<span style="color: #00bb00; font-weight: bold;">int</span> i <span style="color: #666666;">=</span> <span style="color: #666666;">0</span> ; i <span style="color: #666666;"><</span> edges ; i <span style="color: #666666;">++</span>){
<span style="color: #00bb00; font-weight: bold;">int</span> u, v;
scanf(<span style="color: #bb4444;">"%d%d"</span>,<span style="color: #666666;">&</span>u,<span style="color: #666666;">&</span>v);
adjList[u].push_back(v);
adjList[v].push_back(u);
}
<span style="color: #00bb00; font-weight: bold;">int</span> source;
scanf(<span style="color: #bb4444;">"%d"</span>,<span style="color: #666666;">&</span>source);
bfs(source);
}
</pre>
</td></tr>
</tbody></table>
</div>
<b>Complexity : </b> O(V + E) <br />
where V : Number of vertices and E : Number of Edges.<br />
Thank you for reading this post on BFS.
<br />
<blockquote>
The End !</blockquote>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com1tag:blogger.com,1999:blog-2387425429038449002.post-15979775201266826622017-07-10T11:07:00.000-07:002017-07-17T02:44:58.366-07:00Topological sort on a directed acyclic graph<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>Contents:</b><br />
<ol>
<li><i>What is Topological Sorting ?</i></li>
<li><i>Illustration with the help of an example</i>.</li>
<li><i>Implementation of topological sort in C++.</i></li>
</ol> <a name='more'></a>
<hr />
<ol>
<li>
What is <b>Topological Sorting ?</b><br />
In Acyclic Directed Graph G(E, V), Topological sorting is the ordering of vertices(V) of G in such a way that if vertex <b>u</b> is directed to vertex <b>v</b> then <b>u</b> should come first in this ordering and after that vertex <b>v</b>. There can be many valid topological sorts of a single directed acyclic graph(<b>DAG</b> in short). There are also many ways to implement topological sort algorithm but here we will slightly modify our DFS algorithm to do Topological Sorting. <br />
If you don't know DFS algorithm you must read <a href="http://sleepincode.blogspot.in/2017/07/depth-first-search-in-c.html">this post.</a>
</li>
<li>
<b>Illustration with the help of an example :</b><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhM2E9U6Z6sf6DjVOayb_j1bQcnqL9oA6j2ST_ez5kOvZ8uR2QgWrgDqXIyy5z3ffU_2dFCv8Xf_spomrLtNsTVFPOvAgJW02fe8aQ2zS0pYMpEYxexA0WAXIcy6LhTTB5AUOznLQu735o0/s1600/graph.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="360" data-original-width="521" height="276" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhM2E9U6Z6sf6DjVOayb_j1bQcnqL9oA6j2ST_ez5kOvZ8uR2QgWrgDqXIyy5z3ffU_2dFCv8Xf_spomrLtNsTVFPOvAgJW02fe8aQ2zS0pYMpEYxexA0WAXIcy6LhTTB5AUOznLQu735o0/s400/graph.png" width="400" /></a></div>
There can be many topological sorting of this DAG but i am writing only 3:<br />
<ul>
<li> 1, 2, 4, 5, 3, 6, 7 </li>
<li> 1, 2, 4, 3, 5, 6, 7 </li>
<li> 1, 5, 7, 4, 6, 3, 2 </li>
</ul>
You can check the validity of this sorting by checking any 2 connected vertices(direct or indirect)(direction : u to v) then u must be present before v.
</li>
<li>
<b>Implementation of topological sort in C++ :</b><br />
<b>Logic : </b> Let tSort[ ] stores the topological order of the above DAG <b>G</b>.
<br />
Start dfs from node 1. (node 1) β (node 4) β (node 6)<br />
<i>! Note </i> that 6 has no more unvisited neighbours, so store 6 in tSort i.e. tSort = {6, }.<br />
Now continuing our DFS, [Backtrack to node 4] <br />
(node 4) β (node 3)<br />
tSort = {6, 3, } <b>Why ? follow <i>!Note</i> above</b> [Backtrack to node 4] <br />
tSort = {6, 3, 4, }[Backtrack to node 1]<br />
(node 1) β (node 2) <br />
tSort = {6, 3, 4, 2, }[Backtrack to node 1] <br />
(node 1) β (node 5) β (node 7) <br />
tSort = {6, 3, 4, 2, 7, }[Backtrack to node 5]<br />
tSort = {6, 3, 4, 2, 7, 5, }[Backtrack to node 1]<br />
tSort = {6, 3, 4, 2, 7, 5, 1}<br />
<b>Done !</b><br />
Reverse this array and you will get one of the valid topological sort of G.
<!-- HTML generated using hilite.me --><div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.1em; border: solid black; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42</pre>
</td><td><pre style="line-height: 125%; margin: 0;"> <span style="border: 1px solid #ef2929; color: #a40000;">#</span><span style="color: black;">include</span><span style="color: #ce5c00; font-weight: bold;"><</span><span style="color: black;">bits</span><span style="color: #ce5c00; font-weight: bold;">/</span><span style="color: black;">stdc</span><span style="color: #ce5c00; font-weight: bold;">++</span><span style="color: black; font-weight: bold;">.</span><span style="color: black;">h</span><span style="color: #ce5c00; font-weight: bold;">></span>
<span style="color: #204a87; font-weight: bold;">using</span> <span style="color: #204a87; font-weight: bold;">namespace</span> <span style="color: black;">std</span><span style="color: black; font-weight: bold;">;</span>
<span style="color: #204a87; font-weight: bold;">const</span> <span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">N</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: #0000cf; font-weight: bold;">100000</span><span style="color: black; font-weight: bold;">;</span> <span style="color: #8f5902; font-style: italic;">// Maximum number of nodes, change according to constraints.</span>
<span style="color: black;">map</span><span style="color: #ce5c00; font-weight: bold;"><</span><span style="color: #204a87; font-weight: bold;">int</span><span style="color: black; font-weight: bold;">,</span> <span style="color: black;">vector</span><span style="color: #ce5c00; font-weight: bold;"><</span><span style="color: #204a87; font-weight: bold;">int</span><span style="color: #ce5c00; font-weight: bold;">></span> <span style="color: #ce5c00; font-weight: bold;">></span> <span style="color: black;">adjList</span><span style="color: black; font-weight: bold;">;</span>
<span style="color: #204a87; font-weight: bold;">bool</span> <span style="color: black;">visited</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">N</span><span style="color: black; font-weight: bold;">];</span>
<span style="color: black;">vector</span><span style="color: #ce5c00; font-weight: bold;"><</span><span style="color: #204a87; font-weight: bold;">int</span><span style="color: #ce5c00; font-weight: bold;">></span> <span style="color: black;">tSort</span><span style="color: black; font-weight: bold;">;</span>
<span style="color: #204a87; font-weight: bold;">void</span> <span style="color: black;">dfs</span><span style="color: black; font-weight: bold;">(</span><span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">u</span><span style="color: black; font-weight: bold;">){</span>
<span style="color: black;">visited</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">u</span><span style="color: black; font-weight: bold;">]</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: #204a87;">true</span><span style="color: black; font-weight: bold;">;</span>
<span style="color: #204a87; font-weight: bold;">for</span><span style="color: black; font-weight: bold;">(</span><span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: #0000cf; font-weight: bold;">0</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;"><</span> <span style="color: black;">adjList</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">u</span><span style="color: black; font-weight: bold;">].</span><span style="color: black;">size</span><span style="color: black; font-weight: bold;">()</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;">++</span><span style="color: black; font-weight: bold;">){</span>
<span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">v</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: black;">adjList</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">u</span><span style="color: black; font-weight: bold;">][</span><span style="color: black;">i</span><span style="color: black; font-weight: bold;">];</span> <span style="color: #8f5902; font-style: italic;">// neighbour of u</span>
<span style="color: #204a87; font-weight: bold;">if</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">visited</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">v</span><span style="color: black; font-weight: bold;">]</span> <span style="color: #ce5c00; font-weight: bold;">!=</span> <span style="color: #204a87;">true</span><span style="color: black; font-weight: bold;">){</span> <span style="color: #8f5902; font-style: italic;">// checking if neighbour is already visited or not</span>
<span style="color: black;">dfs</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">v</span><span style="color: black; font-weight: bold;">);</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: black;">tSort</span><span style="color: black; font-weight: bold;">.</span><span style="color: black;">push_back</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">u</span><span style="color: black; font-weight: bold;">);</span> <span style="color: #8f5902; font-style: italic;">// push in tSort[] only when it has no unvisited node left.</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">main</span><span style="color: black; font-weight: bold;">(){</span>
<span style="color: black;">memset</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">visited</span><span style="color: black; font-weight: bold;">,</span> <span style="color: #0000cf; font-weight: bold;">0</span><span style="color: black; font-weight: bold;">,</span> <span style="color: #204a87; font-weight: bold;">sizeof</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">visited</span><span style="color: black; font-weight: bold;">));</span>
<span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">n</span> <span style="color: black; font-weight: bold;">,</span> <span style="color: black;">edges</span><span style="color: black; font-weight: bold;">;</span> <span style="color: #8f5902; font-style: italic;">// n = number of nodes, edges = Number of edges</span>
<span style="color: black;">scanf</span><span style="color: black; font-weight: bold;">(</span><span style="color: #4e9a06;">"%d%d"</span><span style="color: black; font-weight: bold;">,</span><span style="color: #ce5c00; font-weight: bold;">&</span><span style="color: black;">n</span><span style="color: black; font-weight: bold;">,</span><span style="color: #ce5c00; font-weight: bold;">&</span><span style="color: black;">edges</span><span style="color: black; font-weight: bold;">);</span>
<span style="color: #204a87; font-weight: bold;">for</span><span style="color: black; font-weight: bold;">(</span><span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: #0000cf; font-weight: bold;">0</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;"><</span> <span style="color: black;">edges</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;">++</span><span style="color: black; font-weight: bold;">){</span>
<span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">u</span><span style="color: black; font-weight: bold;">,</span> <span style="color: black;">v</span><span style="color: black; font-weight: bold;">;</span>
<span style="color: black;">scanf</span><span style="color: black; font-weight: bold;">(</span><span style="color: #4e9a06;">"%d%d"</span><span style="color: black; font-weight: bold;">,</span><span style="color: #ce5c00; font-weight: bold;">&</span><span style="color: black;">u</span><span style="color: black; font-weight: bold;">,</span><span style="color: #ce5c00; font-weight: bold;">&</span><span style="color: black;">v</span><span style="color: black; font-weight: bold;">);</span> <span style="color: #8f5902; font-style: italic;">// u -> v</span>
<span style="color: black;">adjList</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">u</span><span style="color: black; font-weight: bold;">].</span><span style="color: black;">push_back</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">v</span><span style="color: black; font-weight: bold;">);</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: #204a87; font-weight: bold;">for</span><span style="color: black; font-weight: bold;">(</span><span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: #0000cf; font-weight: bold;">1</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;"><=</span> <span style="color: black;">n</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span><span style="color: #ce5c00; font-weight: bold;">++</span><span style="color: black; font-weight: bold;">){</span>
<span style="color: #204a87; font-weight: bold;">if</span><span style="color: black; font-weight: bold;">(</span><span style="color: #ce5c00; font-weight: bold;">!</span><span style="color: black;">visited</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">i</span><span style="color: black; font-weight: bold;">]){</span>
<span style="color: black;">dfs</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">i</span><span style="color: black; font-weight: bold;">);</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: black;">reverse</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">tSort</span><span style="color: black; font-weight: bold;">.</span><span style="color: black;">begin</span><span style="color: black; font-weight: bold;">(),</span> <span style="color: black;">tSort</span><span style="color: black; font-weight: bold;">.</span><span style="color: black;">end</span><span style="color: black; font-weight: bold;">());</span> <span style="color: #8f5902; font-style: italic;">// Reversing tSort[]</span>
<span style="color: black;">printf</span><span style="color: black; font-weight: bold;">(</span><span style="color: #4e9a06;">"Topological Sorting of DAG G is :\n"</span><span style="color: black; font-weight: bold;">);</span>
<span style="color: #204a87; font-weight: bold;">for</span><span style="color: black; font-weight: bold;">(</span><span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: #0000cf; font-weight: bold;">0</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;"><</span> <span style="color: black;">tSort</span><span style="color: black; font-weight: bold;">.</span><span style="color: black;">size</span><span style="color: black; font-weight: bold;">()</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;">++</span><span style="color: black; font-weight: bold;">){</span>
<span style="color: black;">printf</span><span style="color: black; font-weight: bold;">(</span><span style="color: #4e9a06;">"%d "</span><span style="color: black; font-weight: bold;">,</span><span style="color: black;">tSort</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">i</span><span style="color: black; font-weight: bold;">]);</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: black;">printf</span><span style="color: black; font-weight: bold;">(</span><span style="color: #4e9a06;">"\n"</span><span style="color: black; font-weight: bold;">);</span>
<span style="color: black; font-weight: bold;">}</span>
</pre>
</td></tr>
</tbody></table>
</div>
</li>
</ol>
Thanks for reading this post !
<br />
<blockquote>
The end !</blockquote>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-55487509425860886742017-07-10T02:57:00.000-07:002017-07-17T02:50:34.023-07:00Finding connected Components using DFS in C++<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>Contents : </b>
<br />
<ol>
<li> <i>Pre-requisites</i> </li>
<li> <i>Understanding connected components.</i> </li>
<li> <i>Implementing DFS to find number of connected components.<a name='more'></a></i></li>
</ol>
<hr />
<ol>
<li>
<b>Pre-requisites</b> : <a href="https://sleepincode.blogspot.in/2017/07/depth-first-search-in-c.html">Depth First Search</a>
</li>
<li><b>Understanding connected components :</b><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguowA0J4BeAYdMTQvvMKuROZ2bi7ep4ZbKFiAkr8LqG0yuuKjaWk7tTwI8Xpezri837BxkpL6bnZP5sDiV0qaV-v3I3CwoaIx-kMPRDyq8CSkcKa12pFcsj15HZhaWA9bQnwnnGfJPgr5w/s1600/connected.png" imageanchor="1" style="clear: left; float: center; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="321" data-original-width="320" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguowA0J4BeAYdMTQvvMKuROZ2bi7ep4ZbKFiAkr8LqG0yuuKjaWk7tTwI8Xpezri837BxkpL6bnZP5sDiV0qaV-v3I3CwoaIx-kMPRDyq8CSkcKa12pFcsj15HZhaWA9bQnwnnGfJPgr5w/s400/connected.png" width="399" /></a></div>
Here we can see a graph <b>G </b>, consisting of 7 nodes and 5 edges.<br />
We can reach to any of the nodes in set {2, 3, 4} from node 1 as these nodes are connected directly or indirectly to each other. So {1, 2, 3, 4} make one connected component we can reach from any one node to any other node in this set. Similarly {5, 6} and {7} make other connected components of this graph G.<br />
<b>Implementation Idea : </b><br />
<code>
<b>connectedComponents</b> = 0<br />
<b>for</b> node <b>from</b> 1 to n:<br />
βββif node is <b>not visited</b> :<br />
ββββββ<b>dfs</b>(node)<br />
ββββββ<b>connectedComponents++</b><br />
</code>
We check every node from 1 to n and if that node is not visited earlier then mark all the nodes as visited which are connected to it(either directly or indirectly) using depth first search, so that when we come to that node in our for loop we can skip it. Keep incrementing the connectedComponent variable.
</li>
<li> <b>Implementing DFS to find number of connected components:</b>
<script src="https://gist.github.com/ma5terdrag0n/39bb796e248dccdcf371908c531b46b6.js"></script>
Thank you for reading this post.
<blockquote>
The End !</blockquote>
</li>
</ol>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-72697825494748030442017-07-10T01:06:00.000-07:002017-07-17T03:16:33.195-07:00Depth First Search in C++<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
Hey Guys ! Hope you are doing well !<br />
In my <a href="http://sleepincode.blogspot.in/2017/07/graph-adjacency-list-using-stl-in-c-for.html">previous post</a> i wrote about implementation of Adjacency List in C++. So if you don't know how to implement Adjacency List in C++, you must read <a href="http://sleepincode.blogspot.in/2017/07/graph-adjacency-list-using-stl-in-c-for.html">this post.</a><br />
<hr />
<h3 style="text-align: left;">
Depth First Search </h3>
DFS (in short) is a simple algorithm to traverse a graph. <br />
<a name='more'></a>Lets understand the logic behind this algorithm with the help of following graph. <br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqTknHTQ7d5HP-M581RV0nQDsHXfJOBIrOxbK3XSaKtZbZYEYmHM-ssJTwGy3l8FQn8bV7LAhXt2DQ4dKr7VU-gz2gz6BbQbS6deMNdAoO47gGWeL7GfwiejL4nMqdomz4f7NhuMIWAuFj/s1600/sg.png" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" data-original-height="400" data-original-width="317" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqTknHTQ7d5HP-M581RV0nQDsHXfJOBIrOxbK3XSaKtZbZYEYmHM-ssJTwGy3l8FQn8bV7LAhXt2DQ4dKr7VU-gz2gz6BbQbS6deMNdAoO47gGWeL7GfwiejL4nMqdomz4f7NhuMIWAuFj/s320/sg.png" width="253" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span style="color: #6fa8dc;">Blue</span> > <span style="color: #93c47d;">Green</span> > <span style="color: #e06666;">Red</span></td></tr>
</tbody></table>
<div style="text-align: left;">
</div>
Suppose we start dfs from node 1. We mark it as visited and move to one of its neighbour which is not visited till now. We can see till now neither node 2 nor node 3 is visited. So firstly, we move to node 2. Mark node 2 as visited and similarly move to one of the neighbour of node 2. Neighbours of 2 are 1 and 4 and node 1 is already marked visited, so we move to node 4. Mark node 4 as visited and now we move to node 6 and marked it as visited. But at this point there is no neighbour of node 6 which is not visited. So we move back to node from which we came to node 6 ie. node 4. Now node 4 has one neighbour node 5 which is not visited, So we move node 5 and mark it as visited. Similarly node 5 have no unvisited neighbour. Jump back to node 4. No unvisited neighbours of node 4 so move back to node 2. No unvisited neighbour of node 2 So move back to node 1. Now it has an unvisited neighbour i.e. node 3. So move to node 3 and mark it as visited. Similarly No unvisited neighbours, move back to node 1 and now all vertices are marked visited and we stop at this point.<br />
<hr />
Now i hope after reading this example you got the idea of graph traversal using DFS. So without wasting any time lets see the implementation part.
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.1em; border: solid black; overflow: auto; padding: 0.6em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20</pre>
</td><td><pre style="line-height: 125%; margin: 0;"> <span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">n</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: #0000cf; font-weight: bold;">100000</span><span style="color: black; font-weight: bold;">;</span> <span style="color: #8f5902; font-style: italic;">// Maximum number of nodes, change according to constraints.</span>
<span style="color: black;">map</span><span style="color: #ce5c00; font-weight: bold;"><</span><span style="color: #204a87; font-weight: bold;">int</span><span style="color: black; font-weight: bold;">,</span> <span style="color: black;">vector</span><span style="color: #ce5c00; font-weight: bold;"><</span><span style="color: #204a87; font-weight: bold;">int</span><span style="color: #ce5c00; font-weight: bold;">></span> <span style="color: #ce5c00; font-weight: bold;">></span> <span style="color: black;">adjList</span><span style="color: black; font-weight: bold;">;</span> <span style="color: #8f5902; font-style: italic;">// Considering undirected graph</span>
<span style="color: #204a87; font-weight: bold;">bool</span> <span style="color: black;">visited</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">n</span><span style="color: black; font-weight: bold;">];</span>
<span style="color: #204a87; font-weight: bold;">void</span> <span style="color: black;">dfs</span><span style="color: black; font-weight: bold;">(</span><span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">u</span><span style="color: black; font-weight: bold;">){</span>
<span style="color: black;">visited</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">u</span><span style="color: black; font-weight: bold;">]</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: #204a87;">true</span><span style="color: black; font-weight: bold;">;</span>
<span style="color: #204a87; font-weight: bold;">for</span><span style="color: black; font-weight: bold;">(</span><span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: #0000cf; font-weight: bold;">0</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;"><</span> <span style="color: black;">adjList</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">u</span><span style="color: black; font-weight: bold;">].</span><span style="color: black;">size</span><span style="color: black; font-weight: bold;">()</span> <span style="color: black; font-weight: bold;">;</span> <span style="color: black;">i</span> <span style="color: #ce5c00; font-weight: bold;">++</span><span style="color: black; font-weight: bold;">){</span>
<span style="color: #204a87; font-weight: bold;">int</span> <span style="color: black;">v</span> <span style="color: #ce5c00; font-weight: bold;">=</span> <span style="color: black;">adjList</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">u</span><span style="color: black; font-weight: bold;">][</span><span style="color: black;">i</span><span style="color: black; font-weight: bold;">];</span> <span style="color: #8f5902; font-style: italic;">// neighbour of u</span>
<span style="color: #204a87; font-weight: bold;">if</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">visited</span><span style="color: black; font-weight: bold;">[</span><span style="color: black;">v</span><span style="color: black; font-weight: bold;">]</span> <span style="color: #ce5c00; font-weight: bold;">!=</span> <span style="color: #204a87;">true</span><span style="color: black; font-weight: bold;">){</span> <span style="color: #8f5902; font-style: italic;">// checking if neighbour is already visited or not</span>
<span style="color: black;">dfs</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">v</span><span style="color: black; font-weight: bold;">);</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: black; font-weight: bold;">}</span>
<span style="color: #8f5902; font-style: italic;">// inside int main</span>
<span style="color: black;">memset</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">visited</span><span style="color: black; font-weight: bold;">,</span> <span style="color: #0000cf; font-weight: bold;">0</span><span style="color: black; font-weight: bold;">,</span> <span style="color: #204a87; font-weight: bold;">sizeof</span><span style="color: black; font-weight: bold;">(</span><span style="color: black;">visited</span><span style="color: black; font-weight: bold;">));</span>
<span style="color: #8f5902; font-style: italic;">/*</span>
<span style="color: #8f5902; font-style: italic;"> * Take inputs and make Adjacency List</span>
<span style="color: #8f5902; font-style: italic;"> */</span>
<span style="color: black;">dfs</span><span style="color: black; font-weight: bold;">(</span><span style="color: #0000cf; font-weight: bold;">1</span><span style="color: black; font-weight: bold;">);</span> <span style="color: #8f5902; font-style: italic;">// Let the starting vertex be 1</span>
</pre>
</td></tr>
</tbody></table>
</div>
<b>Complexity:</b><br />
<i>Adjacency List</i> : O(V + E)<br />
<i>Adjacency Matrix</i> : O(V*V)<br />
where V = Number of vertices, E = Number of edges
<br />
<hr />
Some of the applications of DFS :
<br />
<ul>
<li>Topological sorting.</li>
<li>Finding connected components.</li>
<li>Finding the bridges of a graph.</li>
<li>Finding the articulation points of a graph.</li>
<li>Finding strongly connected components.</li>
<li>Finding biconnectivity in graphs.</li>
<li>Solving puzzles with only one solution, such as mazes.(You can use this in Robot maze solving competitions like in IIT Bombay's TechFest)</li>
</ul>
<h3>
<b>I will discuss each of them in detail in my next blog-posts.</b></h3>
This is my third blog-post and I hope you can now implement DFS very easily !
For any doubts you are most welcome and if you find any error in this post please help me correct it.
<br />
<blockquote>
THE END !</blockquote>
</div>
Pritish Thakkarhttp://www.blogger.com/profile/00755419940154081554noreply@blogger.com0tag:blogger.com,1999:blog-2387425429038449002.post-42925471407050249562017-07-04T00:42:00.000-07:002017-07-17T02:55:01.825-07:00Graph : Adjacency List using STL in C++ for competitve programming<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>CONTENTS :</b>
<br />
<ol>
<li><i>Introduction to Adjacency List.</i></li>
<li><i>Some STL Componenets required to make Adjacency List:</i></li>
<ul>
<li><i>Vector</i> </li>
<li><i>Pair</i></li>
<li><i>Map</i></li>
</ul>
<li>
<i>Implementation in C++.<a name='more'></a></i>
</li>
</ol>
<hr />
<ol>
<li>
<b>Introduction to Adjacency List :</b>
According to <b>wikipedia</b>: In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.<br />
We can solve many graph problems much efficiently using Adjacency list representation of a graph as compared to Adjacency Matrix. Example we can run DFS on adjacency List in O(E + V) time while it requires O(V * V) time for Adjacency Matrix. Here E = number of edges and V = number of vertices in a graph.<br />
We can create Adjacency list by making out own classes and functions like addEdge(), removeEdge() etc which is not a good practice in competitive programming because we don't have enough time to write a lot of stuff. So most of the programmers don't use such cumbersome method.<br /> Let's see what they use !
</li>
<li><b>Some STL Componenets required to make Adjacency List:</b>
<ul>
<li><b>Vector :</b>Vectors are sequence containers representing arrays that can change in size. That's great ! we need not to specify the size of a vector. Let's see the implementation part:
<script src="https://gist.github.com/ma5terdrag0n/f5bda975f7f2004e53da1c204ac3673c.js"></script>
<a href="http://www.cplusplus.com/reference/vector/vector/">Click here if you want to learn more about vectors.</a>
</li>
<li><b>Pair :</b> As the name suggests, it is a data structure that can contain a pair of either same or different data types.
<script src="https://gist.github.com/ma5terdrag0n/dcee768dcee342eda291900db11c9355.js"></script> </li>
<li><b>Map :</b> Hash Map in C++.Data is stored in the form of Key-Value pairs. We can insert, search, erase an element from map in O(logN) time. <br />You can learn about maps(STL) on <a href="http://www.geeksforgeeks.org/map-associative-containers-the-c-standard-template-library-stl/">Geeks For Geeks.</a><br />Practice this data structure on <a href="https://www.hackerrank.com/challenges/cpp-maps">Hackerrank.</a>
</li>
</ul>
</li>
<li><b>Implementation :</b>
Its the time to create our own adjacency list for the following graph using the above cool data structures in C++:
<div>
<a href="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/333px-6n-graf.svg.png" imageanchor="1"><img border="0" data-original-height="220" data-original-width="333" height="211" src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/333px-6n-graf.svg.png" width="320" /></a>
</div>
<script src="https://gist.github.com/ma5terdrag0n/87538297c3a2bde9c8b6ac5086d41cba.js"></script>
<a href="http://ideone.com/d09aHu"> Click here to see input and output for this program.</a>
</li>
Remove all the comments from this program to see the actual length of this C++ program. <b>:)</b><br />
Congrats ! You now know how to create your Adjacency List in C++(in not more than 7-10 lines of code) for a given graph.
</ol>
<h2>
Hope this is useful for all my dear programmers.<br />
Happy Coding !</h2>
</div>
Anonymoushttp://www.blogger.com/profile/17206660318007518084noreply@blogger.com4tag:blogger.com,1999:blog-2387425429038449002.post-35457559699660974712017-06-13T01:52:00.000-07:002017-08-07T23:35:30.934-07:00All about Binary Search Trees<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
<b>UPDATES:</b><br />
<hr />
<ul>
<li><a href="http://sleepincode.blogspot.in/2017/06/all-about-binary-search-trees.html#upd1">Added a new problem (prob. 7)</a></li>
<li><a href="http://sleepincode.blogspot.in/2017/06/all-about-binary-search-trees.html#upd2">Added a new traversal technique </a></li>
</ul>
<b>CONTENTS:</b><br />
<hr />
<ol>
<li><i>Insertion in a BST.</i></li>
<li><i>Tree traversal techniques. </i></li>
<li><i>Height of Binary Search Tree.<a name='more'></a></i></li>
<li><i>Validating a BST.</i></li>
<li><i>Finding the Lowest Common Ancestor of key1 and key2 in BST.</i></li>
<li><i>Deletion of a node 'N' from BST.</i></li>
<li><i>Finding maximum (or minimum) in path from node A to node B.</i></li>
</ol>
<b>What is a binary search tree ?</b><br />
<hr />
Binary Search Tree, is a node-based binary tree data structure having the following properties:
<br />
<ul>
<li>The left subtree of a node contains only nodes with keys less than the nodeβs key.</li>
<li>The right subtree of a node contains only nodes with keys greater than the nodeβs key.</li>
<li>The left and right subtree each must also be a binary search tree.</li>
<li>There must be no duplicate nodes.</li>
</ul>
</div>
<hr />
Most of operations on binary search trees like <b>insertion, deletion, search </b> etc can be done in logarithmic time <b>O(logN)</b>. <br />
Let's discuss each of them in detail.<br />
First of all lets see the <b>Structure of binary search tree :</b><br />
<script src="https://gist.github.com/ma5terdrag0n/dae60f82cf27d1d71f87c532f36435ac.js"></script>
<br />
<ol>
<li>
<b> Insertion : insert(root, key) : </b> Starting with root node keep on comparing key with the value of nodes of Binary Search Tree recursively with two conditions :
<ul>
<li>If value of key is greater than current node : move to its right subtree</li>
<li> otherwise : move to its left subtree </li>
</ul>
Remember : New nodes are always inserted as the leaf nodes of Binary Search tree.<br />
<a href="https://www.hackerrank.com/challenges/binary-search-tree-insertion">Practice On Hackerrank</a>
<script src="https://gist.github.com/ma5terdrag0n/88b25521d91d72c11af2acfa4b313a47.js"></script>
<hr />
</li>
<li>
<b>Four types of tree traversal techniques :</b><br />
<ol>
<li><b> Pre-order tree traversal :</b> Follow this order : root --- left --- right<br />
It means that we need to first print the data of current node, then we have to move to its left subtree and then its right subtree recursively.
<script src="https://gist.github.com/ma5terdrag0n/ebb0ce60a3b90f93f0124f0924f5cc53.js"></script>
</li>
<li><b> In-order tree traversal :</b> Follow this order : left --- root --- right<br />
In inorder traversal we first need to visit its left subtree and after printing its left subtree we print the current node data and then print its right subtree recursively. This traversal will print all the nodes of tree in ascending order.
<script src="https://gist.github.com/ma5terdrag0n/ec1cce2c38247348ab8346e629d6f753.js"></script>
</li>
<li><b> Post-order tree traversal :</b> Follow this order : left --- right --- root<br />
In postorder traversal we first need to visit its left subtree and after printing its left subtree we print its right subtree recursively and then the value of current node recursively.
<script src="https://gist.github.com/ma5terdrag0n/237f98d9fd8b805185db9e8c2ab8c5b7.js"></script>
</li>
<li id = "upd2"> <b> Level Order Traversal :</b><br> It is easy to implement if you know BFS algorithm. Before learning this you must learn <a href = "http://sleepincode.blogspot.in/2017/07/breadth-first-search-in-c.html">BFS graph traversal algorithm</a>.<br>
Now make a queue and insert root in it. Then print it out and pop it from queue and insert its left child first and then right child into the queue. Then do the same for each node until queue is not empty.<br>
<script src="https://gist.github.com/ma5terdrag0n/0bf81525438bdf0ec3fb3aa097609039.js"></script>
</ol>
</li>
<li>
<b> Height of Binary Search Tree : </b> Height is defined as the number of nodes in the longest path from the root node to a leaf node. <br />
<a href="https://stackoverflow.com/questions/2597637/finding-height-in-binary-search-tree">StackOverflow : finding height of a BST</a>
<script src="https://gist.github.com/ma5terdrag0n/be705cc781b6da90e99bc4f7c7caaea8.js"></script>
</li>
<li>
<b>Check if a tree is BST or not ? : </b>
Use an awesome property of BST : Inorder traversal of BST prints data in ascending order.
<script src="https://gist.github.com/ma5terdrag0n/26477d39fdd689e1d6e98b1a37c9cc66.js"></script>
</li>
<li>
<b>Finding the Lowest Common Ancestor of key1 and key2 in BST : </b><br />
The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in BST that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).<br />
Consider 3 cases :
<ul>
<li> Both key1 and key2 are on left side of a node. </li>
<li> Both key1 and key2 are on right side of a node. </li>
<li> One is on left side and other is on right side. </li>
<script src="https://gist.github.com/ma5terdrag0n/bbd6ac7c712ba2b72fbde5150d053424.js"></script>
</ul>
</li>
<li>
<b>Deletion of a node 'N' from BST :</b>
Lets consider some cases which are necessary to consider while deleting a node :
<ul>
<li>if left child of N is NULL : replace node N with its right child.</li>
<li>if right child of N is NULL : replace node N with its left child.</li>
<li>if none of child of N is NULL : we have 2 choices :
<ol>
<li> replace it with minimum value node in its right subtree.
<script src="https://gist.github.com/ma5terdrag0n/30dc48a3731710e80dab3751475545e5.js"></script></li>
<li> or replace it with maximum value node in its left subtree.<script src="https://gist.github.com/ma5terdrag0n/ba9b4c785bdc8f191f845a33a96f9711.js"></script> </li>
</ol>
</li>
</ul>
</li>
<li id="upd1"> <b> <i>UPD1</i> : Finding maximum (or minimum) in path from node A to node B :</b><br />
<a href="https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/algorithm/monk-and-cursed-tree/description/">Link for practice @Hackerearth</a><hr />
So after reading about LCA(lowest common ancestor) in point 5, we can easily find it for given 2 nodes. But why LCA ? See. we can easily reach both nodes from LCA by just moving to left or right child recursively but to move from one node to other is difficult if they are in different subtrees without knowing their LCA. So <b>LCA</b> helps us here ! <br />
Now find max in path from LCA to node A. Lets call it ans1<br />
Similarly find max in path from LCA to node B. Lets call it ans2<br />
Finally your answer must be max(ans1, ans2) .
<script src="https://gist.github.com/ma5terdrag0n/0485dcdb3f415487f1f73b4e9ceefac5.js"></script>
</li>
</ol>
So i hope after reading this you have gained a lot of knowledge about Binary search trees and their implementation in C++.
<br />
If you have any doubt about BST you can ask freely and if you find it useful please give your feedback in the comment section.
<br />
Happy Coding !
</div>
Anonymoushttp://www.blogger.com/profile/17206660318007518084noreply@blogger.com15