15295 Spring 2021 #2 Built-Ins -- Problem Discussion

February 10, 2021

This is where we collectively describe algorithms for these problems.  To see the problem statements and scoreboard, go to this page and select this contest.

A. Escape from Stones

Method 1: We can use doubly linked lists (list<int> in C++) to do O(1) insertion before or after the current position. We start at the beginning of the list, for each i = 1,...,n, insert i at the current position, and move left or right depending on the character of the input s[i-1]. Finally print out the linked list. Complexity O(n).

Method 2: Do it reversely by using a double-ended queue (deque<int> in C++), so we only need to insert at the beginning or the end. First insert n, then for each i = n-1,…,1, if s[i-1] is ‘l’ we insert i at back otherwise front. This should be easier to implement if you don’t know how to work with lists and iterators, but actually both implementations are extremely short.

--Yan

Yan, don’t you need two lists?  Or if you are using just one list, can you explain the API calls that you use to put stuff in the middle of this doubly linked list?  --DS

I just used one doubly linked list in C++ (not sure about other languages). We use an iterator and set it to l.begin() at the beginning. Then in each iteration, we first insert at the iterator using l.insert(it, val), which inserts the value before the iterator it. If we want to insert at the left next, we can move to the next position (the element we just inserted) by it--. If we want to insert right next, we don’t need to do anything since the old iterator is already at the right of the new iterator. --Yan

Is anyone else getting time limit exceeded on test 31? -- HJ… Thanks.

I also ran into that problem in C++ because I was using endl instead of ‘\n’ @HJ - Zack

(If anyone uses Java) System.out.println is also too slow, use BufferedOutputStream - Kevin

B. History

For an event (a,b) to be contained in another event, that means of all events with starting time less than a, the maximum ending time is greater than b. We can keep track of this maximum by iterating through the events in increasing start time, since we are taking a maximum of a chain of increasing sets. This takes O(n log n) to sort, and O(n) to process afterwards. - Zack Lee

C. Maximum Xor Secondary

WLOG we can just consider subarrays whose maximum and the second maximum are the two outermost indices (since any subarray where they aren’t on the outside can just be shortened to one in which they are and yield the same answer). For each index i, there are at most two such subarrays for which i is the second maximum: at most one where the maximum is to the right of i, and at most one where the maximum is to the left of i. Finding each of these is equivalent to finding the closest index j to the right of i such that s[j] > s[i], and finding the closest index j to the left of i such that s[j] > s[i] respectively. We’ll denote these two quantities as ub[i] and lb[i] respectively; both of these can be found for every index using a well-known stack method in O(n) time.  [This “well-known stack method” is explained 35 minutes into this video (and implemented in this code) from last semester’s 295 class. In that case it’s used to find the minimum inside every block of some size d.  But it can easily be modified to compute what’s needed here. -DS]

Once we’ve calculated the lb and ub arrays, we can simply iterate through every index i, updating ans with the max of s[lb[i]]^s[i] and s[ub[i]]^s[i] each time. -- Aditya

I had a different algorithm.  I insert the pairs (i, s[i]]) into an ordered set (built-in).  I do this insertion in order of decreasing value of s[i]; the largest is inserted first, the 2nd largest second and so on.

Now when I’m about to insert (i,s[i]) I find the closest element to its left, call it (j,s[j]) and the closest element to its right, call it (k,s[k]).  And I consider these two options, namely s[i] XOR s[j] and s[i] XOR s[k].  The s[k] and s[j] are the only possible larger elements of a pair that involves s[i] as the smaller element, as Aditya explained above.  All of the needed set operations are supported in the API for sets. O(n log n) ---Danny

D. Bridge Automation

Notice that everytime the bridge is raised/closed a contiguous segment of the boats pass through. This leads us to try to define DP[i] as the cost of letting the first i boats pass through.

DP[i] = minj < i (DP[j] + cost(j+1, i))

and DP[N] would be the answer. To calculate cost(j,i) we note that it’s always optimal to make the j’th boat wait as long as it can, to minimize downtime waiting for boats to arrive. We also see that since the time between boat arrivals is at least the time for a boat to cross, then we need to leave the bridge up until at most Ti + 20. So we can just return 120 + max(T_i + 20 - (T_j + 1800), 20*(i-j+1)) - Zack Lee

E. Multiplying Digits

First: if we factor n to start and take logs, we can see that the problem becomes at least as hard as the bin packing problem, so there is no “nice” way of solving this.  The problem is also only impossible when n has a prime factor at least b.  Consider a naive dp approach, where we try to compute the answer for a given n knowing the answer for all smaller n.  Well, we could figure out all of the possibilities for the smallest digit i---from 2 to b-1---and if that were a divisor of the target number we let that be our last digit and we have the same setup now for n / i, which we invoke the dp on.  Once we’ve gone through all of the last digits that work, we find the one that gave us the smallest number (i + b * subproblem) and return that (if it existed).  Naively, this takes O(nb) time and O(n) memory: clearly unreasonable for our problem.

To optimize this, let’s first try to reduce the number of possible arguments to the dp function.  If we only call the dp function when we need to, we know that we’re going to be calling it with a divisor of n.  Any divisor i of n has corresponds to another n / i, on the opposite side of sqrt(n), so there are at most 2sqrt(n) different calls to the dp function, so our new bound is O(sqrt(n)b) time and O(sqrt(n)) memory.  The other reduction we can make is that we don’t need to check every number from 2 to b, as only divisors of the original n could work and we can compute all those immediately.  This thins down the possibilities for our search by some amount (not sure exactly what).  This passes on its own in just above 90% of the 4 seconds we were given.  - Chris Lambert

F. Airport Logistics

My solution is in this video , starting at minute 39.

---DS