11491 - Erasing and Winning

[FAQ]

Keep WA, could anyone tell me some tricky cases please?

[Robert Gerbicz]

Greedy method.

[FAQ]

I know, but still WA

[FAQ]

ACed at last, some cases for who still getting stuck

Code: Select all

2 1
80
10 2
4824551711
16 3
4614232216857618
10 5
9954312334
2 1
38
8 2
27793198
17 12
62860248650900613
9 6
644606618
5 4
33788
3 2
935
7 2
8999900
5 1
18919
5 2
18919
5 3
18919
5 4
18919
3 1
101
12 5
110101010001
12 7
110101010001
7 3
9198810
10 8
1000000000
5 2
19090
10 8
1239498711
10 9
1239498711
10 9
1111111111
6 3
100010
2 1
91 
6 3
119219
5 2
12919
4 1
9321 
4 2
3759
6 3
123123
7 4
1000000
0 0

Code: Select all

8
84551711
6432216857618
99544
8
793198
90613
668
8
9
99990
8919
919
99
9
11
1111101
11111
9988
10
990
99
9
1
110
9
929
919
932
79
323
100

[bleedingeyes]

please help
got TLE

Code: Select all

#include<stdio.h>

int main()
{
	long a,b,i,j,k;
	char data[1000000];


//	freopen("in.txt","r",stdin);

	while(scanf("%ld %ld%*c",&a,&b)==2)
	{
		if(a==0 && b==0) 
			break;

		scanf("%s",&data);
		
		for(i=0;i<a;i++)
		{
			if(!b) break;

			for(j=i+1;j<i+1+1;j++)
			{
				if(data[i]<data[j])
				{
					for(k=i;k<a-1;k++)
						data[k]=data[k+1];
					data[k]='\0';
					a--;
					b--;
					if(i==0)
						i=-1;
					else
						i=i-2;
					break;
				}
			}

		}

		if(b)
			data[a-b]='\0';


		printf("%s\n",data);
	}

	return 0;
}

[baodog]

http://www.topcoder.com/tc?module=Stati ... onAncestor

See tutorial here, replace with O(lgn) or O(1) op for each max find.

[Chirag Chheda]

Can someone please help me on this question. I have passed all the test cases posted here on the forum but still getting a WA.Please help me.

Code: Select all

#include<iostream>
#include<cmath>

using namespace std;

int main()
{
    int n,d,i,j,k,p,mi;
    char c;
    bool f;
    while(scanf("%d %d",&n,&d)==2 && n && d)
    {
          char arr[n];
          
          for(i=0;i<n;i++)
          cin>>arr[i];
          
          p=(int)sqrt(n);          
          int M[p+1];
          
          for(j=0;j<p;j++)
          {
                mi = j*p;
                for(i=mi+1;i<(j+1)*p;i++)
                {
                      if(arr[mi]<arr[i])
                      mi=i;
                }
                M[j]=mi;
          }
          
          mi=(p*p);
          for(i=mi+1;i<n;i++)
          {
                 if(arr[mi]<arr[i])
                 mi=i;
          }
          M[p]=mi;
          
          i=0;
          while(d>0)
          {
                if(i+d+1>n)
                {
                n-=d;
                break;
                }

                mi=i;
                j=i;

                f=0;
                if(i!=0)
                {
                        while(j%p!=0)
                        {
                             if(arr[j]>arr[mi])
                             mi=j;

                             j++;

                             if(j>i+d+1)
                             {
                             f=1;
                             break;
                             }
                        }
                }

                while(f==0 && i+d>=j+p-1)
                {
                        if(arr[mi]<arr[M[j/p]])
                        mi= M[j/p];
                        j+=p;
                }
                
                while(f==0 && j<=i+d)
                {
                        if(arr[mi]<arr[j])
                        mi=j;
                        j++;
                }
                c = arr[mi];

                for(k=i;arr[k]!=c;k++)
                {
                     d--;
                     arr[k]='!';
                }
                i=k+1;
          }

          for(i=0;i<n;i++)
          if(arr[i]!='!')
          cout<<arr[i];
          printf("\n");
    }
    return 0;
}

Thanking u in advance

[andysoft]

Hi there!
I was trying hard to solve the problem, now got AC, thanks to baodog, who posted link to TopCoder manual.

But my time is something about 0.880, and I see guys with absolute zero time and 0.020 and so on. My question is, how to improve the solution so that it counts answer in such a minimal time? What solution method was used to get such a small time?

Thanx ))

[mmonish]

But my time is something about 0.880, and I see guys with absolute zero time and 0.020 and so on. My question is, how to improve the solution so that it counts answer in such a minimal time? What solution method was used to get such a small time?

I used link list(manually by pointer) which takes .170 sec. one of my friend got AC in .040 sec using array(implemented as linked list).

[Chirag Chheda]

Can someone please post some more test cases. My code is posted above. I have passes all the test cases posted here but unable to get an ACC

[sijal]

hi
why TLE ?
is there any infinite loop in my algorithm ? or there is a problem about my algorithm ?
thnx

Code: Select all

ACC

[mak(cse_DU)]

http://www.topcoder.com/tc?module=Stati ... onAncestor

See tutorial here, replace with O(lgn) or O(1) op for each max find.

Thanks Baodog && FAQ .

[Igor9669]

Please tell me why I got TLE???
My algo is O(2*N)....
Here is my code:

Code: Select all

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

string s;

int main(){
//freopen("win.in","r",stdin); freopen("win.out","w",stdout);
int i,n,j,k,len,del,x,y;
bool ok;
while(1)
{
	ok=false;
	cin>>n>>k;
	if(n==0 && k==0)break;
    cin>>s;
	len=s.length();
	del=k;
	i=0;j=1;
	while(del>0)
	{
		if(ok)
		{
			len=s.length();
			x=s[len-1]-'0';
			y=s[len-2]-'0';
			if(x<y)s.erase(s.end()-1);
			else
				s.erase(s.end()-2);
			del--;
		}
		else
		{
			x=s[i]-'0';
	    	y=s[j]-'0';
		
    		if(x<y)
	    	{
		    	s.erase(s.begin()+i);
	    		if(i!=0)
	    		{
		    		i--;
			    	j--;
	    		}
	    		del--;
	    	}
	    	else
	    	{
		    	if(j+1<s.length())
		    	{
			    	i++;
			    	j++;
		    	}
		    	else
		    	{
			    	ok=true;
			    }
	    	}
		}
	}
	cout<<s<<endl;
}
return 0;
}

[Shafaet_du]

The main idea is you will delete a digit d if d[i+1]>d. if there are multiple such d,than delete the leftmost. if there are no d delete the last digit. Now its upto you,how you will implement the code. I implemented using a queue. I got tle using stl,than used simple array and got ac. to pop from queue i just increased the start pointer.

[Merengues]

http://www.topcoder.com/tc?module=Stati ... onAncestor
See tutorial here, replace with O(lgn) or O(1) op for each max find.

nice. very good tutorial