Reposted: Is there a better algorithm to solve this problem?

[cire]

The problem is not the erasing. The problem is having to traverse the big array (M), for every element. That makes a total time of O(N*M)

I read the OP's post and, from the sound of it, he was just barely over the time limit. Perhaps I was mistaken.

While I (think) I understand the basics of big O notation, I'm not certain how to classify the (other) solution I came up with, which was simply to keep track of the ranges of "occupied" shelf.

In the best case (all elements removed from an end) it would be O(1). In the worst case, for a particular i, i/2 ranges have to be traversed (and in that case, every search results in a range being split, which is costly.) I can't quite conceptualize how these factors figure in. No college here and programming is a hobby -- maybe I just don't have the background to grasp it on an intuitive level.

Annoyingly verbose code:

#include <iostream>
#include <vector>
#include <list>
#include <utility>

struct ShelfSegment
{
    unsigned start_index ;
    unsigned n_books ;

    ShelfSegment(unsigned books, unsigned index = 0)
        : start_index(index), n_books(books) {}
};

class BookShelf
{
public:

    BookShelf(unsigned v_size)
        : _books(v_size), _occupied_segments(1, ShelfSegment(v_size))
    {}

    unsigned& operator[](unsigned i)
        { return _books[i]; }

    unsigned loan_nth( unsigned n) ;

private:

    typedef std::list<ShelfSegment>::iterator list_iter ;

    // return an iterator pointing to the nth element's segment
    // and the element's ordinal position in the segment.
    std::pair<list_iter,unsigned> _find_nth(unsigned nth) ;

    std::vector<unsigned> _books ;
    std::list<ShelfSegment> _occupied_segments;
};

std::pair<BookShelf::list_iter,unsigned> BookShelf::_find_nth(unsigned nth)
{
    unsigned skipped = 0 ;
    std::list<ShelfSegment>::iterator i = _occupied_segments.begin();

    while ( nth-skipped > i->n_books )
    {
        skipped += i->n_books ;
        ++i ;
    }

    return std::make_pair(i, nth-skipped) ;
}

unsigned BookShelf::loan_nth(unsigned nth)
{
    std::pair<list_iter, unsigned> found = _find_nth(nth) ;

    const list_iter & segment = found.first ;
    const unsigned & position = found.second ;

    unsigned book_index = segment->start_index + position-1 ;

    if ( position == segment->n_books || position == 1)
    {  // shrink the range
        if ( --segment->n_books == 0 )
            _occupied_segments.erase(segment) ;
        else
            if( position == 1 )
                ++segment->start_index ;
    }
    else // Split the range.
    {
        _occupied_segments.insert(segment, ShelfSegment(position-1, segment->start_index)) ;
        segment->start_index += position ;
        segment->n_books -= position ;
    }

    return _books[book_index] ;
}

inline unsigned get_num()
{
    unsigned num ;
    std::cin >> num ;
    return num ;
}

int main()
{
    const unsigned n_books = get_num();

    BookShelf shelf(n_books) ;

    for ( unsigned i=0; i<n_books; ++i )
        shelf[i] = get_num() ;

    const unsigned n_books_loaned = get_num() ;
    for ( unsigned i=0; i<n_books_loaned; ++i )
        std::cout << shelf.loan_nth(get_num()) << '\n' ;
}

