3
This problem is a case of maximum flow problem.
Suppose we are given internet providers $p_1, p_2, \cdots, p_m$ and residents $r_1, r_2, \cdots, r_n$. Consider a flow network specified as the following.
Nodes are $s,\ p_1, p_2, \cdots, p_m,\ r_1, r_2, \cdots, r_n,\ t$, where $s$ and $t$ are two extra nodes standing for the source and the sink.
There is an ...
2
Dynamic programming doesn't necessarily mean that your solution will be efficient. It just means that your problem can be defined using a recursive function, for which you can use memoization.
To understand what this function is, take a look at the proof. The invariant is "after $i$ iterations, we've found all shortest paths of length at most $i$". ...
2
Usually when trying to figure out a dynamic programming solution's time complexity, you need to find two values:
The number of elements that will be calculated (or a bound on this number. Notice that "elements that would be calculated" refers to the elements you save with the memoization technique)
The time it takes to process an item, assuming ...
1
The problem confused me as well until I understood that smileys can be separated into a colon and a parentheses if required (because a colon as the text says is also a valid character.) Now you can write a linear algorithm. By counting how many brackets are open, how many could be opened by smileys and how many could be closed by smileys:
int main() {
...
Only top voted, non community-wiki answers of a minimum length are eligible
