SPOILER ALERT: Please do not read these hints if you want to solve some problems in this contest but haven't attempted yet.

**DO NOT open if you want to solve them by yourself**

Hints are categorized by the number of accepted teams.

**hints for ADEFI**

102028A - Xu Xiake in Henan Province

**hint for A**

Read and implement.

102028D - Keiichi Tsuchiya the Drift King

**hint for D**

There are only two cases, so just draw them on draft paper.

102028E - Resistors in Parallel

**hint for E**

The resistance of the *n*-th section is a multiplicative function of *n*, which only depends on distinct prime factors.

**hint for F**

BFS is enough.

Be careful with leading whitespaces and too many test cases.

**hint for I**

Picking half of points from every boundary is enough.

**hints for BCH**

102028B - Ultraman vs. Aodzilla and Bodzilla

**hint for B**

Let *f*(*n*) be the minimal integer *t* such that .

If the first died monster has *p* health points and the second one has *q*, the best strategy should lead the former one to die at *f*(*p*)-th second and lead the latter one to die at *f*(*p* + *q*)-th second.

The rest is just to enumerate which one should die firstly, and construct the lexicographical smallest strategy greedily.

Be careful when the received damages are equal in these two cases.

**hint for C**

One observation is that coordinates of rooks in each type form a permutation.

If split the area into 9 grid regions, one can find rooks can only collide in at most 4 regions.

Coordinates are easy to maintain as well.

102028H - Can You Solve the Harder Problem?

**hint for H**

Suffix structures may help counting distinct contiguous subsequences (intervals).

Segment tree (or fenwick tree) with stack may help maintaining maximum values of intervals offline.

**hints for GJKL**

102028G - Shortest Paths on Random Forests

**hint for G**

Let *f*(*n*) be the number of labelled forests having *n* vertices, *g*(*n*) be the number of pairs of reachable vertices in labelled forests having *n* vertices, and *h*(*n*) be the sum of lengths of the shortest path between every pair of reachable vertices in labelled forests having *n* vertices.

Calculating *f*(*n*) is typical: Enumerate the size of component containing label 1, and conclude . Speed it up by divide and conquer (or Newton iteration).

For *g*(*n*), one can conclude by enumerating contributions of each component.

For *h*(*n*), it can be reduced into counting the number of ways to pick *k* ordered edges on the shorest path between every ordered pair of vertices (*k* = 1, 2). Imagine these *k* edges split a component (tree) into (*k* + 1) components (trees), and one can conclude calculating the number of ways is equivalent to calulcate the (*k* + 1)-th power of the polynoimial .

**hint for J**

There are two cases which depend on if carpets intersect, so we need to know the number of squares covered by exact *k* carpets (*k* = 1, 2).

It is easy to show the number of useful pairs of 2 carpets is at most *m*^{2}, so the difficulty of this problem is only counting the number of squares covered by exact *k* carpets.

Sweep line with segment tree can do this in , while maintaining some statistics obtained from 2-dimensional partial sum and solving equations for each square can do this in *O*(*k*(*n* + *m*^{2})).

102028K - Counting Failures on a Trie

**hint for K**

One can easily determine if a substring forms a matching path starting from node 0 by binary search with hashing, so for each left endpoint, one can find the mismatched right endpoint quickly.

Then for each query, binary lifting could speed up the process of failed matching.

**hint for L**

There are 5 types of connected subgraphs, one can count them using inclusion-exclusion principle, which leads to count the number of *k*-cycles in the graph (*k* = 3, 4).

One can solve the typical counting problem in .

For problem K, though solutions are accepted, there exist some solutions in .

One observation is that what we need to do is to match the suffix tree of

Swith the trie.Assuming suffixes of string

Sare sorted in lexicographical order, one can observe that each node in the trie can match a contiguous subsequence of sorted suffixes.Thus, using binary search to match a single character with these suffixes is enough, which does not require hashing.

For problem L, how to count the number of 4-cycles in such time complexity?

Let's sort vertices in degree non-ascending order and relabel them, that is, if

uis thei-th element after the sort, we relabel it asi.We may enumerate

a,b,c,dranged from 1 tonand check ifa-b-c-d-aform a 4-cycle whena=min(a,b,c,d) andb<d. It is easy to show, for each simple 4-cycle, it will be counted exactly once.Actually, we can just enumerate 3 vertices to accomplish the mission. Let's set a counter

cnt(w) for each vertexw. And then, do the following algorithm:ufrom 1 ton:u, vertexv, such thatu<v:v, vertexw, such thatu<w:cnt(w) is set to 0.u, vertexv, such thatu<v:v, vertexw, such thatu<w:cnt(w) 4-cycles (u-v-w-x-u,xis one of visitedv);cnt(w) by 1.~~Do you notice that~~vcan be less or greater thanxbut each 4-cycle is still counted exactly once?Analysis of time complexity:

uisO(n);u→vare in totalO(m);u→v→wwithu<vare categorized by the degree ofv:vis less thanT, then for eachu→v, the number ofwsuch thatv→wis less thanT, so the number of this type ofu→v→wisO(mT);vis at leastT, then the degree ofuis at leastTas well, so the number ofusuch thatu→vandu<vis at most , and thus the number of this type ofu→v→wis ;T≤n) is , when .~~Does the aforementioned algorithm really need a threshold~~T?Btw, you need to store the graph using something like

`std::vector`

, otherwise the cache missing will lead to TLE like my code.How to solve problem E (Resistors in Parallel)?

for the given Input:

am I missing something?

r_{8}= ∞ because 2^{2}|8. And consequently, the resistance ofS_{8}should be , which is equal to the resistance ofS_{2k}fork= 1, 2, ....sorry, my bad! how should i proceed with this since the numbers are really large (100 digit number) and couldn't find any relation with the given hint(finding prime factors would also timeout)?

With the hint, the remaining is a problem about the constructive algorithm. Try to avoid the factorization. GL!

Can someone please elaborate on the hints given for problems D and E?

The time limit of L seems too tight? I tried various ways of optimization (including

`fread`

-based input) and finally get AC in around 11.2 sec / 12.0 sec...ps. My AC code

I couldn't understand the hints given for problem C. Can someone please explain ?

How do you prove that the greedy solution is correct in B?