Calculate the sum of the digits of both integers, and print out the maximum.

Time complexity: $$$O(1)$$$ My solution

As the slope $$$m$$$ of a line between two points $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ can be found by the equation $$$m = \frac{y_2-y_1}{x_2-x_1}$$$, we simply need to compute the value of $$$m$$$ for each pair $$$(i,j)$$$, while adding $$$1$$$ to our count every time $$$-1 \le m \le 1$$$.

Time complexity: $$$O(N^2)$$$ My solution

We observe that a string $$$T$$$ is unsatisfiable if there exists $$$S_i$$$ such that $$$S_i = T$$$ and $$$S_j$$$ such that "!" $$$+ S_j = T$$$. We can maintain a data structure, such as a map or a set, and each time we add a new string to our set, we check if its pair string (with or without a leading "!") has already been added. If it has, we have found our answer, and we can simply print it (removing a leading "!" if necessary), and exit.

If, after processing all the input strings, no unsatisfiable string has been found, we print "satisfiable".

Time complexity: $$$O(|S|log(|S|))$$$ My solution

Notice that every time Takahashi makes a speech in some town $$$i$$$, his vote count, relative to Aoki's vote count, increases by $$$2A_i + B_i$$$, as he gains $$$A_i + B_i$$$ voters, while Aoki loses $$$A_i$$$ voters. We can sort the towns in decreasing order of $$$2A_i + B_i$$$, and greedily take the town which adds most relative votes until Takahashi's relative votes are greater than Aoki's.

Time complexity: $$$O(NlogN)$$$ My solution

As all queries involve certain edges, once we perform a DFS traversal of the tree, rooted at some arbitrary vertex, each query will involve a parent and child vertex in some order. If we are asked to increase by $$$x_i$$$ the vertexes reachable from the child vertex without visiting the parent vertex, we can simply increase the value of all vertexes in the child vertex's subtree by $$$x_i$$$. On the other hand, if we are asked to increase by $$$x_i$$$ all the vertexes reachable from the parent vertex without visiting the child vertex, we need to increase by $$$x_i$$$ all vertexes which are not in the subtree of the child vertex. We can do this by maintaining a variable which is to be added to all vertexes, and increasing it by $$$x_i$$$, and decreasing the value of all the vertexes in the child vertex's subtree by $$$x_i$$$, effectively undoing the global change for those vertexes. We can perform these changes by doing a total of two DFS traversals.

Time complexity: $$$O(N)$$$ My solution

This is a classical dynamic programming with bitmasks problem. We can calculate the minimum amount of components possible for some mask $$$m$$$, and iterate over its submasks to reduce this number further. More to be added if there are requests for such.

Time complexity: $$$O(3^N)$$$ My solution