894A — QAQ

Since n ≤ 100, we can iterate on the place of first 'Q','A' and second 'Q'. The brute force solution will work in O(n³) time which can surely pass. If we only iterate on the place of 'A', we can get the number of 'Q' before and after it using prefix sums, and it leads to O(n) solution.

PS: The characters in problem 894A is Diamond and Bort from Land of the Lustrous.

894B — Ralph And His Magic Field

First, it's obvious that the numbers put can be only \t{1} or \t{-1}. If k equals to \t{-1} and the parity of n and m differ, the answer is obviously 0.

Otherwise, for the first (n - 1) lines and the first (m - 1) columns, we can put either \t{1} or \t{-1} in it, and there're 2[(n - 1) * (m - 1)] ways in total. Then it's obvious that the remaining numbers are uniquely determined because the product of each row and each column is known already. So in this case the answer is 2[(n - 1) * (m - 1)].

894C — Marco and GCD Sequence

If the minimum element isn't the gcd of the given set, the answer is \t{-1}. Otherwise, we can insert the minimum element between two consecutive elements of the set. And the length of the sequence is 2n - 1 which satisfies the constraints.

894D — Ralph And His Tour in Binary Country

Before answering each query, pre-process on the tree. On each vertice, we can get a sorted array of all the vertices in its subtree sorted by distance to this vertex. And it costs O(nlog(n)) time using merge sort or O(n(log(n))²) time using \t{std::sort}. If you use \t{std::sort}, you should implement it carefully or it won't be able to fit in the time limit. Because the tree is an almost complete binary tree, one vertex will appear at most [log(n)] times in all n sorted arrays,so the memory complexity is O(nlog(n)).

To answer each query, we can iterate on the highest vertex on the tour and do binary search on the sorted array to get the answer. We'll do at most [log(n)] times of iteration and the binary search is O(log(n)) per iteration, so we can answer each query in O((log(n))²) time.

Overall, the time complexity is O(nlog(n) + m(log(n))²) and the memory complexity is O(nlog(n)). If you use \t{std::sort}, the time complexity will be O((n + m)(log(n))²) and the memory complexity is the same.

894E — Ralph and Mushrooms

For collecting the most mushrooms, when in a strongly-connected component we can pass all the edges in the component until the mushrooms on the edges are all 0. So we can run Tarjan's algorithm to find all the SCCs in O(n + m) time and calculate the sum of mushrooms picked in each component by binary search or maths knowledge in O(m) time.

Then we can regard each SCC as a new vertex and get a DAG, and the remaining work is just to find the longest path on the DAG from a given vertex, where the length of an edge is the number of mushrooms in it initially, since we can only pass through it once. We can use topological sort and apply dynamic programming on the DAG in O(n + m) time. Overall, the time complexity is O(n + m).