Questions asked by akashbhalotiahttps://discuss.codechef.com/questions/asked-by/173016/akashbhalotia/?type=rssQuestions asked by <a href="/users/173016/akashbhalotia" >akashbhalotia</a>enWed, 06 Mar 2019 14:12:36 +0530Efficiently converting a space separated String of numbers into an integer array in Javahttps://discuss.codechef.com/questions/92500/efficiently-converting-a-space-separated-string-of-numbers-into-an-integer-array-in-java<p>Hi. I'm quite new to CP. I use <strong>Java</strong>. </p>
<p>I often notice in contests that we are given a String of space separated integers as inputs, which we have to convert into an integer array to perform operations on them. What I do is split the String (String a[] = str.split(" ");) to convert it into a String array and then use <strong>for</strong> loop to convert it into an integer array. </p>
<p>What I mean to ask is <strong><em>whether there is a better way of doing so, i.e., converting it into an integer array using less number of code steps, i.e., whether there is any in-built java function which may help me.</em></strong> </p>
<p>Thanks :)</p>akashbhalotiaSun, 05 Mar 2017 08:06:13 +0530https://discuss.codechef.com/questions/92500/efficiently-converting-a-space-separated-string-of-numbers-into-an-integer-array-in-javajavaIn-built useful Java functionshttps://discuss.codechef.com/questions/92501/in-built-useful-java-functions<p>When I was extremely new to CP, I used to manually sort the arrays(by typing the whole sorting code) instead of using the Java in-built Arrays.sort(array_name) of the util package. </p>
<p>I would do a similar thing for binary search, until I came to know of Arrays.binarySearch(array_name,key) of the util package.</p>
<p>Programmers, I want to know <strong>whether there are any other such short-cut array functions, String functions, techniques,tricks, anything that you use that saves a lot of time or code writing and would help newbie coders like me as well as anyone who may not be aware of them.</strong></p>
<p>You can also mentions short-cuts of other languages to help the users coding in them.</p>
<p>Thanks in advance :)</p>akashbhalotiaSun, 05 Mar 2017 08:53:05 +0530https://discuss.codechef.com/questions/92501/in-built-useful-java-functionspythoncjavac++Eclipse tricks and short-cuts.https://discuss.codechef.com/questions/92523/eclipse-tricks-and-short-cuts<p><strong><em>What are some cool and helpful tricks/tips/short-cuts that you know and may help fellow coders?<strong>
</strong>What are the things that makes it better as compared to other Java IDEs like BlueJ?</em></strong></p>
<p>I have recently shifted from BlueJ to Eclipse after hearing about its short-cuts like sysout(Ctrl+Space) , templates, etc. Earlier I was reluctant as it seemed very complicated as compared to the seemingly easy-to-use BlueJ. It still does. But most people in the industry, as well as professionals, experts and Java coders as a whole, use Eclipse for coding. What's the reason? What makes it stand out? Please also mention any available online guides for Eclipse as well as any tips or tricks that you know of.</p>
<p>Thanks :)</p>akashbhalotiaSun, 05 Mar 2017 13:25:38 +0530https://discuss.codechef.com/questions/92523/eclipse-tricks-and-short-cutsjavaeclipseNew Rating Systemhttps://discuss.codechef.com/questions/92675/new-rating-system<p>Can someone please explain me the new stars and colours system on Codechef?
Thanks :)</p>akashbhalotiaThu, 09 Mar 2017 20:37:27 +0530https://discuss.codechef.com/questions/92675/new-rating-systemcodechefWhy isn't the second implementation working?https://discuss.codechef.com/questions/99197/why-isnt-the-second-implementation-working<p>Here, I have two implementations of the problem <strong>Art</strong>, code- <strong>MAKEART</strong> in JAVA. The first one is giving me AC, while the seond one is giving wrong answer. Please help.
It is a problem from SNACKDOWN 2016, pre-elimination round A. Thanks.</p>
<p>link-<a href="https://www.codechef.com/problems/MAKEART">https://www.codechef.com/problems/MAKEART</a></p>
<p>1st implementation- </p>
<pre><code>import <a href="http://java.io">java.io</a>.*;
class MAKEART
{
public static void main(String args[]) throws IOException
{
BufferedReader br=new BufferedReader
(new InputStreamReader(<a href="http://System.in">System.in</a>));
int i,T,N,j;
System.out.println();
T=Integer.parseInt(br.readLine());
String s[]=new String[100011];
int a[]=new int[100011];
for(i=0;i<T;i++)
{
N=Integer.parseInt(br.readLine());
s=br.readLine().trim().split(" ");
for(j=0;j<N;j++)
a[j]=Integer.parseInt(s[j]);
int flag=0;
for(j=2;j<N;j++)
{
if(a[j]==a[j-1]&&a[j-1]==a[j-2])
{
flag=1;
break;
}
}
if(flag==1)
System.out.println("Yes");
else
System.out.println("No");
}
}
}
</code></pre>
<p>Second implementation- </p>
<pre><code>import <a href="http://java.io">java.io</a>.*;
class MAKEART2 //incorrect
{
public static void main(String args[]) throws IOException
{
BufferedReader br=new BufferedReader
(new InputStreamReader(<a href="http://System.in">System.in</a>));
int i,T,N,j;
System.out.println();
T=Integer.parseInt(br.readLine());
String s[]=new String[100011];
for(i=0;i<T;i++)
{
N=Integer.parseInt(br.readLine());
s=br.readLine().trim().split(" ");
int flag=0,c=1;
char ch=s[0].charAt(0),ch2;
for(j=1;j<N;j++)
{
ch2=s[j].charAt(0);
if(ch2==ch)
c++;
else
{
ch=ch2;
c=1;
}
if(c==3)
{
flag=1;
break;
}
}
if(flag==1)
System.out.println("Yes");
else
System.out.println("No");
}
}
}
</code></pre>akashbhalotiaSat, 27 May 2017 13:23:18 +0530https://discuss.codechef.com/questions/99197/why-isnt-the-second-implementation-workingjavaHow to start with Topcoderhttps://discuss.codechef.com/questions/103025/how-to-start-with-topcoder<p>I wanted to start participating in Topcoder SRMs, just like I do for Codeforces and Codechef. But Topcoder seems so weird and unfriendly. Participating in Codechef/Codeforces contests is sooo simple, but I don't understand how to participate in Topcoder contests. Do I have to download an applet called 'Arena'? What am I supposed to do? How to procced? How to know the contest dates? Please help me out. Thanks a lot Codechef community :)</p>akashbhalotiaFri, 23 Jun 2017 22:11:14 +0530https://discuss.codechef.com/questions/103025/how-to-start-with-topcodertopcoderPleeeeease tell me what is wrong in this solutionhttps://discuss.codechef.com/questions/109909/pleeeeease-tell-me-what-is-wrong-in-this-solution<p>Problem link- <a href="https://www.codechef.com/ZCOPRAC/problems/ZCO16001/">Bookshelves</a></p>
<p>The link to my solution- <a href="https://ideone.com/TbzHOW">greedy strategy</a></p>
<p>Please tell me a counter case which would fail in my solution. Thanks a lot.</p>akashbhalotiaMon, 28 Aug 2017 21:30:23 +0530https://discuss.codechef.com/questions/109909/pleeeeease-tell-me-what-is-wrong-in-this-solutionzcoA nice, honest and relevant review and wake-up callhttps://discuss.codechef.com/questions/113977/a-nice-honest-and-relevant-review-and-wake-up-call<p><a href="https://www.quora.com/Why-do-a-lot-of-successful-competitive-programmers-not-participate-actively-on-CodeChef-but-participate-often-on-sites-like-TopCoder-and-Codeforces/answer/Bohdan-Pryshchenko?share=a92db33c&srid=XWJD">link</a></p>
<p>In the above link, <strong>Bohdan Pryshchenko</strong> (I<em>_</em>love<em>_</em>Tanya_Romanova) answers the question why Codechef is less popular than other sites like Topcoder and Codeforces.</p>
<p>I believe that it is a very <strong>honest</strong> and <strong>relevant</strong> answer. <strong>It is sad to hear that coders from all over the world have such viewpoint about Indian platforms and Indians</strong>. But most of the points he has mentioned are nothing less than the <em>bitter</em> but <em>sheer</em> truth.</p>
<p>I trust that Codechef should take this as a kind of <strong>wake-up call</strong> and take necessary steps to improve the contests' and Discuss quality. </p>
<p>Everyone here is aware that Codechef has had its share of low-quality questions and test cases. There have been countless server issues. Every week or two there is a new post on Discuss, <strong>complaining about a contest, or plagiarism, or weak test cases</strong>. Discuss is usually filled with <strong>irrelevant posts and unchecked drama</strong>. </p>
<p>I hope that this comes to the immediate attention of the <a href="/users/1/admin">@admin</a> . </p>
<p>I would also like to hear your views, especially those of <a href="/users/187411/vijju123">@vijju123</a> and <a href="/users/114061/meooow"><a href="/users/114061/meooow">@meooow</a></a> . Any viewpoint, whatever be the nature, is greatly welcomed.</p>
<p>Here's hoping that Codechef will one day become the top Online Judge. Their efforts in promoting ICPC and IOI participation have not gone unnoticed. </p>akashbhalotiaSat, 07 Oct 2017 01:22:02 +0530https://discuss.codechef.com/questions/113977/a-nice-honest-and-relevant-review-and-wake-up-callcodechefHBDANA - Editorialhttps://discuss.codechef.com/questions/134426/hbdana-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/HBDANA">Practice</a><br>
<a href="https://www.codechef.com/COPH2018">Contest</a></p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/aakashjaiswal">Aakash Jaiswal</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/sonu_628">Deepansh Parmani</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/akashbhalotia">Akash Bhalotia</a></p>
<h1>DIFFICULTY:</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES:</h1>
<p><a href="https://en.wikipedia.org/wiki/Sorting">Sorting</a></p>
<h1>PROBLEM:</h1>
<p>Given an array of size N, find the sum of the K largest elements of the array.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Sort the array in non-decreasing or ascending order. Find the sum of the last K elements.</p>
<h1>EXPLANATION:</h1>
<p>One of the simplest ways to solve this problem is to use <strong>Sorting</strong>. </p>
<p>As <em>1 $\leq$ N $\leq$ 2* $10^5$, O($N^2$)</em> sorting algorithms like <a href="https://en.wikipedia.org/wiki/Bubble_sort">Bubble Sort</a>, <a href="https://en.wikipedia.org/wiki/Selection_sort">Selection Sort</a>, <a href="https://en.wikipedia.org/wiki/Insertion_sort">Insertion Sort</a>, etc. would result in <em>Time Limit Exceeded</em> (<strong>TLE</strong>). Thus we have to use faster sorting algorithms like <a href="https://en.wikipedia.org/wiki/Merge_sort">Merge Sort</a>, <a href="https://en.wikipedia.org/wiki/Quicksort">Quick Sort</a>, <a href="https://en.wikipedia.org/wiki/Heapsort">Heap Sort</a>, etc. which generally result in a time complexity of <em>O(NlogN)</em>.</p>
<p>In CP (Competitive Programming), one doesn't generally implement the full sorting algorithm, but uses in-built library sorting function of the language; </p>
<p>For Example: </p>
<ol>
<li><a href="https://www.geeksforgeeks.org/arrays-sort-in-java-with-examples/">Arrays.sort() of JAVA</a></li>
<li><a href="https://www.geeksforgeeks.org/comparator-function-of-qsort-in-c/">qsort() of C</a></li>
<li><a href="https://www.geeksforgeeks.org/sort-algorithms-the-c-standard-template-library-stl/">sort() of C++</a></li>
</ol>
<p>1) Sort the array in ascending order. Now the <em>K-largest</em> elements are all populated towards the end of the array, from index (N-K+1) to index N, 1-based indexing.</p>
<p>2) Using a loop, you can find the sum of the last K elements of this sorted array. A 32-bit integer datatype should be sufficient to store the sum, as <em>$1\leq a[i]\leq 10^4$</em> and <em>$1\leq K \leq 20$.</em> </p>
<p>Another way to solve this problem, using sorting, is to sort the array in descending order and find the sum of the first K elements in it.</p>
<h1>COMPLEXITY:</h1>
<p><strong>Time complexity:</strong> <em>O(NlogN)</em> per test case</p>
<p><strong>Space Complexity:</strong> <em>O(N)</em></p>
<h1>SOLUTIONS:</h1>
<p><a href="https://www.codechef.com/viewsolution/19878667">Editorialist's solution</a></p>
<h2>Similar Problem:</h2>
<p>Find the sum of the K-smallest elements of the array. Same constraints.</p>
<p>===============================================</p>
<h1>ALTERNATIVE SOLUTION:</h1>
<p>1) <strong>O(N*K) using <em>Looping</em>:</strong></p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>Run a loop K times. Each time find the largest element in the array. Add it to the sum. Set the element equal to -1, so that it doesn't get selected as the largest element again.</p>
<p>In my approach, I have used swapping instead of setting the next largest element =-1 each time. </p>
<p><a href="https://www.codechef.com/viewsolution/19878881">Solution</a></p>
</div></div>
<p>2) <strong>O(N*logK) using a <em>Min-Heap</em>:</strong></p>
<p><a href="https://en.wikipedia.org/wiki/Binary_heap">Heap</a></p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>Create a Min-Heap of size K. Insert the first K elements into it and each time add that element to the sum. For the next (N-K) elements, if an element is greater than the root element of the heap,</p>
<p>1) Remove the root element</p>
<p>2) Subtract it from the sum</p>
<p>3) Add the current element to the heap</p>
<p>4) Add it to the sum.</p>
<p><a href="https://www.codechef.com/viewsolution/19879005">Solution</a></p>
</div></div>
<h1>USEFUL READ-UPS AND TUTORIALS:</h1>
<p>Don't know a topic? No worries :) You'll find the links below useful.</p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>1) <a href="https://www.codechef.com/getting-started">How to get Started?</a></p>
<p>2) <a href="https://www.iarcs.org.in/inoi/online-study-material/topics/efficiency.php">Time Complexity and Big-O</a></p>
<p>3) <a href="https://www.iarcs.org.in/inoi/online-study-material/topics/sorting.php">Sorting</a></p>
<p>4) <a href="https://www.iarcs.org.in/inoi/online-study-material/topics/heaps.php">Heaps</a></p>
<p><strong>General Tutorials:</strong></p>
<p>There are many sites which provide excellent tutorials on data structures and algorithms. Some of them, in no particular order, are:</p>
<ol>
<li>
<p><a href="https://www.topcoder.com/community/data-science/data-science-tutorials/">Topcoder</a></p>
</li>
<li>
<p><a href="https://www.iarcs.org.in/inoi/online-study-material/topics/index.php">ICO Study Material</a></p>
</li>
<li>
<p><a href="https://www.geeksforgeeks.org/fundamentals-of-algorithms/">GeeksForGeeks</a></p>
</li>
<li>
<p><a href="http://codeforces.com/blog/entry/23054">Codeforces</a></p>
</li>
<li>
<p><a href="https://www.hackerearth.com/practice/codemonk/">HackerEarth</a></p>
</li>
</ol>
</div></div>
<p>===============================================</p>
<h1>BONUS:</h1>
<p>Can we solve this problem in O(N) time?</p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>1) <a href="https://www.geeksforgeeks.org/quickselect-algorithm/">Quickselect</a> : <a href="https://www.codechef.com/viewsolution/19879601">Solution</a></p>
<p>2) <a href="https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/">Worst-case linear-time</a></p>
</div></div>
<p>==================================================================================================</p>
<p>Feel free to share your approach if it differs. If you have any doubts or you feel stuck at any point, feel free to ask them below. You can also reach me at $akashbhalotia\.unofficial@gmail\.com$ . I tried my best to make the editorial beginner-friendly. Suggestions are always welcomed :) </p>akashbhalotiaSun, 26 Aug 2018 14:55:56 +0530https://discuss.codechef.com/questions/134426/hbdana-editorialakashbhalotiacoph2018sortingeditorialcakewalkSHIVIGOD - EDITORIALhttps://discuss.codechef.com/questions/144492/shivigod-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/SHIVIGOD">Practice</a><br>
<a href="https://www.codechef.com/ICOP1904/problems/SHIVIGOD">Contest</a></p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/kjain1810">Kunal Jain</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/kjain1810">Kunal Jain</a>, <a href="https://www.codechef.com/users/taran_1407">Taranpreet Singh</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/akashbhalotia">Akash Bhalotia</a> </p>
<h1>DIFFICULTY:</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES:</h1>
<p><a href="https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/">Prefix sums</a>, <a href="https://www.geeksforgeeks.org/window-sliding-technique/">Sliding Window</a>.</p>
<h1>PROBLEM:</h1>
<p>Given an array of length <em>N</em>, find the <strong>maximum average</strong> of the numbers among <strong>all subarrays</strong> of length between <em>A</em> and <em>B</em>, inclusive.</p>
<h1>CONSTRAINTS:</h1>
<ul>
<li>1 $\leq$ T $\leq$ 5</li>
<li>1 $\leq$ N $\leq$ 1000</li>
<li>0 $\leq$ arr[i] $\leq$ $10^{10}$</li>
</ul>
<h1>QUICK EXPLANATION:</h1>
<p>Compute prefix sums of the array. For all subarrays of size in range <em>A</em> to <em>B</em>, compute the average of the elements efficiently using prefix sums and print the maximum of all these averages.</p>
<h1>EXPLANATION:</h1>
<ul>
<li>Looking at the constraints, one can
guess that an O($N^2$) solution should work.</li>
<li>Remember that a <a href="https://stackoverflow.com/questions/5298300/definition-of-subarray">subarray</a> is just like a <em>substring</em>, a <em>contiguous sequence</em> of elements in an array. </li>
<li>Let's consider every subarray of size <em>A</em> to <em>B</em>. We can do this by running two nested loops.</li>
<li>We can compute the sum of every such subarray and divide it by its size to get the average, maintaining the max average each time.</li>
<li>If we do it naively, i.e., calculate the sum of each subarray each time using a separate loop, its complexity increases to O($N^3$), which shouldn't pass in the ideal case.</li>
<li>What we can do is to maintain a <strong>prefix sums</strong> array. This way we can get the sum of elements of a subarray in <em>constant time</em>, improving the complexity by a factor of <em>N</em>, now making it O($N^2$), which is sufficient to work here.</li>
<li>Lastly, don't forget to use a 64-bit data type like <em>double</em> or <em>long</em> to store the values.</li>
</ul>
<h1>COMPLEXITY:</h1>
<ul>
<li>Time Complexity: <em>O($N^2$)</em> per test case.</li>
<li>Space Complexity: <em>O(N)</em> per test case.</li>
</ul>
<hr>
<h1>ALTERNATIVE APPROACH:</h1>
<p><strong>Using <em>Sliding Window</em>:</strong></p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>For a subarray of size <em>x</em>, run a sliding window of size x through its elements to get their sum efficiently. Do this for every <em>x</em> in range <em>A</em> to <em>B</em>, each time maintaining the maximum average. This too takes <em>O($N^2$)</em>.</p>
</div></div>
<h1>AC SOLUTIONS:</h1>
<ul>
<li><a href="https://www.codechef.com/viewsolution/22605507">Brute Force</a></li>
<li><a href="https://www.codechef.com/viewsolution/22605518">Prefix sums</a></li>
<li><a href="https://www.codechef.com/viewsolution/22605525">Sliding Window</a></li>
<li><a href="http://">Setter</a></li>
<li><a href="http://">Tester</a></li>
</ul>
<h1>SIMILAR PROBLEMS:</h1>
<ul>
<li><a href="https://www.codechef.com/ZCOPRAC/problems/ZCO15002">Variation</a></li>
<li><a href="https://www.iarcs.org.in/inoi/online-study-material/topics/sliding-window.php">IARCS</a></li>
<li><a href="https://www.iarcs.org.in/inoi/online-study-material/topics/prefix-sums-maximum-sum-subsection.php">Max sum subarray</a></li>
<li><a href="https://www.codechef.com/tags/problems/sliding-window">Sliding-window</a></li>
</ul>
<hr>
<p>Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :) </p>
<p>Thanks to <a href="/users/211453/taran_1407">@taran_1407</a> and <a href="/users/187411/vijju123">@vijju123</a> for their constant guidance and support.</p>akashbhalotiaSat, 26 Jan 2019 18:57:01 +0530https://discuss.codechef.com/questions/144492/shivigod-editorialicoakashbhalotiaprefix-sumsicop1904sliding-windowcakewalkSSJG - EDITORIALhttps://discuss.codechef.com/questions/144493/ssjg-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/SSJG">Practice</a><br>
<a href="https://www.codechef.com/ICOP1904/problems/SSJG">Contest</a></p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/kjain1810">Kunal Jain</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/kjain1810">Kunal Jain</a>, <a href="https://www.codechef.com/users/taran_1407">Taranpreet Singh</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/akashbhalotia">Akash Bhalotia</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY</p>
<h1>PREREQUISITES:</h1>
<p><a href="https://www.geeksforgeeks.org/prefix-sum-2d-array/">2-D Prefix Sums</a></p>
<h1>PROBLEM:</h1>
<p>An <em>N</em> * <em>N</em> grid contains coins in some cells. Divide it into <strong>4 parts</strong> using a vertical and a horizontal line such that the number of coins in the part containing the <strong>least number</strong> of coins is <strong>maximum possible</strong>.</p>
<h1>CONSTRAINTS:</h1>
<ul>
<li>1 $\leq$ T $\leq$ 10</li>
<li>1 $\leq$ N $\leq$ 1000</li>
</ul>
<h1>QUICK EXPLANATION:</h1>
<p>Compute 2-D prefix sums for the grid. For every intersection, compute the number of coins present in its 4 subgrids in constant time using the prefix sums. The intersection that has the maximum min value is the best intersection.</p>
<h1>EXPLANATION:</h1>
<ul>
<li>We need to calculate the number of coins present in the 4 subgrids created by every possible intersection.</li>
<li>We can do this by running nested loops for every intersection. This will take <em>O($N^4$)</em>, which is sufficient to pass the first subtask, but will result in <em>TLE</em> for the second subtask.</li>
<li>Thus, we need to improve the complexity from <em>O($N^4$)</em> to <em>O($N^2$)</em>. We need to somehow make the step of computing the number of coins present in a subgrid a constant time process.</li>
<li>We can do this by creating a <a href="https://www.geeksforgeeks.org/prefix-sum-2d-array/">Prefix sums matrix</a>. <em>PrefSum[i][j]</em> will contain the number of coins present in the subgrid from <em>(1,1)</em> to <em>(i,j)</em>.</li>
<li>The formula for this is : </li>
</ul>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p><strong>PrefSum[i][j] = PrefSum[i-1][j] + PrefSum[i][j-1] - PrefSum[i-1][j-1] + coins[i][j]</strong>
(why?)</p>
</div></div>
<ul>
<li>If you are having trouble understanding 2-D Prefix Sums, first make sure that you have a good understanding of <a href="https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/">1-D Prefix Sums</a>. 2-D Prefix Sums is simply an extension of that in 2 Dimensions.</li>
<li>Now let us compute the number of coins present in the subgrids of an intersection at <em>(i,j)</em> in <em>O(1)</em> :</li>
</ul>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<ol>
<li><strong>Top Left Subgrid:</strong> <em>PrefSum[i][j]</em> </li>
<li><strong>Top Right Subgrid:</strong> <em>PrefSum[i][N] - PrefSum[i][j]</em> </li>
<li><strong>Bottom Left Subgrid:</strong> <em>PrefSum[N][j] - PrefSum[i][j]</em> </li>
<li><strong>Bottom Right Subgrid:</strong> <em>M - sum of above three</em></li>
</ol>
</div></div>
<ul>
<li>Now we just need to output the maximum min value we can achieve among all intersections.</li>
</ul>
<hr>
<h1>BONUS:</h1>
<p>What if we had to find the number of coins present in a subgrid starting at <em>(i,j)</em> and ending at <em>(x,y)</em>?</p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>The general formula for this is: </p>
<p><strong>PrefSum[x][y] - PrefSum[x][j] - PrefSum[i][y] + PrefSum[i][j]</strong>
(why?)</p>
</div></div>
<h1>COMPLEXITY:</h1>
<ul>
<li>Time Complexity: <em>O($N^2$)</em> per test case.</li>
<li>Space Complexity: <em>O($N^2$)</em> per test case.</li>
</ul>
<h1>AC SOLUTIONS:</h1>
<ul>
<li><a href="https://www.codechef.com/viewsolution/22614379">First Subtask</a></li>
<li><a href="https://www.codechef.com/viewsolution/22614517">Second Subtask</a></li>
</ul>
<h1>SIMILAR PROBLEMS:</h1>
<ul>
<li><a href="https://www.iarcs.org.in/inoi/online-study-material/topics/prefix-sums-ramus-mango-trees.php">Ramu's Mango Trees</a></li>
<li><a href="https://www.iarcs.org.in/inoi/online-study-material/problems/oil-soln.php#solution">Oil</a></li>
</ul>
<hr>
<p>Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :)</p>
<p>Thanks to <a href="/users/211453/taran_1407">@taran_1407</a> and <a href="/users/187411/vijju123">@vijju123</a> for their constant guidance and support.</p>akashbhalotiaSat, 26 Jan 2019 19:00:56 +0530https://discuss.codechef.com/questions/144493/ssjg-editorialakashbhalotiaicoeasyprefix-sumsicop1904JVPHOBIA - EDITORIALhttps://discuss.codechef.com/questions/144495/jvphobia-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/JVPHOBIA">Practice</a><br>
<a href="https://www.codechef.com/ICOP1904/problems/JVPHOBIA">Contest</a> </p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/jvjplus">Jayprakash Mahto</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/jvjplus">Jayprakash Mahto</a>, <a href="https://www.codechef.com/users/taran_1407">Taranpreet Singh</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/akashbhalotia">Akash Bhalotia</a> </p>
<h1>DIFFICULTY:</h1>
<p>EASY </p>
<h1>PREREQUISITES:</h1>
<p><a href="https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/">DFS</a> </p>
<h1>PROBLEM:</h1>
<p>Given an undirected weighted graph with <em>N</em> nodes and <em>M</em> edges. <em>K</em> nodes are initially reachable. A node is <strong>reachable</strong> from another reachable node <strong>if their edge weight is $\leq$ <em>S</em>.</strong> Find out <strong>how many nodes are reachable.</strong> </p>
<h1>CONSTRAINTS:</h1>
<ul>
<li>1 $\leq$ N $\leq$ $10^5$</li>
<li>M $\leq$ min (123456, N(N-1)/2) </li>
</ul>
<h1>QUICK EXPLANATION:</h1>
<p>Run a DFS from each reachable node. If any neighbour has edge weight $\leq$ <em>S</em>, it is reachable and run a DFS from it. Maintain a visited array so that you visit each node atmost once. Print the number of nodes that were visited.</p>
<h1>EXPLANATION:</h1>
<ul>
<li>We simply need to <em>traverse</em> the graph and find out which nodes are reachable. Let's do this using <strong>Depth-First Search.</strong> </li>
<li>Initially, <em>K</em> nodes are reachable. We'll run a DFS from each one of them.</li>
<li>Once we have run DFS from a node, we don't gain anything by running a DFS through it again. Hence, we'll maintain an array <em>visited[]</em> and marked a node as visited before running DFS from it.</li>
<li>If a neighbour of a reachable node has an edge weight $\leq$ <em>S</em> with it, it too is reachable. Thus, we will add it to the DFS stack and mark it as visited. We'll keep doing this till we have run a DFS on all nodes which are reachable.</li>
<li>Note that we only visit nodes which are reachable. Thus, the answer is the number of nodes marked as visited in the <em>visited</em> array.</li>
<li>This works even when the graph is disconnected as we check for every edge of a node.</li>
</ul>
<h1>COMPLEXITY:</h1>
<ul>
<li>Time Complexity: <em>O(N+M)</em> </li>
<li>Space Complexity: <em>O(N+M)</em> using an <a href="https://en.wikipedia.org/wiki/Adjacency_list">adjacency list</a></li>
</ul>
<hr>
<h1>AC SOLUTIONS:</h1>
<ul>
<li><a href="https://www.codechef.com/viewsolution/22618832">Solution</a></li>
<li><a href="http://">Setter</a> </li>
<li><a href="http://">Tester</a></li>
</ul>
<h1>SIMILAR PROBLEMS:</h1>
<ul>
<li><a href="https://www.codechef.com/INOIPRAC/problems/ROADTRIP">ROADTRIP</a></li>
<li><a href="https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=dfs+and+similar">Codeforces</a></li>
<li><a href="https://www.codechef.com/tags/problems/dfs">Codechef</a></li>
</ul>
<hr>
<p>Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :)</p>
<p>Thanks to <a href="/users/211453/taran_1407">@taran_1407</a> and <a href="/users/187411/vijju123">@vijju123</a> for their constant guidance and support.</p>akashbhalotiaSat, 26 Jan 2019 19:06:59 +0530https://discuss.codechef.com/questions/144495/jvphobia-editorialakashbhalotiaicoeasydfsicop1904GRP - EDITORIALhttps://discuss.codechef.com/questions/144496/grp-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/GRP">Practice</a><br>
<a href="https://www.codechef.com/ICOP1904/problems/GRP">Contest</a> </p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/devarshi09">Devarshi Khanna</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/devarshi09">Devarshi Khanna</a>, <a href="https://www.codechef.com/users/taran_1407">Taranpreet Singh</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/akashbhalotia">Akash Bhalotia</a> </p>
<h1>DIFFICULTY:</h1>
<p>EASY </p>
<h1>PREREQUISITES:</h1>
<p><a href="https://www.geeksforgeeks.org/dynamic-programming/">Dynamic Programming</a> </p>
<h1>PROBLEM:</h1>
<p>Given an array <em>A</em> of size <em>N</em>, containing only 0's and 1's, find the <strong>minimum cost</strong> to <strong>flip</strong> elements such that the size of <strong>every 'group'</strong> is <strong>between <em>x</em> and *y</strong><em> (both inclusive). The cost to flip the </em>$i^{th}$<em> element is </em>B[i]*. If no solution exists, print -1. </p>
<h1>CONSTRAINTS:</h1>
<ul>
<li>1 $\leq$ T $\leq$ 70 </li>
<li>1 $\leq$ N $\leq$ 1000 </li>
<li>0 $\leq$ B[i] $\leq$ 1000 </li>
</ul>
<h1>QUICK EXPLANATION:</h1>
<p>Precompute prefix sums <em>cost[i][k]</em> = cost to make all elements from start to position <em>i</em> equal to bit <em>k</em> (0 $\leq$ k $\leq$ 1). Using Dynamic Programming, for all <em>$x \leq j \leq y$</em> compute <em>DP[i][k]</em> = min of all valid <em>DP[i-j][k^1] + cost to make all elements from position (i-j+1) to i equal to bit k</em>. If no solution exists for <em>N</em>, print -1, else print <em>$min(DP[N][0], DP<a href="https://www.codechef.com/problems/GRP">N</a>)$</em>. </p>
<h1>EXPLANATION:</h1>
<ul>
<li>Let us use 1-based array indexing to understand this. </li>
<li>We want to divide the array into disjoint groups of size <em>j</em>, <em>$x \leq j \leq y$</em>. If we can do this, a solution exists, otherwise we'll be printing -1.</li>
<li>If make all elements of the first group = 1, we'll have to make all elements of the second group = 0 and keep alternating. Similarly, if instead, we make all elements of the first group = 0, we'll have to make all elements of the second group = 1 and keep alternating. Assuming that a solution exists, we'll have to print the minimum of these two, i.e, either making the first group = 1 and alternating, or making the first group = 0 and alternating.</li>
<li>Since we are alternating, if we make a group = k, we would have definitely made the previous group = k <em>xor</em> 1. If the current group is of size j and its last element is at position i, then the previous group must have ended at position <em>i-j</em>. </li>
<li>We'll be using basic dynamic programming to solve this. Remember, that in DP, generally, first we simply solve the problem for a smaller instance of the problem. For example, if the array has N elements, say, we first solve the problem assuming that the array has only 1 element. Then, we <em>extend</em> this solution to solving the the problem for more elements. Once we have the solution for size <em>i</em>, we never compute it for i again. We simply store this result and use it when needed in future. This is what we'll be doing here too.</li>
<li>Let us consider a DP solution with two states: <em>DP[i][k]</em>. This means, if a solution exists for i, <em>DP[i][k]</em> is the minimum cost to give a solution where the last group ends at position <em>i</em> and is set to bit <em>k</em>, where k is 0 or 1. If this group is of size j, then the cost for the previous group must have been stored at <em>DP[i-j][k^1]</em>. Thus, formally: </li>
</ul>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p><strong>DP[i][k] = min(DP[i-j][k^1] + cost to make all elements from (i-j+1) to i equal to bit k)</strong>.</p>
</div></div>
<ul>
<li>To compute the cost for range efficiently, we can precompute their <a href="https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/">prefix-sums</a>. Now to use this in our problem: </li>
</ul>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p><em>Cost for range of size j, ending at i, setting all elements to k:</em> <strong>cost[i][k]-cost[i-j][k]</strong></p>
</div></div>
<ul>
<li>Initially, we'll set all <em>DP[i][k]</em> = -1, signifying that no solution exists for it. We'll make <em>$DP[0][0] = DP[0]{[}10{]} = 0$</em>, signifying that a solution exists when the array has 0 elements. Then, if a solution exists which ends at position i and makes all elements = k, we'll set <em>DP[i][k]</em> = min of all those solutions.</li>
<li>If <em>$DP[N]{[}0{]} = -1 $</em> or <em>$ DP[N]{[}11{]} = -1 $</em>, it means that we can't divide the array into valid sized groups and so we print -1. Otherwise, a solution exists. This involves either setting the elements of the final group to 0 or setting them to 1. Thus, <em>ans</em> = min<em>$ (DP[N][0], DP[N]{[}12{]}) $</em>. </li>
</ul>
<h1>COMPLEXITY:</h1>
<p>Computing prefix sums takes <em>O(N)</em>. DP involves nested loops of size <em>N</em> each. Thus: </p>
<ul>
<li>Time Complexity: <em>O($N^2$)</em> per test case.</li>
<li>Space Complexity: <em>O(N)</em> per test case.</li>
</ul>
<hr>
<h1>AC SOLUTION:</h1>
<ul>
<li><a href="https://www.codechef.com/viewsolution/22629203">Solution</a></li>
<li><a href="http://">Setter</a></li>
<li><a href="http://">Tester</a></li>
</ul>
<h1>PROBLEMS BASED ON DP:</h1>
<p><a href="https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=dp">Codeforces</a> </p>
<hr>
<p>Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :)</p>
<p>Thanks to <a href="/users/211453/taran_1407">@taran_1407</a> and <a href="/users/187411/vijju123">@vijju123</a> for their constant guidance and support.</p>akashbhalotiaSat, 26 Jan 2019 19:15:58 +0530https://discuss.codechef.com/questions/144496/grp-editorialicodynamic-programmingakashbhalotiaeasyicop1904prefix-sumTREEDGE - EDITORIALhttps://discuss.codechef.com/questions/144635/treedge-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/TREEDGE">Practice</a><br>
<a href="https://www.codechef.com/ICOP1904/problems/TREEDGE">Contest</a> </p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/aman_robotics">Aman Kumar Singh</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/aman_robotics">Aman Kumar Singh</a>, <a href="https://www.codechef.com/users/taran_1407">Taranpreet Singh</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/akashbhalotia">Akash Bhalotia</a> </p>
<h1>DIFFICULTY:</h1>
<p>EASY-MEDIUM </p>
<h1>PREREQUISITES:</h1>
<p><a href="https://www.geeksforgeeks.org/dynamic-programming/">Dynamic Programming</a>, <a href="https://cp-algorithms.com/graph/lca_binary_lifting.html">Lowest Common Ancestor</a> </p>
<h1>PROBLEM:</h1>
<p>Given a weighted, rooted Tree with <em>N</em> vertices, root is at 1, answer <em>Q</em> queries of type <em>u</em>, <em>v</em>, <em>x</em>. Here, <em>u</em> and <em>v</em> are vertices whose subtrees are disjoint. Find the <strong>maximum weighted path</strong> between <em>u</em> and <em>v</em>, given that you are allowed to add atmost 1 edge of weight <em>x</em> (x is positive) between any vertex of subtree of <em>u</em> and any vertex of subtree of <em>v</em>. </p>
<h1>USEFUL CONSTRAINTS:</h1>
<ul>
<li>$1 \leq T \leq 5$</li>
<li>$1 \leq N,Q \leq 2*10^5$ </li>
</ul>
<h1>QUICK EXPLANATION:</h1>
<p>We will compare the weights of exactly two paths. 1) From <em>u</em> to <em>LCA</em> of (u,v) and from this <em>LCA</em> to <em>v</em>. 2) From the bottom-most node in the maximum weight subtree of <em>u</em>, connect an edge of weight <em>x</em> to the bottom-most node in the maximum weight subtree of <em>v</em>. The maximum of these two is the answer. </p>
<h1>EXPLANATION:</h1>
<p>First let's consider the case when we don't add any extra edge. From any node in a tree, there is a unique path to any other node. This path passes through the <a href="https://en.wikipedia.org/wiki/Lowest_common_ancestor">Lowest Common Ancestor</a> of the two nodes. You can study about LCA from <a href="https://cp-algorithms.com/graph/lca_binary_lifting.html">here</a>, or if you like video tutorials, <a href="https://youtu.be/kOfa6t8WnbI">here</a>. These tutorials explain a technique called <strong>Binary Lifting</strong> to find the LCA of two nodes in <em>O($logN$)</em> per query. Another technique to find the LCA using <strong>dynamic programming</strong> has been explained <a href="https://www.topcoder.com/community/competitive-programming/tutorials/range-minimum-query-and-lowest-common-ancestor/">here</a>.</p>
<p>We can <em>precompute</em> the weighted distance from the root to every other node:<br>
<strong>dist[i] = dist[itsParent]+weightOfThisEdge</strong>.<br>
Once we find the LCA of <em>u</em> and <em>v</em>, we can find the total weight of the path from <em>u</em> to <em>v</em>, passing through the LCA using this distance in constant time: </p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p><strong>lcaPathWeight = (dist[u] - dist[lca]) + (dist[v] - dist[lca])</strong> </p>
</div></div>
<p>Now let us consider the case when we add an edge to connect the subtrees of <em>u</em> and <em>v</em>. On connecting any vertex of subtree of <em>u</em> to that of <em>v</em>, we get another path from <em>u</em> to <em>v</em>. Remember, we need to maximise the weight of the path. This can only be achieved if we connect the maximum weight subtree of <em>u</em> to the maximum weight subtree of <em>v</em>. </p>
<p>We can compute the maximum weight subtree of every node using <strong>dynamic programming</strong> and <a href="https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/">DFS</a>. For every node, we compute the maximum weight subtree for each of its children. The maximum of all these is the one with which we shall form our path. We can also decide to not take any children in its path if all their maximum subtree sums are negative as we can have a path from this node to itself, of weight 0. Formally:<br>
<strong>DP[i] = 0.<br>
DP[i]= max(DP[i], DP[acrossAllChildrenOfi] +weightOfThisEdge)</strong></p>
<p>Thus, for a pair of vertices <em>u</em> and <em>v</em>, then maximum weighted path through an edge of weight <em>x</em> to connect their subtrees : </p>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p><strong>SubtreePathWeight = DP[u] + DP[v] + x</strong></p>
</div></div>
<p>The maximum of lcaPathWeight and SubtreePathWeight shall give us our answer. </p>
<p><strong>Note:-</strong><br>
This problem has tight constraints. It is advisable to avoid recursive steps wherever possible and to also use <a href="https://www.geeksforgeeks.org/fast-io-for-competitive-programming/">Fast IO</a> to avoid <em>TLE</em> in some languages. </p>
<h1>COMPLEXITY:</h1>
<p>DP takes <em>O(N)</em>. Binary Lifting takes <em>O(NlogN)</em> for precomputation and <em>O(logN)</em> per query. Thus</p>
<ul>
<li><strong>Time Complexity: <em>O(NlogN) + O(QlogN)</em> per test case</strong> </li>
<li><strong>Space Complexity: <em>O(NlogN)</em> per test case</strong>, for Binary Lifting table.</li>
</ul>
<hr>
<h1>AC SOLUTIONS:</h1>
<ul>
<li><a href="http://pasted.co/7aed424e">Setter</a> </li>
<li><a href="http://">Tester</a> </li>
<li><a href="https://www.codechef.com/viewsolution/22689199">Editorialist</a> </li>
</ul>
<h1>SIMILAR PROBLEMS:</h1>
<ul>
<li><a href="https://open.kattis.com/problems/tourists">Tourists</a></li>
<li><a href="https://codeforces.com/blog/entry/43917">CF Blog</a></li>
</ul>
<hr>
<p>Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :)</p>
<p>Thanks to <a href="/users/211453/taran_1407">@taran_1407</a> and <a href="/users/187411/vijju123">@vijju123</a> for their constant guidance and support.</p>akashbhalotiaTue, 29 Jan 2019 18:43:41 +0530https://discuss.codechef.com/questions/144635/treedge-editorialicodynamic-programmingakashbhalotiabinary-liftingeasy-mediumlcaicop1904Review questions before allowing them to be posted during contestshttps://discuss.codechef.com/questions/146243/review-questions-before-allowing-them-to-be-posted-during-contests<p>I'm sure many of you would have noticed that during contests, many participants post their codes, strategies, etc. here on Codechef Discuss, asking for help, even though it's strictly against the rules. Sometimes, users also report cheating on discuss so that immediate action is taken, but this only makes the source of cheating accessible to more users. </p>
<p>I would request Codechef to implement a feature, so that during a live contest, posts appear on discuss only after they have been reviewed by admin or a moderator. You can do this for everyone, or for those below a certain karma limit, as you deem fit. </p>
<p>I know that this shall greatly increase the work load of the admin and the moderators, however, I think that this will benefit the community even more. </p>
<p>Do give it a thought.</p>akashbhalotiaMon, 04 Mar 2019 01:46:52 +0530https://discuss.codechef.com/questions/146243/review-questions-before-allowing-them-to-be-posted-during-contestsadminfeature-requestsuggestioncontestSTRGRA - EDITORIALhttps://discuss.codechef.com/questions/146336/strgra-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/STRGRA">Practice</a><br>
<a href="https://www.codechef.com/ICOP1904/problems/STRGRA">Contest</a> </p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/rishik123/">Rishik Sood</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/rishik123/">Rishik Sood</a>, <a href="https://www.codechef.com/users/taran_1407">Taranpreet Singh</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/akashbhalotia">Akash Bhalotia</a></p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM </p>
<h1>PREREQUISITES:</h1>
<p><a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra's Algorithm</a>, <a href="https://en.wikipedia.org/wiki/Greedy_algorithm">Greedy Approach</a></p>
<h1>PROBLEM:</h1>
<p>Given a weighted, undirected graph <strong>G</strong>, (<strong>N</strong> nodes, <strong>M</strong> edges) and a string <strong>S</strong> of length <strong>X</strong>. Each node in <strong>G</strong> has a letter attached to it. Find the minimum cost of a walk in <strong>G</strong> such that the path contains <strong>S</strong> as a subsequence. </p>
<h1>USEFUL CONSTRAINTS:</h1>
<ul>
<li><em>1 $\leq$ N,X $\leq$ $10^3$</em> </li>
<li><em>0 $\leq$ M $\leq$ $10^3$</em> </li>
<li><em>No two consecutive characters of string S are same.</em> </li>
</ul>
<h1>SUPER QUICK EXPLANATION:</h1>
<p>Run a multi-source dijkstra from every node <strong>i</strong>, such that <strong>letter[i]=s[0]</strong>. Use <strong>DP[i][x]</strong> = minimum cost to reach node <strong>i</strong> after covering the first <strong>x</strong> characters of the string. The answer is <strong>min(DP[i][|S|-1])</strong>. Impossible cases occur when the graph is not well-connected and character is not present at all. </p>
<h1>EXPLANATION:</h1>
<p>We can start our walk from any vertex. So, obviously we'll start from a vertex <strong>i</strong> such that <strong>letter[i]=s[0]</strong>. Let's call each of these vertices <strong>i</strong> a <strong><em>source</em></strong>. As we can start from any of these <strong><em>sources</em></strong>, the cost to reach them is 0. When we start from any <strong>source</strong>, we have already covered the <strong>first letter</strong> of the string at cost 0. </p>
<p>We eventually want to end our walk at a vertex <strong>i</strong> such that <strong>letter[i]=s[|s|-1]</strong>. The cost for this walk has to be minimum possible, while having visited all previous characters of the string as a subsequence. We could have computed the same for all vertices <strong>s[|s|-2]</strong> and then extended our walk to reach a vertex <strong>s[|s|-1]</strong>, such that the <strong>cost of the walk</strong> to reach <strong><em>that</em></strong> <strong>vertex s[|s|-1]]</strong> is minimum possible. Thus, all vertices which have the character <strong>s[|s|-2]</strong> become a new <strong><em>source</em></strong> after having covered all characters till <strong>s[|s|-2]</strong> in their walks. Same can be done for <strong>s[|s|-3]</strong> and so on. </p>
<p>Let's define <strong>cost[i][x]</strong> as the minimum cost (as a walk) to reach vertex <strong>i</strong> after having covered the first <strong>x</strong> characters of the string as a subsequence. The final answer we are looking for will be minimum of all <strong>cost[i][x]</strong> such that <strong>letter[i]=s[|s|-1]</strong>. Impossible cases shall occur when either the graph doesn't contain a particular character present in the string, or the graph isn't well connected enough to reach all characters of the string in a walk. If we find that we can reach no vertex <strong>i</strong> for a state <strong>s[x]</strong> after having covered all the previous characters, then it's an impossible case.</p>
<p>Thus, we get some kind of <strong>greedy algorithm</strong>, where for every state <strong>x</strong>, we have to make <strong>locally-optimal</strong> choices to get the optimal solution for that state. We can do this by running a <strong>multi-source Dijsktra's algorithm</strong>, where, initially, the sources are all vertices <strong>i</strong> such that <strong>letter[i]=s[0]</strong>. We run Dijkstra on them for the state <strong>x=1</strong>, <strong>cost=0</strong>, signifying that it took us cost 0 to reach them, while having covered the first character of the string. All other nodes have cost = INF initially for all states. While exploring a node <strong>i</strong>, for each of its neighbour <strong>j</strong>, we update the cost for <strong>j</strong> for the state <strong>x</strong> if it costs us less to reach <strong>j</strong> for that state from <strong>i</strong>. If <strong>j</strong> has the <strong>(x+1)th</strong> character of the string, we update its cost for state <strong>(x+1)</strong> instead, as on walking through that node, we are also covering the <strong>(x+1)th</strong> character of the string. If either of this reduces the cost to reach <strong>j</strong> for the respective states, we add <strong>j</strong> for that state to the Dijkstra queue. Thus, <strong>j</strong> for that state becomes a new source to run <strong>Dijkstra</strong> from. You can read about <strong>Dijsktra's Algorithm</strong> <a href="https://cp-algorithms.com/graph/dijkstra.html">here</a> and <a href="https://cp-algorithms.com/graph/dijkstra_sparse.html">here</a>. I found them helpful. </p>
<h1>COMPLEXITY:</h1>
<p>We have <strong>X</strong> destinations in worst case. For each of them Multi-source dijkstra takes <strong>O(MlogN)</strong>. The cost array takes <strong>O(N*X)</strong>. Thus,<br>
- <strong>Time Complexity:</strong> <strong><em>X*(M+N)logN</em></strong><br>
- <strong>Space Complexity:</strong> <strong><em>O(N*X)</em></strong></p>
<h1>EXTRA:</h1>
<h3>1) Multi-source Dijkstra and a little on the implementation:</h3>
<div class="hidden-block"> <div class="hide-bar view">View Content</div> <div class="hide-bar hide" style="display:none;">Hide Content</div> <div class="hidden-content" style="display:none;">
<p>In <strong>classical Dijkstra</strong>, we have a single source. We need to find the cost to reach every other node from this source. We assign the distance to reach the source 0 and put it in a priority queue. As we keep exploring the neighbours, we apply distance relaxation on them and if we found a shorter distance to reach them, we update it and add it again to the priority queue with the updated distance. When popping from the queue, if this was the older version of an-already popped node, we ignore this, otherwise we explore the neighbours of this node. </p>
<p>In <strong>Multi-source Dijkstra</strong>, instead of having a single source, we have multiple sources, that is, we can start our walk from <strong>any</strong> source. We are only concerned about <strong>reaching the destination</strong> with minimum cost, irrespective of which source node we started from. The cost to start from each of these sources is 0. Thus, we assign distance 0 to all these sources and put them in the priority queue to explore their neighbours. After all these sources are explored, their neighbours will be treated as the new sources and the neighbour with the minimum cost will be popped out first. This is different from <strong>All-pairs shortest path</strong> algorithm because here we have only a single destination to reach with minimum cost from multiple possible starting positions, as compared to reaching every possible destination from every node. In all-pairs, we run a disjoint dijkstra from every node, while here, we run 1 dijkstra with the source vertices having distance 0. We could have solved this problem using all-pairs dijkstra with dynamic programming as has been done <a href="https://www.codechef.com/viewsolution/23314541">here</a>, but we run into some <strong>TLE</strong> issues. The theoretical complexity of all-pairs shortest path problem is <strong>$N*MlogN$</strong> while that of multi-source dijkstra is <strong>$MlogN$</strong> (for a single destination). </p>
<p>Here, we had multiple destinations too, so we implemented this using a structure having three parameters- <br>
- <strong>i</strong> The node we are currently at,<br>
- <strong>x</strong> The number of characters of the string from the start that we have covered, and <br>
- <strong>d</strong> The cost it incurred. </p>
<p>This structure gave the minimum cost to reach node <strong>i</strong> after covering the first <strong>x</strong> letters in the string. Initially, we inserted all nodes which have <strong>letter[i]=s[0]</strong> into the priority queue, setting their <strong>d</strong> to 0 and <strong>x</strong> to 1, signifying that we have covered 1 character of the string. The queue is prioritised according to <strong>d</strong>. We run multi-source dijkstra for each destination. As soon as we have covered <strong>x</strong> characters in the string, we exit from the queue as this must have been the shortest distance to cover <strong>x</strong> characters.</p>
</div></div>
<hr>
<h1>AC SOLUTIONS:</h1>
<ul>
<li><a href="https://www.codechef.com/viewsolution/22630659">Setter</a> </li>
<li><a href="http://">Tester</a> </li>
<li><a href="https://www.codechef.com/viewsolution/23391009">Editorialist</a> </li>
</ul>
<h1>SIMILAR PROBLEMS:</h1>
<ul>
<li><a href="https://codeforces.com/contest/938/problem/D">Buy a Ticket</a> </li>
<li><a href="https://www.codechef.com/AMR18ROL/problems/PALPATH">Palindromic Walks</a> </li>
</ul>
<hr>
<p>Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :)</p>
<p>Thanks to <a href="/users/211453/taran_1407"><a href="/users/211453/taran_1407">@taran_1407</a></a> and <a href="/users/187411/vijju123">@vijju123</a> for their constant guidance and support. I can't thank <a href="/users/211453/taran_1407"><a href="/users/211453/taran_1407">@taran_1407</a></a> , <a href="/users/223722/bharat2002">@bharat2002</a> and <a href="/users/135804/sonu_628">@sonu_628</a> enough for helping me with the solutions. </p>akashbhalotiaWed, 06 Mar 2019 14:12:36 +0530https://discuss.codechef.com/questions/146336/strgra-editorialmediumicoakashbhalotiagreedydijkstraicop1904