Questions Tagged With jan14https://discuss.codechef.com/tags/jan14/?type=rssquestions tagged <span class="tag">jan14</span>enSat, 23 Apr 2016 17:56:04 +0530MTRICK-getting WA...https://discuss.codechef.com/questions/47165/mtrick-getting-wa<p>Can anyone please check my solution...I am unable to find mistake...it is giving WA....
<a href="http://www.codechef.com/viewsolution/4316478">http://www.codechef.com/viewsolution/4316478</a></p>neal95Sun, 13 Jul 2014 14:07:59 +0530https://discuss.codechef.com/questions/47165/mtrick-getting-wajan14[FGFS-JAN14]How to keep connection between arrival and departure timings if I have to sort one of them?https://discuss.codechef.com/questions/47121/fgfs-jan14how-to-keep-connection-between-arrival-and-departure-timings-if-i-have-to-sort-one-of-them<p>Can anyone please explain the algorithm in detail....and
provide the code in C...?Here my doubt is ..I am scanning the arriving times,departure times and preferred places in three different arrays....if I had sorted anyone of them,I would have lost the connection between three of them....How can I get rid of this...? <br>
Thanks in advance...!!!</p>neal95Sat, 12 Jul 2014 18:03:51 +0530https://discuss.codechef.com/questions/47121/fgfs-jan14how-to-keep-connection-between-arrival-and-departure-timings-if-i-have-to-sort-one-of-themjan14arrays.sortsortingFGFS test casehttps://discuss.codechef.com/questions/51985/fgfs-test-case<p>Can someone give me corner cases for this problem</p>
<p><a href="http://www.codechef.com/problems/FGFS">http://www.codechef.com/problems/FGFS</a></p>yagyankTue, 30 Sep 2014 00:52:27 +0530https://discuss.codechef.com/questions/51985/fgfs-test-casejan14fgfsHELP..sereja and graph(seagrp)https://discuss.codechef.com/questions/54308/helpsereja-and-graphseagrp<p>basically the code searches for a path in the graph using dfs..that there is no node repeated in the path..
(for ex. 1->2->3->4->5)for 5 nodes..and runs for all 5 nodes..if there is a path with no node repeated than it prints yes else prints no .........i don't know why u am getting wrong answer</p>
<pre><code>#include<stdio.h>
int a[101][101],reach[101],n,visit[101];
void dfs(int v)
{
int i;
reach[v]=1;
for(i=1;i<=n;i++)
if(a[v][i] && !reach[i])
{
visit[v]++;
dfs(i);
}
}
int main()
{
int i,j,count=0,m,t,x,y,count2;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
reach[i]=0;
for(j=1;j<=n;j++)
a[i][j]=0;
visit[i]=0;
}
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
if(x!=y)
{
a[x][y]=1;
a[y][x]=1;
}
}
for(i=1;i<=n;i++)
{
count=0;count2=0;
for(j=1;j<=n;j++)
{
visit[j]=0;
reach[j]=0;
}
dfs(i);
for(j=1;j<=n;j++)
{
if(reach[j])
count++;
if(visit[j]==1)
count2++;
}
if(count==n&&count2==n-1&&m>=n&&n>1)
break;
}
if(i==n+1)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
</code></pre>ankit10000Tue, 28 Oct 2014 18:44:40 +0530https://discuss.codechef.com/questions/54308/helpsereja-and-graphseagrpjan14serejamediummatchingPlease help me understand the ForbiddenSum problem.https://discuss.codechef.com/questions/60765/please-help-me-understand-the-forbiddensum-problem<p>Hi fellas. I am having tough time understanding the solution to <a href="http://www.codechef.com/problems/FRBSUM">this</a> problem. It has a editorial. Although from editorial approach is quite clear, but when I try to read the code of the author, I don't quite understand it. Points I specifically don't understand in the authors solution are following:</p>
<ol>
<li>How is the segment tree being constructed.</li>
<li>What is the purpose of the "Root" array.</li>
<li>And in the "rect" function, why "res" is chosen that way. I mean like upper_bound function of C++.</li>
</ol>
<p>Other quite good/readable solution, I found was of the user <a href="/users/21752/deneo">@deneo</a>, <a href="http://www.codechef.com/viewsolution/3333760">here</a>, he also did the same thing.
Please help me!!!</p>
<p>Thnx</p>paramviMon, 05 Jan 2015 01:14:42 +0530https://discuss.codechef.com/questions/60765/please-help-me-understand-the-forbiddensum-problemsegment-treejan14binary-searchGetting SIGSEGV error in GCDQhttps://discuss.codechef.com/questions/61563/getting-sigsegv-error-in-gcdq<p><a href="http://www.codechef.com/viewsolution/5891418">http://www.codechef.com/viewsolution/5891418</a></p>amantheviperTue, 13 Jan 2015 22:15:45 +0530https://discuss.codechef.com/questions/61563/getting-sigsegv-error-in-gcdqjan14problemgcdqQuestion missing from profile pagehttps://discuss.codechef.com/questions/61586/question-missing-from-profile-page<p>In january i solved 8 questions but showing only 7 on my profile page.....missing problem is XRQRS. how will it come back in the january problem list...please help</p>raja44everWed, 14 Jan 2015 00:19:13 +0530https://discuss.codechef.com/questions/61586/question-missing-from-profile-pagejan14TAPAIR - Editorialhttps://discuss.codechef.com/questions/35361/tapair-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/TAPAIR">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/TAPAIR">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/tuananh93">Tuan Anh Tran Dang</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/gerald">Gerald Agapov</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Hard</p>
<h1>PREREQUISITES:</h1>
<p>DFS order</p>
<h1>PROBLEM:</h1>
<p>Given an undirected <a href="http://en.wikipedia.org/wiki/Simple_graph#Simple_graph">simple graph</a> with <b>N</b> nodes and <b>M</b> edges, find how many pairs of edges are fatal. A pair of edges are fatal if and only if the graph will be disconnected after we removed them.</p>
<h1>EXPLANATION:</h1>
<p>First of all, a trivial case is that, the given graph is disconnected. In such case, the answer should be <b>M * (M - 1) / 2</b>.</p>
<p>Therefore, we only concern the connected graph. Because of the connectivity, we can find a spanning tree first. Then, all edge can be classified into two sets: (1) Tree-Edge, (2) Non-Tree-Edge.</p>
<p>If we remove two Non-Tree-Edges, obviously, the graph will be still connected. If any Tree-Edge is removed, the connectivity depends on whether there are still some Non-Tree-Edges connect the two parts separated by this Tree-Edge in the spanning tree.</p>
<p>Let's have a example as following (same as the sample input). Since the spanning tree can be chosen in any way, we choose the <a href="http://en.wikipedia.org/wiki/Depth-first_search">DFS-Tree</a> starting from node 1 for the convenience (we will state the convenience later).</p>
<p><img alt="alt text" src="http://discuss.codechef.com/upfiles/dfs-tree.png"></p>
<p>In this example, we can see that there are two Non-Tree-Edges (labeled as 1 and 2). And then, for each Tree-Edge, it is labeled by a set of Non-Tree-Edges which are crossing the edge. That is, if we delete that Tree-Edge, the Non-Tree-Edges in that set will connect the two separated parts. For a given Non-Tree-Edge, it will take care of a path on the DFS-Tree. Furthermore, in the DFS-Tree, there are only "children --> ancestor" Non-Tree-Edges (i.e. back edges. This provides some conveniece).</p>
<p>Based on this label system, the forbidden pairs of edges are those edges with same label or some edge with empty set. For the first case, that is they depends on the same set of Non-Tree-Edges, after removing them together, the Non-Tree-Edges are not able to connect the three parts of tree (or the Non-Tree-Edge which is needed to connect the two parts are deleted). For the second case, edges with empty set as labels are all cuts, i.e. removing them will lead to disconnected state.</p>
<p>Therefore, our task is now focused on calculating the label of each edge. For a simple hash idea and the perfect (perfect because <b>x</b> xor <b>x</b> = 0) operation <a href="http://en.wikipedia.org/wiki/XOR">XOR</a>, we can set a random number ranging from 1..2^64 - 1 to each Non-Tree-Edges. And then, represent a set of numbers as their XOR sum. That is, if a set is {1, 3}, the label will be treated as 2 (since 1 xor 3 = 2). Two sets are identical, if and only if their labels are same (high probability correct). </p>
<p>Finally, the only obstacle comes that how to XOR a number <b>x</b> to the edges between node <b>u</b> and <b>v</b> for all Non-Tree-Edges. And we need to query the XOR sum after all operations for all Tree-Edges. Thanks to the DFS-Tree we selected, without loss of generality, we suppose <b>u</b> is an ancestry of <b>v</b>. Denote <b>prefix[u]</b> as the XOR sum added to the path from root 1 to node <b>u</b>. Adding <b>x</b> to the path between <b>u</b> and <b>v</b> is equivalent to</p>
<pre><code>prefix[u] = prefix[u] xor x;
prefix[v] = prefix[v] xor x
</code></pre>
<p>And after all Non-Tree-Edges are added to their corresponding paths on the DfS-Tree, we traverse the DFS-Tree again and can get the label on all Tree-Edges (it depends on the XOR sum of prefix[] in its sub-tree).</p>
<p>In the end, what we need is to count the number of pairs of labels, which are same or at least one zero. This could be done by hash too.</p>
<p>In summary, we have a <b>O(N + M)</b> algorithm to solve this problem with a high probability (due to the randomness to choose the Non-Tree-Edges' labels). Because 2^64 is large enough comparing to the range of <b>N</b> and <b>M</b>, don't worry about the probability. :) You will get AC if you implemented correctly.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/TAPAIR.cpp">here</a>.<br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/TAPAIR.cpp">here</a>. </p>shangjingboMon, 13 Jan 2014 15:13:40 +0530https://discuss.codechef.com/questions/35361/tapair-editorialjan14dfs-orderhardeditorialxorERROR - Editorialhttps://discuss.codechef.com/questions/35340/error-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ERROR">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/ERROR">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/viv001">Vivek Hamirwasia</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/white_king">Mahbub</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>Programming Language.</p>
<h1>PROBLEM:</h1>
<p>Determine whether the given binary string contains the substring (consecutive) "010" or "101".</p>
<h1>EXPLANATION:</h1>
<p>You can use a loop and condition clauses to check directly. Also, you can use some built-in functions to solve this problem too.</p>
<p>For example, C++, we can use</p>
<pre><code>int position = strstr(s, "010") - s;
</code></pre>
<p>to get the first occurrence of "010" and check whether this position is in range. Or, if string is used in C++, then</p>
<pre><code>int position = s.find("010");
</code></pre>
<p>will work for string.</p>
<p>Similarly, Java, Python, etc... a lot of languages have such functions. Post your accepted solution and let's find which one is the shortest! I think it will be interesting :P</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/ERROR.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/ERROR.cpp">here</a>. </p>shangjingboMon, 13 Jan 2014 15:11:26 +0530https://discuss.codechef.com/questions/35340/error-editorialjan14programmingeditorialcakewalkSEAGRP - Editorialhttps://discuss.codechef.com/questions/35358/seagrp-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SEAGRP">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/SEAGRP">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/sereja">Sergey Nagin</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/white_king">Mahbub</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Matching, Gaussian Elimination</p>
<h1>PROBLEM:</h1>
<p>Determine whether there is any perfect matching.</p>
<h1>EXPLANATION:</h1>
<p>The problem setting is exactly same as the perfect <a href="http://en.wikipedia.org/wiki/Matching_(graph_theory)">matching</a>. That is, find a subset of edges, there are no edges have common nodes and all nodes are covered by one edge. Since the graph is general, <a href="http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm">Blossom algorithm</a> which can provide the maximum matching in O(<b>VE</b>) time is enough.</p>
<p>Here, I would like to introduce a simpler way to solve this problem. Of course, it is not some strange greedy algorithms which may passed because we can't design cases for all wrong solutions (contestants are always creative :D). Anyway, let me introduce the simple solution -- <a href="http://en.wikipedia.org/wiki/Tutte_matrix">Tutte matrix</a>. We can randomly choose the <b>X[i][j]</b>. Since we only need to check whether its <a href="http://en.wikipedia.org/wiki/Determinant">determinant</a> is zero, we can module all number during <a href="http://en.wikipedia.org/wiki/Gaussian_Elimination">Gaussian Elimination</a> (used to calculate the determinant) by a big prime, such as 10^9 + 7. Due to the randomness, we can solve this problem with a high probability. This solution is O(<b>V^3 log MOD</b>), where <b>MOD</b> is the big prime number we chosen. O(<b>log MOD</b>) is caused by the calculating the inverse or elimination by subtracting.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/SEAGRP.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/SEAGRP.cpp">here</a>. </p>shangjingboMon, 13 Jan 2014 15:12:31 +0530https://discuss.codechef.com/questions/35358/seagrp-editorialjan14mediummatchingeditorialCNTDSETS - Editorialhttps://discuss.codechef.com/questions/35337/cntdsets-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CNTDSETS">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/CNTDSETS">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/mugurelionut">Mugurel Ionut Andreica</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/white_king">Mahbub</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Hard</p>
<h1>PREREQUISITES:</h1>
<p>Combination, Inclusionâ€“exclusion principle, Euler's theorem</p>
<h1>PROBLEM:</h1>
<p>Find out how many distinct integer point sets are there in <b>N</b> dimension with diameter <b>D</b>. Diameter is defined as the maximum range of the point set among <b>N</b> dimensions. And two point sets are treated as same if and only if they can be coincided after <a href="http://en.wikipedia.org/wiki/Translation_(geometry)">translation</a> (adding some offset).</p>
<h1>EXPLANATION:</h1>
<p>First of all, we need to make our goal clearer. Because of the restriction of <b>D</b>, we can assume all points are in the cube of <b>[0, D]^N</b>. And, to eliminate the duplicated point set, we can force that the zeros in all dimensions should be reached by at least one point in the chosen point set (can be several points to cover different dimensions). Further, to make sure the diameter is exactly <b>D</b>, we need there exists one dimension, whose <b>D</b> is reached by some point.</p>
<p>After writing this clearer goal, you may find it is still complicate. Let's see a simpler version:</p>
<pre><code>Replace the restriction of diameter = D of diameter <= D.
</code></pre>
<p>If we can solve this simpler version, the original problem can be solved too -- using the answer of <= <b>D</b> minus the answer of <= <b>D</b> - 1. Therefore, let's focus on the simpler one:</p>
<pre><code>How many point sets are there, satisfying (1) points are in [0, D]^N; (2) zeros in all dimensions are reached by some point (can be several points to cover different dimensions).
</code></pre>
<p>Intuitively, this problem can be solved by <a href="http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle">Inclusionâ€“exclusion principle</a>. Follow the same notations in wiki, let's define <b>A<sub>i</sub></b> as the event of the zero of <b>i-th</b> dimension has NOT been reached. And then, the number of point sets that zeros from at least <b>k</b> dimensions have NOT been reached equals:</p>
<pre><code>C(N, k) * 2^(D^k * (D + 1)^(N-k))
</code></pre>
<p>We can prepare the <b>C(N, k)</b>, which is the <a href="http://en.wikipedia.org/wiki/Combination">combination number</a>, in O(<b>N</b>^2) time. Via <a href="http://en.wikipedia.org/wiki/Euler_theorem">Euler's Theorem</a>, we can calculate <b>D^k * (D + 1)^(N-k)</b> module <b>phi</b>(10^9 + 7) (equals to 10^9 + 6, denote as <b>PHI</b>).</p>
<p>Therefore, we can calculate the summation of the following term from <b>k = 0</b> to <b>k = N</b> in O(<b>N</b>log<b>PHI</b>) time. The log comes from the fast power module.</p>
<pre><code>(-1)^k * C(N, k) * 2^(D^k * (D+1)^(N-k))
</code></pre>
<p>In summary, we can solve this problem in O(<b>N</b>^2 + <b>T * N log PHI</b>) time, T is the number of test cases. Furthermore, if we calculate the combination number by factorials (Buffer all factorials in an array. The division can be handled in O(<b>log PHI</b>) time since the 10^9+7 is a prime), the time complexity can be controlled within O(<b>T * N log PHI</b>).</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/CNTDSETS.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/CNTDSETS.cpp">here</a>. </p>shangjingboMon, 13 Jan 2014 15:11:13 +0530https://discuss.codechef.com/questions/35337/cntdsets-editorialcombinatoricsjan14inclusn-exclusnhardeditorialMTRICK - Editorialhttps://discuss.codechef.com/questions/35352/mtrick-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/MTRICK">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/MTRICK">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/yellow_agony">Nikhil Garg</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/gerald">Gerald Agapov</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium</p>
<h1>PREREQUISITES:</h1>
<p>Programming Language, Simple Math.</p>
<h1>PROBLEM:</h1>
<p>Perform the "Ancient Algorithm" described in the problem. And output the results in all steps. Remember that all numbers and operations are modulo by <b>C</b>.</p>
<h1>EXPLANATION:</h1>
<p>As same as the title of the problem "Magic Trick", there are some math and programming tricks in this problem. </p>
<p>Denote the array after <b>i</b>-th loop as <b>L<sub>i</sub>[]</b>.</p>
<p>The first trick is a math trick -- we can maintain a slope <b>K<sub>i</sub></b> and a intercept <b>D<sub>i</sub></b>, such that all current numbers in <b>L<sub>i</sub>[]</b> equals to the original numbers <b>K<sub>i</sub> * L[] + D<sub>i</sub></b>. For each operation, we can update the <b>K</b> and <b>D</b> as the following rules:</p>
<pre><code>if operation == 'R' {
K[i + 1] = K[i]
D[i + 1] = D[i]
} else if operation == 'A' {
K[i + 1] = K[i]
D[i + 1] = D[i] + A
} else if operation == 'M' {
K[i + 1] = K[i] * B
D[i + 1] = D[i] * B
}
</code></pre>
<p>The second trick is a programming trick -- at any time, <b>L<sub>i</sub>[]</b> is an interval of <b>L[]</b> (may reversed). Therefore, we can record the <b>begin</b>, <b>end</b>, and <b>direction</b> each time such that the <b>L<sub>i</sub>[i]</b> equals to the <b>L[begin]</b>. That is,</p>
<pre><code>begin = 1
end = N
direction = 1
for i = 1 to N do {
if operation == 'R' {
swap(begin, end)
direction = -direction
}
UPDATE K and D
print L[begin] * K + D
begin = begin + direction
}
</code></pre>
<p>Beside these magic tricks, <b>there is also a common trick of long long exceeding</b>. That is, because <b>C</b> is as large as 10^18, the multiple operation may exceed the type of long long. We can use a fast multiple, similar to fast power, to solve this exceeding problem without big integer in O(<b>logC</b>) time.</p>
<pre><code>long long multiple(long long a, long long b, long long c) // a * b % c
{
if (b == 0) {
return 0
}
long long ret = multiple(a, b >> 1, c)
ret = (ret + ret) % c
if (b & 1) {
ret = (ret + a) % c
}
return ret
}
</code></pre>
<p>For explanation about fast multiplication, please refer to <a href="http://discuss.codechef.com/questions/36576/fast-multiplication-explanation">this</a></p>
<p>In summary, we can solve this problem in O(<b>N log C</b>) for each test case.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/MTRICK.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/MTRICK.cpp">here</a> and <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/MTRICK_1.cpp">here</a></p>shangjingboMon, 13 Jan 2014 15:12:09 +0530https://discuss.codechef.com/questions/35352/mtrick-editorialjan14programmingeasy-mediumeditorialsimple-mathI got run time error.Help me.https://discuss.codechef.com/questions/81115/i-got-run-time-errorhelp-me<p><a href="https://www.codechef.com/viewsolution/9963237">https://www.codechef.com/viewsolution/9963237</a></p>vickycodSat, 23 Apr 2016 17:56:04 +0530https://discuss.codechef.com/questions/81115/i-got-run-time-errorhelp-mejan14METEORAK - Editorialhttps://discuss.codechef.com/questions/35349/meteorak-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/METEORAK">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/METEORAK">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/white_king">Mahbub</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Dynamic Programming</p>
<h1>PROBLEM:</h1>
<p>Given a <b>N * M</b> matrix <b>mat</b> with some obstacles inside, deal with <b>Q</b> queries of finding the maximum empty submatrix in the submatrix <b>mat[L<sub>i</sub>..H<sub>i</sub>, *]</b>.</p>
<h1>EXPLANATION:</h1>
<p>First of all, we need to know how to deal with a single query. It is a classical dynamic programming problem, such as <a href="http://poj.org/problem?id=3494">POJ 3494 Largest Submatrix with All 1's</a>. We can maintain an array <b>up[1..N][1..M]</b>, where <b>up[i][j]</b> stands for the number of consecutive empty entries starting from <b>(i, j)</b> (inclusive). This array can be generated by the formula as following in O(<b>NM</b>) time.</p>
<pre><code>if mat[i][j] is an obstacle:
up[i][j] = 0
else
up[i][j] = up[i - 1][j] + 1
</code></pre>
<p>To find the maximum empty submatrix, we only need to consider the extremal submatrix as shown in the following figure.</p>
<p><img alt="alt text" src="http://discuss.codechef.com/upfiles/extreme.png"></p>
<p>That is, the candidate (extremal) submatrix can't extend itself in any directions. Extend means to enlarge the submatrix by adding an empty row or column to four directions (left, up, right, down).</p>
<p>Suppose the matrix is bound by the vertical line based on <b>(i, j)</b>, its height should be <b>up[i][j]</b> and what we need is to calculate the horizonal boundary <b>(left[i][j], right[i][j])</b>, left and right are both exclusive. Because left and right are similar, we only focus on the left here. By the definition, <b>left[i][j]</b> is the first column <b>k</b> on the left side of <b>j</b>, such that <b>up[i][k]</b> is smaller than <b>up[i][j]</b>. There are two ways to calculate the <b>left[i][*]</b>.</p>
<p>First one, using the similar way to the <a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure">disjoint set</a>:</p>
<pre><code>for i = 1 to N do {
for j = 1 to M do {
left[j] = j - 1;
while (left[j] > 0 && up[i][left[j]] >= up[i][j]) {
left[j] = left[left[j]];
}
}
}
</code></pre>
<p>This algorithm is O(<b>NM alpha(M)</b>), where <b>alpha()</b> is the inverse of the <a href="http://en.wikipedia.org/wiki/Ackermann_function">Ackermann function</a>.</p>
<p>The second one is to use the monotonic stack (<b>up[i][stack[ptr]] > up[i][stack[ptr - 1]]</b> ) to solve this problem in O(<b>NM</b>) time.</p>
<pre><code>for i = 1 to N do {
top = 0;
for j = 1 to M do {
while (top > 0 && up[i][stack[top - 1]] >= up[i][j]) {
top = top - 1;
}
if (top == 0) {
left[i][j] = 0;
} else {
left[i][j] = stack[top - 1];
}
stack[top] = j;
top = top + 1;
}
}
</code></pre>
<p>Till now, with the help <b>up</b>, <b>left</b> and <b>right</b>, we can easily deal with a single query in O(<b>NM</b>) time (take all extremal empty submatrix and find the maximum). It is the time to start to deal with the orignal queries.</p>
<p>It is worth noting that, even for the query with <b>L, H</b> restrictions, we only need to consider the extremal submatrix too. Because if the best submatrix can extend in any direction (extend means adding an empty row or column to four directions to enlarge the "best submatrix"), the new area will not be worse after we extended that submatrix even if the extended parts are not in the query boundary.</p>
<p>Let's define some auxiliary variables. Let <b>c[l][r]</b> is the maximal width of empty rectangle between <b>l</b>-th and <b>r</b>-th rows such that height is <b>r - l + 1</b>. </p>
<p>Initially, <b>c[][] = 0</b>. And then, for each non-obstacle entry <b>(i, j)</b>, we update the extremal submatrix to their exact boundaries, as following:</p>
<pre><code>c[i - up[i][j] + 1][i] = max{ c[i - up[i][j] + 1][i], right[i][j] - left[i][j] - 1 }
</code></pre>
<p>Finally, we extend the exact boundaries to their inner ones.</p>
<pre><code>c[l][r] = max(c[l][r], c[x][y]), (1 <= x <= l <= r <= y <= N)
</code></pre>
<p>we can update <b>c[][]</b> in O(<b>N^2</b>), as following:</p>
<pre><code>for len = N downto 2 do {
for l = 1 to N - len + 1 do {
r = l + len - 1;
c[l + 1][r] = max{c[l + 1][r], c[l][r]};
c[l][r - 1] = max{c[l][r - 1], c[l][r]};
}
}
</code></pre>
<p>Similarly, we define <b>d[l][r]</b> as answer for corresponding query. The answer is <b>max{c[i][j] * (j - i + 1), d[i][j - 1], d[i + 1][j]}</b> (the bounary case is <b>d[i][i-1] = 0</b>). So, we should fill in the <b>d[][]</b> in order of increasing the length of interval <b>j - i + 1</b>, in similar way to that we get <b>c[][]</b>.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/METEORAK.cpp">here</a>. <br>
Tester's solution will be uploaded soon. <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/METEORAK.cpp">here</a> and <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/METEORAK_1.cpp">here</a>.</p>shangjingboMon, 13 Jan 2014 15:12:00 +0530https://discuss.codechef.com/questions/35349/meteorak-editorialdynamic-programmingjan14mediumeditorialTOURBUS - Editorialhttps://discuss.codechef.com/questions/35364/tourbus-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/TOURBUS">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/TOURBUS">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/pieguy">David Stolp</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/gerald">Gerald Agapov</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Challenge</p>
<h1>PREREQUISITES:</h1>
<p>Greedy, Dynamic Programming, Search, Random</p>
<h1>PROBLEM:</h1>
<p>Given a undirected graph with <b>N</b> nodes and <b>M</b> edges, while each node is associated with a 2D coordinate, find minimum number of simple paths or cycles, which are not self-intersected and covered each edge exactly once.</p>
<h1>EXPLANATION:</h1>
<p>This is a challenge problem. The most important thing in solving challenge problem is to find some approximation/partial methods using the combination of search, greedy, dynamic programming, etc..., because this challenge problem is NP-hard. Also, it is important to write a local test system to help you find the best strategy (almost all top ranked guys wrote their own test codes).</p>
<p>To solve this problem, first of all, we need to know why there is a restriction of the length of answer -- should be smaller than or equal to <b>(N+M)/2</b>. That is because we can connect two edges share a common vertex as a path, which is definitely not self-intersected. Therefore, we can achieve the restriction of output.</p>
<p>And then, considering the special cases with smaller size. For example, if <b>M</b> is smaller than 15, we can use dynamic programming to get the perfect answer. First of all, generate all valid paths and cycles. They are distinguished by its set of edges (represented in a binary mask, 0..2^<b>M</b>). And then, for a given subset <b>S</b> of edges, we enumerate all its subset check whether it is a possible path/cycle and update the optimal answer accordingly. More specifically, denote the minimum valid paths/cycles needed to exactly cover the edge set <b>S</b> as <b>f[S]</b>. The DP procedure is O(3^<b>M</b>) after we obtain all valid paths/cycles as following:</p>
<pre><code>f[0] = 0; // it is an empty set
for S = 1 to 2^M - 1 {
f[S] = infinite
for (sub = S; sub > 0; sub = S & (sub - 1)) {
if (sub is a valid path/cycle) {
f[S] = min{ f[sub] + 1, f[S] }
}
}
}
</code></pre>
<p>The trick is to enumerate the <b>sub</b> via binary operations instead of 0..2^<b>M</b>.</p>
<p>For the general cases, i.e. large <b>N</b> and <b>M</b>, we can find some greed ways. For example, intuitively, we may need to find out the longest valid path/cycle, remove them, and go on. Most of the top solutions during contest apply this idea or similar ideas. But, even finding the longest valid path/cycle is NP-hard in undirected graph. Here, we introduce two ways to find the longest path. The framework is as following:</p>
<pre><code>while there is any edge remained in the graph {
longest = the longest valid path/cycle in the graph
remove longest from the graph
}
</code></pre>
<p>For both methods, we need to find some heuristic functions to rank the next edge to add to the current path. The most intuitive function is based on the intersections of other edges. It reflects how an edge conflicts with others, which means those edges will be invalid after we select this edge. Therefore, we can rank the edges in order. For the ties of edges, we can break them randomly.</p>
<p>The first method is Search. It takes a starting edge, and use dfs to expand the path as long as possible. The second method is Greedy, choose the best edges in each step. For Search, we also need to add constrains to the number of expanded solutions or the time it costs. Search may give better solution while Greedy is much faster. This is a trade-off.</p>
<p>In the end, I would like to give you 3 more tips:</p>
<ol>
<li>Due to the randomness of the order of edges, it will be better to run the algorithm multiple times to get a better score. </li>
<li>Use different heuristic functions for different type of data or for different runs of the algorithm, may also benefit to your score.</li>
<li>Implement your codes as fast as possible, such that it could be run more times in the time limit.</li>
</ol>
<p>Any more awesome ideas are welcome to share in the replies. :)</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/TOURBUS.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/TOURBUS.cpp">here</a>. </p>shangjingboMon, 13 Jan 2014 15:15:02 +0530https://discuss.codechef.com/questions/35364/tourbus-editorialheuristicsearchdynamic-programmingjan14challengegreedyeditorialFRBSUM - Editorialhttps://discuss.codechef.com/questions/35346/frbsum-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/FRBSUM">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/FRBSUM">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/kostya_by">Constantine Sokol</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/white_king">Mahbub</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Segment Tree, Binary Search, Persistent Segment Tree.</p>
<h1>PROBLEM:</h1>
<p>Given <b>A[1..N]</b>, and <b>M</b> queries about what is the smallest number that can't be represented by the sum of some subset of <b>A[L<sub>i</sub> ... R<sub>i</sub>]</b> (so called forbidden sum).</p>
<h1>EXPLANATION:</h1>
<p>First of all, we need to know how to process a single query. That is, given a set of number, determine the forbidden sum. Consider a special case, the answer should be 1 if we have no ones. Based on this observation, we can firstly sort the number ascending. Take the numbers one by one while maintain a sum <b>S</b> (initially <b>S = 0</b>). The algorithm is as following:</p>
<pre><code>S = 0
while (there is the next number x) {
if x <= S + 1:
S = S + x
else
break;
}
the forbidden sum is S + 1.
</code></pre>
<p>Suppose we have the next number <b>x</b>. If <b>x</b> is greater than <b>S + 1</b>, because of the numbers are ascending, <b>S + 1</b> will be never got. Therefore, there is a break. Otherwise, <b>1 .. S + x</b> are all possible.</p>
<p>And also, we can describe the algorithm in an alternative way (but helpful):</p>
<pre><code>S = 0
while (true) {
newS = the sum of {x | x <= S + 1}
if (S == newS):
break
S = newS
}
the forbidden sum is S + 1.
</code></pre>
<p>we should observe that, the answer is smaller than the sum of <b>A[1..N]</b>, <= 10^9, denoted as <b>P</b>. Moreover, <b>S</b> is increasing exponentionally, as fast as the <a href="http://en.wikipedia.org/wiki/Fibonacci_Number">Fibonacci Number</a>, because the newly added number should be greater than previous loop's <b>S</b>. Therefore, there will be only O(<b>log P</b>) loops.</p>
<p>Back to the original problem, for a given query, if we can fast perform the "newS = the sum of {x | x <= S + 1}" in the given <b>A[L .. R]</b>, such as in O(<b>log N</b>) or O(<b>log^2 N</b>) time, then we can solve this problem. Fortunately, we can ask Segment Tree for help. </p>
<p>For the static Segment Tree, we can maintain a sorted list in each node with their prefix sum (O(<b>N log N</b>) space is needed, because there are <b>O(N)</b> numbers stored in each level). When the query covered the whole interval stated by the node, binary search is adopted to fast locate the "x <= S + 1" position and return the prefix sum. Therefore, we can solve each query in O(<b>log^2 N</b>) time.</p>
<p>Furthermore, we can try Persistent Segment Tree to solve this problem in O(<b>log N</b>) time. <a href="http://en.wikipedia.org/wiki/Persistent_data_structure">Persistent Data Structure</a> can help us to deal with the <b>L .. R</b> query into the delta of <b>1 .. R</b> query and <b>1 .. L - 1</b> query. Therefore, we can build the Persistent Segment Tree on their values (each node stands for an interval of values of <b>A[]</b>) and insert the A[i] from <b>i = 1 to N</b> one by one. After that, we can have <b>N + 1</b> roots stand for different prefixs (ranging from 0 to <b>N</b>. 0-th is an empty tree, <b>i</b>-th is the segment tree after inserted <b>A[1..i]</b>). Each node this time stores the total numbers have been inserted in to this subtree. For a given query <b>[L .. R]</b> and the <b>S</b> we maintained, we query the total number <= <b>S + 1</b> on the <b>R</b>-th tree and <b>(L-1)</b>-th tree, and then get the delta. This process is O(<b>log N</b>).</p>
<p>Finally, using the Persistent Segment Tree, we can solve this problem in O(<b>N log N + M log P log N</b>).</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/FRBSUM.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/FRBSUM.cpp">here</a>. </p>shangjingboMon, 13 Jan 2014 15:11:51 +0530https://discuss.codechef.com/questions/35346/frbsum-editorialbinary-searchmediumjan14segment-treeeditorialpersistencePLZLYKME - Editorialhttps://discuss.codechef.com/questions/35355/plzlykme-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/PLZLYKME">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/PLZLYKME">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/kaushik_iska">Kaushik Iska</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/white_king">Mahbub</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Simple</p>
<h1>PREREQUISITES:</h1>
<p>Programming Language</p>
<h1>PROBLEM:</h1>
<p>Define <b>F[1] = S, F[i > 0] = F[i - 1] * (C + 1)</b>. Determine whether <b>F[D] >= L</b>.</p>
<h1>EXPLANATION:</h1>
<p>First of all ,we need to observe that <b>F[]</b> is monotone increasing, because of (C + 1) > 1. </p>
<p>Second, <b>F[]</b> is increasing exponentially, while <b>L</b> is smaller than 10^9. That means, only O(<b>log L</b>) days are needed for F[D] to exceed <b>L</b>.</p>
<p>Third, when F[] exceed <b>L</b>, it is possible about 10^18 (exceeding <b>int</b> in C++ and Java). So please choose the appropriate type to store.</p>
<p>In summary, what we need to do is calculate <b>F[0..D]</b> one by one, until all <b>D + 1</b> ones are got or some one is greater than <b>L</b>. The time complexity is in O(min{<b>D</b>, <b>log L</b>}).</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/PLZLYKME.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/PLZLYKME.cpp">here</a>. </p>shangjingboMon, 13 Jan 2014 15:12:18 +0530https://discuss.codechef.com/questions/35355/plzlykme-editorialsimplejan14programmingeditorialtime difference in two same solutionhttps://discuss.codechef.com/questions/40626/time-difference-in-two-same-solution<p>i submitted my solution for the problem <a href="http://www.codechef.com/JAN14/problems/PLZLYKME">Please like me</a> in jan2014 long challenge. my first <a href="http://www.codechef.com/viewsolution/3172104">solution</a> got time limit exceeded than i created one more <a href="http://www.codechef.com/viewsolution/3172451">solution</a> and in that solution i just added function that is called for every test cases and that is accepted!! can you tell me guys why there is so much time difference in <a href="http://www.codechef.com/JAN14/status/PLZLYKME%2Cjakesahir">both solution</a>? </p>jakesahirSat, 29 Mar 2014 14:37:43 +0530https://discuss.codechef.com/questions/40626/time-difference-in-two-same-solutionjan14time-limittimeFGFS - Editorialhttps://discuss.codechef.com/questions/35343/fgfs-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/FGFS">Practice</a><br>
<a href="http://www.codechef.com/JAN14/problems/FGFS">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/viv001">Vivek Hamirwasia</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/white_king">Mahbub</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/shangjingbo">Jingbo Shang</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Sort, Greedy.</p>
<h1>PROBLEM:</h1>
<p>Given some sets of open intervals (exclusive at two ends), for each set, find the maximum number of disjoint intervals.</p>
<h1>EXPLANATION:</h1>
<p>First of all, we need to observe that the intervals in different sets are independent (in the original statement, the customers preferred in different compartments are independent).</p>
<p>For a single set, it is a classical greedy problem, called <a href="http://en.wikipedia.org/wiki/Activity_selection_problem">Activity Selection problem</a>. The greedy method is as following:</p>
<ol>
<li>Sort the intervals by their right end ascending.</li>
<li>Initialized the select intervals as an empty set</li>
<li>Consider the sorted intervals one by one, add it if it is possible (only need to check the last select interval and the current one).</li>
</ol>
<p>The intuition of this greedy is that, we need to make sure the space remained for the later intervals is as large as possible. The proof is also easy. For the first interval, we definite choose the interval which ends earliest. Otherwise, we can replace the first interval in the best solution with that earliest ended interval (with at least same best solution). Therefore, we can achieve the maximum interval selections with choosing the earliest ended interval. Recursively, we can see that the greedy is correct.</p>
<p>In summary, we can solve this problem in O(<b>N</b> log <b>N</b>), where <b>N</b> is the total number of intervals in all sets.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Setter/FGFS.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/2014/January/Tester/FGFS.cpp">here</a>. </p>shangjingboMon, 13 Jan 2014 15:11:41 +0530https://discuss.codechef.com/questions/35343/fgfs-editorialjan14sortingeasygreedyeditorial