Questions Tagged With programminghttps://inoi15.discuss.codechef.com/tags/programming/?type=rssquestions tagged <span class="tag">programming</span>enFri, 23 Jan 2015 20:44:03 +0530Substring with least mod value - DP?https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dp<p>This is from IARCS Problem archive (DEVIOUS). Given a sequence of integers, how do you find the contiguous substring with the absolute value of the sum of its numbers being minimum?
Is it even DP? How do you relate it to smaller subproblems?</p>vikramnitin9Sun, 04 Jan 2015 19:14:03 +0530https://inoi15.discuss.codechef.com/questions/60742/substring-with-least-mod-value-dpdynamiccontiguousprogrammingsubstringiarcsdeviousarchiveabsoluteDiscussion on Java and some tipshttps://inoi15.discuss.codechef.com/questions/60417/discussion-on-java-and-some-tips<p>I have found that the BufferedReader is faster than the Scanner at taking inputs. My program was getting TLE with Scanner and as soon as I switched to BufferedReader, it ran perfectly well. Same goes with PrintWriter. My program which was getting TLE with System.out.print ran perfectly when I used PrintWriter instead. Will this be true for all programs? Can I save execution time by using BufferedReader and PrintWriter?</p>
<p>I have seen many programmers who import library classes one by one instead of the whole. I mean they write,"import java.io.BufferedReader; import java.io.PrintWriter;". I always write,"import <a href="http://java.io">java.io</a>.*;". This imports the entire IO library. Does importing only the required libraries save time/memory or both?</p>
<p>What are some other ways I can reduce the execution and memory required in Java?
If you guys know some quick tips or techniques in Java that are helpful, please write them for every Java programmer. </p>
<p>I'll start by saying Arrays.sort() is the best way to sort an array(even Strings). </p>
<p>Thanks a lot :-)</p>infam0usThu, 01 Jan 2015 17:44:18 +0530https://inoi15.discuss.codechef.com/questions/60417/discussion-on-java-and-some-tipsjavatleprogramminginoiioizioinoi2015HIGHWAYBYPASS - Flaw in inductive step of solution?https://inoi15.discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solution<p>HIGHWAYBYPASS from INOI 2014.</p>
<p>The solution on the INOI Practice Server goes something like this</p>
<p>rght[r][c][x] = (rght[r][c-1][x-1] + down[r][c-1][d]);<br>
down[r][c][x] = (down[r-1][c][x-1] + rght[r-1][c][d]);</p>
<p>Where rght[r][c][x] is the number of paths to (r,c) that use at most 'x' consecutive moves in some direction (at some point in the path), and similarly for down[r][c][x].</p>
<p>But I think there is a flaw in this argument. I'll try to give a counterexample.</p>
<p>Let the starting square be (0,0). I move 4 to the right, 2 down and 2 right, ending up at (2,6).</p>
<p>This is one of the ways that corresponds to rght[2][6][4] (Since the maximum number of consecutive segments is 4). Note that this path passes through (2,5) and (2,4).</p>
<p>Now according to the inductive step of the DP solution, the number of ways to reach (2,6) from (2,5) using at most 4 segments is the number of ways to reach (2,5) from (2,4) using at most<b> 3 segments. <i> But while assuming this, the path we discussed above is omitted! </i></b></p>
<p>That path provides a way to reach (2,5) from (2,4) using <b><i>4 segments.</i></b> And it is also a way to reach (2,6) from (2,5), still using only 4 segments.</p>
<p>Please let me know whether this is compensated for elsewhere in the algorithm.</p>vikramnitin9Fri, 23 Jan 2015 20:44:03 +0530https://inoi15.discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solutionpathsprogrammingofdynamicnumberbypassinoihighway