Page 1 of 2

12356 - Army Buddies

Posted: Mon Feb 03, 2014 1:22 pm
by uDebug
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.

Re: 12356 - Army Buddies

Posted: Fri Aug 29, 2014 7:03 am
by mhsn06
1 <= L <=R <= N
what is the meaning of L>R input?
3 2
They are already killed. how it could be?
2 3

Re: 12356 - Army Buddies

Posted: Thu Sep 04, 2014 1:21 am
by brianfry713
v1n1t, your input is invalid.

Re: 12356 - Army Buddies

Posted: Thu Sep 04, 2014 8:46 am
by uDebug
brianfry713 wrote:v1n1t, your input is invalid.
Thanks for bringing this to my attention. I've removed my input.

Re: 12356 - Army Buddies

Posted: Tue Sep 09, 2014 7:31 pm
by Shahidul.CSE
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;
}

Re: 12356 - Army Buddies

Posted: Wed Sep 10, 2014 7:25 pm
by brianfry713
Don't read from a file.

Re: 12356 - Army Buddies

Posted: Sat Sep 13, 2014 1:42 pm
by Shahidul.CSE
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

Re: 12356 - Army Buddies

Posted: Sat Sep 13, 2014 7:27 pm
by brianfry713
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).

Re: 12356 - Army Buddies

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

Code: Select all

Accepted ! 

Re: 12356 - Army Buddies

Posted: Mon Sep 15, 2014 9:38 pm
by brianfry713

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]

Re: 12356 - Army Buddies

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

Code: Select all

Accepted !

Re: 12356 - Army Buddies

Posted: Tue Sep 16, 2014 7:54 pm
by brianfry713
Try running your code on the sample input.

Re: 12356 - Army Buddies

Posted: Tue Sep 16, 2014 8:21 pm
by Shahidul.CSE
To
brianfry713,
Thanks sir, got ACCEPTED :D

Re: 12356 - Army Buddies

Posted: Thu Oct 30, 2014 7:59 pm
by cleiva
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?

Re: 12356 - Army Buddies

Posted: Thu Oct 30, 2014 9:13 pm
by brianfry713
Yes printf and scanf are faster than cin and cout.