Questions Tagged With cseqhttps://discuss.codechef.com/tags/cseq/?type=rssquestions tagged <span class="tag">cseq</span>enTue, 21 Apr 2015 17:29:28 +0530CSEQ:getting WAhttps://discuss.codechef.com/questions/67667/cseqgetting-wa<p>in my compiler , i'm getting absolute correct answer but here getting wrong answer.why??</p>maninderyoSun, 12 Apr 2015 16:07:20 +0530https://discuss.codechef.com/questions/67667/cseqgetting-wacseqCSEQ - April15 Long (Time Limit Verification)https://discuss.codechef.com/questions/67500/cseq-april15-long-time-limit-verification<p>Hi, </p>
<p>I would like to know the time constraints about this problem. I have an algorithm which takes </p><pre><code>O(20*N) time. </code></pre> where N is ((10power6) + 3).<p></p>
<p>Subtask-3 is getting TLE. Does the solution needs more improvement then that? I'm really exhausted optimizing it. I may have reached the atomic state of optimization.</p>
<p>Please let me know the Time constraints in O() notation. <a href="/users/1/admin">@admin</a>: In case, any verification of code needed please see this submission. <a> </a><a href="http://www.codechef.com/viewsolution/6692845">http://www.codechef.com/viewsolution/6692845</a> </p>
<p>Thanks.</p>codedecode0111Tue, 07 Apr 2015 13:03:49 +0530https://discuss.codechef.com/questions/67500/cseq-april15-long-time-limit-verificationcseqtime-limitHelp regarding CSEQ [April Challenge]?https://discuss.codechef.com/questions/67933/help-regarding-cseq-april-challenge<p>I was not able to solve this problem during contest, but this is my CSEQ code
-> <a href="http://ideone.com/iaqmIp">http://ideone.com/iaqmIp</a></p>
<p>codechef solution link -> <a href="http://www.codechef.com/viewsolution/6781060">http://www.codechef.com/viewsolution/6781060</a></p>
<p>I cant figure out why there is error in program.</p>
<p>Can anyone please help me, as, this is not getting accepted now ?</p>
<p>Thanks.</p>glowThu, 16 Apr 2015 17:39:25 +0530https://discuss.codechef.com/questions/67933/help-regarding-cseq-april-challengecseqhelpCSEQ - Wrong Answerhttps://discuss.codechef.com/questions/68209/cseq-wrong-answer<p>For the problem <a href="http://www.codechef.com/problems/CSEQ">CSEQ</a>, I mathematically could prove that the total ways to create a non-decreasing sequence of length K (1<= K <= N) equals choose(K + R - L, K) (the same formula given in the ediorial).</p>
<p>Then we can see that choose(K + R - L, K)*(K + R - L + 1)/(K + 1) equals choose(K + R - L + 1, K + 1). Hence in <a href="http://www.codechef.com/viewsolution/6640264">my code here</a>, I wrote a for loop which starts with sumtemp intialised to 1 and which multiplies sumtemp with (j + R - L)/j thus creating the jth element of the sequence. Now this term is added to ans every time in the loop and I also have added the modulus statement there to avoid overflow.</p>
<p>This gives me a correct ans to some cases which I found out manually and then verified with the code, but codechef isn't accepting my solution. Can anyone help me find the mistake in my approach?</p>almondpieTue, 21 Apr 2015 17:29:28 +0530https://discuss.codechef.com/questions/68209/cseq-wrong-answerwrong-answercseqwaCSEQ - Editorialhttps://discuss.codechef.com/questions/67643/cseq-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CSEQ">Practice</a><br>
<a href="http://www.codechef.com/APRIL15/problems/CSEQ">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/adurysk">Adury Surya Kiran</a> </p>
<h1>DIFFICULTY:</h1>
<p>EASY – MEDIUM</p>
<h1>PREREQUISITES:</h1>
<p>Combinatorics</p>
<h1>PROBLEM:</h1>
<p>Given three positive integers <strong>N</strong>, <strong>L</strong> and <strong>R</strong>, find the number of non-decreasing sequences of size at least 1 and at most <strong>N</strong>, such that each element of the sequence lies between <strong>L</strong> and <strong>R</strong>, both inclusive. </p>
<h1>QUICK EXPLANATION:</h1>
<p>Number of non-decreasing sequences of size exactly <strong>K</strong> will be Choose(<strong>K</strong> + <strong>R</strong> - <strong>L</strong>, <strong>K</strong>). Where Choose(<strong>N</strong>, <strong>R</strong>) is number of ways to choose <strong>R</strong> elements from <strong>N</strong> distinct elements.<br>
Summation of Choose(<strong>K</strong> + <strong>R</strong> - <strong>L</strong>, <strong>K</strong>) for all <strong>K</strong> between 1 and N (inclusive) will be Choose(<strong>N</strong> + <strong>R</strong> - <strong>L</strong> + 1, <strong>N</strong>) - 1.<br>
In the question it is given that the answer should be printed mod (10^6+3) which is a prime number.
Choose(<strong>N</strong>, <strong>R</strong>) mod <strong>P</strong> for <strong>N</strong> > <strong>P</strong> can be found by using Lucas Theorem. </p>
<h1>EXPLANATION:</h1>
<p>Let us assume that our non-decreasing sequence is of length <strong>K</strong>, i.e in other terms the sequence a[1], a[2], a[3] ….. a[<strong>K</strong>] and a[<strong>i</strong>] <= a[<strong>i</strong>+1] and <strong>L</strong> <= a[<strong>i</strong>] <= <strong>R</strong> for each <strong>i</strong>.<br>
Let us replace each a[<strong>i</strong>] of the sequence with a[<strong>i</strong>] – <strong>L</strong>. Let <strong>P</strong> = <strong>R</strong> – <strong>L</strong>. Now each a[<strong>i</strong>] satisfies the condition 0 <= a[<strong>i</strong>] <= <strong>P</strong>. </p>
<p><strong>Subtask 1:</strong> </p>
<p>We can solve this by using DP. Make a dp[][] array where dp[i][j] stores number of non-decreasing sequences ending with j and are of length i.<br>
If a[<strong>i</strong>] = <strong>j</strong>, and a[<strong>i</strong> - 1] = <strong>k</strong>, then <strong>k</strong> should be <= <strong>j</strong>. So dp[<strong>i</strong>][<strong>j</strong>] will be sum of dp[<strong>i</strong> – 1][<strong>k</strong>] such that <strong>k</strong> <= <strong>j</strong>.<br>
Boundary case : dp<a href="http://www.codechef.com/problems/CSEQ">1</a>[<strong>j</strong>] = 1 for all <strong>j</strong>.<br>
Calculate these values for all 1 <= <strong>i</strong> <= MAX_N and 0 <= <strong>j</strong> <= MAX_P. For each test case output the sum of dp[<strong>i</strong>][<strong>P</strong>] for all <strong>i</strong>. <br>
Complexity = O(<strong>N</strong> * <strong>P</strong>) Where <strong>P</strong> = <strong>R</strong> - <strong>L</strong>.</p>
<p><strong>Subtasks 2 & 3:</strong> </p>
<p>Now let us consider that there are <strong>K</strong> red balls lying in a row. Now for each <strong>i</strong>, add a[<strong>i</strong>+1] – a[<strong>i</strong>] blue balls between <strong>i</strong>’th red ball and <strong>i</strong>+1’th red ball in the row. Add a[1] blue balls before 1st red ball and <strong>P</strong> – a[<strong>K</strong>] blue balls after <strong>K</strong>’th red ball in the row. </p>
<p><strong>Few observations:</strong> </p>
<ol>
<li>
<p>We can see that there will be exactly P blue balls in the row.<br>
<strong>Proof</strong>: Total number of blue balls = a[1] + a[2] – a[1] + a[3] – a[2] + …..a[<strong>K</strong>] – a[<strong>K</strong> – 1] + <strong>P</strong> – a[<strong>K</strong>]. All the terms of sequence a[] will be cancelled out leaving us with <strong>P</strong>. </p>
</li>
<li>
<p>Two different sequences produce different permutations of red and blue balls.<br>
<strong>Proof</strong>: Let us assume the two sequences are a[1], a[2]…a[<strong>K</strong>] and b[1], b[2]…b[K]. Let <strong>i</strong> be the smallest index where a[<strong>i</strong>] != b[<strong>i</strong>]. Simply assume a[0] = 0 and b[0] = 0. So there will be a[<strong>i</strong>] - a[<strong>i</strong> - 1] blue balls between <strong>i</strong>’th and <strong>i</strong>-1’th red balls in the first permutation and b[<strong>i</strong>] – b[<strong>i</strong>-1] blue balls between <strong>i</strong>’th and <strong>i</strong>-1’th red balls in the second permutation. Hence, the two permutations are different.</p>
</li>
<li>
<p>For each permutation of red and blue balls there exists a sequence which produces it.<br>
<strong>Proof</strong>: The sequence can be generated this way, each a[<strong>i</strong>] will be equal to (total number of blue balls to the left of it). In this sequence a[<strong>i</strong>] will never be greater than a[<strong>i</strong>+1] because there any blue ball to the towards left of <strong>i</strong>’th red ball in the row will also be to the left of <strong>i</strong>+1’th red ball in the row. So the sequence is non-decreasing. As the total number of blue balls is <strong>P</strong>, the highest element of the sequence can be <strong>P</strong>. Hence all the elements lie in the range 0 to <strong>P</strong>. </p>
</li>
<li>
<p>Observations 2 and 3 are enough to say that the mapping between the sequences and the permutation of balls is a Bijection. You can read about Bijective functions <a href="http://en.wikipedia.org/wiki/Bijection">here</a>.</p>
</li>
</ol>
<p>So total number of sequences will be equal to total number of permutations. The total number of permutations of <strong>K</strong> red balls and <strong>P</strong> blue balls in a row is a standard result which is equal to Choose(<strong>K</strong> + <strong>P</strong>, <strong>K</strong>). </p>
<p>This much solution is enough to solve the second subtask. Iterate through each of <strong>K</strong> between 1 and <strong>N</strong> and add Choose(<strong>K</strong> + <strong>P</strong>, <strong>K</strong>) to the answer. </p>
<p>Actually we can reduce this summation to single term to solve subtask 3. The summation is Choose(<strong>P</strong> + 1, 1) + Choose(<strong>P</strong> + 2, 2) ….+ Choose(<strong>P</strong> + <strong>N</strong>, <strong>N</strong>). Add and subtract Choose(<strong>P</strong> + 1, 0) to the summation, which shouldn’t change the value of the sum. </p>
<p>Choose(<strong>P</strong>+1, 1) + Choose(<strong>P</strong>+1, 0) = Choose(<strong>P</strong> + 2, 1) (Since it is known that Choose(<strong>N</strong>, <strong>R</strong>) + Choose(<strong>N</strong>, <strong>R</strong> – 1) = Choose(<strong>N</strong> + 1, <strong>R</strong>)).<br>
Now Choose(<strong>P</strong> + 2, 2) + Choose(<strong>P</strong> + 2, 1) = Choose(<strong>P</strong> + 3, 2).<br>
Now Choose(<strong>P</strong> + 3, 3) + Choose(<strong>P</strong> + 3, 2) = Choose(<strong>P</strong> + 4, 3).<br>
… So on till <strong>N</strong>’th term gives Choose(<strong>P</strong> + <strong>N</strong> + 1, <strong>N</strong>). </p>
<p>So the final answer is Choose(<strong>P</strong> + <strong>N</strong> + 1, <strong>N</strong>) – 1. </p>
<p>You can find the best ways to calculate Choose(<strong>N</strong>, <strong>R</strong>) mod <strong>P</strong> <a href="http://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m">here</a>. </p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/APRIL15/Setter/CSEQ.cpp">Author's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/APRIL15/Tester/CSEQ.cpp">Tester's solution</a></p>aduryskSat, 11 Apr 2015 19:12:15 +0530https://discuss.codechef.com/questions/67643/cseq-editorialcombinatoricslucas-theoremdynamic-programmingcseqapril15editorialmathseasy-mediumHelp needed in CSEQ - April15 Long Challengehttps://discuss.codechef.com/questions/68206/help-needed-in-cseq-april15-long-challenge<p>I was trying to understand this <a href="http://www.codechef.com/viewsolution/6713333">solution</a>. But I'm not able to get what does the following code do?</p>
<pre><code>long long factorial(int n)
{
long long res = 1;
while (n > 0)
{
for (int i = 2, m = n % MOD; i <= m; i++)
res = (res * i) % MOD;
if ((n /= MOD) % 2 > 0)
res = MOD - res;
}
return res;
}
</code></pre>
<p>Can someone please help?</p>ksharma377Tue, 21 Apr 2015 15:45:21 +0530https://discuss.codechef.com/questions/68206/help-needed-in-cseq-april15-long-challengecombinatoricsmodulocseq