Let's choose a subset of edges, and then color each vertex black and white. If u and v are connected by a chosen edge, they must be colored with the same color. Also, vertex 1 must be colored white. How many ways are there to do this?

• Suppose that we fix the set of edges. Then, the number of valid colorings is 2^{components - 1} and this is odd only when the entire graph is connected. Thus this is what we want to compute.

• Now let's fix the coloring first. In this case, the number of valid subset of edges is odd only when the coloring is a valid bipartite coloring for the entire graph.

"what is the intuition behind this fact? How to come up with it without knowing it in advance? I would be grateful if the readers could shed some light here." — ok, so here's how we derived the answer, not just proved the guess (more specifically Marcin_smu did it). Strategy was very similar to the solution of problem C2 from that Petrozavodsk. If one knew solution to that problem this one was much easier.

Consider bad subsets of edges. For bad subset of edges we can divide vertices into two groups (A, B) so that there are no edges between them. We will count such triples (bad subset of edges, A, B), where (A, B) is partition of V and first vertex belongs to A (otherwise everything would be even trivially). But hey, if graph with our subset of edges has more than two connected components there is more than oen way to divide connected components into A and B! But if there are k of them then there are 2^k - 1 - 1 ways to do so, which is always odd! So our answer is equal to number of such triples! But if we fix A and B first then there are 2^e bad subsets of edges corresponding to them, where e is number of edges within A and within B in total. But this is almost always even. Only case when it is odd is when A and B are independent sets, or in other words if our graph is bipartite :). Since our graph is connected there is only one way to partition its vertices into two independent sets, so we are done.

Maybe a bit more complicated than Makoto's proof, but that's how you can come up with it not knowing answer in advance.

C: Duh, that SRM's editorial is so long :P. What I did is very similar to what is described here: http://petr-mitrichev.blogspot.com/2015/10/a-week-with-sheafs.html (probably similar to what is written on TC, however much shorter), however my solution has complexity and at first it took my code 100s to complete maxtest, whereas TL was 2s. Using some weird optimizations I fortunately made it to pass :p. However I have heard that there is a solution in complexity , but I couldn't understand it at problem analysis.

D: I am not sure it can pass by using preprocessing. We had that idea, but there are some problems with this approach. Note that there are 100000 testcases. Moreover we need to compute those phis (that comes with log log n factor to complexity). We can do something a bit more clever and preprocess points of form k³ instead of k·100000, but it is still shaky. Maybe it will pass, maybe not, but this task still has a solution not using "preprocessing cheating". Computing those sums boils down to computing prefix sums of μ(i)·i^k for k=0,1,2 for some specifics points. I didn't figure it out to the end, but I think main ideas are contained here: https://www.mimuw.edu.pl/~pan/papers/farey-algorithmica.pdf or in editorial to Four Divisors problem: http://mirror.codeforces.com/blog/entry/44466

D can be solved in O(n^2 / 3) as described here

Divide rectangles on left and right and sort them by b. Then calculate dp[i][j] as maximum weight when upper left rectangle is left[i] and upper right — right[j].
It can be computed in next way:
If left[i].a > right[j].a then dp[i][j] = left[i].weight + max_over_k(dp[k][j]), where left[k].b < left[i].a. Otherwise same logic but with right[j].
Use two additional maximum_on_prefix_dp and it will be O(N²).

How did you solve it?

I: Theorem: Let T = A·B with , and let Y be a subtree of root(B) with maximum number n_Y of vertices. Then the subtrees of root(B) are exactly the subtrees of root(T) with at most n_Y vertices. Proof: Reduction to Absurdity.

Using above theorem you can easily to prove that the factorization is unique.

Compute the hash value of all the subtree, and sort all the subtree according to their size. By enumerating the value of n_Y, we can find the subtrees of B. Using the hash value to check if this tree is a factor of T. This leads to an O(n·d(n)) solution, where d(n) is the number of divisors of n. By combining with some string matching technique, we can get an O(n) solution.

For problem A.

Apparently, if s is less than or equal to 1010, there is no solutions. Otherwise, we can always find a solution.

If s has d (d > 4) digits, then$\underline{999\ldots 999}898$((d - 4)'s 9 followed by 898, (d - 1) digits in total) is almost bobo. We can use this fact to solve the case where there is no almost bobo number having the same length with s. Now, we can assume there always exists an almost bobo number having the same length of s.

Apparently, the answer has a longest common prefix with s, let's denote it as p. In order to find p, we need to enumerate all the prefix, and check if this prefix can be a solution.

Assume the prefix is s^′, we need to append another digit c to s^′, in such a manner that c < s(|s^′| + 1). Let's call the new string be t (assume the consecutive equal digits are merged). To append some other digits to make t almost bobo, we need find a border u of t (t = uxu, for some nonempty string x), such that |t| - 2|u| ≤ |s| - |s^′| - 1 (there are some other small cases, just ignore it for now). So, we should find a u with maximum length, we can call it half border.

As showed in this paper, Efficient data structures for the factor periodicity problem, all the border longer than half forms an arithmetic progression, we can determine the half-border with KMP in O(1).

After finding the longest prefix, we can just append more digits from 9 to 0 to find a largest answer (the rule used above can be used to check if the digit is a part of the answer).

Yes. http://opencup.ru/files/och/gp11/problems1-e.pdf