11491 - Erasing and Winning

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

11491 - Erasing and Winning

Post by FAQ » Sun Sep 21, 2008 8:10 am

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

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11491 - Erasing and Winning

Post by Robert Gerbicz » Sun Sep 21, 2008 2:30 pm

Greedy method.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Re: 11491 - Erasing and Winning

Post by FAQ » Sun Sep 21, 2008 2:56 pm

I know, but still WA

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Re: 11491 - Erasing and Winning

Post by FAQ » Sun Sep 21, 2008 5:34 pm

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
New poster
Posts: 9
Joined: Thu Aug 21, 2008 3:08 am
Location: IUT

11491 - Erasing and Winning -TLE

Post by bleedingeyes » Thu Sep 25, 2008 4:06 am

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;
}
wanna be notorious....

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11491 - Erasing and Winning

Post by baodog » Thu Sep 25, 2008 6:33 am

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
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11491 - Erasing and Winning

Post by Chirag Chheda » Fri Sep 26, 2008 10:41 am

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. :oops:

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
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11491 - Erasing and Winning

Post by andysoft » Sat Sep 27, 2008 12:55 pm

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 ))
Now I lay me down to sleep...
my profile

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11491 - Erasing and Winning

Post by mmonish » Sat Sep 27, 2008 2:17 pm

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
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11491 - Erasing and Winning

Post by Chirag Chheda » Mon Sep 29, 2008 9:15 am

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
New poster
Posts: 9
Joined: Fri Jul 18, 2008 12:10 pm
Location: Iran-shiraz
Contact:

Re: 11491 - Erasing and Winning

Post by sijal » Thu Oct 09, 2008 4:32 pm

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

Code: Select all

ACC
Learn to swim.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11491 - Erasing and Winning

Post by mak(cse_DU) » Thu Nov 13, 2008 10:15 pm

baodog wrote: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 :wink: .
Mak
Help me PLZ!!

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11491 - Erasing and Winning

Post by Igor9669 » Sun Dec 28, 2008 6:09 pm

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11491 - Erasing and Winning

Post by Shafaet_du » Fri Jul 08, 2011 2:39 pm

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
New poster
Posts: 1
Joined: Sun Aug 21, 2011 10:47 pm

Re: 11491 - Erasing and Winning

Post by Merengues » Sun Aug 21, 2011 10:52 pm

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
Shop For Spy Earpiece To Become Successful In The Exams
how to buy spy earpiece http://www.reema.fr/wakka.php?wiki=spyearpieceset

Post Reply

Return to “Volume 114 (11400-11499)”