The Dragon's Wrath

Computer Science Level 5

Eons from today, the dragon, fed up with the human race, rises from the scorching depths of the earth. Unparalleled in intelligence and strength, she knows nothing can oppose her. She descends on the last city of earth and summons its $10000$ residents. She then thunders:

"Every one of you, brand your skin with a different number from $1$ to $10000$ . Then stand in a circle in ascending order of your numbers. I will start counting from number $1$ and devour every $7{th}$ person. I will keep doing this, till there is just one of you left. And that person will be spared."

The people recognized the end, the numbers were permanent, branded with the fire of the dragon herself. They decide to assign numbers through a lottery. The mayor, being the world's last remaining mathematician, rigs the lottery, and ensures that he gets the number that would guarantee his survival.

On the fateful day, the dragon appears. She starts counting. And when she reaches the $7{th}$ person, she snatches him up with her powerful claws and puts him in a nearby cage. The people are confused, then they realize that the dragon is putting all her food in the cage. One-by-one each person is picked up and put into the cage. In the end, the mayor remains. The dragon gives him a twisted grin, and as soon as the truth dawns on him, she snaps him up.

Everyone was terrified. The dragon had not kept her word. As they remained petrified in their fear, the dragon roared:

"The rules have changed! Now all of you come stand in a circle again, in ascending order of the number on your skin. We will then continue. I will start counting from the lowest number and put every $7^{th}$ person in the cage. The person who will remain after the rest of you are in the cage will be eaten. You will then be let out of the cage, and we will repeat this, till only one of you is left"

The people comply. Many hours later, the dragon leaves. One last person remains. Light catches his hand, revealing the number which was etched upon his skin. What is this number?

Note:

As an example, consider the case when there are $5$ people and the dragon puts every $2^{nd}$ person in the cage:

$1,2,3,4,5$ : 2 in cage,4 in cage,1 in cage,5 in cage, 3 dies

$1,2,4,5$ : 2 in cage,5 in cage,4 in cage, 1 dies

$2,4,5$ : 4 in cage, 2 in cage, 5 dies

$2,4$ :4 in cage, 2 dies

$4$ survives.

The answer is 1080.

4 solutions

Prabowo Prabowo
Jun 4, 2015

Here is my solution in C++

#include <cstdio>

int n, k;
int josephus[10002];
int bit[10002];

void update(int x, int val) {
    for (int i=x; i<=n; i+=i&-i) bit[i] += val;
    return;
}

int query(int x) {
    int ret = 0;
    for (int i=x; i>0; i-=i&-i) ret += bit[i];
    return ret;
}

int l_bound(int x) {
    int l = 1;
    int r = n;
    while (l < r) {
        int k = (l+r) >> 1;
        if (query(k) < x) l = k+1;
        else r = k;
    }
    return l;
}

int main() {
    scanf("%d %d", &n, &k);

    josephus[0] = 0;
    for (int i=1; i<=n; i++) josephus[i] = (k + josephus[i-1]) % i;

    for (int i=1; i<=n; i++) update(i, 1);
    for (int i=n; i>1; i--) update(l_bound(josephus[i]+1), -1);

    printf("%d\n", l_bound(1));

    return 0;
}

David Holcer
Mar 22, 2015

Wow first of all, what a great question. I am so happy that I got one of the only level 5 computer science questions correct. :)

global dead
dead=[]
n=10**4
m=7
def remains(n,m):
    n+=1
    array=[]
    for i in range(1,n):
        if i not in dead:
            array.append(i)
    num=m-1    
    while len(array)>1:
        num=(num%len(array))
        array.remove(array[num])
        num+=(m-1)
    dead.append(array[0])
    if len(dead)==n-1:
        print array
while len(dead)<n:
    remains(n,m)

My approach was with two arrays, one to keep track of everyone whose dead, and the other to find the dead. With this approach, it was possible to find the remaining person once the dead array was one less than full. n signifies the total number of people and m stands for every mth person that gets selected. This took quite a lot of computing power. I left it sometime in the night, and found it in the morning, but must've taken ~2 hrs.

Thanks! Sorry to break it to you, but this problem will soon become level 4. The scoring system on Brilliant takes into account the number of people who get the question wrong, hence if a lot of people who attempt it get it right, then the points go down.

Python codes are almost always shorter. But why does your code take so long to run? Do you have an infinite loop somewhere? My code takes just a few seconds to get to the answer. I too used the same algorithm that you did.

Raghav Vaidyanathan - 6 years, 2 months ago

I'm really not sure why, probably a while loop? or very large arrays? It's not the best coding, but I'm glad it still worked.

David Holcer - 6 years, 2 months ago

Okay! Keep up your interest in CS. And try to figure out ways to better your programs(not just here). All the best.

Raghav Vaidyanathan - 6 years, 2 months ago

Raghav Vaidyanathan
Mar 15, 2015

This is a variation of the Josephus problem. I like to call it reverse Josephus.

Here is my unnecessarily big C++ solution:

#include<fstream.h>
#include<conio.h>
#include<math.h>
#include<iomanip.h>

struct node
    {
    double data;node*link;
    };

class ll
    {
    node* f,*r;
    public:
    ll()
    {f=NULL,r=NULL;}
    void del()
        {
        node*p=f->link;
        for(;p!=f;)
            {
            node*t=p;
            p=p->link;
            delete t;
            }
        delete f;
        }
    void insert(double elm)
        {
        node*p=new node;
        (f==0)?f=p:r->link=p;
        p->data=elm;p->link=NULL;
        r=p;
        }
    void del(node *d)
        {
        node*t=d->link;
        d->link=t->link;
        delete t;
        f=d->link;
        }
    node* retf()
        {
        return f;
        }
    void circomplete()
        {
        r->link=f;
        }
    };

class round
    {
    double n,r,*x;
    public:
    round(double p,double q)
        {
        n=floor(p);r=floor(q);
        long k=n;
        x=new double[k+1];
        for(long i=1;i<=n;i++)
            {
            x[i]=1;
            }
        }
    void fire()
        {
        long w;
        for(double m=1;m<n;m++)
            {
            ll L;
            for(long i=1;i<=n;i++)
                if(x[i]==1)
                    {
                    L.insert(i);
                    }
            L.circomplete();
            for(;L.retf()->link!=L.retf();)
                {
                node*p =L.retf();
                for(double i=1;i<=r-2;i++)
                    {
                    p=p->link;
                    }
                L.del(p);
                }
            w=L.retf()->data;
            x[w]=0;
            L.del();
            }
        for(long i=1;i<=n;i++)
            if(x[i]==1)
                {
                cout<<i;
                break;
                }
        delete []x;
        }
    };

int main()
    {
    clrscr();
    cout<<"revrsJosephus(n,r)"<<endl;
    double n,r;
    cout<<"n= "<<endl;cin>>n;
    cout<<"r= "<<endl;cin>>r;
    round R(n,r);
    R.fire();
    getch();
    return 0;
    }

Abdelhamid Saadi
Jun 22, 2015

In Python

def wrath(nth, count):  
    ll = list(range(1,count+1))
    while len(ll) > 1:
        l = ll[:]
        order = 0
        while len(l) > 1:
            order = (order + nth - 1)%len(l)
            del l[order]    
        ll.remove(l[0])
    return ll[0]

wrath(7,10000)

The Dragon's Wrath

The answer is 1080.

4 solutions

0 pending reports