Solving the ODD problem in the easy section, using STL - list

general
, ,
1

Ok, so want to solve this problem - http://www.codechef.com/problems/DCE05
Basically I want to remove the elements present in odd positions from a LIST.
So, i used erase and STL to do it.
But it’s showing me time limit exceeded. Now, I there is another method to do it, but i would really appreciate if someone could tell me how to make my STL code efficient?

#include<iostream>
#include<list>
using namespace std;

int compute(int num)
{
list<int> L;
list<int>::iterator i;

for(int k=1;k<=num;k++)
{
	L.push_back(k);
}

int k=1;

while(L.size()!=2)
{
	i=L.begin();

	while(i!=L.end())
	{
		if(k%2!=0)
			i=L.erase(i);
		else
			i++;
		k++;
	}
}


return L.back();

 }

int main()
{
int testcases,AR[1000];
scanf("%d",&testcases);
int num;
for(int i=1 ; i<=testcases ; i++)
{
	scanf("%d",&num);
	AR[i]=compute(num);
}

for(int i=1;i<=testcases ; i++)
{
	printf("%d\n",AR[i]);
}

return 0;
}
1 Like
2

Hello shashvat92,

I think that maybe you’re looking at this problem from an incorrect perspective… i.e., all your code is efficientely written, you are using the right I/O statements, however, you still have TLE… Have you tried to work some formulas on paper that can give you the position where you need to stand directly from the input value N? :wink: There’s a very clever way of solving this problem and I wrote a tutorial for it in the tutorials section, but first I recommend you to try and solve it on your own :smiley:

Best of luck,

Bruno

1 Like