Thread: Last Man Standing

  1. #1
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308

    Last Man Standing

    After losing in battle, a ruthless Roman General has N men left, but is cornered on all sides. His only way to escape is a small boat which can carry only two people. He has no option but to select 1 out of the remaining N men to accompany him back to Rome.

    He chooses to devise a plan to decide a random winner.

    He orders all N soldiers to be numbered and to form a circle in order of their numbers. Number 1 is given a sword and he must kill the next soldier (i.e. soldier Number 2) and give the sword to the next surviving soldier (i.e. soldier Number 3). All soldiers have t do the same until one of them is left. Which soldier survives in the end?

    INPUT:
    The number N denoting the number of soldiers.

    OUTPUT:
    The number of the last surviving soldier.

    CONSTRAINTS:
    0<N<1000000

    SAMPLE INPUT #1:
    100

    SAMPLE OUTPUT #1:
    73

    SAMPLE INPUT #2:
    10

    SAMPLE OUTPUT #2:
    5


    This question is from HP Code Wars 2019 Bangalore.

    My issue:
    I wrote the code for odd and even inputs of N separately and it works so logically I do know the solution but do I? I tried making a general code for both odd and even inputs and it works but only partially i.e. only for odd inputs and not the even inputs i.e. shows the wrong output. I'm not able to figure out the mistake in my logic and I need help with the entire code for a general case whether ODD or EVEN input.

    Don't suggest to use my own ODD and EVEN code like this:

    Code:
    int N=cin.get();
    
    if ( N%2==0 )
    {
           //EVEN NUMBER CODE
    }
    
    else
    {
           //ODD NUMBER CODE
    }
    Thanks!

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Sounds like this rather more classic expression of the same problem.
    Josephus problem - Wikipedia

    > I'm not able to figure out the mistake in my logic and I need help with the entire code for a general case whether ODD or EVEN input.
    So where is the rest of your code then?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Quote Originally Posted by Salem View Post
    So where is the rest of your code then?
    Here's the one that works for ODD inputs...

    Code:
    #include <iostream>
    
    
    using namespace std;
    
    
    void Left_Shift( int , int& , int* );
    
    
    int main (void)
    {
        int N, sword_pos = 0 , ctr_var;
        cin >> N;
    
    
        int soldier[N], Num = N;
    
    
        for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
            soldier[ctr_var]=ctr_var+1;
    
    
        for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
        {
            if ( sword_pos == N-1 )
                sword_pos = -1;
    
    
            Left_Shift( sword_pos + 1 , N , soldier );
            sword_pos++;
        }
    
    
        cout<<endl<<soldier[0];
    }
    
    
    void Left_Shift ( int Who_To_Kill , int &N , int ARR[] )
    {
        for ( int i = Who_To_Kill ; i < N - 1 ; i++ )
        {
            ARR[i] = ARR[i+1];
        }
        N--;
    }
    
    // Compiled on Code::Blocks with GNU GCC Compiler
    How it works?

    Code:
    // ODD NUMBER INPUT
    
    
    N = 9
    
    
    -1- 2 3 4 5 6 7 8 9
    1 -3- 4 5 6 7 8 9
    1 3 -5- 6 7 8 9
    1 3 5 -7- 8 9
    1 3 5 7 -9-
    -3- 5 7 9
    3 -7- 9
    -3- 7
    -3-
    
    
    Survivor = 3
    
    
    // EVEN NUMBER INPUT
    
    
    N = 10
    
    
    -1- 2 3 4 5 6 7 8 9 10
    1 -3- 4 5 6 7 8 9 10
    1 3 -5- 6 7 8 9 10
    1 3 5 -7- 8 9 10
    1 3 5 7 -9- 10
    -1- 3 5 7 9
    1 -5- 7 9
    1 5 -9-
    -5- 9
    -5-
    
    
    Survivor = 5
    Okay, so I realised that when I was working on a generalised program, I actually was messing around in the EVEN input code and I seem to have lost the original code that worked...
    I'll have to write the code down again which I'll hopefully start and finish in a few hours after school. I'm not sharing the generalised program that I tried making (and failed) because, honestly, I don't like the way I've written it and I know of a certain flaw in the code.

    I'll try doing it again after school with a fresh and calm mind as I got frustrated yesterday and came on here and asked the question anyway. I wouldn't mind having some help either way.

    I read through the Wikipedia thing earlier this morning very briefly and its very interesting. I think it's a different approach to the problem than what I have tried but I wouldn't know unless I read through carefully (after school).... Thanks @Salem!

  4. #4
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    I replied to the @Salems message and it didn't get posted. Did I do something wrong?

  5. #5
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Here's the one that works for ODD inputs:

    Code:
    #include <iostream>
    
    
    using namespace std;
    
    
    void Left_Shift( int , int& , int* );
    
    
    int main (void)
    {
        int N, sword_pos = 0 , ctr_var;
        cin >> N;
    
    
        int soldier[N], Num = N;
    
    
        for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
            soldier[ctr_var]=ctr_var+1;
    
    
        for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
        {
            if ( sword_pos == N-1 )
                sword_pos = -1;
    
    
            Left_Shift( sword_pos + 1 , N , soldier );
            sword_pos++;
        }
    
    
        cout<<endl<<soldier[0];
    }
    
    
    void Left_Shift ( int Who_To_Kill , int &N , int ARR[] )
    {
        for ( int i = Who_To_Kill ; i < N - 1 ; i++ )
        {
            ARR[i] = ARR[i+1];
        }
        N--;
    }
    My logic:

    Code:
    // ODD NUMBER INPUT
    
    
    N = 9
    
    
    -1- 2 3 4 5 6 7 8 9
    1 -3- 4 5 6 7 8 9
    1 3 -5- 6 7 8 9
    1 3 5 -7- 8 9
    1 3 5 7 -9-
    -3- 5 7 9
    3 -7- 9
    -3- 7
    -3-
    
    
    Survivor = 3
    
    
    // EVEN NUMBER INPUT
    
    
    N = 10
    
    
    -1- 2 3 4 5 6 7 8 9 10
    1 -3- 4 5 6 7 8 9 10
    1 3 -5- 6 7 8 9 10
    1 3 5 -7- 8 9 10
    1 3 5 7 -9- 10
    -1- 3 5 7 9
    1 -5- 7 9
    1 5 -9-
    -5- 9
    -5-
    
    
    Survivor = 5
    I went through the Wikipedia on the Josephus problem earlier this morning before school very briefly and I did find it interesting and I guess the logic is pretty different from my approach but I will never know until I go through carefully which I will in about 2 hours from now. Thanks Salem for the reference.

    I realised that I was messing around on my EVEN input code to get a generalised program so I need to remake it for the time being but it's fairly similar to the ODD input one with different test cases.
    I'm not adding my version of the generalised program as I don't think it's gonna be of much use as the logic is flawed and I'd be slightly embarrassed by it.

    Also, I replied to @Salem earlier when I was at school but that message didn't show up here. Was there any issue in it?
    Last edited by Zeus_; 08-15-2019 at 11:56 AM.

  6. #6
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Okay, I have no idea what's going on. I've replied twice and I don't see either of my messages here..... Did something go wrong? I did see them when I posted it but when I visited the page again, it wasn't there.

  7. #7
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    I'm gonna type again as a last try....

    Here's my code that works for ODD inputs:

    Code:
    #include <iostream>
    
    
    using namespace std;
    
    
    void Left_Shift( int , int& , int* );
    
    
    int main (void)
    {
        int N, sword_pos = 0 , ctr_var;
        cin >> N;
    
    
        int soldier[N], Num = N;
    
    
        for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
            soldier[ctr_var]=ctr_var+1;
    
    
        for ( ctr_var = 0 ; ctr_var < Num ; ctr_var++ )
        {
            if ( sword_pos == N-1 )
                sword_pos = -1;
    
    
            Left_Shift( sword_pos + 1 , N , soldier );
            sword_pos++;
        }
    
    
        cout<<endl<<soldier[0];
    }
    
    
    void Left_Shift ( int Who_To_Kill , int &N , int ARR[] )
    {
        for ( int i = Who_To_Kill ; i < N - 1 ; i++ )
        {
            ARR[i] = ARR[i+1];
        }
        N--;
    }
    My logic:

    Code:
    /*// ODD NUMBER INPUT
    
    
    N = 9
    
    
    -1- 2 3 4 5 6 7 8 9
    1 -3- 4 5 6 7 8 9
    1 3 -5- 6 7 8 9
    1 3 5 -7- 8 9
    1 3 5 7 -9-
    -3- 5 7 9
    3 -7- 9
    -3- 7
    -3-
    
    
    Survivor = 3
    
    
    // EVEN NUMBER INPUT
    
    
    N = 10
    
    
    -1- 2 3 4 5 6 7 8 9 10
    1 -3- 4 5 6 7 8 9 10
    1 3 -5- 6 7 8 9 10
    1 3 5 -7- 8 9 10
    1 3 5 7 -9- 10
    -1- 3 5 7 9
    1 -5- 7 9
    1 5 -9-
    -5- 9
    -5-
    
    
    Survivor = 5
    I was at school when I first replied but the message didn't show up here when I looked again. @Salem I went through the Josephus problem on Wiki very briefly earlier this morning and I found it interesting as I believe it's a very different approach to the problem than mine but I wouldn't know unless I looked into it carefully which I will in about 2 hours from now.

    I realised I was messing around on my EVEN input code for a generalised program and so I need to write it again to be able to post it here (I will in 2 hours). I'm not gonna be sharing my version of the generalised program because it's logic is flawed and I don't think it's gonna be of much use or help and I will be embarrassed slightly too :shy:

    Thanks @Salem for the reference

  8. #8
    Registered User
    Join Date
    May 2019
    Posts
    214
    Well, sometimes servers have little glitches...your post of 21 minutes ago appeared, to try again.

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Your posts were in the moderation queue.
    It should have told you something along those lines.
    I've now approved your posts.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > This question is from HP Code Wars 2019 Bangalore.
    There is a general theme to programming contests, and that is you sit down and think about the problem.

    The first answer that comes into your head which involves "try every possible combination" is always the wrong approach. Occasionally you'll get lucky, but invariably you'll end up with either memory limit exceeded or time limit exceeded when the automated tests start throwing really large N values at your submission.

    Remember, the problem as originally stated in mythology was N=40 and was meant to be a calculation you could do in your head in seconds.

    Watch this for 10 minutes.
    YouTube

    Done right, you don't need a for loop from 0 to N, and a massive array.

    You just need a math expression.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Makes sense Salem, thanks for the tips but this was the only thing I could come up with in the span of 3 hours given for 22 question ranging from 4 points to 25/30 points. I haven't tried any approach other than constantly trying to make my logic better i.e. come up with a generalised program and I didn't really start thinking of any other possible solutions. However, I tried a different approach after reading the Josephus problem on Wiki and it WORKS!!

    Thanks again @Salem. Respect.

Popular pages Recent additions subscribe to a feed

Tags for this Thread