[ Edit: On a side note, I wanted to try it out on the site linked by the OP just to make sure it worked, but in the process somehow I selected a different problem for the submission, so of course it failed. Spent quite a bit of time re-tracing through the logic before I figured out I'd been submitting for the wrong problem! ]

[helios]

How about a tree? Every node can hold how many books its subtrees hold, and leaves can hold sequences of books.

For example, we start out with
([1,2,3,4,5,6,7,8,9,10], 0, null, 0, null)

input: 2

([],
    1,
    ([1], 0, null, 0, null),
    8,
    ([3,4,5,6,7,8,9,10], 0, null, 0, null)
)

input: 5
5>1, so modify the right branch:

([],
    1,
    ([1], 0, null, 0, null),
    7,
    ([],
        3,
        ([3,4,5], 0, null, 0, null),
        4,
        ([7,8,9,10], 0, null, 0, null)
    )
)

input: 5
5>1, so modify the right branch.
5-1>3, so modify the right-right branch:

([],
    1,
    ([1], 0, null, 0, null),
    6,
    ([],
        3,
        ([3,4,5], 0, null, 0, null),
        3,
        ([8,9,10], 0, null, 0, null)
    )
)

input: 3
3>1, so modify the right branch.
3-1<=3, so modify the right-left branch:

([],
    1,
    ([1], 0, null, 0, null),
    
    5,
    ([],
        2,
        ([],
            1,
            ([3], 0, null, 0, null),
            1,
            ([5], 0, null, 0, null)
        )
        3,
        ([8,9,10], 0, null, 0, null)
    )
)

And so on.
On average, removing a book should take O(log n). If an array of books is kept, the sequences of books can be represented as a pair of integers denoting ranges on the vector.

[meteora]

@JLBorges and @Cire I will have a look at your codes, thank you.
Meanwhile here's what happened, using @ne555 idea,

There is an easy O(N^2) were you consider only the taken books, (not sure if fast enough)
suppose that you want to borrow the K book,
If there is a J, with J<=K, that was borrowed, then you need to take the K+1 book.

i came up with this:

#include <iostream>
#include <algorithm>

using namespace std;

int main(){

	int n;
	cin >> n;

	int books[n];

	for(int i = 0;i < n;i ++){
		cin >> books[i];
	}

	int t;
	cin >> t;
	int test[t];

	for(int i = 0; i <t;i ++){
		cin >> test[i];
		for(int j = 0; j < i;j ++){
			if(test[j] <= test[i]){
				test[i]++;
			}
		}
	}

	for(int i = 0;i < t;i ++){
		cout << books[test[i]-1] <<  endl;
	}

	return 0;
}

It is working for the sample example and for my own test cases. But when it is submitted, i get a wrong answer, however it is well within the time limit. So i think O(N^2) will be fine for this problem.

[meteora]

@helios I didn't understand your post, i always get confused when it comes to trees. So i always try to avoid using them.

[helios]

Alright. My solution passed.
Worst time: case #0, 1.8 seconds.
Best time: case #5, 0.01 seconds.

EDIT: Oh, by the way, cire: I didn't read all of your code, but I think I originally I had the same idea you have. If I'm right, then your solution takes O(N^2) time, because in the worst case, you have to iterate over the entire list every time a book is removed. The first time the list will contain one element; the second, two; the third, three; and so on. Adding up everything, we come up with (1/2)*N^2 + (1/2)*N iterations. As N tends to infinity, the linear term becomes insignificant, so the function looks a lot like (1/2)*N^2. One quadratic function is basically the same as another, so big O notation drops the coefficient: O(N^2).

[cire]

helios wrote:

because in the worst case, you have to iterate over the entire list every time a book is removed.

Correct.

helios wrote:

The first time the list will contain one element; the second, two; the third, three; and so on. Adding up everything, we come up with (1/2)*N^2 + (1/2)*N iterations

Well, this is true up to a point. Once we have removed N/2 books the (maximum) number of iterations required to traverse the list declines by one for each subsequent removal. (At that point there are only one element ranges left .) So the maximum number of iterations would look something like: let J = N/2, then 2(1+2+ ... +J).

Which is the same as 2( (J(J+1))/2) = J(J+1) = J² + J

And if we substitute N back in: (N/2)²+N/2 = (N²+N)/4

Which, I suppose, as N approaches infinity is overwhelmed by N²! I guess I could've stopped at J²+ J.

Drat. I thought I was on to something. And, I suppose worst case should only be considering M < n/2, anyway.

Thanks for makin' me think.

results from the submission:
Worst Case was 0 at 1.81
Best Case was 3 at .01

[ne555]

Passed too (worst time 1.67)

@JLBorges, A 06 (maybe rollie too)

input
5
1 2 3 4 5
5
3 3 2 1 1

expected output
3 4 2 1 5

your output
3 4 2 1 2

¿do you understand why?

[rollie]

As long as the gauntlet has been thrown down...impl of my original solution, worst time 0.66s for problem #9

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <limits>
#include <vector>
#include <fstream>
#include <string>
#include <map>
#include <set>
#include <list>

using namespace std;

int main() 
{
	set<int> absoluteCheckoutIndices;
	list<int> lstAbsoluteCheckoutIndices;
	vector<int> originalBookOrder;

	int bookCount;
	cin >> bookCount;	

	originalBookOrder.resize(bookCount);
	
	for (int i = 0; i < bookCount; ++i)
	{
		scanf ("%d", &originalBookOrder[i]);
	}

	int checkoutCount, newCheckoutIndex;
	cin >> checkoutCount;

	while (--checkoutCount >= 0)
	{
		cin >> newCheckoutIndex;

		for (set<int>::iterator itr = absoluteCheckoutIndices.begin(); itr != absoluteCheckoutIndices.end(); itr++)
		{
			if (*itr <= newCheckoutIndex)
			{
				newCheckoutIndex++;
			}
			else
			{
				break;
			}
		}

		absoluteCheckoutIndices.insert(newCheckoutIndex);
		lstAbsoluteCheckoutIndices.push_back(newCheckoutIndex);
	}

	for (list<int>::iterator itr = lstAbsoluteCheckoutIndices.begin(); itr != lstAbsoluteCheckoutIndices.end(); ++itr)
	{
		cout << originalBookOrder[*itr - 1] << "\n";
	}

	cout.flush();

	return 0;
}

[helios]

Well, this is true up to a point. Once we have removed N/2 books the (maximum) number of iterations required to traverse the list declines by one for each subsequent removal. (At that point there are only one element ranges left .)

Aren't you assuming that N=M?
What would happen if, while M>=2*N, someone entered a string of N twos?

[cire]

cire wrote:

And, I suppose worst case should only be considering M < N/2, anyway.

I should hope the number of books to remove would never be greater than the number of books.

[helios]

M is the number of books, so M < N/2 is a contradiction.

[cire]

So it is. Must've mixed them up at some point.

[meteora]

@ne555 Yes I understood why!! Its because the array test[] isnt sorted. Rollie's solution is similar to what i had thought, only his set is sorted so it works!

Thank you everyone for helping me solve this problem, now i have many different methods for solving this thanks a lot.