Problem statement

A car is traveling in a directed graph from point $$$A$$$ to point $$$B$$$. Its fuel tank has a capacity of $$$F$$$. Traveling along an edge takes $$$1$$$ unit of time, and will burn $$$1$$$ unit of fuel. The car starts with a full tank of fuel. Some of the vertices in the graph are gas stations where the car can refuel. Refueling takes $$$1$$$ unit of time. What is the minimum time to travel from $$$A$$$ to $$$B$$$ (if it is possible at all)?

Original link to the problem

The best I can come up with

Make a new graph where every vertex is a combination of the vertex in the original graph, and the remaining fuel in the tank: $$$vertex_{new-graph} = (vertex, fuel)$$$. For every edge in the original graph, add corresponding edges in the new graph. If the original vertex is a gas station then we have to add 2 edges (one corresponding to refueling, and one corresponding to not refueling). We can now do a BFS which will take $$$O(V_{new-graph} + E_{new-graph})$$$ time which equals $$$O(F * (V + E))$$$.

Is there a better solution?

Edit: I messed up the time complexity.

I have $$$N$$$ elements and I want to maximize the number of elements that can be selected given to some constraints of the type “you can take at most 1 element from this subset of the elements”.

Example

I have 10 elements (labeled 1 through 10) with constraints:

• You can pick at most 1 element from the set { 3, 4 }
• You can pick at most 1 element from the set { 2, 5, 6, 9 }
• You can pick at most 1 element from the set { 1, 5, 7 }

An optimal solution is selecting elements { 1, 2, 3, 8, 10 }. I found this solution by writing the exponential solution.

I first thought I could reduce it to a maximum matching or flow problem but I failed to do so. Is it a known problem and can it be solved in polynomial time?

After watching SecondThread's Segment tree tutorial I have the following questions:

Question 1: Not merging lazy updates

At this point in the video SecondThread mentions that you need to merge lazy updates for every node into a single update in order for the segment tree to stay $$$O(K * log N)$$$ time for $$$K$$$ queries. I don't understand why that is the case.

Imagine we have a segment tree implemented for range sums and we implement it such that every node has a list of lazy propagation operations (which SecondThread says is bad), instead of a single lazy propagation operation. So for instance if you add +3 to some range, and then add +5 to the same range you would have [+3, +5] as your operations for the corresponding node instead of +8.

Since every rangeAdd will add at most $$$log(N)$$$ of these operations to our lists, it means that in total we will have to push something down $$$O(K * log(N) * log(N)) = O(K * log(N))$$$ times. So the algorithmic complexity does not change. Am I wrong here?

Question 2: Combining "set to" and "add to" operations

Is it possible to make a segment tree that supports both "setting a range to some value" and "adding some value to a range"? I understand how to do each of those separately but I don't see how you can support them both.

This post contains a spoiler for problem C from the Facebook HackerCup finals. If you still want to upsolve this, you might not want to read further.

I really liked this problem but in the end was a bit disappointed that in the end we could not compute the actual probability. What we compute has no interpretation and only proves to the problem setters that we are able to compute this "answer" efficiently. But what is then the usecase of having an algorithm that quickly computes a nonsensical number? If it has no use in practice, then it demotivates me to learn how to solve these kind of large combinatorics questions.

Thinking a bit more about this... we could make a custom BigInteger class using 1000 bit integers and then we could compute the actual probability, right? Is this the reason that it is still useful to be able to solve a question like this efficiently?

Say you have a binary string of length N where each character is equally likely to appear. What is the probability that there will be a substring of K 1 characters?

For instance if K = 2, N = 3 the answer is 3/8 = 37.5%.

000: NO
001: NO
010: NO
011: YES
100: NO
101: NO
110: YES
111: YES

How to solve this problem. Can it be done in polynomial time?