Daily Programming Dose Day 2 Solutions

In order to calculate the minimum possible lifted weight, we should find the initial stack first. Let’s find the positions one by one.

  • First, let’s decide the position of book b1. After day 1, book b1 will be on the top of the stack, regardless of the order of the initial stack. Therefore, in order to minimize the lifted weight during day 1, book b1 must be on the top of the initial stack. (so actually, in day 1, you won’t lift any book)
  • Next, let’s decide the position of book b2. (assume that b1 ≠ b2 for simplicity) Currently, b1 is on the top of the stack, and it cannot be changed because of the procedure. Therefore, in order to minimize the lifted weight during day 2, book b2 must be immediately below book b1.

Considering this, we can find the optimal strategy to create the initial stack: Scan b1, b2, …, bm step by step. Let’s assume that I am handling bi now. If bi has appeared before (formally, if ), erase bi from the sequence. Otherwise, leave bi. The resulting sequence will be the optimal stack.

You should note that it is not necessary for you to read all the books during 2015, which means the size of the resulting sequence may be smaller than n. The books which doesn’t appear in the resulting sequence must be in the bottom of the initial stack (obviously). However, this problem doesn’t require us to print the initial stack, so it turned out not to be important.

In conclusion, finding the initial stack takes O(n + m) time.

After finding the initial stack, we can simulate the procedure given in the statement naively. It will take O(nm) time.

  • Time: O(nm)
  • Memory: O(n + m)

You could also check out my solution at :

http://ideone.com/Ji4WHx

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s