Questions asked by sikander_nsithttps://discuss.codechef.com/questions/asked-by/3349/sikander_nsit/?type=rssQuestions asked by <a href="/users/3349/sikander_nsit" >sikander_nsit</a>enFri, 31 Aug 2018 19:55:26 +0530Solution copied from ideonehttps://discuss.codechef.com/questions/17457/solution-copied-from-ideone<p>After the contest I was looking at some solutions of the challenge question in this july contest SEASOR. When I looked at one solution that had the same score as mine, I was shocked to see that it was my exact solution copied. I think there is some problem in my ideone account as I mark all of my codes as user. I don't know how this happened. The following users have the exact solution as mine:</p>
<ol>
<li><a href="http://www.codechef.com/users/fakeddt">fakeddt</a></li>
<li><a href="http://www.codechef.com/users/me_1990_123">me_1990_123</a></li>
<li><a href="http://www.codechef.com/users/jamie015">jamie015</a></li>
<li><a href="http://www.codechef.com/users/ankit2014">ankit2014</a></li>
<li><a href="http://www.codechef.com/users/mohit13">mohit13</a> (his code is very similar though not exactly same).</li>
</ol>
<p><a href="http://www.codechef.com/users/coderrk">coderrk</a> has the exact solution as mine for MOU1H.</p>
<p>I urge the users to come forward and tell the truth.</p>sikander_nsitMon, 15 Jul 2013 23:11:40 +0530https://discuss.codechef.com/questions/17457/solution-copied-from-ideoneideonecheatingseasorChallenge Problem Scorehttps://discuss.codechef.com/questions/29455/challenge-problem-score<p>During the contest my best solution for SEAVEC got 0.085 points and it was in the top 20 solutions for SEAVEC. Now after the rejudge the solution shows [0]points and my contest rank(global) has gone from 26 to 170. I don't understand how there can be so much difference when the test cases are randomly generated and I didn't use any random seed in my code. Is it possible that I got lucky on the first two test files and everyone else's code scored way more than me for the rest 8 files. This is very frustrating and if anyone has got an explanation for this, I'd be grateful.</p>
<p>My best solution during the contest <a href="http://www.codechef.com/viewsolution/2968074.">http://www.codechef.com/viewsolution/2968074.</a></p>sikander_nsitFri, 15 Nov 2013 14:46:46 +0530https://discuss.codechef.com/questions/29455/challenge-problem-scorenovembercontestchallengeseavecProvide test cases for SEAVEChttps://discuss.codechef.com/questions/29533/provide-test-cases-for-seavec<p>As we all know, there have been significant changes in the challenge problem score after the rejudging. Many people(including me) are finding it hard to understand what led to such major changes and are not able to feel comfortable with this 20% rule. So I request <a href="/users/1/admin">@admin</a> to provide the test data for the problem SEAVEC, so that we can see for ourselves the reason for this and the participants who have suffered a major rank drop can get some closure.</p>sikander_nsitSat, 16 Nov 2013 15:38:30 +0530https://discuss.codechef.com/questions/29533/provide-test-cases-for-seavecadminchallengetest-casesseavecCDZ14A - Editorialhttps://discuss.codechef.com/questions/38236/cdz14a-editorial<h1>PROBLEM LINKS:</h1>
<p><a href="http://www.codechef.com/problems/CDZ14A">Practice</a><br>
<a href="http://www.codechef.com/CDZL2014/problems/CDZ14A">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a></p>
<h1>DIFFICULTY:</h1>
<p>SIMPLE-EASY</p>
<h1>PROBLEM:</h1>
<p>Given a string consisting of three possible characters 'B', 'R' and 'G' find the length of the shortest substring such that it contains all three characters atleast once.</p>
<h1>EXPLANATION:</h1>
<p>This was an implementation based problem. There are numerous ways to do it. One way is to traverse the string and for each position calculate the answer if the substring ended at the current position. For this we can keep three variables to keep track of the most recent position of each pill. At each position update the most recent position of the current pill as the current index and calculate the answer by subtracting from this the minimum of the three values. <br>
PSEUDOCODE</p>
<pre><code> arr['R']=arr['G']=arr['B']=-10000000;
for(j=0;j<n;++j)
{
arr[str[j]]=j;
num=j-min(arr['R'],min(arr['G'],arr['B']))+1;
ans=min(ans,num);
}
</code></pre>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/viewsolution/3385247">here</a>. </p>sikander_nsitTue, 11 Feb 2014 03:33:10 +0530https://discuss.codechef.com/questions/38236/cdz14a-editorialsimpleimplementationcdzl14cdz14aeditorialCDZ14B - Editorialhttps://discuss.codechef.com/questions/38237/cdz14b-editorial<h1>PROBLEM LINKS:</h1>
<p><a href="http://www.codechef.com/problems/CDZ14B">Practice</a><br>
<a href="http://www.codechef.com/CDZL2014/problems/CDZ14B">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY-MEDIUM</p>
<h1>PROBLEM:</h1>
<p>Given string S and number L we had to find the number of valid passwords. There are three conditions on the password. </p>
<ol>
<li>Its length should be less than equal to L. <br></li>
<li>Password[i] <= S[i] for 0 <= i < min( |S|, |password| ). <br></li>
<li>The password is lexicographically smaller than S.</li>
</ol>
<h1>EXPLANATION:</h1>
<p>Let us take an example to understand it.</p>
<p>Given string is: “DBF” and L=6.</p>
<p>Strings with maximum length 1 which are smaller than “DBF” are “A”, “B”, “C” and “D” so 4.<br>
Number of Strings with maximum length 2 will be 4*2=8.<br>
Similarly number of strings with maximum length 3 will be 4*2*6-1=47 (because we cannot include “DBF”).<br>
Now number of strings with maximum length 4 will be 47*26 (adding a letter at the end).<br>
Similarly number of strings with maximum length 5 and 6 will be 47*26*26 and 47*26*26*26 respectively.<br>
So the total answer becomes 4 + 4*2 + 4*2*6 – 1 + 47*26 + 47*26*26 + 47*26*26*26.</p>
<p>The first part of the answer can be calculated in O(n) where n is length of given string using the following pseudocode.</p>
<pre><code> for(j=0;j<str.length();++j)
{
temp*=(str[j]-96);
ans+=temp;
}
</code></pre>
<p>The second part can be calculated using the formula for the sum of GP. Since L can be very large modular exponentiation can be used to do this in O(log L).
Also the term 25 in the denominator while calculating the GP sum would have to be taken care of. For this inverse modulus can be used also logarithmic time.</p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/viewsolution/3385335">here</a>. </p>sikander_nsitTue, 11 Feb 2014 03:54:38 +0530https://discuss.codechef.com/questions/38237/cdz14b-editorialmoduloeditorialsimple-mathcdzl14easy-mediumcdz14bCDZ14C - Editorialhttps://discuss.codechef.com/questions/38239/cdz14c-editorial<h1>PROBLEM LINKS:</h1>
<p><a href="http://www.codechef.com/problems/CDZ14C">Practice</a><br>
<a href="http://www.codechef.com/CDZL2014/problems/CDZ14C">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY-MEDIUM</p>
<h1>PROBLEM:</h1>
<p>Given a 2D matrix consisting of 0 and 1 find the shortest path from (1,1) to (n,m) such that the path should consist of alternate 0 and 1.</p>
<h1>EXPLANATION:</h1>
<p>This was a standard BFS problem. In the question the condition was that if Eon is standing in a room marked ‘0’ then he can only go to a room marked ‘1’ and if he is in room ‘1’ then he must go to a room marked ‘0’. So he had to travel from (1,1) to (n,m) with alternate ‘0’ and ‘1’. </p>
<p>Start the BFS at (1,1). Visit the current node. Check all 4 adjacent cells. If different than the current cell then push its coordinates in the queue. We can keep 2D DP array to store the minimum distance of every cell from (1,1). Whenever a cell(i,j) is visited DP[i][j] is updated and its neighbours if valid are pushed into the queue. This will be O(nm) complexity. At the end we can simply print dp[n][m] and if it is not visited then it means there was no path so print “-1”.</p>
<p>The property of BFS which is used here is that BFS visits every node with shortest distance from the source. DFS can timeout if not implemented properly when the whole maze is made up of alternate 1s and 0s.</p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/viewsolution/3385385">here</a>. </p>sikander_nsitTue, 11 Feb 2014 04:08:15 +0530https://discuss.codechef.com/questions/38239/cdz14c-editorialbfscdzl14easy-mediumeditorialcdz14cCDZ14D - Editorialhttps://discuss.codechef.com/questions/38240/cdz14d-editorial<h1>PROBLEM LINKS:</h1>
<p><a href="http://www.codechef.com/problems/CDZ14D">Practice</a><br>
<a href="http://www.codechef.com/CDZL2014/problems/CDZ14D">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a></p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM</p>
<h1>PROBLEM:</h1>
<p>In this problem, we had to find the count of numbers between a range[R,L] such that their GCD with N is X. </p>
<h1>EXPLANATION:</h1>
<p>It would be the same as finding the count of numbers between L/X and R/X such that their GCD with N/X is 1. This is because if divide two numbers by their GCD then the resulting numbers would be coprime. So the task remains to find the count of numbers between a range which are coprime to N. </p>
<p>Let f(C) be the number of integers from 1 to A which are coprime to N. <br>So we can calculate our answer as f(R)-f(L-1).
f(C) is A minus the number of integers that are not relatively prime to N.
Call this number g(C). So f(C)=C−g(C). We attack the problem of finding g(C).</p>
<p>If N is a prime power p^a, it is easy. <br>The numbers in the interval [1,C] that are not relatively prime to N are the multiples of p.<br>
Thus</p>
<blockquote>
<p>g(C)=⌊C/p⌋</p>
</blockquote>
<p>where ⌊x⌋ is the usual "floor" function.</p>
<p>If N has prime power factorization p^a*q^b, where p and q are distinct primes, then g(C) is the number of integers in [1,C] that are divisible by p or q or both. By Inclusion/Exclusion, we obtain</p>
<blockquote>
<p>g(C)=⌊C/p⌋+⌊C/q⌋−⌊C/pq⌋.</p>
</blockquote>
<p>The reason is that when we add the first two terms above, we are counting twice all the multiples of pq.</p>
<p>If N has prime power factorization p^a*q^b*r^c, the same basic idea works. We get</p>
<blockquote>
<p>g(C)=⌊C/p⌋+⌊C/q⌋+⌊C/r⌋−⌊C/qr⌋−⌊C/pr⌋−⌊C/pq⌋+⌊C/pqr⌋.</p>
</blockquote>
<p>The number of distinct primes for a number less than 10^9 will not be greater than 9. So bitmasking can be used to calculate all product combinations and then calculating f(R) and f(L-1). Each query can be answered in <br>
O(2^number of distinct primes).</p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/viewsolution/3385409">here</a>. </p>sikander_nsitTue, 11 Feb 2014 04:20:25 +0530https://discuss.codechef.com/questions/38240/cdz14d-editorialmediumbitmaskingnumber-theorycdz14dcdzl14editorialCDZ14E - Editorialhttps://discuss.codechef.com/questions/38243/cdz14e-editorial<h1>PROBLEM LINKS:</h1>
<p><a href="http://www.codechef.com/problems/CDZ14E">Practice</a><br>
<a href="http://www.codechef.com/CDZL2014/problems/CDZ14E">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/sikander_nsit">sikander_nsit</a></p>
<h1>DIFFICULTY:</h1>
<p>MEDIUM</p>
<h1>PROBLEM:</h1>
<p>In the problem we had to find the sum of the smallest k elements in the given array range. </p>
<h1>EXPLANATION:</h1>
<p>Brute force solution would not work because of the constraints. Segment tree can be used for this.</p>
<p>Each node of the segment tree will consist of two arrays : first is the list of elements in the range in sorted order and the second stores the cumulative sum. </p>
<p>For every query we can find a list of S sorted arrays such that their union is the given range in query [L,R].</p>
<pre><code> 1. Go through all the arrays and if any have length > k, truncate to length k .
2. Identify the largest remaining array A. If more than one, pick one.
3. Pick the middle element M of the largest array A.
4. Use a binary search on the remaining arrays to find the same element (or the smallest element > M).
5. Based on the indexes of the various elements, calculate the total number of elements <= M. This should give you B, the count of numbers <= M.
6. If k < B, truncate all the arrays at the split points you've found and iterate on the smaller arrays (use the bottom halves).
7. If k > B, truncate all the arrays at the split points you've found and iterate on the smaller arrays (use the top halves, and search for element (k-B)). Add the cumulative sums till the split points to the answer.
</code></pre>
<p>When you get to the point where you only have one element per array (or 0), make a new array of size n with those data, sort, and calculate the sum of first k elements.
Because you're always guaranteed to remove at least half of one array, in S iterations, you'll get rid of half the elements. That means there are S log k iterations. Each iteration is of order S log k (due to the binary searches), so the whole thing is S^2 (log k)^2 in worst case. But the actual performance would be much better than the worst case.</p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/viewsolution/3385422">here</a>. </p>sikander_nsitTue, 11 Feb 2014 04:37:38 +0530https://discuss.codechef.com/questions/38243/cdz14e-editorialmediumsegment-treecdz14ecdzl14editorialdivide-and-conqHow is this solution getting AC?https://discuss.codechef.com/questions/41553/how-is-this-solution-getting-ac<p><a href="http://www.codechef.com/viewsolution/3784470">http://www.codechef.com/viewsolution/3784470</a></p>
<p>Can somebody tell me how is this getting accepted. I ran it on ideone and it is giving wrong answer for the sample test cases.</p>sikander_nsitMon, 21 Apr 2014 01:00:19 +0530https://discuss.codechef.com/questions/41553/how-is-this-solution-getting-acproblemaprilcookoffBug in long challenge contest pagehttps://discuss.codechef.com/questions/49117/bug-in-long-challenge-contest-page<p>The number of successful submissions for sereja and shuffling has suddenly become more than 400 on the contest page but only 45 correct submissions are shown on the problem page. Here are the screenshots.</p>
<p><img alt="contest page" src="http://discuss.codechef.com/upfiles/temp_5.png"></p>
<p><img alt="problem page" src="http://discuss.codechef.com/upfiles/temp2_1.png"></p>
<p><a href="/users/1/admin">@admin</a> Please have a look at this and resolve the issue.</p>sikander_nsitThu, 07 Aug 2014 01:56:10 +0530https://discuss.codechef.com/questions/49117/bug-in-long-challenge-contest-pageaugust14buglong-contestTimings of ICPC onsite regional contestshttps://discuss.codechef.com/questions/55102/timings-of-icpc-onsite-regional-contests<p>What are the exact timings for the ACM ICPC onsite regional contests, both the practice and the main contest for all the three sites. Please share an official source if possible.</p>sikander_nsitSun, 09 Nov 2014 23:11:31 +0530https://discuss.codechef.com/questions/55102/timings-of-icpc-onsite-regional-contestsonsiteregionalsacm-icpcSamsung Hiring Challenge 2nd Roundhttps://discuss.codechef.com/questions/134709/samsung-hiring-challenge-2nd-round<p>Anybody got an email for Samsung onsite test? I have received an email from a Muniraju M for the Samsung Software Competency Test and I wanted to know if that mail is the result of the online hiring challenge on Codechef or something random. The center is quite far from my place, so I want to know if the trip would be worth the trouble.</p>sikander_nsitFri, 31 Aug 2018 19:55:26 +0530https://discuss.codechef.com/questions/134709/samsung-hiring-challenge-2nd-roundhiringchallengesamsung