For every x in range A to B, run sliding window of size x maintaining the sum of elements in ranges of length x, and take the one having the maximum average. Read about Sliding window here. The max(max sum in the range of length x/x) is the answer. Time complexity O(N^2).
Build prefix arrays in 2d to compute the sum of subgrid in O(1) time as explained here and for each intersection point, calculate the values of all 4 subgrids if the current intersection is chosen and take the min. The intersection has the maximum value of min is the best intersection. Time complexity O(N^2).
We run a DFS from each node maintaining an included array. The thing is, that once we consider one friend, there’s no benefit to consider him again. So, Running DFS only on non-included nodes at each step leads to a solution in O(N) time.
This problem is dynamic programming. We precompute cost(i, j, k) being min cost to convert array range [i, j] to bit k, k being 0 or 1.
Now, Let us use dynamic programming with two states, index of array covered and bit at ith node. DP*[j] = min(DP[i-j][k^1]+cost[i-j+1][k]) for all x \leq j \leq y. Time complexity O(N^2).
It is tree DP, for each node x, calculate DP(x) = max length path from x to any node in the subtree of x, which has a maximum length. The minimum value of DP(x) is 0 since we can always have a path from x to x itself.
For query u, v, we join two nodes in the subtree of u and v, to get max path length DP(u)+dp(v)+w.
Now, only 2 paths exist between u and v. One with length DP(u)+dp(v)+w and the other from u to LCA(u,v) to v, the length of which can be precomputed computed by DP or binary lifting.
Time complexity is O(N*logN+Q*logN). Dp can be precomputed in O(N) time, overall time complexity dominated by LCA finding.
We use DP*[j] meaning min cost to reach node i after covering first j characters of the string. Clearly, at each character, we can run multisource Dijkstra to compute min cost to other vertices. Now, Core thing is, for next step, consider only those vertices as the source which have s[j] == a*. This way, answer is min(dp*[|s|]) for i such that a* == s[|s|-1]. Impossible cases include disconnected graphs and character not present at all.
Time complexity is O(|S|*(N+M)*log(N)).
Hope you guys had a nice contest.