12356 - Army Buddies

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

Moderator: Board moderators

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

12356 - Army Buddies

Post by uDebug » Mon Feb 03, 2014 1:22 pm

Since I coded in C++, I got TL when I used cout statements for this problem. However, when I switched to printf, I got AC. (Note that I was already using scanf to read data in (instead of cin).)

Update: Input / output removed after it was pointed out to be faulty. Thanks brianfry713 and mhsn06.
Last edited by uDebug on Thu Sep 04, 2014 7:15 am, edited 2 times in total.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

mhsn06
New poster
Posts: 16
Joined: Tue Apr 01, 2014 7:36 pm

Re: 12356 - Army Buddies

Post by mhsn06 » Fri Aug 29, 2014 7:03 am

1 <= L <=R <= N
what is the meaning of L>R input?
3 2
They are already killed. how it could be?
2 3

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12356 - Army Buddies

Post by brianfry713 » Thu Sep 04, 2014 1:21 am

v1n1t, your input is invalid.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 12356 - Army Buddies

Post by uDebug » Thu Sep 04, 2014 8:46 am

brianfry713 wrote:v1n1t, your input is invalid.
Thanks for bringing this to my attention. I've removed my input.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 12356 - Army Buddies

Post by Shahidul.CSE » Tue Sep 09, 2014 7:31 pm

I am getting TLE with my code. Please suggest me any faster way.

Code: Select all

#include<stdio.h>
int main()
{
    int n,r,L,R,p[100003],i,j,l,fL,fR,rp,lm,rm;

    while(scanf("%d %d",&n,&rp)!=EOF)
    {
        for(i=1;i<=n;i++)
            p[i]=1;  /* initially all soldiers are alive */
        if(n==0 && rp==0)
            break;

        for(i=1;i<=rp;i++)
        {
            fL=fR=0; //Assume left and right buddies are dead and not exist
            scanf("%d %d",&L,&R);

            for(j=L;j<=R;j++) //from L to R all buddies are killed
                p[j]=0;

            if(L>1)
            {
                for(j=L-1;j>=1;j--)   // search alive left buddy from L-1 to 1
                {
                    if(p[j]>0)
                    {
                        l=j;
                        fL=1;    // as a left alive buddy found
                        break;
                    }
                }
            }
            if(R<n)
            {
                for(j=R+1;j<=n;j++)  // search alive right buddy from R+1 to n
                {
                    if(p[j]>0)
                    {
                        r=j;
                        fR=1;    // as a right alive buddy found
                        break;
                    }
                }
            }
            if(fL==0)  // if left buddy not exist
                printf("* ");
            else
                printf("%d ",l);
            if(fR==0)  // if right buddy not exist
                printf("*\n");
            else
                printf("%d\n",r);



        }
        printf("-\n");
    }
    return 0;
}
Last edited by Shahidul.CSE on Sat Sep 13, 2014 1:34 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12356 - Army Buddies

Post by brianfry713 » Wed Sep 10, 2014 7:25 pm

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 12356 - Army Buddies

Post by Shahidul.CSE » Sat Sep 13, 2014 1:42 pm

brianfry713 wrote:Don't read from a file.
Actually I submitted my code not using freopen(...);
I just used it for checking input and output.

But my code getting TLE
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12356 - Army Buddies

Post by brianfry713 » Sat Sep 13, 2014 7:27 pm

You can answer each query in constant time.
At the start of each test case initialize two int arrays that keep track each of the S soldiers nearest living neighbor to the left and right.
For each of the B loss reports print the neighbor values from the arrays, and update (also in constant time) the left and right arrays of the new neighbors.
Total running time should be O(S + B) for each test case, your code runs in O(S * B).
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 12356 - Army Buddies

Post by Shahidul.CSE » Sat Sep 13, 2014 7:56 pm

Code: Select all

Accepted ! 
Last edited by Shahidul.CSE on Tue Sep 16, 2014 8:19 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12356 - Army Buddies

Post by brianfry713 » Mon Sep 15, 2014 9:38 pm

Code: Select all

foreach 1 <= i <= S
  left[i] = i - 1 and right[i] = i + 1

foreach of the B loss reports
  print left[L], right[R]
  left[right[R]] = left[L]
  right[left[L]] = right[R]
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 12356 - Army Buddies

Post by Shahidul.CSE » Mon Sep 15, 2014 10:04 pm

Code: Select all

Accepted !
Last edited by Shahidul.CSE on Tue Sep 16, 2014 8:17 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12356 - Army Buddies

Post by brianfry713 » Tue Sep 16, 2014 7:54 pm

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 12356 - Army Buddies

Post by Shahidul.CSE » Tue Sep 16, 2014 8:21 pm

To
brianfry713,
Thanks sir, got ACCEPTED :D
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

cleiva
New poster
Posts: 1
Joined: Thu Oct 30, 2014 7:53 pm

Re: 12356 - Army Buddies

Post by cleiva » Thu Oct 30, 2014 7:59 pm

Hello,

I/O functions should be a factor in here?

I have an AC solution in C++ which runs in 0.175 seconds if I use printf and scanf, but goes TLE if I use cin and cout.

What do you guys think about that?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12356 - Army Buddies

Post by brianfry713 » Thu Oct 30, 2014 9:13 pm

Yes printf and scanf are faster than cin and cout.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 123 (12300-12399)”