Questions asked by sandeep9https://discuss.codechef.com/questions/asked-by/52053/sandeep9/?type=rssQuestions asked by <a href="/users/52053/sandeep9" >sandeep9</a>enSun, 26 Feb 2017 18:10:33 +0530RRSTONE ERROR EVEN THOUGH THE CODE IS CORRECT!https://discuss.codechef.com/questions/42579/rrstone-error-even-though-the-code-is-correct<p>SEE my code for RRSTONE,Its working very well but why codechef is showing wrong result!!!</p>
<h1>include<stdio.h></h1>
<h1>include<stdlib.h></h1>
<p>int main()
{
long int n,k;
long int max=0,i=0,j=0;
scanf("%ld%ld",&n,&k);
long int <em>A=(long int </em>)calloc(n,sizeof(int));
while(i<n)
{
scanf("%ld",&A[i]);
i++;
}
x:
i=0;
max=A[i];
while(i<n)
{</p>
<pre><code>if(max<A[i])
{
max=A[i];
i++;
}else {
max=max;
i++;
}
}
i=0;
if(k!=0)
{j=0;
while(j<n)
{
A[j]=max-A[j];
j++;
}if(k%2==0)
{
k++;
goto x;
}
} else{ goto r;
}
r:
j=0;
while(j<n)
{
printf("%ld ",A[j]);
j++;
}return(0);
}
</code></pre>sandeep9Mon, 12 May 2014 16:19:25 +0530https://discuss.codechef.com/questions/42579/rrstone-error-even-though-the-code-is-correctrrstonecodechef BUY1 GET1 problemhttps://discuss.codechef.com/questions/43920/codechef-buy1-get1-problem<p>I am very much frustrated now..Please tell me what's wrong with my code?
<a href="http://www.codechef.com/viewsolution/3969611">http://www.codechef.com/viewsolution/3969611</a>
Its working fine on my lappy,but codechef is showing error.:-(</p>sandeep9Wed, 04 Jun 2014 15:50:55 +0530https://discuss.codechef.com/questions/43920/codechef-buy1-get1-problembuy1get1WA IN STATUES,even though everything seems to be righthttps://discuss.codechef.com/questions/49727/wa-in-statueseven-though-everything-seems-to-be-right<p>What is wrong with this code?</p>
<p><a href="http://www.codechef.com/viewsolution/4567062">http://www.codechef.com/viewsolution/4567062</a></p>
<p>its hard to understand why codechef is giving wrong answer for this?</p>
<p>The question can be found at</p>
<p><a href="http://www.codechef.com/problems/STATUES">http://www.codechef.com/problems/STATUES</a></p>sandeep9Sat, 16 Aug 2014 02:59:40 +0530https://discuss.codechef.com/questions/49727/wa-in-statueseven-though-everything-seems-to-be-rightacm-icpcSuraj sharma contesthttps://discuss.codechef.com/questions/53069/suraj-sharma-contest<p>What type of contest is this? Everything seems to be fake,do anyone know anything about this contest? Or somebody has organised it just for fun??</p>sandeep9Mon, 13 Oct 2014 23:07:42 +0530https://discuss.codechef.com/questions/53069/suraj-sharma-contestcontesthow to tackle a problem using recursionhttps://discuss.codechef.com/questions/53162/how-to-tackle-a-problem-using-recursion<p>I have started dynamic programming,then i found that in most of the problems related to dynamic programming there is heavy use of <a href="http://recursion.So">recursion.So</a> i thought to grip recursion,and I am finding it a bit difficult to tackle,So can anyone please help me in understanding how recursion works,and how to approach for the recuurence relation used in most of the recursion.Like i was trying to understand the solution of this problem via recursion
<a href="http://www.spoj.com/problems/DANGER/">http://www.spoj.com/problems/DANGER/</a> (JOSEPHUS PROBLEM),
and i wonder how to come out the recuurence relation of such type of problems.
Thanks in Advance</p>sandeep9Tue, 14 Oct 2014 17:37:53 +0530https://discuss.codechef.com/questions/53162/how-to-tackle-a-problem-using-recursionrecursionTechfest screening roundhttps://discuss.codechef.com/questions/53249/techfest-screening-round<p>What happened to the results of techfest screening round? They have not put the results either in codechef or their own website.Why this delay even though the results of portal round were declared within a day or two.</p>sandeep9Wed, 15 Oct 2014 17:34:52 +0530https://discuss.codechef.com/questions/53249/techfest-screening-roundexternalcontestACM GWALIOR(online) TRIAL ROUNDhttps://discuss.codechef.com/questions/54434/acm-gwalioronline-trial-round<p>When is the trial round for ACM Gwalior preliminary online round scheduled? The main contest is on 1st nov and today is 30th oct,but still we didn't get the login credentials(neither of the trial nor the final round)!</p>sandeep9Thu, 30 Oct 2014 10:56:07 +0530https://discuss.codechef.com/questions/54434/acm-gwalioronline-trial-roundacm-icpcTentative Selection List of ACM-ICPC Kanpurhttps://discuss.codechef.com/questions/54573/tentative-selection-list-of-acm-icpc-kanpur<p>Can someone provide the tentative selection List of ACM KAN 14 held today?</p>sandeep9Sat, 01 Nov 2014 17:05:02 +0530https://discuss.codechef.com/questions/54573/tentative-selection-list-of-acm-icpc-kanpurkan14acm-icpcseaperm2 Doubthttps://discuss.codechef.com/questions/55368/seaperm2-doubt<p>What are the constraints over the value of p[i]?And also tell that in the input q[1],q[2] is serially given or its random shuffle like q[2],q[1],q[3] is given? Somebody help,i have already got 3 WA.</p>sandeep9Fri, 14 Nov 2014 20:51:55 +0530https://discuss.codechef.com/questions/55368/seaperm2-doubtseaperm2PRIME1 getting TLE!!!https://discuss.codechef.com/questions/70184/prime1-getting-tle<p>I dont know why my solution is geting TLE!!!Please have a look <a href="http://www.codechef.com/viewsolution/6943810">http://www.codechef.com/viewsolution/6943810</a></p>
<p>I am implementing sieve of erasothenes to caclulate primes upto sqrt(10^9) and then applying these primes in the given segment to print all prime no's..then why it's giving TLE?? where is my code getting slow and how to correct that..Please help</p>sandeep9Thu, 21 May 2015 15:59:16 +0530https://discuss.codechef.com/questions/70184/prime1-getting-tleprime1sieveStucked in SPOJ GSS1https://discuss.codechef.com/questions/71412/stucked-in-spoj-gss1<p>I have read and implemented segment trees recently and i am trying to solve this problem(GSS1) in spoj but wasn't able to solve it..Then i read from different sources on internet on how to solve this problem but isn't able to understand the combine part and why it works!!
<a href="http://tiny-code.blogspot.in/2013/07/spoj-1043can-you-answer-these-queries-i.html">http://tiny-code.blogspot.in/2013/07/spoj-1043can-you-answer-these-queries-i.html</a>
can anyone please help me with an example on how to write the combine part?
I am stucked in this problem since the last 2 days.</p>sandeep9Fri, 12 Jun 2015 14:06:04 +0530https://discuss.codechef.com/questions/71412/stucked-in-spoj-gss1segment-treegss1Difference between these 2 codes?https://discuss.codechef.com/questions/71466/difference-between-these-2-codes<p>Link to problem:<a href="https://www.hackerrank.com/challenges/counter-game">https://www.hackerrank.com/challenges/counter-game</a>
The first solution is mine which isn't being accepted while the second one is the AC solution.What's the difference between them!!!</p>
<p>This is my solution</p>
<p>#include<bits stdc++.h="">
using namespace std;
int main()</p>
<p>{</p>
<p>unsigned long long int n,temp=0,count=0,p_count=0,winner=1;</p>
<p>int t;</p>
<p>scanf("%d",&t);</p>
<p>while(t--)
{</p>
<p>winner=1;</p>
<pre><code>scanf("%llu",&n);
while(n!=1)
{
if((n&(n-1))==0) // n is a power of 2
{
n/=2;
}
else
{
n=n-pow(2,floor(log2(n)));
count++;
}
winner=!winner;
}
if(winner)
puts("Richard");
else
puts("Louise");
</code></pre>
<p>}
return 0;
} </p>
<p>The correct solution</p>
<h1>include<bits stdc++.h=""></h1>
<p>using namespace std;</p>
<p>int main()</p>
<p>{</p>
<pre><code>int t;
scanf("%d",&t);
while(t--)
{
unsigned long long n;
scanf("%llu",&n);
unsigned long long k ;
int winner = 1; //1 - richard 0 - louise
while(n!=1)
{
if( n && !(n&(n-1)))
n/=2;
else
{
k = pow(2,floor(log2(n)));
n-=k;
}
if(winner)
winner = 0;
else
winner = 1;
}
if(winner)
printf("Richard\n");
else
printf("Louise\n");
}
return 0;
</code></pre>
<p>}</p>sandeep9Sat, 13 Jun 2015 14:19:15 +0530https://discuss.codechef.com/questions/71466/difference-between-these-2-codesbitmaskingRange update and query without segment or fenwick tree?https://discuss.codechef.com/questions/71534/range-update-and-query-without-segment-or-fenwick-tree<p>Link to problem:
<a href="https://www.hackerrank.com/challenges/crush">https://www.hackerrank.com/challenges/crush</a></p>
<p>I tried to solve this problem using segment tree with lazy propogation but wasn't able to get full points because of the huge constraints in the problem(10^7),so finally i read the editorial here
<a href="https://www.hackerrank.com/challenges/crush/editorial">https://www.hackerrank.com/challenges/crush/editorial</a>
but isn't getting it and how the concept works.can anyone please explain me how we are maintaining prefix sum's and getting the max in required range?
Thaks in advance. :)</p>sandeep9Sun, 14 Jun 2015 20:41:56 +0530https://discuss.codechef.com/questions/71534/range-update-and-query-without-segment-or-fenwick-treeprefix-sumsortingPrime equivalency in hackerrankhttps://discuss.codechef.com/questions/73143/prime-equivalency-in-hackerrank<p>Link to question:
<a href="https://www.hackerrank.com/contests/ode-to-code-finals/challenges/prime-equivalency">https://www.hackerrank.com/contests/ode-to-code-finals/challenges/prime-equivalency</a></p>
<pre><code>#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll a[10000003];
vector<long long int> v;
void sieve(ll start,ll end)
{
int i=0,j=0,sum=1;
a[1]=0;
if(start==1)
start+=1;
for(i=(start);i<=end;i++)
{
if(a[i]!=i)
continue;
for(j=(2*i);j<=end;j+=i)
{
a[j]=0;
}
a[i]=1;
</code></pre>
<p>}
}</p>
<pre><code>int main()
{
ll n=10000000,i=0,j=0,k=0,t=0,l=0,r=0,count=0;
//ios_base::sync_with_stdio(0);
for(i=1;i<=n;i++)
a[i]=i;
sieve(2,n);
for(i=2;i<=n;i++)
a[i]=a[i-1]+a[i]; //prefix_sum array
//k=v.size();
//for(i=1;i<=10;i++)
// cout<<a[i]<<" ";
cin>>t;
while(t--)
{
scanf("%lld %lld",&l,&r);
l=(ll)sqrt(l);
r=(ll)sqrt(r);
printf("%lld\n",a[r]-a[l]);
}
return 0;
}
</code></pre>
<p>This is my solution..I am applying sieve to generate all prime numbers upto 10^7 and then maintaining a prefix array which stores the number of primes calculated till now(as the constraints are too large)..The solution is running well on the first 2 test cases,but givin WA on the 3rd,seems there is some minor error..can anyone please help me,where i am getting wrong and how to modify it?</p>sandeep9Sat, 18 Jul 2015 11:24:50 +0530https://discuss.codechef.com/questions/73143/prime-equivalency-in-hackerrankprimehackerrankgenerating all combinations of size r from n elements?https://discuss.codechef.com/questions/73286/generating-all-combinations-of-size-r-from-n-elements<p>Can anyone tell me an efficient method and implementation of how to generate all combinations of size r from a given array of n elements?</p>sandeep9Wed, 22 Jul 2015 18:18:05 +0530https://discuss.codechef.com/questions/73286/generating-all-combinations-of-size-r-from-n-elementscombinationsSubset sum problemhttps://discuss.codechef.com/questions/73316/subset-sum-problem<p>Problem Link-<a href="https://www.hackerrank.com/contests/ode-to-code-finals/challenges/rahul-and-another-sum">https://www.hackerrank.com/contests/ode-to-code-finals/challenges/rahul-and-another-sum</a></p>
<p>Well using bit masking gives correct results for upto n=27-28,and we can't use dp approach here..So how to solve this problem for 100 marks?</p>sandeep9Fri, 24 Jul 2015 00:53:49 +0530https://discuss.codechef.com/questions/73316/subset-sum-problemsubset-sumA doubtregarding MMI(modulo multiplacative inverse)https://discuss.codechef.com/questions/73431/a-doubtregarding-mmimodulo-multiplacative-inverse<p>Is calculating MMI of 2**n through pow(pow(2,n),M-2,M) and pow(pow(2,n),M-1,M) is same,when do we use M-1 and when do we use M-2,given that 2 and M are co-prime.
See this question
<a href="https://www.hackerrank.com/challenges/number-of-subsets">https://www.hackerrank.com/challenges/number-of-subsets</a>
Here is lalit kundu's solution.Why p-1 instead of p-2?
<a href="https://www.hackerrank.com/rest/contests/infinitum10/challenges/number-of-subsets/hackers/xorfire/download_solution">https://www.hackerrank.com/rest/contests/infinitum10/challenges/number-of-subsets/hackers/xorfire/download_solution</a></p>sandeep9Tue, 28 Jul 2015 15:49:40 +0530https://discuss.codechef.com/questions/73431/a-doubtregarding-mmimodulo-multiplacative-inversemmiStucked in FloorI4https://discuss.codechef.com/questions/73586/stucked-in-floori4<p>Problem Link:
<a href="https://www.codechef.com/SEPT14/problems/FLOORI4/">https://www.codechef.com/SEPT14/problems/FLOORI4/</a></p>
<p>I am not getting the concept to solve this question. i also tried to read the editorials and solutions but all in vain.Can anyone please explain me in detail how to solve this and what is the tricky thing that needs to be observed??</p>sandeep9Wed, 05 Aug 2015 17:38:06 +0530https://discuss.codechef.com/questions/73586/stucked-in-floori4ad-hocEditorials please....https://discuss.codechef.com/questions/73742/editorials-please<p>After 10 days of struggle we have been waiting for the editorials for AUG15,but its not out yet..Please post it as soon as possible..</p>sandeep9Mon, 17 Aug 2015 16:20:37 +0530https://discuss.codechef.com/questions/73742/editorials-pleaseeditorialsPrerequisities for FFT?https://discuss.codechef.com/questions/73806/prerequisities-for-fft<p>Recently i have seen a lot of questions being asked on fast fourier transforms. I have tried to read and understand it from T. cormen's book(Introduction to algorithms) but i think it requires some other concepts of mathematics too and thus i was unable to proceed.Can anyone please tell me what are the prerequisities before learning fast fourier transforms?</p>sandeep9Tue, 18 Aug 2015 07:36:54 +0530https://discuss.codechef.com/questions/73806/prerequisities-for-fftfftThis is really frustrating codechef! :(https://discuss.codechef.com/questions/74626/this-is-really-frustrating-codechef<p>I have never got so many wrong answers but then this question came <a href="http://www.codechef.com/LTIME27/problems/CLOST">www.codechef.com/LTIME27/problems/CLOST</a> on codechef(LTIME27).Still i am not able to find a test case where my code fails.Please someone find a test case for me..I have matched with all the test cases(in the first 2 pages) of the editorial page of this probelm and all those cases works fine in my code..Link to my code:
<a href="https://www.codechef.com/viewsolution/7951755">https://www.codechef.com/viewsolution/7951755</a>
To add fuel to the fire One solution from my college mate:
<a href="https://www.codechef.com/viewplaintext/7956106">https://www.codechef.com/viewplaintext/7956106</a>
(accepetd by codechef)
is giving wrong answer at
1
10 4
3 6
2 9
4 5
8 9
output:
((()()()()</p>
<p>while mine is giving correct answer (Wrong answer by codechef):
1
10 4
3 6
2 9
4 5
8 9
output:
()((()))()</p>
<p>Isn't this frustrating codechef?</p>
<p>Please someone find a test case where my code fails..(I have tried a lot).That will be really helpful codechef..</p>sandeep9Mon, 31 Aug 2015 20:40:56 +0530https://discuss.codechef.com/questions/74626/this-is-really-frustrating-codechefratingsDoubt in LIGHTHSE test cases.https://discuss.codechef.com/questions/74787/doubt-in-lighthse-test-cases<p>Many people in this problem have scored 85/100 points..It means that they have solved the larger set but failed in the smaller set which is itself a subset of the larger set...Can anyone explain how can this happen if the test cases are set properly..(Means smaller subtask is also a part of the larger subtask).Although if what i doubt is correct i would suggest the codechef team to append the smaller subtask of this problem into the larger subtask and rejudging the solutions then...</p>sandeep9Sun, 06 Sep 2015 20:51:04 +0530https://discuss.codechef.com/questions/74787/doubt-in-lighthse-test-caseslighthseDoubt in c++https://discuss.codechef.com/questions/75178/doubt-in-c<p>Why something like printf("%.0f\n",pow(2,1001)) gives correct output even though it is supposed to give correct output upto pow(2,64)?</p>sandeep9Sat, 19 Sep 2015 01:06:35 +0530https://discuss.codechef.com/questions/75178/doubt-in-cc++Why my recurrence is getting wrong?https://discuss.codechef.com/questions/77941/why-my-recurrence-is-getting-wrong<p>I was solving this question on hackerearth -
<a href="https://www.hackerearth.com/problem/algorithm/supernatural-squad-2/description/">https://www.hackerearth.com/problem/algorithm/supernatural-squad-2/description/</a></p>
<p>I came through the recurrence relation
(doesn't works correctly</p>
<pre><code>if(dp[N][K] != -1)
return dp[N][K];
if(K == 0)
return 0;
if(K > N)
return 0;
if(N == K)
return 1;
else
{
dp[N-K][K] = solve(N-K,K); // Kth number is selected,problem reduced to subproblem with new sum as N - K
dp[N][K - 1] = solve(N,K - 1); // Kth number isn't selected,we need to explore upto (K - 1) now
dp[N][K] = dp[N-K][K] + dp[N][K - 1];
return dp[N][K];
}
</code></pre>
<p>instead of(works fine)</p>
<pre><code>if(dp[N][K] != -1)
return dp[N][K];
if(K == 0)
return 0;
if(K > N)
return 0;
if(N == K)
return 1;
else
{
dp[N-K][K] = solve(N-K,K);
dp[N][K + 1] = solve(N,K + 1);
dp[N][K] = dp[N-K][K] + dp[N][K + 1];
return dp[N][K];
}
</code></pre>
<p>Whats the difference between 2 approaches for solving the above problem?</p>sandeep9Wed, 23 Dec 2015 16:05:00 +0530https://discuss.codechef.com/questions/77941/why-my-recurrence-is-getting-wrongcombinatoricsdynamic-programmingHow this algorithm for LIS works ?https://discuss.codechef.com/questions/81476/how-this-algorithm-for-lis-works<p>This is the O(n*lg(n)) solution for Longest Increasing subsequence taken from The Hitchhikerâ€™s Guide to the Programming Contests (note: this implementation assumes there are no duplicates in the list):</p>
<pre><code>enter code here
set<int> st;
set<int>::iterator it;
st.clear();
</code></pre>
<p>for(i=0; i<n; i++) {
st.insert(array[i]);
it=st.find(array[i]);
it++;
if(it!=st.end()) st.erase(it);
}
cout<<st.size()<<endl;</p>
<p>I am not able to understand why this algorithm works? Can anybody help me out?</p>sandeep9Wed, 18 May 2016 09:15:20 +0530https://discuss.codechef.com/questions/81476/how-this-algorithm-for-lis-worksdynamic-programmingSnackdown pre Elimination Round B Editorialshttps://discuss.codechef.com/questions/82161/snackdown-pre-elimination-round-b-editorials<p>Can anyone please tell by when we can expect the editorials of <a href="https://www.codechef.com/SNCKPB16..">https://www.codechef.com/SNCKPB16..</a> I have few doubts regarding the solutions and i wanna ask them there.
Thanks in advance</p>sandeep9Tue, 14 Jun 2016 10:42:49 +0530https://discuss.codechef.com/questions/82161/snackdown-pre-elimination-round-b-editorialssnckpb16snackdownWrong answer in SPOJ HORRIBLEhttps://discuss.codechef.com/questions/82730/wrong-answer-in-spoj-horrible<p>Everything seems fine to me,still am getting WA..Can someone help ?
My code :
<a href="http://ideone.com/emfOqD">http://ideone.com/emfOqD</a></p>sandeep9Tue, 28 Jun 2016 14:59:03 +0530https://discuss.codechef.com/questions/82730/wrong-answer-in-spoj-horriblesegment-treeADDMUL Wrong Answer Codechefhttps://discuss.codechef.com/questions/82739/addmul-wrong-answer-codechef<p>Hi, I have been trying hard to solve the subtask 3 (for 30 points) of the problem
<a href="https://www.codechef.com/problems/ADDMUL">https://www.codechef.com/problems/ADDMUL</a></p>
<p>I have implemented segment tree with lazy propogation and everything seems fine..But still getting WA.
Can anyone find a test case where the solution not works or any mistake in the code?
(Please keep in mind that the solution is targeted for Subtask 3 only i.e queries of type 3 will not be there).</p>
<p>My solution goes here <a href="https://www.codechef.com/viewsolution/10636427">https://www.codechef.com/viewsolution/10636427</a></p>sandeep9Tue, 28 Jun 2016 20:49:07 +0530https://discuss.codechef.com/questions/82739/addmul-wrong-answer-codechefsegment-treejuly15can someone share their Approach to POLYEVAL?https://discuss.codechef.com/questions/82994/can-someone-share-their-approach-to-polyeval<p>I was astonished after seeing this problem as this problem basically asks to calculate the convolution of the given polynomial with a constrained K. I know about fast fourier transform to multiply two polynomial in O(nlogn) but there we used the idea of nth roots of unity in place of some random K, to reduce the input size by half in each level of recurrence. But, if we are constrained to choose a paricular K, how to sample N points in better than O(N^2)!!! Also what does it means to "design" a DFT which works on some particular Modulo?</p>sandeep9Wed, 13 Jul 2016 15:41:16 +0530https://discuss.codechef.com/questions/82994/can-someone-share-their-approach-to-polyevaldftfftHelp required in this questionhttps://discuss.codechef.com/questions/92053/help-required-in-this-question<p>Hi i am stucked in this problem <a href="https://www.hackerrank.com/contests/h42-finals/challenges/mathematical-graph.">https://www.hackerrank.com/contests/h42-finals/challenges/mathematical-graph.</a> Can anyone suggest an approach.. I tried to calculate all the divisors of each no upto 10^6,but that's a bit slow. What can be a faster approach to solve this ?</p>sandeep9Sun, 26 Feb 2017 18:10:33 +0530https://discuss.codechef.com/questions/92053/help-required-in-this-questionprimesieve