BEX - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Practice

Contest

DIFFICULTY

EASY

PREREQUISITES

Stack Data Structure

PROBLEM

Harry has a lot of books messed on the floor. He keeps a pile of books. At any time, he can put a book that has some remaining exercises on top of the pile, or do a book exercise by picking a book with minimum number of remaining exercises and removing all books above it. If there are more than one such book, pick the book with the minimum number of removed books. Help him determine which book to pick whenever he wants to do a book exercise.

QUICK EXPLANATION

Maintain a stack of books. Each book is represented by a pair of (name, number of remaining exercises, number of books above with greater number of remaining exercises). When Harry wants to do a book exercise, pop the stack and retrieve the name of the book. When Harry wants to put a book on the top of the stack, there are two possibilities. If the number of remaining exercises is greater than the number of remaining exercises of the book on the top of the stack, ignore this book and increase the “number of books above” of the book on the top of the stack. Otherwise, push a new book (name of the book, number of remaining exercises, 0) to the stack.

The time complexity of this solution is of course linear.

EXPLANATION

This is clearly a data structure problem. The problem statement implies that we need to invent an augmented (modified) stack that supports these operations.

  1. Add a book on the top of the stack.
  2. Retrieve a book with the minimum number remaining exercises, and pop all books above it, including the book itself.

To solve this problem, we need this important lemma.

Lemma 1. Suppose there is a book A above a book B in the pile, and book A has greater number of remaining exercises than B. Then, book A will never get picked by Harry.

Proof. Because Harry always pick a book with the minimum number of remaining exercises, book B must be removed first before book A can be picked. However, removing book B will remove book A as well. Therefore, book A will never get picked.

Lemma 1 implies that we don’t have to physically put a book above another book with lower number of remaining exercises as the book can’t be picked. For each book, we can just store the number of books above it that have greater number of remaining exercises. Therefore, we have a stack in non-decreasing order of number of remaining exercises from top to bottom. All operations above can then be implemented in constant time:

  1. If the number of remaining exercises is greater than the number of remaining exercises of the book on the top of the stack, ignore this book (as this book can be never get picked) and increase the "number of books above" of the book on the top of the stack. Otherwise, push a new book (name of the book, number of remaining exercises, 0) to the stack. Of course, if the stack is initially empty, we can just push the book to the stack.
  2. As the stack is sorted in non-decreasing order, just retrieve the book on the top of the stack (and pop it).

Because each operation is done in constant time, the whole solution runs in O(N), i.e., linear time.

Note. There is a tricky case in this problem! When Harry grabs a book with no remaining exercises, he does not put in to the pile. :slight_smile:

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

8 Likes
2

Could someone point out why my


[1] got a runtime error? I can't find the bug.

  [1]: http://www.codechef.com/viewsolution/1621806
3

Could anyone tell me where I have gone wrong…Code is here

Basically, I have two stacks, one which represents the pile of books and the other the minimum no of books to remove to reach the book with minimum no of problems left to solve.

I have also taken care of the tricky test case mentioned above.

I am getting WA

4

I tried your code and I’m getting RE - http://ideone.com/BGO4YF

I tried correctness of the input with tester’s solution - http://ideone.com/Yy98Ow

5

Try this two test cases:

5
8 a
6 b
-1
7 c
-1

6
8 a
6 b
-1
7 c
-1
-1
1 Like
6

One more way of tackling this problem is to create a custom stack, where each element of the stack also keeps the index of the minimum element lying beneath it. So at each user query you have to get the index of the minimum element from the top of the stack in O(1). Once you know the min_index, erase of all the elements from top, till the min_index. The number of elements erased is the number of books that you need to take out from the pile. Nice problem :slight_smile:

2 Likes
7

Thank you, with your help, I fixed the bug caused RE. However, the new code have a unexpected TLE error while I thought its time complexity is O(N), can you give me a hint?

8

The problem is that you are using cin and it is slow, replace cin with scanf and it will get AC :wink:

9

@jigsaw004: reading someone’s code is good practice for challenges (for example fot TopCoder or CodeForces competitions). hacker007’s code is really well written and short, it’s bigger problem with longer codes

2 Likes
10

Can someone please tell me for which testcase my code will fail

Thanks

11

@betlista, thanks for the help!

12

my code is showing SIGSEV error … if it due to large memory … then why it is not showing for tester solution … i have also used same type of arrays having same size … here is link to my code
http://www.codechef.com/viewsolution/1650094

13

I am not able to follow the solution completely. Suppose if the testcase is

6

8 geography

3 Maths

9 english

-1

-1

-1

this is i think a valid testcase but with the solution explained in editorials, i dont think the answer would be right as we have never pushed english on the stack and the last -1 wont be properly answered. Could you please explain this? thanks

14

Can anyone figure out why my code is getting WA? I am using two stacks- one for storing the pile of books in a general fashion and the other is a special stack which has the minimum number of exercises in any book present in stack 1.Every time a new book is pushed in stack 1, i am checking if the top of stack 2 has a book that has left exercises greater than that new book- if yes then that book is even pushed in the 2nd stack,otherwise ignored. In case of a query i am counting …i pop the topmost book from stack 2 and keep poping the books from stack 1 until that book matches.I have tried all sample test cases that i could find anywhere and my code is giving the correct output but the judge rules it out.
Any help would be hoghly appreciated.
Here is the link~~ http://www.codechef.com/viewsolution/2570642

15

awesome…

16

can someone tell why i am getting runtime error sigsegv… my code is here:
http://www.codechef.com/viewsolution/3599271

17

figured the mistake… we can declare at max 10 power 5 size array in c functions… so to declare 10 power 6 size we must declare the array as a global array.

18

I tried the same algorithm as author’s using both vector and stack data type. I am getting correct answers for small test cases, but TLE on submission. Could someone help out?
https://www.codechef.com/viewsolution/8924342

19

#include
#include
#include

struct Book
{
char name[16];
int booksOnTop;
int exercisesLeft;
Book()
{
}
Book(char *_name, int _exercisesLeft)
: booksOnTop(0), exercisesLeft(_exercisesLeft)
{
strcpy(name, _name);
}
};

int main()
{
int n, ex;
std::stack nextMin;
char name[16];

scanf("%d", &n);

while (n--)
{
    scanf("%d", &ex);

    if (ex != -1)
    {
        scanf("%s", name);
        if (ex == 0)
            continue;
        if (nextMin.size() == 0)
            nextMin.push(Book(name, ex));
        else
        {
            Book& b = nextMin.top();
            if (b.exercisesLeft >= ex)
                nextMin.push(Book(name, ex));
            else
                b.booksOnTop++;
        }
    }
    else
    {
        Book b = nextMin.top();
        nextMin.pop();
        printf("%d %s\n", b.booksOnTop, b.name);
    }
}
return 0;

}