Holes (Hard)

Computer Science Level 2

One fateful day, 9 people numbered 1, 2, 3, 4, 5, 6, 7, 8 and 9 are trying to cross a road that contains several deep holes. To pass through a hole with depth 3, the 3 leading people have to go into the holes in order so that the other people can safely cross the hole. Then, the last people who crossed the hole will pull the highest people from the hole up, and so on. For clarity, look at the diagram below where 4 people is crossing a hole with depth 3 :

If the output sequence is 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 1,2,3,4,5,6,7,8,9 and the 30 30 holes they must pass through in order has depth of 

1
 
3 5 9 8 5 1 8 5 4 5 3 8 6 7 2 6 3 9 2 5 2 7 8 6 7 3 6 9 2 5

respectively, what is the input sequence ?

If you think the output sequence is 6 , 5 , 4 , 3 , 2 , 1 6,5,4,3,2,1 , input your answer as 654321 .

You are advised to solve the Easy and Medium version of this problem first.


The answer is 342961875.

View wiki
Christopher Boo by Christopher Boo , 24, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Mehdi K.
May 23, 2016

Python3 

1
2
3
 
def holes_hard(people, holes):        #people can be either a list or a string, holes is a list
    for hole in holes[::-1]: people = people[-hole:][::-1] + people[:-hole]
    return people

4 Helpful 0 Interesting 1 Brilliant 0 Confused

Did anyone realize that the 9 people are stuck in hole 3 of depth 9 with no one left to pull them out?

Chris Arsenault - 4 years, 1 month ago

Log in to reply

Yeah, I did! I'm gonna initiate a report now!

A Former Brilliant Member - 3 years, 7 months ago
Christopher Boo
May 15, 2016

Since there are quite a number of holes, we need to write a program to help us compute it efficiently and accurately. This is just a simulating problem, that is, we just write a code to do exactly what we're doing from the previous problems.

Let the number of holes be Q Q , the time complexity for my algorithm is O ( Q N ) O(QN) . 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
void solve() {

    deque<int> d;    // store the sequence
    for (int i = 1; i < 10; i++)
        d.push_back(i);

    for (int i = 0, x; i < 30; i++) {
        scanf("%d",&x);

        stack<int> s;    // hole
        for (int i = 0; i < x; i++) {
            s.push(d.front());
            d.pop_front();
        }

        while (!s.empty()) {
            d.push_back(s.top());
            s.pop();
        }
    }

    int ans[10], cnt = 1;
    while (!d.empty()) {
        ans[d.front()] = cnt++;
        d.pop_front();
    }

    for (int i = 1; i < 10; i++)
        printf("%d ", ans[i]);
}

1 Helpful 1 Interesting 0 Brilliant 0 Confused

Implementation of C++ STL stack and queue, 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include<bits/stdc++.h>
using namespace std;

int main(){
    queue<int> antrian;  //'antrian' is 'queue' in Indonesian
    stack<int> tumpukan;  //'tumpukan' is 'stack' in Indonesian
    int masukan[]={3,5,9,8,5,1,8,5,4,5,3,8,6,7,2,6,3,9,2,5,2,7,8,6,7,3,6,9,2,5};  //'masukan' is 'input' in Indonesian
    int keluaran[99];  //'keluaran' is 'output' in Indonesian
    int a,b,c=1;
    bool idx=true;


            for(int k=9;k>0;k--) antrian.push(k);

    while(idx==true){   
        for(int i=29;i>=0;i--){
            a=masukan[i];
            b=a;

        while(a--){
            tumpukan.push(antrian.front());
            antrian.pop();          
        }
        while(b--){
            antrian.push(tumpukan.top());
            tumpukan.pop();
        }
        }
        idx=false;
    }
        for(int k=9;k>0;k--){
            keluaran[k]=antrian.front();
            antrian.pop();
        }
            while(c<10){
                cout<<keluaran[c];
                c++;
            }

}

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Abdelhamid Saadi
Jun 7, 2016

In python3: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
 
def uncrossone(people, hole):
    return  list(reversed(people[-hole:])) + people[0:-hole]

def uncross(people , holes):
    res = people
    for hole in reversed(holes):
        res = uncrossone(res, hole)
    return res

def solve():
    "Holes (Hard)"
    people = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
    holes = [3, 5, 9, 8, 5, 1, 8, 5, 4, 5, 3, 8, 6, 7, 2, 6, 3, 9, 2, 5, 2, 7, 8, 6, 7, 3, 6, 9, 2, 5 ]
    print( "".join(uncross(people, holes)))

solve()

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Daniel Venable
Oct 8, 2018

Haskell solution for doing it forwards: 

solve :: [Int] -> [Int] -> [Int]
solve (hole:holes) guys = solve holes $ (drop hole guys) ++ (reverse $ take hole guys)
solve [ ] guys = guys

To do it backwards, look at the index each number appears in.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

In C++ 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
#include<bits/stdc++.h>
#include<stack>
#include<deque>

using namespace std;


void print(int d, deque<int> seq)
{
    int a;
    //printf("For d=%d  ", d);
    for(int i=0; i<9; i++)
    {
        a=seq.front();
        printf("%d", a);
        seq.pop_front();
    }
    printf("\n\n");
    return;
}

int main()
{
    char c;
    deque<int> seq;
    stack<int> depth;

    while(!depth.empty())
        depth.pop();
    seq.clear();

    for(int i=1; i<10; i++)
        seq.push_back(i);

    int d;
    for(int i=0; i<30; i++)
    {
        scanf("%d", &d);
        depth.push(d);
    }


    int a;
    stack<int> inhole;
    while(!inhole.empty())
            inhole.pop();

    print(-1, seq);

    while(!depth.empty())
    {
        d=depth.top();
        depth.pop();

        for(int i=0; i<d; i++)
        {
            a=seq.back();
            seq.pop_back();
            inhole.push(a);
        }

        while(!inhole.empty())
        {
            a=inhole.top();
            inhole.pop();
            seq.push_front(a);
        }

        //print(d,seq);
        //c=getchar();









    }
    print(1,seq);


    return 0;
}

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...