tag:blogger.com,1999:blog-76565163166877952202024-02-18T17:55:25.025-08:00I solved a problemA problem solving blogArifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-7656516316687795220.post-45787339149550710982013-02-01T20:50:00.000-08:002013-02-02T06:39:49.262-08:00Maxim and Restaurant (Part 2)<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<a href="http://isolvedaproblem.blogspot.com/2013/01/maxim-and-restaurant.html" target="_blank">Maxim and Restaurant (Part 1)</a><br />
<br />
In previous post I discussed a O(n ^ 3 * k) solution. Today, I'm going to discuss how we can reduce the complexity to O(n ^ 2 * k). Basically if we see the problem from a different angle we don't need to run our DP for each blocker.<br />
<br />
For n persons in queue, we have n! permutations. Lets consider the number of permutations for which we can allow only one person is p1, number of permutations for which we can allow two persons is p2, and so on.<br />
<br />
So expected number of persons -<br />
$e = \frac{p1 * 1 + p2 * 2 + ... pn * n}{n!}$<br />
<br />
Which can be represented as -<br />
$e = \frac{(p1 + p2 + ... + pn) + (p2 + p3 + ... + pn) + ... + (pn)}{n!}$<br />
<br />
Here, p1 + p2 + ... + pn actually represents the number of ways where we can allow at least 1 persons. Lets call it m1. Similarly, p2 + p3 + .. + pn represents number of ways where we can allow at least 2 persons, which is m2 and so on.<br />
<br />
So our equation is now -<br />
$e = \frac{m1 + m2 + ... + mn}{n!}$<br />
$=> e = \frac{m1}{n!} + \frac{m2}{n!} + \frac{m2}{n!}$<br />
$=> e = f1 + f2 + .. + fn$<br />
<br />
Here, fi = probability of allowing at least i persons.<br />
<br />
In last post, in our dynamic programming has states dp[i][j]. In dp[i][j], we calculated probability of having sum j by adding first i persons. For a given k, if we add up all dp[k][j] for all 1 <= j <= p, we'll find the probability of allowing at least k persons. So by removing the blocker and running the dynamic programming algorithm only once we can simply calculate f1, f2, .. fn, and by adding these values, we can get our result.<br />
<br />
So here is the simplified code -<br />
<br /></div>
<pre style="background: #ffffff; color: black;"><span style="color: maroon; font-weight: bold;">public</span> void solve(int testNumber, InputReader in, OutputWriter out) <span style="color: purple;">{</span>
<span style="color: #bb7977;">int</span> n <span style="color: #808030;">=</span> in<span style="color: #808030;">.</span>readInt<span style="color: #808030;">(</span><span style="color: #808030;">)</span><span style="color: purple;">;</span>
<span style="color: #bb7977;">int</span><span style="color: #808030;">[</span><span style="color: #808030;">]</span> a <span style="color: #808030;">=</span> <span style="color: maroon; font-weight: bold;">new</span> <span style="color: #bb7977;">int</span><span style="color: #808030;">[</span>n<span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: #bb7977;">int</span> total <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: #bb7977;">int</span> i <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> i <span style="color: #808030;"><</span> n<span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>i<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
a<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span> <span style="color: #808030;">=</span> in<span style="color: #808030;">.</span>readInt<span style="color: #808030;">(</span><span style="color: #808030;">)</span><span style="color: purple;">;</span>
total <span style="color: #808030;">+</span><span style="color: #808030;">=</span> a<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
<span style="color: #bb7977;">int</span> p <span style="color: #808030;">=</span> in<span style="color: #808030;">.</span>readInt<span style="color: #808030;">(</span><span style="color: #808030;">)</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">if</span> <span style="color: #808030;">(</span>total <span style="color: #808030;"><</span><span style="color: #808030;">=</span> p<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
out<span style="color: #808030;">.</span>printLine<span style="color: #808030;">(</span>n<span style="color: #808030;">)</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">return</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
<span style="color: #bb7977;">double</span> res <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: #808030;">.</span><span style="color: purple;">;</span>
<span style="color: #bb7977;">double</span><span style="color: #808030;">[</span><span style="color: #808030;">]</span><span style="color: #808030;">[</span><span style="color: #808030;">]</span> dp <span style="color: #808030;">=</span> <span style="color: maroon; font-weight: bold;">new</span> <span style="color: #bb7977;">double</span><span style="color: #808030;">[</span>n <span style="color: #808030;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">]</span><span style="color: #808030;">[</span>p <span style="color: #808030;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">]</span><span style="color: purple;">;</span>
dp<span style="color: #808030;">[</span><span style="color: #008c00;">0</span><span style="color: #808030;">]</span><span style="color: #808030;">[</span><span style="color: #008c00;">0</span><span style="color: #808030;">]</span> <span style="color: #808030;">=</span> <span style="color: green;">1.0</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: #bb7977;">int</span> i <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> i <span style="color: #808030;"><</span> n<span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>i<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
<span style="color: #bb7977;">int</span> cur <span style="color: #808030;">=</span> a<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: #bb7977;">int</span> oldCount <span style="color: #808030;">=</span> n <span style="color: #808030;">-</span> <span style="color: #008c00;">1</span><span style="color: purple;">;</span> oldCount <span style="color: #808030;">></span><span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> <span style="color: #808030;">-</span><span style="color: #808030;">-</span>oldCount<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: #bb7977;">int</span> oldSum <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> oldSum <span style="color: #808030;">+</span> cur <span style="color: #808030;"><</span><span style="color: #808030;">=</span> p<span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>oldSum<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
dp<span style="color: #808030;">[</span>oldCount <span style="color: #808030;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">]</span><span style="color: #808030;">[</span>oldSum <span style="color: #808030;">+</span> cur<span style="color: #808030;">]</span> <span style="color: #808030;">+</span><span style="color: #808030;">=</span> dp<span style="color: #808030;">[</span>oldCount<span style="color: #808030;">]</span><span style="color: #808030;">[</span>oldSum<span style="color: #808030;">]</span> <span style="color: #808030;">/</span> <span style="color: #808030;">(</span>n <span style="color: #808030;">-</span> oldCount<span style="color: #808030;">)</span> <span style="color: #808030;">*</span> <span style="color: #808030;">(</span>oldCount <span style="color: #808030;">+</span> <span style="color: #008c00;">1</span><span style="color: #808030;">)</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
<span style="color: purple;">}</span>
<span style="color: purple;">}</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: #bb7977;">int</span> count <span style="color: #808030;">=</span> <span style="color: #008c00;">1</span><span style="color: purple;">;</span> count <span style="color: #808030;"><</span><span style="color: #808030;">=</span> n<span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>count<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: #bb7977;">int</span> size <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> size <span style="color: #808030;"><</span><span style="color: #808030;">=</span> p<span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>size<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
res <span style="color: #808030;">+</span><span style="color: #808030;">=</span> dp<span style="color: #808030;">[</span>count<span style="color: #808030;">]</span><span style="color: #808030;">[</span>size<span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
<span style="color: purple;">}</span>
out<span style="color: #808030;">.</span>printLine<span style="color: #808030;">(</span>res<span style="color: #808030;">)</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
</pre>
</div>
Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com14tag:blogger.com,1999:blog-7656516316687795220.post-35540185974311335872013-01-28T21:34:00.000-08:002013-01-30T15:13:27.978-08:00Maxim and Restaurant (Part 1)<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
Today I am going to discuss about a problem from <a class="g-profile" href="http://plus.google.com/102644929604870634333" target="_blank">+Codeforces</a> - <a href="http://codeforces.com/contest/261/problem/B" target="_blank">Maxim and Restaurant</a>.<br />
<br />
Maxim has n(<=50) guests in a queue and his table length is p (<=50). Maxim cannot arrange guests if summation of width of guests is more than p. So he allows next person in the queue to enter the room if total summation doesn't exceed p. If by adding next person makes it more than p, Maxim just discards the rest of the queue and doesn't allow anyone else to enter. What is the expected number of guests Maxim will allow if all of his guests queued up in a random order?<br />
<br />
<b>Solution:</b><br />
We can iterate over all guests and consider that guest as a blocker, that means, this person will block the rest of the queue and will make the sum more than p.<br />
<br />
We will now calculate a function f(count, sum), for all 0<=count<=n-1 and 0<=sum<=p. Here f(count, sum) represents, probability of having summation "sum" by adding first "count" persons in the queue. We'll be calculating f, without using the "blocker". For all values of count and sum, f(count, sum) will contribute to our result if after adding blocker it makes the sum more than p. i.e. sum + width(blocker) > p. If that condition is true, we'll add $ f(count, sum) \times \frac{1}{n - count} \times count $. Here f(count, sum) is the probability of having summation "sum" by first "count" person, (1 / (n - count)) is the probability of having the blocker as a next person and count is the number persons will enter for this kind of permutation.<br />
<br />
Check my java solution to see below how I calculated f using dynamic programming. Here dp(i, j) represents f(i, j).<br />
<br /></div>
<pre style="background: #ffffff; color: black;"><span style="color: #7f0055; font-weight: bold;">public</span> void solve(int testNumber, InputReader in, OutputWriter out) {
<span style="color: #7f0055; font-weight: bold;">int</span> n = in.readInt();
<span style="color: #7f0055; font-weight: bold;">int</span>[] a = <span style="color: #7f0055; font-weight: bold;">new</span> <span style="color: #7f0055; font-weight: bold;">int</span>[n];
<span style="color: #7f0055; font-weight: bold;">int</span> total = 0;
<span style="color: #7f0055; font-weight: bold;">for</span> (<span style="color: #7f0055; font-weight: bold;">int</span> i = 0; i < n; ++i) {
a[i] = in.readInt();
total += a[i];
}
<span style="color: #7f0055; font-weight: bold;">int</span> p = in.readInt();
<span style="color: #7f0055; font-weight: bold;">if</span> (total <= p) {
out.printLine(n);
<span style="color: #7f0055; font-weight: bold;">return</span>;
}
<span style="color: #7f0055; font-weight: bold;">double</span> res = 0.;
<span style="color: #7f0055; font-weight: bold;">for</span> (<span style="color: #7f0055; font-weight: bold;">int</span> blocker = 0; blocker < n; ++blocker) {
<span style="color: #7f0055; font-weight: bold;">double</span>[][] dp = <span style="color: #7f0055; font-weight: bold;">new</span> <span style="color: #7f0055; font-weight: bold;">double</span>[n][p + 1];
dp[0][0] = 1.0;
<span style="color: #7f0055; font-weight: bold;">for</span> (<span style="color: #7f0055; font-weight: bold;">int</span> i = 0; i < n; ++i) {
<span style="color: #7f0055; font-weight: bold;">if</span> (i == blocker) <span style="color: #7f0055; font-weight: bold;">continue</span>;
<span style="color: #7f0055; font-weight: bold;">int</span> cur = a[i];
<span style="color: #7f0055; font-weight: bold;">for</span> (<span style="color: #7f0055; font-weight: bold;">int</span> oldCount = n - 2; oldCount >= 0; --oldCount) {
<span style="color: #7f0055; font-weight: bold;">for</span> (<span style="color: #7f0055; font-weight: bold;">int</span> oldSum = 0; oldSum + cur <= p; ++oldSum) {
dp[oldCount + 1][oldSum + cur] +=
dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1);</pre>
<pre style="background: #ffffff; color: black;"> }
}
}
<span style="color: #7f0055; font-weight: bold;">for</span> (<span style="color: #7f0055; font-weight: bold;">int</span> count = 0; count < n; ++count) {
<span style="color: #7f0055; font-weight: bold;">for</span> (<span style="color: #7f0055; font-weight: bold;">int</span> size = 0; size <= p; ++size) {
<span style="color: #7f0055; font-weight: bold;">if</span> (size + a[blocker] <= p) <span style="color: #7f0055; font-weight: bold;">continue</span>;
res += (dp[count][size] * count) / (n - count);
}
}
}
out.printLine(res);
}
</pre>
<pre style="background: #ffffff; color: black;"></pre>
Here,
dp[oldCount + 1][oldSum + cur] += dp[oldCount][oldSum] / (n - oldCount) * (oldCount + 1);
because, after having a permutation of oldCount I can add a new person in this permutation in (oldCount + 1) possible positions. So we're multiplying (oldCount + 1), and probability of being selected at (oldCount + 1)th person from (n - oldCount) person is 1 / (n - oldCount). So we're multiplying this also.
All f(count, sum) can be counted in O(n * n * p). As we're iterating over all the blockers. So the overall algorithm will be O(n ^3 * p).<br />
<br />
No can you think of a solution having complexity O(n ^ 2 * p). I'll try to explain that in next post.</div>
Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com8Sunnyvale, CA, USA37.36883 -122.036349637.166977 -122.35907309999999 37.570683 -121.7136261tag:blogger.com,1999:blog-7656516316687795220.post-40800346948842409472012-06-16T15:10:00.000-07:002013-01-28T21:42:38.042-08:00Height to Area (UVA - 10522)<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
I'm not good at Geometry at all. Now I'm trying to learn geometry and want to become good at it. I'm using this <a href="https://docs.google.com/spreadsheet/pub?key=0Avbf9q-07MMHdEI4RWhmeXRXQXJNQ09WVWl2TVptalE&output=html">list of geometry problems</a> shared by <a href="https://plus.google.com/u/0/112603990590563184887/posts">Shahriar Rouf Nafi</a>.
Today I'm going to discuss about this problem - <a href="http://uva.onlinejudge.org/external/105/10522.html">Height to Area</a>. You are given 3 heights of a triangle, you have to find out the area of the triangle.
<a href="http://uva.onlinejudge.org/external/105/p10522.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="280" src="http://uva.onlinejudge.org/external/105/p10522.jpg" width="350" /></a>
<br />
<br />
<br />
Now given 3 sides Ha, Hb and Hc. We have to calculate the area A.<br />
<br />
If three sides are a, b and c we can have -<br />
<br />
\[
A = \frac{1}{2} \times a \times Ha ........ (1)
\]
\[
A = \frac{1}{2} \times b \times Hb ........ (2)
\]
\[
A = \frac{1}{2} \times c \times Hc ........ (3)
\]
<br />
Now from 1 and 2, we can get<br />
\[
\frac{a}{b} = \frac{Hb}{Ha} ........ (4)
\]
\[
\frac{b}{c} = \frac{Hc}{Hb} ........ (5)
\]
<br />
From (4) and (5)<br />
\[
a : b : c = Hb \times Hc : Hc \times Ha : Ha \times Hb
\]
As Ha, Hb and Hc given, we got the ratio of a, b and c.<br />
<br />
So there will be a k, for which<br />
\[
a = k \times Hb \times Hc ...... (6)
\]
\[
b = k \times Hc \times Ha ...... (7)
\]
\[
c = k \times Ha \times Hb ...... (8)
\]
<br />
If the angles are A, B and C. We know that -<br />
<br />
\[
\cos C = \frac{a^2 + b^2 - c^2}{2 \times b \times c} = \frac{Hb^2 \times Hc^2 + Hc^2 \times Ha^2 + Ha^2 \times Hb^2}{2 \times Hb \times Hc^2 \times Ha}
\]
<br />
So,
\[
C = \cos^{-1} \frac{Hb^2 \times Hc^2 + Hc^2 \times Ha^2 + Ha^2 \times Hb^2}{2 \times Hb \times
Hc^2 \times Ha}
\]
<br />
Now, from sin rule<br />
\[
Ha = b \times \sin C
\]
\[
So, b = \frac{Ha} {\sin C} ...... (9)
\]
<br />
From (7) and (9) we get<br />
\[
k = \frac{1} {Hc \times \sin C}
\]
<br />
We know Ha, Hb, Hc, and k, so we can calculate the exact value of a, b and c. So we can calculate the area of triangle by the following formula -<br />
\[
A = \sqrt{ \frac{s \times (s - a) \times (s - b) \times (s - c)} {2} }, where s = \frac{a + b + c}{2}
\]
This was my solution.<br />
<br />
While discussing my solution with Nafi, he gave me a much smarter solution, Here it is<br />
Area<br />
\[
A = \frac{1}{2} \times a \times Ha
\]
So
\[
a = 2 \times \frac{A}{Ha} ... (1)
\]
Similarly,
\[
b = 2 \times \frac{A}{Hb} ... (2)
\]
\[
c = 2 \times \frac{A}{Hc} ... (3)
\]
Now,
\begin{align}
s &= \frac{a + b + c}{2}\\
&= (\frac{A}{Ha} + \frac{A}{Hb} + \frac{A}{Hc})
\end{align}
And,
\[
A^2 = s \times (s - a) \times (s - b) \times (s - c)
\]
\[
A^2 = (\frac{A}{Ha} + \frac{A}{Hb} + \frac{A}{Hc}) \times (\frac{A}{Hb} + \frac{A}{Hc} - \frac{A}{Ha}) \times (\frac{A}{Hc} + \frac{A}{Ha} - \frac{A}{Hb}) \times (\frac{A}{Ha} + \frac{A}{Hb} - \frac{A}{Hc})
\]
\[
\Rightarrow A^2 = A^4 \times (\frac{1}{Ha} + \frac{1}{Hb} + \frac{1}{Hc}) \times (\frac{1}{Hb} + \frac{1}{Hc} - \frac{1}{Ha}) \times (\frac{1}{Hc} + \frac{1}{Ha} - \frac{1}{Hb}) \times (\frac{1}{Ha} + \frac{1}{Hb} - \frac{1}{Hc})
\]
\[
\Rightarrow A^2 = \frac{1}{(\frac{1}{Ha} + \frac{1}{Hb} + \frac{1}{Hc}) \times (\frac{1}{Hb} + \frac{1}{Hc} - \frac{1}{Ha}) \times (\frac{1}{Hc} + \frac{1}{Ha} - \frac{1}{Hb}) \times (\frac{1}{Ha} + \frac{1}{Hb} - \frac{1}{Hc})}
\]
\[
\Rightarrow A = \sqrt{\frac{1}{(\frac{1}{Ha} + \frac{1}{Hb} + \frac{1}{Hc}) \times (\frac{1}{Hb} + \frac{1}{Hc} - \frac{1}{Ha}) \times (\frac{1}{Hc} + \frac{1}{Ha} - \frac{1}{Hb}) \times (\frac{1}{Ha} + \frac{1}{Hb} - \frac{1}{Hc})}}
\]
<br />
Much cleaner solution. Thanks Nafi.<br />
</div>Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com0tag:blogger.com,1999:blog-7656516316687795220.post-51888856028273600812012-02-20T13:23:00.000-08:002013-02-02T08:11:01.553-08:00Silly Sort (Spoj - 2277, UVa - 1016)<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Today I'll discuss the problem <a href="http://www.spoj.pl/problems/SSORT/">Silly Sort</a> from <a href="http://www.spoj.pl/">spoj</a>, which is also <a href="http://uva.onlinejudge.org/external/10/1016.html">in uva</a>.</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"><br /></span>
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">In this problem you have to sort an array of integers in ascending order. Quite familiar to you. But here you are only allowed to swap any two elements. And each swap has a cost which is the sum of those two elements. You have to sort the array in minimum cost.</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"><br /></span>
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Seems tricky, so let's brainstorm. At first we have to know which element will go to which place after the complete sort. We can easily calculate that by copying the array into another array and sorting that array. Let's say original array is a and sorted array is b. So b[i] will go to i<sup>th</sup> place for each i, in other word i is the <b>destination</b> of b[i].
First thing comes to our mind is, in each swap we will ensure that at least one element will move to it's destination. This will ensure minimum number of swaps, but will it confirm the minimum cost?</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"><br /></span>
<div class="p1">
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Let's work with the first example -</span></div>
<div class="p1">
<span style="font-family: 'Courier New',Courier,monospace;">3</span></div>
<div class="p1">
<span style="font-family: 'Courier New',Courier,monospace;">3 2 1</span></div>
<div class="p1">
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Sorted array will be -</span></div>
<div class="p1">
<span style="font-family: 'Courier New',Courier,monospace;">1 2 3</span></div>
<div class="p1">
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">So If we want to ensure at least one element will go to it's destination in each swap, then we have to swap 1 and 3, and after that that is our sorted array, cost is 4, which is minimum cost. So it's working for this example.</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"><br /></span></div>
<div class="p1">
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Let's try with another example</span></div>
<div class="p1">
<span style="font-family: 'Courier New',Courier,monospace;">3</span></div>
<div class="p1">
<span style="font-family: 'Courier New',Courier,monospace;">3 1 2</span></div>
<div class="p1">
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">If we swap 3 and 1, then 1 will go to it's destination and the array will become - {1, 3, 2}, now we have to swap 3 and 2, then it will be sorted. Cost is (3 + 1) + (3 + 2) = 9. But in first move if we swap 1 and 2, it will become {3, 2, 1} and then swapping 3 and 1 will make it sorted and the cost will be (1 + 2) + (3 + 1) = 7. So two different ordering causes two different costs. So what will be our strategy?</span></div>
<div class="p1">
<br /></div>
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Let's work with 4th example given with the problem -</span><br />
<pre><span style="font-family: 'Courier New',Courier,monospace;">6
8 4 5 3 2 7 </span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">
</span></pre>
<pre><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Sorted array will be -</span></pre>
<pre><span style="font-family: 'Courier New',Courier,monospace;">2 3 4 5 7 8</span></pre>
<pre></pre>
<pre><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">So, 2 will go to 8's place, 3 will go to 4's place, etc. Let's draw these relations.</span></pre>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhL7EQaHAeUt9zil8KdKQ0bfPfHIIrW2uMhajBioP-TsKdtllbYjtSwOO6Fgo74oAzJyfC1_LKIoV2zdb1TLV_8bfwwSqrn9_-chVMyfg_4LH9vQioKQCDRUT3PQMO2oHDtS4ptbc8K-IY/s1600/silly-sort-1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="186" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhL7EQaHAeUt9zil8KdKQ0bfPfHIIrW2uMhajBioP-TsKdtllbYjtSwOO6Fgo74oAzJyfC1_LKIoV2zdb1TLV_8bfwwSqrn9_-chVMyfg_4LH9vQioKQCDRUT3PQMO2oHDtS4ptbc8K-IY/s400/silly-sort-1.png" width="400" /></a></div>
<pre></pre>
<br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">In the above image, it is seen that 2 will go to 8's place, 8 will go to 7's place, 7 will go to 2's place. These three formed a cycle, another cycle is 3 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 4 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 5 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 3. So every input can be decomposed into some cycles.</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"><br /></span>
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">So, our next approach is solving each cycles independently and sum of the costs for all cycles is our result. But what is the cost of solving a cycle. We see If we swap 2 and 8 of 2 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 8 <span style="background-color: white; font-size: 12px;">→</span> 7 <span style="background-color: white; font-size: 12px;">→</span> 2 cycle. 2 will go to it's destination, and 7 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 8 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 7 will form a smaller cycle.</span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6ksu1fQDmi03FJiqNkuNxGbcEHUgAOSbWK578AiKB9NpBJkbHF3IVCAH4gb0zQdl9jXDT-TuzXC6KHIVj05iybxSF3K_ecltG95AtfOEaD-ueItSRN533kQTpupwAyJVrmrk5OnDIgYM/s1600/silly-sort-2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="175" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh6ksu1fQDmi03FJiqNkuNxGbcEHUgAOSbWK578AiKB9NpBJkbHF3IVCAH4gb0zQdl9jXDT-TuzXC6KHIVj05iybxSF3K_ecltG95AtfOEaD-ueItSRN533kQTpupwAyJVrmrk5OnDIgYM/s200/silly-sort-2.png" width="200" /></a></div>
<br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">If we swap two elements in a cycle of length K > 1 such that at least 1 element of this cycle will go to it's destination. Then after the swap, it will be splited into two cycles, one with length K - 1 and another one with length 1. We don't need to do anything with the cycle of length 1 because the element is already in it's destination.</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"><br /></span>
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Now for solving a cycle optimally, we need some observations -</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">1. Every element of this cycle will participate in at least 1 swap.</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">2. We need K - 1 swaps to sort this cycle. Each swap will add two elements to the cost. So 2 </span><span style="background-color: #eeffdd;">×</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> (K - 1) elements will be added to the cost. There are K elements. So some elements will be added multiple times.</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"><br /></span>
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">So if we want to move an element x to it's destination by swapping with another value, we should try to swap with the minimum value of that cycle. If we can do that for every element other than the smallest element. Than in the final cost, every element will be added once and the minimum element will be added K - 1 times. And we cannot make any less cost by confirming (1) and (2). So this is the optimal approach to solve a cycle.</span><br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"><br /></span>
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">So In the above cycle 2 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 8 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 7 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 2, we'll swap 7 and 2 first. Cost is 9, then 8 and 2, cost is 10. So total cost is 19 for this cycle. In the same way, solving the second cycle 3 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→ </span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">4 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→ </span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">5 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px;">→ </span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">3 will cost 15. Total cost for this case is 34. This is the result of that example also.</span><br />
<br />
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Now let's try example 3 -</span><br />
<pre style="text-align: -webkit-auto;"><span style="font-family: 'Courier New',Courier,monospace;">5
1 8 9 7 6 </span></pre>
<pre style="text-align: -webkit-auto;"><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">There are two cycles.</span></pre>
<pre style="text-align: -webkit-auto;"><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">1 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px; white-space: normal;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 1</span></pre>
<pre style="text-align: -webkit-auto;"><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">6 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px; white-space: normal;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 8 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px; white-space: normal;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 7 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px; white-space: normal;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 9 </span><span style="background-color: white; font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif; font-size: 12px; white-space: normal;">→</span><span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"> 6</span></pre>
<br />
<div class="p1">
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Solving the first cycle costs 0, and second cycle costs 42, total 42. But result is 41. So solving every cycles independently will not give the best result. Here in this example, the minimum element is 6 in the second cycle. As the cycle length is 4 it will be added 3 times which will cost 18. But if know there is an 1 in another cycle. We can borrow it by swapping with 6, which will cost 6 + 1 = 7, then do the sorting this time we use 1 instead of 6, this will add 3 instead of 18. After sorting 1 will be in place of 6's destination and we have to give the 1 back to it's own cycle and bring our 6 back. We can do it by one more swap which will cost another 7. So total cost 7 + 3 + 7 = 17 which is 1 less than 18. That's how the result is 41. So we'll try to borrow the minimum value of the whole given array and see whether it gives the optimal results or not.</span></div>
<div class="p2">
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;"><br /></span></div>
<div class="p1">
<span style="font-family: 'Helvetica Neue',Arial,Helvetica,sans-serif;">Here is my simple solution in c++.</span></div>
<div class="p1">
<br /></div>
</div>
<pre style="background: #ffffff; color: black;"><span style="color: #004a43;">#</span><span style="color: #004a43;">include </span><span style="color: maroon;"><</span><span style="color: #40015a;">iostream</span><span style="color: maroon;">></span>
<span style="color: #004a43;">#</span><span style="color: #004a43;">include </span><span style="color: maroon;"><</span><span style="color: #40015a;">cstdio</span><span style="color: maroon;">></span>
<span style="color: #004a43;">#</span><span style="color: #004a43;">include </span><span style="color: maroon;"><</span><span style="color: #40015a;">map</span><span style="color: maroon;">></span>
<span style="color: #004a43;">#</span><span style="color: #004a43;">include </span><span style="color: maroon;"><</span><span style="color: #40015a;">algorithm</span><span style="color: maroon;">></span>
<span style="color: maroon; font-weight: bold;">using</span> <span style="color: maroon; font-weight: bold;">namespace</span> <span style="color: #666616;">std</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">int</span> a<span style="color: #808030;">[</span><span style="color: #008c00;">100000</span><span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">int</span> b<span style="color: #808030;">[</span><span style="color: #008c00;">100000</span><span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">bool</span> vis<span style="color: #808030;">[</span><span style="color: #008c00;">100000</span><span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">int</span> <span style="color: #400000;">main</span> <span style="color: #808030;">(</span><span style="color: maroon; font-weight: bold;">void</span><span style="color: #808030;">)</span> <span style="color: purple;">{</span>
<span style="color: maroon; font-weight: bold;">int</span> N<span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">int</span> t <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">while</span> <span style="color: #808030;">(</span><span style="color: #603000;">scanf</span><span style="color: #808030;">(</span><span style="color: maroon;">"</span><span style="color: #0f69ff;">%d</span><span style="color: maroon;">"</span><span style="color: #808030;">,</span> <span style="color: #808030;">&</span>N<span style="color: #808030;">)</span> <span style="color: #808030;">&</span><span style="color: #808030;">&</span> N<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
t<span style="color: #808030;">+</span><span style="color: #808030;">+</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: maroon; font-weight: bold;">int</span> i <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> i <span style="color: #808030;"><</span> N<span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>i<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
<span style="color: #603000;">scanf</span><span style="color: #808030;">(</span><span style="color: maroon;">"</span><span style="color: #0f69ff;">%d</span><span style="color: maroon;">"</span><span style="color: #808030;">,</span> <span style="color: #808030;">&</span>a<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span><span style="color: #808030;">)</span><span style="color: purple;">;</span>
b<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span> <span style="color: #808030;">=</span> a<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span><span style="color: purple;">;</span>
vis<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span> <span style="color: #808030;">=</span> <span style="color: maroon; font-weight: bold;">false</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
<span style="color: #603000;">sort</span><span style="color: #808030;">(</span>b<span style="color: #808030;">,</span> b <span style="color: #808030;">+</span> N<span style="color: #808030;">)</span><span style="color: purple;">;</span>
<span style="color: dimgrey;">// Map the numbers to their desired place after sort</span>
<span style="color: #603000;">map</span><span style="color: purple;"><</span><span style="color: maroon; font-weight: bold;">int</span><span style="color: #808030;">,</span> <span style="color: maroon; font-weight: bold;">int</span><span style="color: purple;">></span> place<span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: maroon; font-weight: bold;">int</span> i <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> i <span style="color: #808030;"><</span> N<span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>i<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
place<span style="color: #808030;">[</span>b<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span><span style="color: #808030;">]</span> <span style="color: #808030;">=</span> i<span style="color: purple;">;</span>
<span style="color: purple;">}</span>
<span style="color: maroon; font-weight: bold;">int</span> res <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">for</span> <span style="color: #808030;">(</span><span style="color: maroon; font-weight: bold;">int</span> i <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span> i <span style="color: #808030;"><</span> N<span style="color: purple;">;</span> <span style="color: #808030;">+</span><span style="color: #808030;">+</span>i<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
<span style="color: maroon; font-weight: bold;">if</span> <span style="color: #808030;">(</span>vis<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span> <span style="color: #808030;">=</span><span style="color: #808030;">=</span> <span style="color: maroon; font-weight: bold;">false</span><span style="color: #808030;">)</span> <span style="color: purple;">{</span>
<span style="color: maroon; font-weight: bold;">if</span> <span style="color: #808030;">(</span>place<span style="color: #808030;">[</span>a<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span><span style="color: #808030;">]</span> <span style="color: #808030;">=</span><span style="color: #808030;">=</span> i<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
vis<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span> <span style="color: #808030;">=</span> <span style="color: maroon; font-weight: bold;">true</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">continue</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
<span style="color: dimgrey;">// We're in new cycle</span>
<span style="color: maroon; font-weight: bold;">int</span> min_val <span style="color: #808030;">=</span> a<span style="color: #808030;">[</span>i<span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">int</span> num <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">int</span> sum <span style="color: #808030;">=</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">int</span> j <span style="color: #808030;">=</span> i<span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">while</span> <span style="color: #808030;">(</span>vis<span style="color: #808030;">[</span>j<span style="color: #808030;">]</span> <span style="color: #808030;">=</span><span style="color: #808030;">=</span> <span style="color: maroon; font-weight: bold;">false</span><span style="color: #808030;">)</span> <span style="color: purple;">{</span>
sum <span style="color: #808030;">+</span><span style="color: #808030;">=</span> a<span style="color: #808030;">[</span>j<span style="color: #808030;">]</span><span style="color: purple;">;</span>
num<span style="color: #808030;">+</span><span style="color: #808030;">+</span><span style="color: purple;">;</span>
<span style="color: maroon; font-weight: bold;">if</span> <span style="color: #808030;">(</span>a<span style="color: #808030;">[</span>j<span style="color: #808030;">]</span> <span style="color: #808030;"><</span> min_val<span style="color: #808030;">)</span> <span style="color: purple;">{</span>
min_val <span style="color: #808030;">=</span> a<span style="color: #808030;">[</span>j<span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
vis<span style="color: #808030;">[</span>j<span style="color: #808030;">]</span> <span style="color: #808030;">=</span> <span style="color: maroon; font-weight: bold;">true</span><span style="color: purple;">;</span>
j <span style="color: #808030;">=</span> place<span style="color: #808030;">[</span>a<span style="color: #808030;">[</span>j<span style="color: #808030;">]</span><span style="color: #808030;">]</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
sum <span style="color: #808030;">-</span><span style="color: #808030;">=</span> min_val<span style="color: purple;">;</span>
res <span style="color: #808030;">+</span><span style="color: #808030;">=</span> sum <span style="color: #808030;">+</span> min_val <span style="color: #808030;">*</span> <span style="color: #808030;">(</span>num <span style="color: #808030;">-</span> <span style="color: #008c00;">1</span><span style="color: #808030;">)</span><span style="color: purple;">;</span>
<span style="color: dimgrey;">// Let's try to borrow the minimum value.</span>
<span style="color: dimgrey;">// If it's less costly then update our result.</span>
<span style="color: maroon; font-weight: bold;">if</span> <span style="color: #808030;">(</span><span style="color: #008c00;">2</span> <span style="color: #808030;">*</span> <span style="color: #808030;">(</span>b<span style="color: #808030;">[</span><span style="color: #008c00;">0</span><span style="color: #808030;">]</span> <span style="color: #808030;">+</span> min_val<span style="color: #808030;">)</span> <span style="color: #808030;"><</span>
<span style="color: #808030;">(</span>min_val <span style="color: #808030;">-</span> b<span style="color: #808030;">[</span><span style="color: #008c00;">0</span><span style="color: #808030;">]</span><span style="color: #808030;">)</span> <span style="color: #808030;">*</span> <span style="color: #808030;">(</span>num <span style="color: #808030;">-</span> <span style="color: #008c00;">1</span><span style="color: #808030;">)</span><span style="color: #808030;">)</span> <span style="color: purple;">{</span>
res <span style="color: #808030;">-</span><span style="color: #808030;">=</span> <span style="color: #808030;">(</span>min_val <span style="color: #808030;">-</span> b<span style="color: #808030;">[</span><span style="color: #008c00;">0</span><span style="color: #808030;">]</span><span style="color: #808030;">)</span> <span style="color: #808030;">*</span> <span style="color: #808030;">(</span>num <span style="color: #808030;">-</span> <span style="color: #008c00;">1</span><span style="color: #808030;">)</span> <span style="color: #808030;">-</span>
<span style="color: #008c00;">2</span> <span style="color: #808030;">*</span> <span style="color: #808030;">(</span>b<span style="color: #808030;">[</span><span style="color: #008c00;">0</span><span style="color: #808030;">]</span> <span style="color: #808030;">+</span> min_val<span style="color: #808030;">)</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
<span style="color: purple;">}</span>
<span style="color: purple;">}</span>
<span style="color: #603000;">printf</span><span style="color: #808030;">(</span><span style="color: maroon;">"</span><span style="color: #0000e6;">Case </span><span style="color: #0f69ff;">%d</span><span style="color: #0000e6;">: </span><span style="color: #0f69ff;">%d</span><span style="color: #0f69ff;">\n</span><span style="color: #0f69ff;">\n</span><span style="color: maroon;">"</span><span style="color: #808030;">,</span> t<span style="color: #808030;">,</span> res<span style="color: #808030;">)</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
<span style="color: maroon; font-weight: bold;">return</span> <span style="color: #008c00;">0</span><span style="color: purple;">;</span>
<span style="color: purple;">}</span>
</pre>
<pre style="background-attachment: initial; background-clip: initial; background-color: white; background-image: initial; background-origin: initial; background-position: initial initial; background-repeat: initial initial;"><span style="color: purple;">
</span></pre>
</div>
Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com10Sunnyvale, CA, USA37.36883 -122.036349637.166977 -122.35769959999999 37.570683 -121.7149996tag:blogger.com,1999:blog-7656516316687795220.post-33044457427344914822011-08-28T12:06:00.000-07:002011-08-31T14:29:43.688-07:00SGU - 101 - DominoThis is another interesting problem.
<br />
<br />Problem link : <a href="http://acm.sgu.ru/problem.php?contest=0&problem=101">http://acm.sgu.ru/problem.php?contest=0&problem=101</a>
<br />
<br />Problem summery: You're given N (N <= 100) dominoes. Each of the dominoes has two numbers on it between 0 to 6, one in left side and another in right side. You have to arrange all the dominoes in a row so that they touch through equal marked side. If not possible print "No solution". Note that, we also have to check the graph is connected.
<br />
<br />For example, we have three dominoes [1 2], [3, 2], [3 4]
<br />If we arrange these dominoes like this -
<br />[1 2] - [3 2] - [3, 4], this is invalid, because right side of first domino and left side of second domino marked with different numbers. But if we flip the second domino, to change left and right side, it will become -
<br />[1 2] - [2 3] - [3 4], now every two adjacent dominoes touches with equal marked side. So it's a valid arrangement. So to organize it like this, we are allowed to rearrange dominoes and rotate any domino.
<br />
<br />To solve this problem, we cannot try all possible arrangements because number of arrangements is too large. As the dominoes are marked with numbers between 0 to 6, we can consider we have a graph of 7 nodes named 0 to 6. If there is a domino [a b], we will consider there is an edge between a and b. Now we have a graph of at most 7 nodes and at most 100 edges. Our problem can be described as - is it possible to start traversing from one node and visit each of the edges exactly once?
<br />
<br />Let's use the example from the problem. We have 5 dominoes [1 2], [2 4], [2 4], [6 4], [2 1]. We can build our graph like this -
<br />
<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgzOi_sfJd6LtKE781Z3WyD8s6bu6Uof36OhdQcNDbPd4FH8U4GtdCaZF1a3YDIdhfiW-qb0dT3XPSySi_-lcGVqtLmR_sycF613Xhc2jMntImJAyWIl0soS9Edu-DnAlqlx4PB14XyZVY/s1600/domino-2.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 349px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgzOi_sfJd6LtKE781Z3WyD8s6bu6Uof36OhdQcNDbPd4FH8U4GtdCaZF1a3YDIdhfiW-qb0dT3XPSySi_-lcGVqtLmR_sycF613Xhc2jMntImJAyWIl0soS9Edu-DnAlqlx4PB14XyZVY/s400/domino-2.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5646006433278608162" /></a>
<br />
<br />And what about the solution? See the following image, yes we can traverse all edges exactly once.
<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5lo63B4Ncjkoqb6X0ZcRgbnb4IMC5auh2iTG7AiDkAKWtjyKQAVHcS7rxmk5gSiEldwq4rG_fQAq6wBKIogDxfsaBHCmGeIQKi2aOm0xRi3mtKXgqbPlz4zRMxN6kfB3Krw1VbrAw3Uc/s1600/domino-2.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 349px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5lo63B4Ncjkoqb6X0ZcRgbnb4IMC5auh2iTG7AiDkAKWtjyKQAVHcS7rxmk5gSiEldwq4rG_fQAq6wBKIogDxfsaBHCmGeIQKi2aOm0xRi3mtKXgqbPlz4zRMxN6kfB3Krw1VbrAw3Uc/s400/domino-2.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5646010056882559842" /></a>
<br />
<br />The path we traversed is 4 -> 2 -> 1 -> 2 -> 4 -> 6. So, our domino arrangement will be, [4 2] - [2 1] - [1 2] - [2 4] - [4 6], if we write the indices of the dominoes this sequence is 2, 5, 1, 3, 4. Note that we flipped one [2 4] tile to [4 2] and [6 4] tile to [4 6]. We also need to output which domino we used as it is by a '+' sign, and which domino we flipped by a '-' sign. So our answer is -
<br />2 -
<br />5 +
<br />1 +
<br />3 +
<br />4 -
<br />Which is also given in the sample output.
<br />
<br /><a href="http://en.wikipedia.org/wiki/Leonhard_Euler">Leonhard Euler</a> proved that, we can visit every edge exactly once in a graph if number of nodes having odd degree is not more than two. If number of odd degree in the graph is two, we have to start from one of them and end our tour in another of them. By the name of Euler, this path is called Eulerian trail or Eulerian walk. For example in our graph in the image above, node 4 and 6 have odd degree, so we started at 4 and ended at 6.
<br />
<br />So, if the number of odd degree of the graph is more than two, we will output "No solution", otherwise we will try to print any one of the solution, by finding out the Eulerian walk. But, what will be the strategy of our Eulerian walk. We can use the strategy of Fleury's algorithm. The strategy is, start with an odd degree node if there exists any, otherwise start with any node. At each iteration we visit the edge whose deletion would not disconnect the graph.
<br />
<br />Now, as we have n edge, so we will remove one edge at each step of our algorithm. We'll try 7 different edges and after removing that edge we'll check whether the graph is connected nor not using a dfs, in our case, which is O(n). So our algorithm is somewhat like O(n * n).
<br />
<br />My simple C++ solution -
<br /><pre style='color:#000000;background:#ffffff;'><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>iostream</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>cstdio</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>vector</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>cstring</span><span style='color:#800000; '>></span><br /><br /><span style='color:#800000; font-weight:bold; '>using</span> <span style='color:#800000; font-weight:bold; '>namespace</span> <span style='color:#666616; '>std</span><span style='color:#800080; '>;</span><br /><br /><span style='color:#800000; font-weight:bold; '>bool</span> vis<span style='color:#808030; '>[</span><span style='color:#008c00; '>7</span><span style='color:#808030; '>]</span><span style='color:#800080; '>;</span><br /><span style='color:#603000; '>vector</span><span style='color:#800080; '><</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#800080; '>></span> edge_index<span style='color:#808030; '>[</span><span style='color:#008c00; '>7</span><span style='color:#808030; '>]</span><span style='color:#808030; '>[</span><span style='color:#008c00; '>7</span><span style='color:#808030; '>]</span><span style='color:#800080; '>;</span><br /><span style='color:#800000; font-weight:bold; '>int</span> degree<span style='color:#808030; '>[</span><span style='color:#008c00; '>7</span><span style='color:#808030; '>]</span><span style='color:#800080; '>;</span><br /><br /><span style='color:#696969; '>// can reach v from u?</span><br /><span style='color:#800000; font-weight:bold; '>bool</span> dfs<span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> u<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>int</span> v<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>u <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> v<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#800000; font-weight:bold; '>true</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> vis<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span> <span style='color:#808030; '>=</span> <span style='color:#800000; font-weight:bold; '>true</span><span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>6</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span><span style='color:#808030; '>(</span>edge_index<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>></span> <span style='color:#008c00; '>0</span> <span style='color:#808030; '>|</span><span style='color:#808030; '>|</span> edge_index<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>></span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>)</span><br /> <span style='color:#808030; '>&</span><span style='color:#808030; '>&</span> vis<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span> <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#800000; font-weight:bold; '>false</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>dfs<span style='color:#808030; '>(</span>i<span style='color:#808030; '>,</span> v<span style='color:#808030; '>)</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#800000; font-weight:bold; '>true</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#800000; font-weight:bold; '>false</span><span style='color:#800080; '>;</span><br /><span style='color:#800080; '>}</span><br /><br /><span style='color:#800000; font-weight:bold; '>bool</span> is_connected<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> memset<span style='color:#808030; '>(</span>vis<span style='color:#808030; '>,</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>sizeof</span><span style='color:#808030; '>(</span>vis<span style='color:#808030; '>)</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>6</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>degree<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> dfs<span style='color:#808030; '>(</span>i<span style='color:#808030; '>,</span> <span style='color:#808030; '>-</span><span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>break</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span> <br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>6</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>degree<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span> <span style='color:#808030; '>></span> <span style='color:#008c00; '>0</span> <span style='color:#808030; '>&</span><span style='color:#808030; '>&</span> vis<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span> <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#800000; font-weight:bold; '>false</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#800000; font-weight:bold; '>false</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#800000; font-weight:bold; '>true</span><span style='color:#800080; '>;</span><br /><span style='color:#800080; '>}</span><br /><br /><span style='color:#800000; font-weight:bold; '>int</span> <span style='color:#400000; '>main</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>void</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>int</span> n<span style='color:#800080; '>;</span> <span style='color:#696969; '>// number of dominoes i.e. number of edges</span><br /> scanf<span style='color:#808030; '>(</span><span style='color:#800000; '>"</span><span style='color:#0f69ff; '>%d</span><span style='color:#800000; '>"</span><span style='color:#808030; '>,</span> <span style='color:#808030; '>&</span>n<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> memset<span style='color:#808030; '>(</span>degree<span style='color:#808030; '>,</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>sizeof</span><span style='color:#808030; '>(</span>degree<span style='color:#808030; '>)</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>6</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> j <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> j <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>6</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>j<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> edge_index<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>clear<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>1</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> n<span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>int</span> u<span style='color:#808030; '>,</span> v<span style='color:#800080; '>;</span><br /> scanf<span style='color:#808030; '>(</span><span style='color:#800000; '>"</span><span style='color:#0f69ff; '>%d</span><span style='color:#0f69ff; '>%d</span><span style='color:#800000; '>"</span><span style='color:#808030; '>,</span> <span style='color:#808030; '>&</span>u<span style='color:#808030; '>,</span> <span style='color:#808030; '>&</span>v<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> edge_index<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>v<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>push_back<span style='color:#808030; '>(</span>i<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> degree<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>+</span><span style='color:#808030; '>+</span><span style='color:#800080; '>;</span><br /> degree<span style='color:#808030; '>[</span>v<span style='color:#808030; '>]</span><span style='color:#808030; '>+</span><span style='color:#808030; '>+</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /><br /> <span style='color:#800000; font-weight:bold; '>int</span> n_odd <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> <span style='color:#696969; '>// number of nodes with odd degree</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>6</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>degree<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span> <span style='color:#808030; '>%</span> <span style='color:#008c00; '>2</span> <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> n_odd<span style='color:#808030; '>+</span><span style='color:#808030; '>+</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>n_odd <span style='color:#808030; '>></span> <span style='color:#008c00; '>2</span> <span style='color:#808030; '>|</span><span style='color:#808030; '>|</span> is_connected<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#800000; font-weight:bold; '>false</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#696969; '>// if number of odd degree node is more than 2</span><br /> <span style='color:#696969; '>// eulerian path doesn't exist for this graph</span><br /> printf<span style='color:#808030; '>(</span><span style='color:#800000; '>"</span><span style='color:#0000e6; '>No solution</span><span style='color:#0f69ff; '>\n</span><span style='color:#800000; '>"</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span> <span style='color:#800000; font-weight:bold; '>else</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>int</span> u <span style='color:#808030; '>=</span> <span style='color:#808030; '>-</span><span style='color:#008c00; '>1</span><span style='color:#800080; '>;</span> <span style='color:#696969; '>// starting node</span><br /><br /> <span style='color:#696969; '>// start node with an odd degree node, if exists</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>6</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>degree<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span> <span style='color:#808030; '>%</span> <span style='color:#008c00; '>2</span> <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> u <span style='color:#808030; '>=</span> i<span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>break</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /><br /> <span style='color:#696969; '>// if odd degree node not found, start with a node</span><br /> <span style='color:#696969; '>// with positive degree, i.e. start with any vertex,</span><br /> <span style='color:#696969; '>// which is used in the graph</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>u <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#808030; '>-</span><span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>6</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>degree<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span> <span style='color:#808030; '>></span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> u <span style='color:#808030; '>=</span> i<span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>break</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /><br /> <span style='color:#696969; '>// Fleury's algorithm</span><br /> <span style='color:#696969; '>// n steps - at each step, remove one edge</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span> n<span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>int</span> selected_ind<span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>bool</span> forward_selected<span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> j <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> j <span style='color:#808030; '><</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>6</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>j<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>edge_index<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>></span> <span style='color:#008c00; '>0</span> <span style='color:#808030; '>|</span><span style='color:#808030; '>|</span><br /> edge_index<span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>></span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>int</span> cur_ind<span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>bool</span> forward<span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>edge_index<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>></span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> cur_ind <span style='color:#808030; '>=</span> edge_index<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>back<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> edge_index<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>pop_back<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> forward <span style='color:#808030; '>=</span> <span style='color:#800000; font-weight:bold; '>true</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span> <span style='color:#800000; font-weight:bold; '>else</span> <span style='color:#800080; '>{</span><br /> cur_ind <span style='color:#808030; '>=</span> edge_index<span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>back<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> edge_index<span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>pop_back<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> forward <span style='color:#808030; '>=</span> <span style='color:#800000; font-weight:bold; '>false</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> degree<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>-</span><span style='color:#808030; '>-</span><span style='color:#800080; '>;</span><br /> degree<span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>-</span><span style='color:#808030; '>-</span><span style='color:#800080; '>;</span><br /><br /> memset<span style='color:#808030; '>(</span>vis<span style='color:#808030; '>,</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>sizeof</span><span style='color:#808030; '>(</span>vis<span style='color:#808030; '>)</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span> <br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>degree<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span> <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span> <span style='color:#808030; '>|</span><span style='color:#808030; '>|</span> dfs<span style='color:#808030; '>(</span>u<span style='color:#808030; '>,</span> j<span style='color:#808030; '>)</span> <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#800000; font-weight:bold; '>true</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#696969; '>// remove this edge</span><br /> selected_ind <span style='color:#808030; '>=</span> cur_ind<span style='color:#800080; '>;</span><br /> forward_selected <span style='color:#808030; '>=</span> forward<span style='color:#800080; '>;</span><br /> u <span style='color:#808030; '>=</span> j<span style='color:#800080; '>;</span> <span style='color:#696969; '>// so we are in j now.</span><br /> <span style='color:#800000; font-weight:bold; '>break</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span> <span style='color:#800000; font-weight:bold; '>else</span> <span style='color:#800080; '>{</span><br /> <span style='color:#696969; '>// this edge cannot be removed</span><br /> <span style='color:#696969; '>// back to previous state</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>forward<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> edge_index<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>push_back<span style='color:#808030; '>(</span>cur_ind<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span> <span style='color:#800000; font-weight:bold; '>else</span> <span style='color:#800080; '>{</span><br /> edge_index<span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>.</span>push_back<span style='color:#808030; '>(</span>cur_ind<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> degree<span style='color:#808030; '>[</span>u<span style='color:#808030; '>]</span><span style='color:#808030; '>+</span><span style='color:#808030; '>+</span><span style='color:#800080; '>;</span><br /> degree<span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>+</span><span style='color:#808030; '>+</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /> printf<span style='color:#808030; '>(</span><span style='color:#800000; '>"</span><span style='color:#0f69ff; '>%d</span><span style='color:#0000e6; '> </span><span style='color:#0f69ff; '>%c</span><span style='color:#0f69ff; '>\n</span><span style='color:#800000; '>"</span><span style='color:#808030; '>,</span> selected_ind<span style='color:#808030; '>,</span> forward_selected <span style='color:#800080; '>?</span> <span style='color:#0000e6; '>'+'</span> <span style='color:#800080; '>:</span> <span style='color:#0000e6; '>'-'</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /><br /> <span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span><br /><span style='color:#800080; '>}</span><br /></pre><br />
<br />
<br />Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com0tag:blogger.com,1999:blog-7656516316687795220.post-87357572610423219452011-08-20T10:37:00.000-07:002011-08-24T01:35:43.408-07:00Maximum Triangle Area (Part 3 and final)<a href="http://isolvedaproblem.blogspot.com/2011/08/maximum-triangle-area-part-2.html">Part 1</a>
<br /><a href="http://isolvedaproblem.blogspot.com/2011/08/maximum-triangle-area-part-1.html">Part 2</a>
<br />
<br />After second part, our algorithm became something like this -
<br />for each 0 <= i < n, initialize A = P<sub>i</sub>, B = P<sub>(i + 1) % n</sub>, C = P<sub>(i + 2) % n</sub>, then move C counter clockwise until area non-decreasing, move B to its adjacent point counter clockwise, if area non-decreasing, move C again until area non decreasing and so on. You will get the maximum area for each A and output the maximum of these areas. For a given point starting point P<sub>i</sub>, if the maximum area is ABC. We can say ABC is 'stable' triangle for A, in other word s(p<sub>i</sub>, P<sub>i + 1</sub>, P<sub>i + 2</sub>) = ABC, that means we cannot move B or C any further by not decreasing the area.
<br />
<br />Now, after getting a maximum ABC for a fixed first point P<sub>i</sub>, we will start with P<sub>i + 1</sub>, P<sub>i + 2</sub> and P<sub>i + 3</sub>. We get A'B'C' as a stable triangle i.e. s(p<sub>i</sub>, p<sub>i + 1</sub>, p<sub>i + 2</sub>) = A'B'C'. Hence our algorithm is O(n ^ 2). But it can be proved that, rather than, start from P<sub>i + 1</sub> as a second point and P<sub>i + 2</sub> as a third point, we can start with B and C as a second and third point and get the same result, i.e. s(P<sub>i + 1</sub>, P<sub>i + 2</sub>, P<sub>i + 3</sub>) = s(P<sub>i + 1</sub>, B, C), where s(P<sub>i</sub>, P<sub>i + 1</sub>, P<sub>i + 2</sub>) = ABC.
<br />
<br />Lets assume that we are wrong, and s(P<sub>i + 1</sub>, P<sub>i + 2</sub>, P<sub>i + 3</sub>) = A'B'C' > s(p<sub>i</sub>, P<sub>i + 1</sub>, P<sub>i + 2</sub>).
<br />
<br /><span style="font-weight: bold;">Case 1: </span>
<br />B' < B and C' = C <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuBtmaBPpqVsaPe9ymymwc9wlA-ehYr9x3s_kbw71Vl4pZJlZ7dcXiWEPKaMLkJP9gYwy9RudihEPlNF9sQYQC7RHIz8acOsd0ILvx4aUpFZFFP6WtyikgptVKF9fZS-zp2LRfIO0dug8/s1600/part-3poly-1.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuBtmaBPpqVsaPe9ymymwc9wlA-ehYr9x3s_kbw71Vl4pZJlZ7dcXiWEPKaMLkJP9gYwy9RudihEPlNF9sQYQC7RHIz8acOsd0ILvx4aUpFZFFP6WtyikgptVKF9fZS-zp2LRfIO0dug8/s400/part-3poly-1.jpg" alt="" id="BLOGGER_PHOTO_ID_5642999782091897794" border="0" /></a>
<br />
<br />
<br />We know that,
<br />ABC >= AB'C (otherwise largest triangle for A would be AB'C)
<br />=> ABC + BB'A >= AB'C + BB'A
<br />=> AB'BC >= AB'C + BB'A
<br />=> AB'C + BB'C >= AB'C + BB'A
<br />=> BB'C >= BB'A
<br />=> BB'C >= BB'A' (for base BB' area is non decreasing from BB'C to BB'A, so it
<br /> will be non decreasing from BB'A to BB'C)
<br />=> BB'C + A'B'C >= BB'A' + A'B'C
<br />=> A'B'BC >= BB'A' + A'B'C
<br />=> A'BC + BB'A' >= BB'A' + A'B'C
<br />=> A'BC >= A'B'C
<br />=> A'BC >= A'B'C' ...... [1] (as C = C')
<br />
<br />So, for case 1, s(P<sub>i + 1</sub>, P<sub>i + 2</sub>, P<sub>i + 3</sub>) = s(P<sub>i + 1</sub>, B, C).
<br />
<br /><b>Case 2:</b>
<br />Let's say, A'B'C' is the largest triangle for first point A'.
<br />Where, B' < B and C' > C. See the following image.
<br />
<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGbnFxhnacLDydivXcKO2alB3L4W7-7rpAjkQUFwxG2_dQksySWWxDyrd5wa6vWyW8K29iRf_6tLCmM0MMgdJ4Rp-AL_8bwgHagGzNfW_3ZJxyC08Wh1mJ6iJCyoyJNl0PZiAZX8c8UM4/s1600/part-3poly-2.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGbnFxhnacLDydivXcKO2alB3L4W7-7rpAjkQUFwxG2_dQksySWWxDyrd5wa6vWyW8K29iRf_6tLCmM0MMgdJ4Rp-AL_8bwgHagGzNfW_3ZJxyC08Wh1mJ6iJCyoyJNl0PZiAZX8c8UM4/s400/part-3poly-2.jpg" alt="" id="BLOGGER_PHOTO_ID_5643072455125329250" border="0" /></a>
<br />
<br />For first point A, ABC is the largest trianlge,
<br />So, ABC >= AB'C
<br />=> ABC + BB'C >= ABC + BB'C
<br />=> ABC + BB'C >= AB'BC
<br />=> ABC + BB'C >= ABC + BB'A
<br />=> BB'C >= BB'A
<br />i.e. BB'A <= BB'C Hence, BB'A <= BB'C' (otherwise, BB'A > BB'C and BB'A <= BB'C, which is not possible for a convex polygon) So, BB'A' <= BB'C' ... [2] (as the triangle area non increasing by moving C' to A, it will be non increasing from A to A') Now as we are considering, for first point A', the largest area triangle is A'B'C'. So, A'B'C' > A'BC'
<br />=> A'B'C' + BB'A' > A'BC' + BB'A
<br />=> A'B'C' + BB'A' > A'B'BC'
<br />=> A'B'C' + BB'A' > A'B'C' + BB'C'
<br />=> BB'A' > BB'C', this contradicts to [2].
<br />
<br />So it is not possible to have, A'B'C' > A'BC' i.e. for case 2, s(P<sub>i + 1</sub>, P<sub>i + 2</sub>, P<sub>i + 3</sub>) = s(P<sub>i + 1</sub>, B, C).
<br />
<br /><b>Case 3:</b>
<br />Let's say, A'B'C' is the largest triangle for fixed first point A', where,
<br />B' < B and C' < C <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh-4p-yn8tsS2FXPUffSrsuQ1WMLF7vn5IavjCWujvKp6fYQ_AJgj8TXrd8-lxx4ABCi4jhS4mIckYpYPKd-fYFwdPwu15Pd3by3arrED1a1rIK3PIc_O6f67pDOp6M3K6oTQM7lOQs3E8/s1600/part-3poly-3%25282%2529.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh-4p-yn8tsS2FXPUffSrsuQ1WMLF7vn5IavjCWujvKp6fYQ_AJgj8TXrd8-lxx4ABCi4jhS4mIckYpYPKd-fYFwdPwu15Pd3by3arrED1a1rIK3PIc_O6f67pDOp6M3K6oTQM7lOQs3E8/s400/part-3poly-3%25282%2529.jpg" alt="" id="BLOGGER_PHOTO_ID_5644294449907560306" border="0" /></a>
<br />
<br />As ABC is the largest triangle having first point A,
<br />either ABC' >= AB'C' (by moving B' to B, area increases) .. (3A)
<br />or AB'C >= AB'C' (by moving C' to C, area increases) .. (3B)
<br />
<br /><b>Case 3A</b>
<br />ABC' >= AB'C'
<br />=> ABC' + BB'A >= AB'C' + BB'A
<br />=> AB'BC' >= AB'C' + BB'A
<br />=> AB'C' + BB'C' >= AB'C' + BB'A
<br />=> BB'C' >= BB'A
<br />=> BB'C' >= BB'A' (As by moving C' to A area non increasing, moving A to A' will area be non increasing)
<br />=> BB'C + A'B'C' >= BB'A' + A'B'C'
<br />=> BB'A'C' >= BB'A' + A'B'C'
<br />=> BB'A' + A'BC' >= BB'A' + A'B'C'
<br />=> A'BC >= A'B'C'
<br />
<br />So it is not possible to have, A'B'C' > A'BC' i.e. for case 3A, s(P<sub>i + 1</sub>, P<sub>i + 2</sub>, P<sub>i + 3</sub>) = s(P<sub>i + 1</sub>, B, C).
<br />
<br /><b>Case 3B</b>
<br />AB'C >= AB'C'
<br />=> AB'C + CC'B' >= AB'C' + CC'B'
<br />=> AB'C'C >= AB'C' + CC'B'
<br />=> AB'C' + CC'A >= AB'C' + CC'B'
<br />=> CC'A >= CC'B'
<br />=> CC'A' >= CC'B' (As moving A to B', area decreases, it's not possible moving A' to B' area increases)
<br />=> CC'A' + A'B'C' >= CC'B' + A'B'C'
<br />=> A'B'C'C >= CC'B' + A'B'C'
<br />=> CC'B' + A'B'C >= CC'B' + A'B'C'
<br />=> A'B'C >= A'B'C'
<br />
<br />So it is not possible to have, A'B'C' > A'B'C i.e. for case 3B, s(P<sub>i + 1</sub>, P<sub>i + 2</sub>, P<sub>i + 3</sub>) = s(P<sub>i + 1</sub>, B, C).
<br />
<br /><b>Case 4:</b>
<br />C' < C and B' = B <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9RXjZbr0v5zL-HlNUEykeistudju0WIS2NVrduEmzN1vCwaLNo1ie_OJF8MSUjDsHVzjm0Qgn3JFS0t0KIOaOVvmTtUCyb5vOrr1kfUsuhLLznSsBiY8T5i4C7N18G4SxWDnQIr96Qg8/s1600/part-3poly4.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9RXjZbr0v5zL-HlNUEykeistudju0WIS2NVrduEmzN1vCwaLNo1ie_OJF8MSUjDsHVzjm0Qgn3JFS0t0KIOaOVvmTtUCyb5vOrr1kfUsuhLLznSsBiY8T5i4C7N18G4SxWDnQIr96Qg8/s400/part-3poly4.jpg" alt="" id="BLOGGER_PHOTO_ID_5644305629230543362" border="0" /></a>
<br />
<br />Here,
<br />ABC >= ABC'
<br />=> ABC + CC'A >= ABC' + CC'A
<br />=> ABC + CC'A >= ABC'C
<br />=> ABC + CC'A >= ABC + CC'B
<br />=> CC'A >= CC'B
<br />=> CC'A' >= CC'B
<br />=> CC'A' + A'BC' >= CC'B + A'BC'
<br />=> A'BC'C >= CC'B + A'BC'
<br />=> A'BC + CC'B >= CC'B + A'BC'
<br />=> A'BC >= A'BC'
<br />=> A'BC >= A'B'C' (as B' = B)
<br />
<br />So it is not possible to have, A'B'C' > A'BC i.e. for case 3B, s(P<sub>i + 1</sub>, P<sub>i + 2</sub>, P<sub>i + 3</sub>) = s(P<sub>i + 1</sub>, B, C).
<br />
<br /><b>Case 5:</b>
<br />B' > B and C' < C <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHE_m7QY380eUnkmzkazS5XUzOkKxaP5hbX-Q61_KDBKTcF0BTNMw-NYQFPo5ean4n1uBpslEpdgAOJReBSLLO4axTxg1oEGO-kMXjA0sGncxFeScROVIHlV1BY9RF6GenhmmweYcEqYQ/s1600/part-3poly5.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgHE_m7QY380eUnkmzkazS5XUzOkKxaP5hbX-Q61_KDBKTcF0BTNMw-NYQFPo5ean4n1uBpslEpdgAOJReBSLLO4axTxg1oEGO-kMXjA0sGncxFeScROVIHlV1BY9RF6GenhmmweYcEqYQ/s400/part-3poly5.jpg" alt="" id="BLOGGER_PHOTO_ID_5644311495177385762" border="0" /></a>
<br />
<br />
<br />Now,
<br />A'BC >= A'BC' (From case 4)
<br />=> A'BC + CC'B >= A'BC' + CC'B
<br />=> A'BC'C >= A'BC' + CC'B
<br />=> A'BC' + CC'A' >= A'BC' + CC'B
<br />=> CC'A' >= CC'B
<br />=> CC'A' >= CC'B'
<br />=> CC'A' + A'B'C' >= CC'B' + A'B'C'
<br />=> CC'B'A' >= CC'B' + A'B'C'
<br />=> CC'B' + A'B'C >= CC'B' + A'B'C'
<br />=> A'B'C >= A'B'C'
<br />
<br />So it is not possible to have, A'B'C' > A'B'C i.e. for case 5, s(P<sub>i + 1</sub>, P<sub>i + 2</sub>, P<sub>i + 3</sub>) = s(P<sub>i + 1</sub>, B, C).
<br />
<br />So, from all of the 5 possible cases, we found that, s(P<sub>i + 1</sub>, P<sub>i + 2</sub>, P<sub>i + 3</sub>) = s(P<sub>i + 1</sub>, B, C). So our algorithm will still work, if we start our iteration for first point i = i + 1, without changing the position 2nd and 3rd point. We will move first point from 0 to n - 1, and 2nd and 3rd point will also not move more than n times. So our algorithm in worst case is O (3 * n) = O(n)
<br />
<br />My simple implementation in C++.
<br />
<br /><!-------- code ------------->
<br /><pre style='color:#000000;background:#ffffff;'><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>cstdio</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>cstring</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>cmath</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>cstdlib</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>vector</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>string</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>algorithm</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>set</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>map</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>cassert</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>sstream</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>queue</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>stack</span><span style='color:#800000; '>></span></br><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include</span><span style='color:#800000; '><</span><span style='color:#40015a; '>iostream</span><span style='color:#800000; '>></span></br><span style='color:#800000; font-weight:bold; '>using</span> <span style='color:#800000; font-weight:bold; '>namespace</span> <span style='color:#666616; '>std</span><span style='color:#800080; '>;</span></br></br><span style='color:#800000; font-weight:bold; '>struct</span> Point <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>int</span> x<span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>int</span> y<span style='color:#800080; '>;</span></br> Point<span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> _x<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>int</span> _y<span style='color:#808030; '>)</span> <span style='color:#800080; '>:</span> x<span style='color:#808030; '>(</span>_x<span style='color:#808030; '>)</span><span style='color:#808030; '>,</span> y<span style='color:#808030; '>(</span>_y<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><span style='color:#800080; '>}</span></br> Point<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>:</span> x<span style='color:#808030; '>(</span><span style='color:#008c00; '>0</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span> y<span style='color:#808030; '>(</span><span style='color:#008c00; '>0</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><span style='color:#800080; '>}</span></br> <span style='color:#800000; font-weight:bold; '>bool</span> <span style='color:#800000; font-weight:bold; '>operator</span> <span style='color:#808030; '><</span><span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>const</span> Point<span style='color:#808030; '>&</span> p<span style='color:#808030; '>)</span> <span style='color:#800000; font-weight:bold; '>const</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>return</span> x <span style='color:#808030; '><</span> p<span style='color:#808030; '>.</span>x <span style='color:#808030; '>|</span><span style='color:#808030; '>|</span> <span style='color:#808030; '>(</span>x <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> p<span style='color:#808030; '>.</span>x <span style='color:#808030; '>&</span><span style='color:#808030; '>&</span> y <span style='color:#808030; '><</span> p<span style='color:#808030; '>.</span>y<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br><span style='color:#800080; '>}</span><span style='color:#800080; '>;</span></br></br><span style='color:#800000; font-weight:bold; '>bool</span> left_turn<span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>const</span> Point<span style='color:#808030; '>&</span> p1<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>const</span> Point<span style='color:#808030; '>&</span> p2<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>const</span> Point<span style='color:#808030; '>&</span> p3<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#808030; '>(</span>p2<span style='color:#808030; '>.</span>y <span style='color:#808030; '>-</span> p1<span style='color:#808030; '>.</span>y<span style='color:#808030; '>)</span> <span style='color:#808030; '>*</span> <span style='color:#808030; '>(</span>p3<span style='color:#808030; '>.</span>x <span style='color:#808030; '>-</span> p1<span style='color:#808030; '>.</span>x<span style='color:#808030; '>)</span> <span style='color:#808030; '>-</span> <span style='color:#808030; '>(</span>p2<span style='color:#808030; '>.</span>x <span style='color:#808030; '>-</span> p1<span style='color:#808030; '>.</span>x<span style='color:#808030; '>)</span> <span style='color:#808030; '>*</span> <span style='color:#808030; '>(</span>p3<span style='color:#808030; '>.</span>y <span style='color:#808030; '>-</span> p1<span style='color:#808030; '>.</span>y<span style='color:#808030; '>)</span> <span style='color:#808030; '>></span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span></br><span style='color:#800080; '>}</span></br></br><span style='color:#696969; '>// Returns list of points of convex hull in counter clockwise</span></br><span style='color:#696969; '>// The last point and first point will be equal</span></br><span style='color:#603000; '>vector</span><span style='color:#800080; '><</span>Point<span style='color:#800080; '>></span> convex_hull<span style='color:#808030; '>(</span><span style='color:#603000; '>vector</span><span style='color:#800080; '><</span>Point<span style='color:#800080; '>></span> p<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#603000; '>vector</span><span style='color:#800080; '><</span>Point<span style='color:#800080; '>></span> ret<span style='color:#800080; '>;</span></br> <span style='color:#603000; '>sort</span><span style='color:#808030; '>(</span>p<span style='color:#808030; '>.</span>begin<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span> p<span style='color:#808030; '>.</span>end<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#696969; '>// build lower hull</span></br> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span> p<span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>while</span> <span style='color:#808030; '>(</span>ret<span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>></span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>2</span> <span style='color:#808030; '>&</span><span style='color:#808030; '>&</span></br> left_turn<span style='color:#808030; '>(</span>ret<span style='color:#808030; '>[</span>ret<span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>-</span> <span style='color:#008c00; '>2</span><span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> ret<span style='color:#808030; '>[</span>ret<span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>-</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> p<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>)</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> ret<span style='color:#808030; '>.</span>pop_back<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br> ret<span style='color:#808030; '>.</span>push_back<span style='color:#808030; '>(</span>p<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br> <span style='color:#800000; font-weight:bold; '>int</span> lower_hull_size <span style='color:#808030; '>=</span> ret<span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#696969; '>// build upper hull</span></br> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> p<span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>-</span> <span style='color:#008c00; '>2</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '>></span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> <span style='color:#808030; '>-</span><span style='color:#808030; '>-</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>while</span> <span style='color:#808030; '>(</span>ret<span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>-</span> lower_hull_size <span style='color:#808030; '>></span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>1</span> <span style='color:#808030; '>&</span><span style='color:#808030; '>&</span></br> left_turn<span style='color:#808030; '>(</span>ret<span style='color:#808030; '>[</span>ret<span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>-</span> <span style='color:#008c00; '>2</span><span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> ret<span style='color:#808030; '>[</span>ret<span style='color:#808030; '>.</span>size<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>-</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> p<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>)</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> ret<span style='color:#808030; '>.</span>pop_back<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br> ret<span style='color:#808030; '>.</span>push_back<span style='color:#808030; '>(</span>p<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br> <span style='color:#800000; font-weight:bold; '>return</span> ret<span style='color:#800080; '>;</span></br><span style='color:#800080; '>}</span></br></br><span style='color:#800000; font-weight:bold; '>double</span> triangle_area <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>const</span> Point<span style='color:#808030; '>&</span> p1<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>const</span> Point<span style='color:#808030; '>&</span> p2<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>const</span> Point<span style='color:#808030; '>&</span> p3<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>return</span> abs<span style='color:#808030; '>(</span><span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> p1<span style='color:#808030; '>.</span>x <span style='color:#808030; '>*</span> p2<span style='color:#808030; '>.</span>y <span style='color:#808030; '>+</span></br> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> p2<span style='color:#808030; '>.</span>x <span style='color:#808030; '>*</span> p3<span style='color:#808030; '>.</span>y <span style='color:#808030; '>+</span></br> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> p3<span style='color:#808030; '>.</span>x <span style='color:#808030; '>*</span> p1<span style='color:#808030; '>.</span>y <span style='color:#808030; '>-</span></br> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> p1<span style='color:#808030; '>.</span>y <span style='color:#808030; '>*</span> p2<span style='color:#808030; '>.</span>x <span style='color:#808030; '>-</span></br> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> p2<span style='color:#808030; '>.</span>y <span style='color:#808030; '>*</span> p3<span style='color:#808030; '>.</span>x <span style='color:#808030; '>-</span></br> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> p3<span style='color:#808030; '>.</span>y <span style='color:#808030; '>*</span> p1<span style='color:#808030; '>.</span>x<span style='color:#808030; '>)</span> <span style='color:#808030; '>/</span> <span style='color:#008000; '>2.0</span><span style='color:#800080; '>;</span></br><span style='color:#800080; '>}</span></br></br><span style='color:#800000; font-weight:bold; '>int</span> <span style='color:#400000; '>main</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>void</span><span style='color:#808030; '>)</span></br><span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>int</span> n<span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>while</span> <span style='color:#808030; '>(</span>scanf<span style='color:#808030; '>(</span><span style='color:#800000; '>"</span><span style='color:#0f69ff; '>%d</span><span style='color:#800000; '>"</span><span style='color:#808030; '>,</span> <span style='color:#808030; '>&</span>n<span style='color:#808030; '>)</span> <span style='color:#808030; '>&</span><span style='color:#808030; '>&</span> n <span style='color:#808030; '>!</span><span style='color:#808030; '>=</span> <span style='color:#808030; '>-</span><span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#603000; '>vector</span><span style='color:#800080; '><</span>Point<span style='color:#800080; '>></span> p<span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span> i <span style='color:#808030; '><</span> n<span style='color:#800080; '>;</span> <span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>int</span> x<span style='color:#808030; '>,</span> y<span style='color:#800080; '>;</span></br> scanf<span style='color:#808030; '>(</span><span style='color:#800000; '>"</span><span style='color:#0f69ff; '>%d</span><span style='color:#0f69ff; '>%d</span><span style='color:#800000; '>"</span><span style='color:#808030; '>,</span> <span style='color:#808030; '>&</span>x<span style='color:#808030; '>,</span> <span style='color:#808030; '>&</span>y<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> p<span style='color:#808030; '>.</span>push_back<span style='color:#808030; '>(</span>Point<span style='color:#808030; '>(</span>x<span style='color:#808030; '>,</span> y<span style='color:#808030; '>)</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br> p <span style='color:#808030; '>=</span> convex_hull<span style='color:#808030; '>(</span>p<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span> p<span style='color:#808030; '>.</span>pop_back<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>int</span> i <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>int</span> j <span style='color:#808030; '>=</span> i <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>int</span> k <span style='color:#808030; '>=</span> j <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>double</span> res <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>.</span><span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>while</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>true</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>double</span> area <span style='color:#808030; '>=</span> triangle_area<span style='color:#808030; '>(</span>p<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> p<span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> p<span style='color:#808030; '>[</span>k<span style='color:#808030; '>]</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>while</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>true</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>while</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>true</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>int</span> nk <span style='color:#808030; '>=</span> <span style='color:#808030; '>(</span>k <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>%</span> n<span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>double</span> narea <span style='color:#808030; '>=</span> triangle_area<span style='color:#808030; '>(</span>p<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> p<span style='color:#808030; '>[</span>j<span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> p<span style='color:#808030; '>[</span>nk<span style='color:#808030; '>]</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>narea <span style='color:#808030; '>></span><span style='color:#808030; '>=</span> area<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> k <span style='color:#808030; '>=</span> nk<span style='color:#800080; '>;</span></br> area <span style='color:#808030; '>=</span> narea<span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span> <span style='color:#800000; font-weight:bold; '>else</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>break</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br> <span style='color:#800080; '>}</span></br> <span style='color:#800000; font-weight:bold; '>int</span> nj <span style='color:#808030; '>=</span> <span style='color:#808030; '>(</span>j <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>%</span> n<span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>double</span> narea <span style='color:#808030; '>=</span> triangle_area<span style='color:#808030; '>(</span>p<span style='color:#808030; '>[</span>i<span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> p<span style='color:#808030; '>[</span>nj<span style='color:#808030; '>]</span><span style='color:#808030; '>,</span> p<span style='color:#808030; '>[</span>k<span style='color:#808030; '>]</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>narea <span style='color:#808030; '>></span><span style='color:#808030; '>=</span> area<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span></br> j <span style='color:#808030; '>=</span> nj<span style='color:#800080; '>;</span></br> area <span style='color:#808030; '>=</span> narea<span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span> <span style='color:#800000; font-weight:bold; '>else</span> <span style='color:#800080; '>{</span></br> <span style='color:#800000; font-weight:bold; '>break</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br> <span style='color:#800080; '>}</span></br> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>area <span style='color:#808030; '>></span> res<span style='color:#808030; '>)</span> res <span style='color:#808030; '>=</span> area<span style='color:#800080; '>;</span></br> i<span style='color:#808030; '>+</span><span style='color:#808030; '>+</span><span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>i <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> j<span style='color:#808030; '>)</span> j <span style='color:#808030; '>=</span> <span style='color:#808030; '>(</span>j <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>%</span> n<span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>j <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> k<span style='color:#808030; '>)</span> k <span style='color:#808030; '>=</span> <span style='color:#808030; '>(</span>k <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>%</span> n<span style='color:#800080; '>;</span></br> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>i <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> n<span style='color:#808030; '>)</span> <span style='color:#800000; font-weight:bold; '>break</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br> printf<span style='color:#808030; '>(</span><span style='color:#800000; '>"</span><span style='color:#0f69ff; '>%.2lf</span><span style='color:#0f69ff; '>\n</span><span style='color:#800000; '>"</span><span style='color:#808030; '>,</span> res<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span></br> <span style='color:#800080; '>}</span></br> <span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span></br><span style='color:#800080; '>}</span></br></pre></br>
<br />
<br />Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com3tag:blogger.com,1999:blog-7656516316687795220.post-87997779622663689682011-08-18T23:52:00.000-07:002011-08-24T00:45:11.718-07:00Maximum Triangle Area (Part 2)I hope you enjoyed the <a href="http://isolvedaproblem.blogspot.com/2011/08/maximum-triangle-area-part-1.html">part 1</a>. In part - 1. We came up to an algorithm of complexity O(n ^ 2 log n). We'll try to improve it now.
<br />
<br />Our problem is now reduced to: Given a convex polygon having n points. Find three points from these n points which form the largest triangle area.
<br />
<br />Let's consider our points are ordered in counter clockwise and named P<sub>0</sub>, P<sub>1</sub>, ... , P<sub>n - 1</sub>.
<br />
<br />Let's start with A = P<sub>0</sub>, B = P<sub>1</sub>, C = P<sub>2</sub>. Now we will be moving C counter clockwise order (i.e. P<sub>3</sub>, P<sub>4</sub>, ...), as long as the triangle area doesn't decrease. And we know(from part 1), the area will not increase anymore after this point. So let's stop moving C. Let's say, we stopped C at P<sub>k</sub>. So we found the largest triangle, having A = P<sub>0</sub>, and B = P<sub>1</sub>. Now it's time to move B. Let's move B to the adjacent point clockwise, if the area doesn't decreases. Now for new AB we have to find the best position of C, so that area is maximized. We will find that, we don't need to iterate from the next point of B, rather we can proceed with C as where it is now and try to move it counter clockwise as long the area doesn't decrease. Will it work always? Let's consider that it will not work, i.e. There will be a case where for a given AB, we will find maximum triangle ABC, and after moving B to B', we will find maximum triangle AB'C', where C' comes before C (By C' comes before C, I mean if we count points of the polygon starting from A, C' will come before C), and AB'C' > ABC, as the following picture.
<br />
<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXL93oSKtn1vnOCoJo21BBX2q6d97I1u05wjfwaJj6Fx_TxiY3CQo_4sIeaQh34gtiYKuhyphenhyphenQjp8ygPvUmvSxPXEn0mBnF8YSH-qO-eqThrB49TV4zpy7k5uDseymdSyq-_o0vVnjlGBhQ/s1600/Untitleddrawing.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXL93oSKtn1vnOCoJo21BBX2q6d97I1u05wjfwaJj6Fx_TxiY3CQo_4sIeaQh34gtiYKuhyphenhyphenQjp8ygPvUmvSxPXEn0mBnF8YSH-qO-eqThrB49TV4zpy7k5uDseymdSyq-_o0vVnjlGBhQ/s400/Untitleddrawing.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5642467321053513778" /></a>
<br />
<br />
<br />In the image above, we got ABC as the largest triangle for base AB. And after moving B to B', we got the largest triangle AB'C', where C' comes before C.
<br />we know that, ABC >= ABC' ... [1] (As ABC is the largest triangle for base AB)
<br />Now,
<br /> ABC' + ACC' = ABC'C = ABC + BCC'
<br />=> ACC' >= BCC' [2] (as ABC >= ABC' from [1])
<br />
<br />From (2), we can say, ACC' >= B'CC' (We already told for a given base, AB, if we move another point C, it will increase area of ABC up to a certain point and than start decreasing, i.e. it will never increase again after that point. Here for base CC', it started decrease from point A to B, so it will not increase from B to B'. As ACC' >= BCC', so ACC' >= B'CC').
<br />
<br />ACC' >= B'CC'
<br />=> ACC' + AB'C' >= B'CC' + AB'C' (adding AB'C' in both side)
<br />=> AB'C'C >= B'CC' + AB'C'
<br />=> AB'C + B'CC' >= B'CC' + AB'C'
<br />=> AB'C >= AB'C'
<br />
<br />So, for base AB' any point C' before C will not increase the area. So we can safely iterate from current position of C to find a larger area triangle. After finding the best position of C, move B again, if it increases the area. If moving B doesn't increases the area, stop moving B. Question is, is there any chance of getting larger triangle don't stop moving B in this case? Let's consider that there is a chance to get a larger area.
<br />
<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbHObzBWyHPpLw_RhHXPfx8BRg24RjStlJuzbLS6aopqIVk22SQNLJxeKtahkQISZzODNPmNdrdIxWHfb_zca4rJcxlJuoyM87t68UgM19vZkJftzqRiCdWPA20NvjX_xfwuZrJUKTFKA/s1600/polygon-4%25281%2529.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbHObzBWyHPpLw_RhHXPfx8BRg24RjStlJuzbLS6aopqIVk22SQNLJxeKtahkQISZzODNPmNdrdIxWHfb_zca4rJcxlJuoyM87t68UgM19vZkJftzqRiCdWPA20NvjX_xfwuZrJUKTFKA/s400/polygon-4%25281%2529.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5642480103770054738" /></a>
<br />
<br />For example, in the above picture, for base AB we found ABC as the largest triangle, but after moving B to B' we found AB'C < ABC. Now for base AC, we already know that there area will not increase any more by moving B. And we also proved that area will not increase moving C in clockwise. So only way left is moving C counter clockwise. Let's say we found a solution AB'C', where C' comes after C. As this is a better solution, AB'C' > AB'C
<br />
<br />Now, ABC > ABC' (If ABC' >= ABC, we would have already moved C to C' for base AB).
<br />=> ABC + CC'A > ABC' + CC'A
<br />=> ABCC' > ABC' + CC'A
<br />=> ABC' + CC'B > ABC' + CC'A
<br />=> CC'B > CC'A [3]
<br />
<br />And, AB'C' > AB'C
<br />=> AB'C' + CC'B' > AB'C + CC'B
<br />=> AB'CC' > AB'C + CC'B
<br />=> AB'C + CC'A > AB'C + CC'B
<br />=> CC'A > CC'B [4]
<br />
<br />[3] and [4] are contradictory. So if after moving B to B', the area decreases, it will not possible to get larger area for the same A. So we have to stop moving B, and this ABC is the largest triangle for a given A. As B can move up to n times and also C can move up to n times. So for a given A, our algorithm complexity is O(2n) ~ O(n). We have to do this for each possible position of A. So our algorithm becomes O(n ^ 2).
<br />
<br />Hopefully you enjoyed it so far. We'll try to improve more in part 3.
<br />
<br />
<br />
<br />Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com7tag:blogger.com,1999:blog-7656516316687795220.post-81857346117860491742011-08-17T21:20:00.000-07:002011-08-19T18:19:30.873-07:00Maximum Triangle Area (Part 1)Today I'll discuss about another interesting problem. Though the analysis is big, hopefully you'll find it interesting.
<br />
<br />Problem name: <a href="http://www.spoj.pl/problems/MTRIAREA/">Maximum Triangle Area</a>
<br />Problem description:
<br />Given n distinct points on a plane, your task is to find the triangle that have the maximum area, whose vertices are from the given points.
<br />
<br />The most obvious solution is trying all possible triangle and find out the maximum area. The complexity of that algorithm is O(n^3). Which is huge as n can be as large as 50000.
<br />
<br />So what can we do now? An interesting fact is, we can solve this problem by only considering the points of the <a href="http://en.wikipedia.org/wiki/Convex_hull">convex hull</a> for the given set of points. This will work because, if there is a triangle which has a vertex A which is not in the boundary of the convex hull, there will be always a point X in convex hull such that, by moving A to X we can increase the area of the triangle. Let's see an example - <a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjREKX4DsS313884lgnUUEHu-jjeaTEz4kZPjcCJ9xGiarKwludomxmybk0qJ1onVI_gr4LdQO69q_QPRPLZWcVrtxqIpC3d_6o2R9kJE40nmnELhjfjLW2Kyd_fewC27DpKgWhfgAr3n8/s1600/Polygon.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjREKX4DsS313884lgnUUEHu-jjeaTEz4kZPjcCJ9xGiarKwludomxmybk0qJ1onVI_gr4LdQO69q_QPRPLZWcVrtxqIpC3d_6o2R9kJE40nmnELhjfjLW2Kyd_fewC27DpKgWhfgAr3n8/s400/Polygon.jpg" alt="" id="BLOGGER_PHOTO_ID_5642058870327649058" border="0" /></a>
<br />
<br />We have a set of points {A, B, C, D, E, F, G, H, I}. The convex hull of these points consists of {D, E, F, G, H, I}. But let's claim that the largest triangle using these points is ABC. None of it's vertex is in convex hull. Let's say, BC is the base of this triangle and AP (perpendicular distance from A to BC) is the height of the triangle. So, the <a href="http://en.wikipedia.org/wiki/Triangle#Computing_the_area_of_a_triangle">area of the triangle</a> is 0.5 * BC * AP. Now draw a line parallel to the BC which goes through A. As A is inside the convex hull, you will find at least one vertex from the convex hull which is on the other side of the parallel line. Here in our example, we found D and BC are in the opposite side of the parallel line, so perpendicular distance from D to BC (DQ) is greater than AP. Hence, 0.5 * BC * AB < 0.5 * BC * DQ. So, triangle area DBC > triangle area ABC. See the following picture to make it clear -
<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiaHSxVfVMF6qaEg0mk21lBcixmiRDjrCisZsGPm2rXYhSG8IMjQyklFYjRTcUcckxsGpiiZj9a2OE7-4u_R2gSG_SClXMt7hWW07R9eSVYjbERmbCWA8E4W60Uy1eDgQ-SCMdrMJ6oDvk/s1600/Polygon%25281%2529.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiaHSxVfVMF6qaEg0mk21lBcixmiRDjrCisZsGPm2rXYhSG8IMjQyklFYjRTcUcckxsGpiiZj9a2OE7-4u_R2gSG_SClXMt7hWW07R9eSVYjbERmbCWA8E4W60Uy1eDgQ-SCMdrMJ6oDvk/s400/Polygon%25281%2529.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5642066235557306082" /></a>
<br />
<br />Now, we got a triangle DBC which has larger area than ABC, but yet we have two vertices in it which are not in the convex hull. Now in the similar way considering DB as a base, and drawing a parallel line of DB which goes through C, we will find that area of DBF is greater than area of DBC. In the next step we can easily show again, that area of DBH is greater than the area of DBF. So we found that, maximum area triangle can be found using only convex hull vertices.
<br />
<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdazeWvLjVwcx5w6JqdTSD8-uGxX6lyZZi8EJTTY4glb5gP_6VG8xrPG5f4YWmJnZvnhc2Ey-xsnG-r4n2HdJS-AbyLEzIc02NhENmm3c7jwOzrFCrVYaRATKvrd75bJik0pw7D_j6D1U/s1600/Polygon%25282%2529.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 300px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdazeWvLjVwcx5w6JqdTSD8-uGxX6lyZZi8EJTTY4glb5gP_6VG8xrPG5f4YWmJnZvnhc2Ey-xsnG-r4n2HdJS-AbyLEzIc02NhENmm3c7jwOzrFCrVYaRATKvrd75bJik0pw7D_j6D1U/s400/Polygon%25282%2529.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5642069785577002514" /></a>
<br />
<br />But if all of the given points is in the convex hull, our algorithm is still O(n ^ 3). Using the convex hull property we can improve it. Now our problem is finding the largest triangle using the vertices of a convex polygon. Let's say we have n vertices 0 to n - 1. We will try to find out three vertices A, B, C in clockwise direction from these vertices which will form the maximum triangle.
<br />
<br />Now for a given AB, rather than iterating all of the points between B and A, to find the C, we can use <a href="http://en.wikipedia.org/wiki/Ternary_search">ternary search</a> to find C, as if we consider AB as a base, and iterate from the next point of B one by one, the height (of the triangle ABC) will increase in every step up to a certain vertex, and after that height will decrease in every step. This way, we can ternary search the point C for every possible AB, and the complexity will become (n ^ 2 log n), which is still not enough.
<br />
<br />As, the analysis becoming large and large, we'll discuss the other improvements in the next part.
<br />
<br />(Special thanks to Anna Fariha for helping me understanding some proofs of this analysis.)
<br />
<br />Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com5tag:blogger.com,1999:blog-7656516316687795220.post-56464796077989218112011-08-07T21:18:00.000-07:002011-08-07T21:36:17.539-07:00Perfect MemoryProblem name: Perfect Memory<br />Problem source: Topcoder, SRM 513, Div 1 - 500<br />Link: <a href="http://www.topcoder.com/stat?c=problem_statement&pm=11500">http://www.topcoder.com/stat?c=problem_statement&pm=11500</a> (Log in is required to see the problem)<br /><br />In this problem you have a board having N * M cells. Each cell has a symbol in it's back. Each symbol is in exactly two cells in the board. So there will be (N * M) / 2 symbols. In each move you can turn two cells one by one to see the symbols behind them. If these two symbols differ, both the cell turned back to hide the symbols again. If both the symbols are same, they will remain same and never turn back again. What is the expected number of moves to make all the symbols visible, if you have the perfect memory?<br /><br />Note that, having perfect memory, you'll never forget what was the symbol in a cell which you saw, but turned back. In this problem it's guaranteed that N * M will be even.<br /><br />I couldn't solve this problem in real contest. I thought in each turn both of the cells will be turned simultaneously. But in the problem statement it was clearly mentioned that, two cells will be turned <span style="font-style:italic;">one by one</span>. It seems that <a href="http://apps.topcoder.com/forums/?module=Thread&threadID=715748&start=0">I am not the only one who got this wrong</a>.<br /><br />This problem can be solved by dynamic programming. Our state will be (total, seen, turn). Here,<br />total = number of symbols for which both cells are not seen yet i.e. at least one cell is unseen. So we are actually considering (2 * total) cells.<br />seen = number of symbols partially seen i.e. number of cells of which exactly one cell is seen.<br />turn = Is this the first turn or second turn of the move? We know each move consists of two turns.<br /><br />Initially, total = (N * M) / 2, seen = 0, and turn = FIRST.<br /><br />Boundary condition: If total = 0, we don't have any symbol left to consider, so expected number will be zero.<br /><br />In state (total, seen, turn), we have (total * 2 - seen) cells we didn't see yet. Lets say unseen = total * 2 - seen.<br /><br />Now if the turn = FIRST, here we will always open an unseen cell and two things can happen after turning a cell on. <br />1. With p1 probability the cell contains a symbol which is already seen in another cell.<br />2. With p2 probability the cell contains a new symbol which is not visible before.<br /><br />Here,<br />p1 = seen / unseen<br />p2 = 1.0 - p1<br /><br />If (1) happens, we will just turn on the other symbol we already saw, and both will remain open forever. So our new state will be (total - 1, seen - 1, FIRST) and one move will be completed.<br />If (2) happens, new state will be (total, seen + 1, SECOND)<br /><br />exp_move(total, seen, FIRST) = p1 * (1 + exp_move(total - 1, seen - 1, FIRST)) +<br /> p2 * (exp_move(total, seen + 1, SECOND)<br /><br />Note that, in first option we completed a move, so added +1, but in second option move is not done yet.<br /><br />If turn = SECOND, we'll open another unseen cell. Three things can happen<br />1. With probability p1, symbol in the SECOND turn matches with the symbol of the FIRST turn.<br />Here p1 = 1 / unseen<br />2. With probability p2, symbol in the SECOND move matches with a symbol which is previously seen, but not seen in the first turn of this move. So, <br />p2 = seen / unseen - p1 = (seen - 1) / unseen<br />3. With probability p3, symbol in the SECOND move is completely a new symbol.<br />p3 = 1 - p2 - p3<br /><br />If (1) happens, this pair will remain visible, so our state will be (total - 1, seen - 1, FIRST) and one move will be completed.<br />If (2) happens, this pair will be turned back, but we know both cells of the symbol of last turn. So we'll open both symbol in next move, so two moves will be completed in this case and new state will be (total - 1, seen - 1, FIRST).<br />If (3) happens, just another seen added. So state will be (total, seen + 1, FIRST), and one move will be completed.<br /><br />exp_move(total, seen, SECOND) = p1 * ((exp_move(total - 1, seen - 1, FIRST) + 1) +<br /> p2 * ((exp_move(total - 1, seen - 1, FIRST) + 2) +<br /> p3 * ((exp_move(total, seen + 1, FIRST) + 1)<br /><br />My solution in C++:<br /><br /><pre style='color:#000000;background:#ffffff;'><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>cstdio</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>cmath</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>cstdlib</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>cctype</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>algorithm</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>map</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>string</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>vector</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>iostream</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>sstream</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>queue</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>cstring</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>set</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>ctime</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>cfloat</span><span style='color:#800000; '>></span><br /><span style='color:#800000; font-weight:bold; '>using</span> <span style='color:#800000; font-weight:bold; '>namespace</span> <span style='color:#666616; '>std</span><span style='color:#800080; '>;</span><br /><br /><span style='color:#800000; font-weight:bold; '>typedef</span> <span style='color:#800000; font-weight:bold; '>long</span> <span style='color:#800000; font-weight:bold; '>long</span> i64<span style='color:#800080; '>;</span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>define</span><span style='color:#004a43; '> I64 </span><span style='color:#800000; '>"</span><span style='color:#0000e6; '>%lld</span><span style='color:#800000; '>"</span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>define</span><span style='color:#004a43; '> rep</span><span style='color:#808030; '>(</span><span style='color:#004a43; '>i</span><span style='color:#808030; '>,</span><span style='color:#004a43; '>n</span><span style='color:#808030; '>)</span><span style='color:#004a43; '> for </span><span style='color:#808030; '>(</span><span style='color:#004a43; '>i</span><span style='color:#808030; '>=</span><span style='color:#004a43; '>0</span><span style='color:#808030; '>;</span><span style='color:#004a43; '> i </span><span style='color:#808030; '><</span><span style='color:#004a43; '> </span><span style='color:#808030; '>(</span><span style='color:#004a43; '>n</span><span style='color:#808030; '>)</span><span style='color:#808030; '>;</span><span style='color:#004a43; '> </span><span style='color:#808030; '>+</span><span style='color:#808030; '>+</span><span style='color:#004a43; '>i</span><span style='color:#808030; '>)</span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>define</span><span style='color:#004a43; '> all</span><span style='color:#808030; '>(</span><span style='color:#004a43; '>c</span><span style='color:#808030; '>)</span><span style='color:#004a43; '> </span><span style='color:#808030; '>(</span><span style='color:#004a43; '>c</span><span style='color:#808030; '>)</span><span style='color:#808030; '>.</span><span style='color:#004a43; '>begin</span><span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span><span style='color:#808030; '>(</span><span style='color:#004a43; '>c</span><span style='color:#808030; '>)</span><span style='color:#808030; '>.</span><span style='color:#004a43; '>end</span><span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#004a43; '> </span><br /><br /><span style='color:#800000; font-weight:bold; '>bool</span> done<span style='color:#808030; '>[</span><span style='color:#008c00; '>1500</span><span style='color:#808030; '>]</span><span style='color:#808030; '>[</span><span style='color:#008c00; '>1500</span><span style='color:#808030; '>]</span><span style='color:#808030; '>[</span><span style='color:#008c00; '>2</span><span style='color:#808030; '>]</span><span style='color:#800080; '>;</span><br /><span style='color:#800000; font-weight:bold; '>double</span> memo<span style='color:#808030; '>[</span><span style='color:#008c00; '>1500</span><span style='color:#808030; '>]</span><span style='color:#808030; '>[</span><span style='color:#008c00; '>1500</span><span style='color:#808030; '>]</span><span style='color:#808030; '>[</span><span style='color:#008c00; '>2</span><span style='color:#808030; '>]</span><span style='color:#800080; '>;</span><br /><span style='color:#800000; font-weight:bold; '>enum</span><span style='color:#800080; '>{</span>FIRST <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>,</span> SECOND<span style='color:#800080; '>}</span><span style='color:#800080; '>;</span><br /><span style='color:#800000; font-weight:bold; '>double</span> exp_move<span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> total<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>int</span> seen<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>int</span> turn<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>double</span> <span style='color:#808030; '>&</span>ret <span style='color:#808030; '>=</span> memo<span style='color:#808030; '>[</span>total<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>seen<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>turn<span style='color:#808030; '>]</span><span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>done<span style='color:#808030; '>[</span>total<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>seen<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>turn<span style='color:#808030; '>]</span><span style='color:#808030; '>)</span> <span style='color:#800000; font-weight:bold; '>return</span> ret<span style='color:#800080; '>;</span><br /> done<span style='color:#808030; '>[</span>total<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>seen<span style='color:#808030; '>]</span><span style='color:#808030; '>[</span>turn<span style='color:#808030; '>]</span> <span style='color:#808030; '>=</span> <span style='color:#800000; font-weight:bold; '>true</span><span style='color:#800080; '>;</span><br /><br /> <span style='color:#800000; font-weight:bold; '>int</span> unseen <span style='color:#808030; '>=</span> total <span style='color:#808030; '>*</span> <span style='color:#008c00; '>2</span> <span style='color:#808030; '>-</span> seen<span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>total <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>)</span> <span style='color:#800000; font-weight:bold; '>return</span> ret <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span><br /><br /> ret <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>.</span><span style='color:#800080; '>;</span><br /> <br /> <span style='color:#696969; '>// open one unseen cell randomly</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>turn <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> FIRST<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>double</span> p1 <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>,</span> p2 <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span><br /><br /> <span style='color:#696969; '>// Probability of it's pair is already seen is p1</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>seen <span style='color:#808030; '>></span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> p1 <span style='color:#808030; '>=</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> seen <span style='color:#808030; '>/</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> unseen<span style='color:#800080; '>;</span><br /> ret <span style='color:#808030; '>+</span><span style='color:#808030; '>=</span> p1 <span style='color:#808030; '>*</span> <span style='color:#808030; '>(</span>exp_move<span style='color:#808030; '>(</span>total <span style='color:#808030; '>-</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>,</span> seen <span style='color:#808030; '>-</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>,</span> FIRST<span style='color:#808030; '>)</span> <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /><br /> <span style='color:#696969; '>// Probability of it's pair is not seen yet is p2</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>unseen <span style='color:#808030; '>></span> seen<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> p2 <span style='color:#808030; '>=</span> <span style='color:#008000; '>1.0</span> <span style='color:#808030; '>-</span> p1<span style='color:#800080; '>;</span><br /> ret <span style='color:#808030; '>+</span><span style='color:#808030; '>=</span> p2 <span style='color:#808030; '>*</span> <span style='color:#808030; '>(</span>exp_move<span style='color:#808030; '>(</span>total<span style='color:#808030; '>,</span> seen <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>,</span> SECOND<span style='color:#808030; '>)</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800000; font-weight:bold; '>else</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>double</span> p1 <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>,</span> p2 <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>,</span> p3 <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span><br /><br /> <span style='color:#696969; '>// Probability of it's pair is already open is p1</span><br /> p1 <span style='color:#808030; '>=</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> <span style='color:#008c00; '>1</span> <span style='color:#808030; '>/</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> unseen<span style='color:#800080; '>;</span><br /> ret <span style='color:#808030; '>+</span><span style='color:#808030; '>=</span> p1 <span style='color:#808030; '>*</span> <span style='color:#808030; '>(</span>exp_move<span style='color:#808030; '>(</span>total <span style='color:#808030; '>-</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>,</span> seen <span style='color:#808030; '>-</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>,</span> FIRST<span style='color:#808030; '>)</span> <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /><br /> <span style='color:#696969; '>// Probability of it's pair is seen but not open is p2</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>seen <span style='color:#808030; '>></span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> p2 <span style='color:#808030; '>=</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>(</span>seen <span style='color:#808030; '>-</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span> <span style='color:#808030; '>/</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>double</span><span style='color:#808030; '>)</span> unseen<span style='color:#800080; '>;</span><br /> ret <span style='color:#808030; '>+</span><span style='color:#808030; '>=</span> p2 <span style='color:#808030; '>*</span> <span style='color:#808030; '>(</span>exp_move<span style='color:#808030; '>(</span>total <span style='color:#808030; '>-</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>,</span> seen <span style='color:#808030; '>-</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>,</span> FIRST<span style='color:#808030; '>)</span> <span style='color:#808030; '>+</span> <span style='color:#008c00; '>2</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /><br /> <span style='color:#696969; '>// Probability of it's pair is unseen is p3</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>unseen <span style='color:#808030; '>></span> seen<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> p3 <span style='color:#808030; '>=</span> <span style='color:#008000; '>1.0</span> <span style='color:#808030; '>-</span> p1 <span style='color:#808030; '>-</span> p2<span style='color:#800080; '>;</span><br /> ret <span style='color:#808030; '>+</span><span style='color:#808030; '>=</span> p3 <span style='color:#808030; '>*</span> <span style='color:#808030; '>(</span>exp_move<span style='color:#808030; '>(</span>total<span style='color:#808030; '>,</span> seen <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>,</span> FIRST<span style='color:#808030; '>)</span> <span style='color:#808030; '>+</span> <span style='color:#008c00; '>1</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800080; '>}</span><br /> <span style='color:#800000; font-weight:bold; '>return</span> ret<span style='color:#800080; '>;</span><br /><span style='color:#800080; '>}</span><br /><br /><span style='color:#800000; font-weight:bold; '>class</span> PerfectMemory <span style='color:#800080; '>{</span><br /><span style='color:#e34adc; '>    </span><span style='color:#800000; font-weight:bold; '>public</span><span style='color:#e34adc; '>:</span><br /> <span style='color:#800000; font-weight:bold; '>double</span> getExpectation<span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> N<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>int</span> M<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>return</span> exp_move<span style='color:#808030; '>(</span><span style='color:#808030; '>(</span>N <span style='color:#808030; '>*</span> M<span style='color:#808030; '>)</span> <span style='color:#808030; '>/</span> <span style='color:#008c00; '>2</span><span style='color:#808030; '>,</span> <span style='color:#008c00; '>0</span><span style='color:#808030; '>,</span> FIRST<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /><span style='color:#800080; '>}</span><span style='color:#800080; '>;</span><br /></pre>Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com0tag:blogger.com,1999:blog-7656516316687795220.post-46106804163487980842011-08-06T23:43:00.000-07:002011-08-07T00:09:39.495-07:00Counting trianglesI'm going to discuss the analysis of the problem <a href="http://www.spoj.pl/problems/CT/">Counting triangles</a> here.<br /><br />Problem description is very short:<br /><blockquote>Consider a 2D integer grid with lower left corner at (0, 0) and upper right corner at (X, Y). We are interested in isosceles right triangles which all the 3 corners at the grid node (integer coordinates). Your task is to count the number of those triangles.</blockquote><br />There was another problem with the same name: <a href="http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3295">Counting Triangles</a>, in which you have to count all the triangles within a grid having all the three corners in integer coordinate inside the grid. But in this problem you need not to count all of those triangles. You only need to count those triangles which are Isosceles triangle and Right triangle. Now, a triangle can have different shapes and same shaped triangle can have different rotations in the grid. We have to count them all carefully.<br /><br />For simplicity, lets consider our triangle is OAB, where angle O is right angle, side OA and side OB are equal, so it fulfills both of the conditions above. lets consider the triangle such that, if we rotate OA clockwise in respect of O by 90 degrees then A will be reach to the exactly on the point B. lets consider the coordinate of A, B and O is (x1, y1), (x2, y2) and (x3, y3) respectfully, and also consider O is in the origin, i.e. (0, 0).<br /><br />Now coordinate of A is (x1, y1) if we rotate it in respect of origin, by rotation matrix of 90 degrees we will get that x2 = y1 and y2 = -x1.<br /><br />Here is the equation to calculate the coordinate of B form O and A.<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZZaNN_hYQ3xWHesk0NAJgoega4KsVZooc3cFNqxXH3DioDkXWUBNEg8WHi8wItiaWZiSeIU6oAR1bc26rlPpj9ruTpou4iRgupt2TRuNwpMCm0dIMsTVOkrGMtV5HkIXX8JtLVtZgsDSU/s1600/Capture1.PNG"><img style="float: left; margin: 0pt 10px 10px 0pt; cursor: pointer; width: 320px; height: 76px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZZaNN_hYQ3xWHesk0NAJgoega4KsVZooc3cFNqxXH3DioDkXWUBNEg8WHi8wItiaWZiSeIU6oAR1bc26rlPpj9ruTpou4iRgupt2TRuNwpMCm0dIMsTVOkrGMtV5HkIXX8JtLVtZgsDSU/s320/Capture1.PNG" alt="" id="BLOGGER_PHOTO_ID_5576777135024682322" border="0" /></a><br /><br /><br /><br /><br /><br /><br>You can find the rotation matrix for 90 degrees <a href="http://en.wikipedia.org/wiki/Rotation_matrix#Common_rotations">here</a>.<br /><br />We know that O (here origin) is an integer coordinate. By the above equation we found that if A is integer coordinate, then B will also be integer coordinate.<br /><br />So we will brute force for all the integer coordinate for A and calculate the coordinate of B. By all I mean [-X, X] for x coordinate and [-Y, Y] for y coordinate, for other values of x or y, it will definitely occupy a bounding box which is larger than the given 2D grid. So the complexity of this brute force solution is O(X * Y), which is not too big.<br /><br />In our brute force we will find several triangles OAB, and coordinates of their corner (x3, y3), (x1, y1) and (x2, y2) respectfully. Can you calculate the height and weight of the bounding box of this triangle?<br /><br />Yes, it's very easy. Height is H = max(y1, y2, y3) - min(y1, y2, y3), and width is W = max(x1, x2, x3) - min(y1, y2, y3).<br /><br />Now we can place this bounding box in our grid if H <!--[if gte mso 9]><xml> <w:worddocument> <w:view>Normal</w:View> <w:zoom>0</w:Zoom> <w:trackmoves/> <w:trackformatting/> <w:punctuationkerning/> <w:validateagainstschemas/> <w:saveifxmlinvalid>false</w:SaveIfXMLInvalid> <w:ignoremixedcontent>false</w:IgnoreMixedContent> <w:alwaysshowplaceholdertext>false</w:AlwaysShowPlaceholderText> <w:donotpromoteqf/> <w:lidthemeother>EN-ZA</w:LidThemeOther> <w:lidthemeasian>X-NONE</w:LidThemeAsian> <w:lidthemecomplexscript>X-NONE</w:LidThemeComplexScript> <w:compatibility> <w:breakwrappedtables/> <w:snaptogridincell/> <w:wraptextwithpunct/> <w:useasianbreakrules/> <w:dontgrowautofit/> <w:splitpgbreakandparamark/> <w:dontvertaligncellwithsp/> <w:dontbreakconstrainedforcedtables/> <w:dontvertalignintxbx/> <w:word11kerningpairs/> <w:cachedcolbalance/> </w:Compatibility> <w:browserlevel>MicrosoftInternetExplorer4</w:BrowserLevel> <m:mathpr> <m:mathfont val="Cambria Math"> <m:brkbin val="before"> <m:brkbinsub val="--"> <m:smallfrac val="off"> <m:dispdef/> <m:lmargin val="0"> <m:rmargin val="0"> <m:defjc val="centerGroup"> <m:wrapindent val="1440"> <m:intlim val="subSup"> <m:narylim val="undOvr"> </m:mathPr></w:WordDocument> </xml><![endif]--><!--[if gte mso 9]><xml> <w:latentstyles deflockedstate="false" defunhidewhenused="true" defsemihidden="true" defqformat="false" defpriority="99" latentstylecount="267"> <w:lsdexception locked="false" priority="0" semihidden="false" unhidewhenused="false" qformat="true" name="Normal"> <w:lsdexception locked="false" priority="9" semihidden="false" unhidewhenused="false" qformat="true" name="heading 1"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 2"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 3"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 4"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 5"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 6"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 7"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 8"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 9"> <w:lsdexception locked="false" priority="39" name="toc 1"> <w:lsdexception locked="false" priority="39" name="toc 2"> <w:lsdexception locked="false" priority="39" name="toc 3"> <w:lsdexception locked="false" priority="39" name="toc 4"> <w:lsdexception locked="false" priority="39" name="toc 5"> <w:lsdexception locked="false" priority="39" name="toc 6"> <w:lsdexception locked="false" priority="39" name="toc 7"> <w:lsdexception locked="false" priority="39" name="toc 8"> <w:lsdexception locked="false" priority="39" name="toc 9"> <w:lsdexception locked="false" priority="35" qformat="true" name="caption"> <w:lsdexception locked="false" priority="10" semihidden="false" unhidewhenused="false" qformat="true" name="Title"> <w:lsdexception locked="false" priority="1" name="Default Paragraph Font"> <w:lsdexception locked="false" priority="11" semihidden="false" unhidewhenused="false" qformat="true" name="Subtitle"> <w:lsdexception locked="false" priority="22" semihidden="false" unhidewhenused="false" qformat="true" name="Strong"> <w:lsdexception locked="false" priority="20" semihidden="false" unhidewhenused="false" qformat="true" name="Emphasis"> <w:lsdexception locked="false" priority="59" semihidden="false" unhidewhenused="false" name="Table Grid"> <w:lsdexception locked="false" unhidewhenused="false" name="Placeholder Text"> <w:lsdexception locked="false" priority="1" semihidden="false" unhidewhenused="false" qformat="true" name="No Spacing"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 1"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 1"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 1"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 1"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 1"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 1"> <w:lsdexception locked="false" unhidewhenused="false" name="Revision"> <w:lsdexception locked="false" priority="34" semihidden="false" unhidewhenused="false" qformat="true" name="List Paragraph"> <w:lsdexception locked="false" priority="29" semihidden="false" unhidewhenused="false" qformat="true" name="Quote"> <w:lsdexception locked="false" priority="30" semihidden="false" unhidewhenused="false" qformat="true" name="Intense Quote"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 1"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 1"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 1"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 1"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 1"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 1"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 1"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 1"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 2"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 2"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 2"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 2"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 2"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 2"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 2"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 2"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 2"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 2"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 2"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 2"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 2"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 2"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 3"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 3"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 3"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 3"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 3"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 3"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 3"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 3"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 3"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 3"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 3"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 3"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 3"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 3"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 4"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 4"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 4"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 4"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 4"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 4"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 4"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 4"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 4"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 4"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 4"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 4"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 4"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 4"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 5"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 5"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 5"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 5"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 5"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 5"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 5"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 5"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 5"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 5"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 5"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 5"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 5"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 5"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 6"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 6"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 6"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 6"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 6"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 6"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 6"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 6"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 6"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 6"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 6"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 6"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 6"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 6"> <w:lsdexception locked="false" priority="19" semihidden="false" unhidewhenused="false" qformat="true" name="Subtle Emphasis"> <w:lsdexception locked="false" priority="21" semihidden="false" unhidewhenused="false" qformat="true" name="Intense Emphasis"> <w:lsdexception locked="false" priority="31" semihidden="false" unhidewhenused="false" qformat="true" name="Subtle Reference"> <w:lsdexception locked="false" priority="32" semihidden="false" unhidewhenused="false" qformat="true" name="Intense Reference"> <w:lsdexception locked="false" priority="33" semihidden="false" unhidewhenused="false" qformat="true" name="Book Title"> <w:lsdexception locked="false" priority="37" name="Bibliography"> <w:lsdexception locked="false" priority="39" qformat="true" name="TOC Heading"> </w:LatentStyles> </xml><![endif]--><!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} </style> <![endif]--><span style="">≤</span> Y and W <span style="">≤</span> X, otherwise it will not fit in our grid and in the same way, our triangle will not fit in the grid. If we can place the bounding box in the grid, we can easily put the lower left corner of the bounding box in (0, 0), so the upper right corner will be (W, H). So, here we found one place where we can place our triangle as well. Can we place the same triangle in another way by shifting our bounding box horizontally or vertically? <xml><w:worddocument><w:trackmoves><w:trackformatting><w:punctuationkerning><w:validateagainstschemas><w:donotpromoteqf><w:compatibility><w:breakwrappedtables><w:snaptogridincell><w:wraptextwithpunct><w:useasianbreakrules><w:dontgrowautofit><w:splitpgbreakandparamark><w:dontvertaligncellwithsp><w:dontbreakconstrainedforcedtables><w:dontvertalignintxbx><w:word11kerningpairs><w:browserlevel></w:browserlevel> <m:mathpr> <m:mathfont val="Cambria Math"> <m:brkbin val="before"> <m:brkbinsub val="--"> <m:smallfrac val="off"> <m:dispdef> <m:lmargin val="0"> <m:rmargin val="0"> <m:defjc val="centerGroup"> <m:wrapindent val="1440"> <m:intlim val="subSup"> <m:narylim val="undOvr"> </m:narylim></m:intlim> </m:wrapindent><!--[endif]--><!--[if gte mso 9]><xml> <w:latentstyles deflockedstate="false" defunhidewhenused="true" defsemihidden="true" defqformat="false" defpriority="99" latentstylecount="267"> <w:lsdexception locked="false" priority="0" semihidden="false" unhidewhenused="false" qformat="true" name="Normal"> <w:lsdexception locked="false" priority="9" semihidden="false" unhidewhenused="false" qformat="true" name="heading 1"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 2"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 3"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 4"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 5"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 6"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 7"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 8"> <w:lsdexception locked="false" priority="9" qformat="true" name="heading 9"> <w:lsdexception locked="false" priority="39" name="toc 1"> <w:lsdexception locked="false" priority="39" name="toc 2"> <w:lsdexception locked="false" priority="39" name="toc 3"> <w:lsdexception locked="false" priority="39" name="toc 4"> <w:lsdexception locked="false" priority="39" name="toc 5"> <w:lsdexception locked="false" priority="39" name="toc 6"> <w:lsdexception locked="false" priority="39" name="toc 7"> <w:lsdexception locked="false" priority="39" name="toc 8"> <w:lsdexception locked="false" priority="39" name="toc 9"> <w:lsdexception locked="false" priority="35" qformat="true" name="caption"> <w:lsdexception locked="false" priority="10" semihidden="false" unhidewhenused="false" qformat="true" name="Title"> <w:lsdexception locked="false" priority="1" name="Default Paragraph Font"> <w:lsdexception locked="false" priority="11" semihidden="false" unhidewhenused="false" qformat="true" name="Subtitle"> <w:lsdexception locked="false" priority="22" semihidden="false" unhidewhenused="false" qformat="true" name="Strong"> <w:lsdexception locked="false" priority="20" semihidden="false" unhidewhenused="false" qformat="true" name="Emphasis"> <w:lsdexception locked="false" priority="59" semihidden="false" unhidewhenused="false" name="Table Grid"> <w:lsdexception locked="false" unhidewhenused="false" name="Placeholder Text"> <w:lsdexception locked="false" priority="1" semihidden="false" unhidewhenused="false" qformat="true" name="No Spacing"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 1"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 1"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 1"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 1"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 1"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 1"> <w:lsdexception locked="false" unhidewhenused="false" name="Revision"> <w:lsdexception locked="false" priority="34" semihidden="false" unhidewhenused="false" qformat="true" name="List Paragraph"> <w:lsdexception locked="false" priority="29" semihidden="false" unhidewhenused="false" qformat="true" name="Quote"> <w:lsdexception locked="false" priority="30" semihidden="false" unhidewhenused="false" qformat="true" name="Intense Quote"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 1"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 1"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 1"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 1"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 1"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 1"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 1"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 1"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 2"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 2"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 2"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 2"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 2"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 2"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 2"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 2"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 2"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 2"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 2"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 2"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 2"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 2"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 3"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 3"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 3"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 3"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 3"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 3"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 3"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 3"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 3"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 3"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 3"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 3"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 3"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 3"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 4"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 4"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 4"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 4"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 4"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 4"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 4"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 4"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 4"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 4"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 4"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 4"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 4"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 4"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 5"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 5"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 5"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 5"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 5"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 5"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 5"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 5"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 5"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 5"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 5"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 5"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 5"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 5"> <w:lsdexception locked="false" priority="60" semihidden="false" unhidewhenused="false" name="Light Shading Accent 6"> <w:lsdexception locked="false" priority="61" semihidden="false" unhidewhenused="false" name="Light List Accent 6"> <w:lsdexception locked="false" priority="62" semihidden="false" unhidewhenused="false" name="Light Grid Accent 6"> <w:lsdexception locked="false" priority="63" semihidden="false" unhidewhenused="false" name="Medium Shading 1 Accent 6"> <w:lsdexception locked="false" priority="64" semihidden="false" unhidewhenused="false" name="Medium Shading 2 Accent 6"> <w:lsdexception locked="false" priority="65" semihidden="false" unhidewhenused="false" name="Medium List 1 Accent 6"> <w:lsdexception locked="false" priority="66" semihidden="false" unhidewhenused="false" name="Medium List 2 Accent 6"> <w:lsdexception locked="false" priority="67" semihidden="false" unhidewhenused="false" name="Medium Grid 1 Accent 6"> <w:lsdexception locked="false" priority="68" semihidden="false" unhidewhenused="false" name="Medium Grid 2 Accent 6"> <w:lsdexception locked="false" priority="69" semihidden="false" unhidewhenused="false" name="Medium Grid 3 Accent 6"> <w:lsdexception locked="false" priority="70" semihidden="false" unhidewhenused="false" name="Dark List Accent 6"> <w:lsdexception locked="false" priority="71" semihidden="false" unhidewhenused="false" name="Colorful Shading Accent 6"> <w:lsdexception locked="false" priority="72" semihidden="false" unhidewhenused="false" name="Colorful List Accent 6"> <w:lsdexception locked="false" priority="73" semihidden="false" unhidewhenused="false" name="Colorful Grid Accent 6"> <w:lsdexception locked="false" priority="19" semihidden="false" unhidewhenused="false" qformat="true" name="Subtle Emphasis"> <w:lsdexception locked="false" priority="21" semihidden="false" unhidewhenused="false" qformat="true" name="Intense Emphasis"> <w:lsdexception locked="false" priority="31" semihidden="false" unhidewhenused="false" qformat="true" name="Subtle Reference"> <w:lsdexception locked="false" priority="32" semihidden="false" unhidewhenused="false" qformat="true" name="Intense Reference"> <w:lsdexception locked="false" priority="33" semihidden="false" unhidewhenused="false" qformat="true" name="Book Title"> <w:lsdexception locked="false" priority="37" name="Bibliography"> <w:lsdexception locked="false" priority="39" qformat="true" name="TOC Heading"> </w:LatentStyles> </xml><![endif]--><!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} </style> <![endif]--> Yes we sometimes we can. if X is less than W we can shift it horizontally and find another position to place our triangle, in the same way we can shift it vertically if Y is less than H.<br /><br />In general, for a given bounding box (W, H) we can place it in (X - W + 1) * (Y - H + 1) ways. So this calculation is simply O(1). We will sum up the values for all triangles we calculated by brute-forcing on coordinate A. So our overall complexity of this algorithm is O(X * Y).<br /><br />Here is my function in java to solve this problem -<br /><pre style="background:#ffffff;color:#000000;">long my_solution(int X, int Y)<span style=" ;color:#800080;" >{</span><br /> <span style=" font-weight:bold; color:#800000;" >if</span> <span style=" ;color:#808030;" >(</span>X <span style=" ;color:#808030;" >=</span><span style=" ;color:#808030;" >=</span> <span style=" ;color:#008c00;" >0</span> <span style=" ;color:#808030;" >|</span><span style=" ;color:#808030;" >|</span> Y <span style=" ;color:#808030;" >=</span><span style=" ;color:#808030;" >=</span> <span style=" ;color:#008c00;" >0</span><span style=" ;color:#808030;" >)</span><span style=" ;color:#800080;" >{</span><br /> <span style=" font-weight:bold; color:#800000;" >return</span> <span style=" ;color:#008c00;" >0</span><span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#800080;" >}</span><br /><br /> <span style=" ;color:#bb7977;" >int</span> x3 <span style=" ;color:#808030;" >=</span> <span style=" ;color:#008c00;" >0</span><span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#bb7977;" >int</span> y3 <span style=" ;color:#808030;" >=</span> <span style=" ;color:#008c00;" >0</span><span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#bb7977;" >long</span> count <span style=" ;color:#808030;" >=</span> <span style=" ;color:#008c00;" >0</span><span style=" ;color:#800080;" >;</span><br /> <span style=" font-weight:bold; color:#800000;" >for</span> <span style=" ;color:#808030;" >(</span><span style=" ;color:#bb7977;" >int</span> x1 <span style=" ;color:#808030;" >=</span> <span style=" ;color:#808030;" >-</span>X<span style=" ;color:#800080;" >;</span> x1 <span style=" ;color:#808030;" ><</span><span style=" ;color:#808030;" >=</span> X<span style=" ;color:#800080;" >;</span> x1 <span style=" ;color:#808030;" >+</span><span style=" ;color:#808030;" >+</span><span style=" ;color:#808030;" >)</span> <span style=" ;color:#800080;" >{</span><br /> <span style=" font-weight:bold; color:#800000;" >for</span> <span style=" ;color:#808030;" >(</span><span style=" ;color:#bb7977;" >int</span> y1 <span style=" ;color:#808030;" >=</span> <span style=" ;color:#808030;" >-</span>Y<span style=" ;color:#800080;" >;</span> y1 <span style=" ;color:#808030;" ><</span><span style=" ;color:#808030;" >=</span> Y<span style=" ;color:#800080;" >;</span> y1 <span style=" ;color:#808030;" >+</span><span style=" ;color:#808030;" >+</span><span style=" ;color:#808030;" >)</span> <span style=" ;color:#800080;" >{</span><br /> <span style=" font-weight:bold; color:#800000;" >if</span> <span style=" ;color:#808030;" >(</span>x1 <span style=" ;color:#808030;" >=</span><span style=" ;color:#808030;" >=</span> <span style=" ;color:#008c00;" >0</span> <span style=" ;color:#808030;" >&</span><span style=" ;color:#808030;" >&</span> y1 <span style=" ;color:#808030;" >=</span><span style=" ;color:#808030;" >=</span> <span style=" ;color:#008c00;" >0</span><span style=" ;color:#808030;" >)</span> <span style=" font-weight:bold; color:#800000;" >continue</span><span style=" ;color:#800080;" >;</span><br /> <br /> <span style=" ;color:#bb7977;" >int</span> x2 <span style=" ;color:#808030;" >=</span> y1<span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#bb7977;" >int</span> y2 <span style=" ;color:#808030;" >=</span> <span style=" ;color:#808030;" >-</span>x1<span style=" ;color:#800080;" >;</span><br /> <br /> <span style=" ;color:#bb7977;" >int</span> maxX <span style=" ;color:#808030;" >=</span> <span style=" font-weight:bold; color:#bb7977;" >Math</span><span style=" ;color:#808030;" >.</span>max<span style=" ;color:#808030;" >(</span>x1<span style=" ;color:#808030;" >,</span> <span style=" font-weight:bold; color:#bb7977;" >Math</span><span style=" ;color:#808030;" >.</span>max<span style=" ;color:#808030;" >(</span>x2<span style=" ;color:#808030;" >,</span> x3<span style=" ;color:#808030;" >)</span><span style=" ;color:#808030;" >)</span><span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#bb7977;" >int</span> minX <span style=" ;color:#808030;" >=</span> <span style=" font-weight:bold; color:#bb7977;" >Math</span><span style=" ;color:#808030;" >.</span>min<span style=" ;color:#808030;" >(</span>x1<span style=" ;color:#808030;" >,</span> <span style=" font-weight:bold; color:#bb7977;" >Math</span><span style=" ;color:#808030;" >.</span>min<span style=" ;color:#808030;" >(</span>x2<span style=" ;color:#808030;" >,</span> x3<span style=" ;color:#808030;" >)</span><span style=" ;color:#808030;" >)</span><span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#bb7977;" >int</span> maxY <span style=" ;color:#808030;" >=</span> <span style=" font-weight:bold; color:#bb7977;" >Math</span><span style=" ;color:#808030;" >.</span>max<span style=" ;color:#808030;" >(</span>y1<span style=" ;color:#808030;" >,</span> <span style=" font-weight:bold; color:#bb7977;" >Math</span><span style=" ;color:#808030;" >.</span>max<span style=" ;color:#808030;" >(</span>y2<span style=" ;color:#808030;" >,</span> y3<span style=" ;color:#808030;" >)</span><span style=" ;color:#808030;" >)</span><span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#bb7977;" >int</span> minY <span style=" ;color:#808030;" >=</span> <span style=" font-weight:bold; color:#bb7977;" >Math</span><span style=" ;color:#808030;" >.</span>min<span style=" ;color:#808030;" >(</span>y1<span style=" ;color:#808030;" >,</span> <span style=" font-weight:bold; color:#bb7977;" >Math</span><span style=" ;color:#808030;" >.</span>min<span style=" ;color:#808030;" >(</span>y2<span style=" ;color:#808030;" >,</span> y3<span style=" ;color:#808030;" >)</span><span style=" ;color:#808030;" >)</span><span style=" ;color:#800080;" >;</span><br /> <br /> <span style=" ;color:#bb7977;" >int</span> WIDTH <span style=" ;color:#808030;" >=</span> maxX <span style=" ;color:#808030;" >-</span> minX<span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#bb7977;" >int</span> HEIGHT <span style=" ;color:#808030;" >=</span> maxY <span style=" ;color:#808030;" >-</span> minY<span style=" ;color:#800080;" >;</span><br /> <br /> <span style=" font-weight:bold; color:#800000;" >if</span> <span style=" ;color:#808030;" >(</span>WIDTH <span style=" ;color:#808030;" >></span> X <span style=" ;color:#808030;" >|</span><span style=" ;color:#808030;" >|</span> HEIGHT <span style=" ;color:#808030;" >></span> Y<span style=" ;color:#808030;" >)</span> <span style=" ;color:#800080;" >{</span><br /> <span style=" font-weight:bold; color:#800000;" >continue</span><span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#800080;" >}</span><br /> <br /> count <span style=" ;color:#808030;" >+</span><span style=" ;color:#808030;" >=</span> <span style=" ;color:#808030;" >(</span>X <span style=" ;color:#808030;" >-</span> WIDTH <span style=" ;color:#808030;" >+</span> <span style=" ;color:#008c00;" >1</span><span style=" ;color:#808030;" >)</span> <span style=" ;color:#808030;" >*</span> <span style=" ;color:#808030;" >(</span>Y <span style=" ;color:#808030;" >-</span> HEIGHT <span style=" ;color:#808030;" >+</span> <span style=" ;color:#008c00;" >1</span><span style=" ;color:#808030;" >)</span><span style=" ;color:#800080;" >;</span><br /> <span style=" ;color:#800080;" >}</span><br /> <span style=" ;color:#800080;" >}</span><br /> <span style=" font-weight:bold; color:#800000;" >return</span> count<span style=" ;color:#800080;" >;</span><br /><span style=" ;color:#800080;" >}</span><br /></pre><br /><br /><span style="font-weight: bold;">Warning:</span><br />The result can be big, don't rely on 32 bit integers.<br /><br /></m:defjc></m:rmargin></m:lmargin></m:dispdef></m:smallfrac></m:brkbinsub></m:brkbin></m:mathfont></m:mathpr></w:word11kerningpairs></w:dontvertalignintxbx></w:dontbreakconstrainedforcedtables></w:dontvertaligncellwithsp></w:splitpgbreakandparamark></w:dontgrowautofit></w:useasianbreakrules></w:wraptextwithpunct></w:snaptogridincell></w:breakwrappedtables></w:compatibility></w:donotpromoteqf></w:validateagainstschemas></w:punctuationkerning></w:trackformatting></w:trackmoves></w:worddocument></xml>Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com0tag:blogger.com,1999:blog-7656516316687795220.post-68633108194337130362011-08-06T23:18:00.000-07:002011-08-06T23:32:40.988-07:00Let's shareI like to solve problems. How about I share my approach and thoughts about the problem I've just solved or trying to solve. Yes that's the intention of this blog. I mostly used to solve problems from programming contest sites. Hope you'll like my blog and suggest to improve it.<br /><br />These blogs also inspired me to start my own blog -<br />http://one-problem-a-day.blogspot.com/<br />http://problem-solving-notes.blogspot.com/<br />http://petr-mitrichev.blogspot.com/Arifhttp://www.blogger.com/profile/05427068343601711364noreply@blogger.com1