Hello,

Greetings good people of Codeforces. I cordially invite you all to take part in the online mirror of 2018-2019 ACM-ICPC, Asia Dhaka Regional Contest. The contest will be held on Saturday, January 19, 2019 at 16:00 (UTC+6).

The onsite contest took place on Saturday, November 10, 2018, where 300 teams competed for a spot in the 2019 ACM ICPC World Finals. I know its been a while, but hey its better late than never.

Contest duration will be 5 hours and will follow standard ICPC rules. The problem set consists of **10** problems and was prepared and tested by Jami_CSEDU, shovonshovo, sgtlaugh, dragoon, nfssdq, raihatneloy, sn23581, SnapDragon, Shahriar Manzoor, Monirul Hasan, Imran Bin Azad and Mehdi Rahman. Moreover, special thanks to Rujia Liu for reviewing and also forthright48 and ridowan007.

Note to any one who participated in the onsite contest, please refrain from sharing or discussing the problems here before the contest. The analysis will be posted once the online mirror ends and afterwards we can all discuss about the problems here.

I hope you enjoy the contest. Cheers!

**UPD:** BUMP! 24 hours to go, buckle up!

**UPD:** Contest has started, see you in the arena.

**Editorial:** https://docs.google.com/document/d/1VEz9q-pXK2KuRJh2WwtlhmdQ882nFDMCdi-7ZOxE47w/edit?usp=sharing

Auto comment: topic has been updated by sgtlaugh (previous revision, new revision, compare).How to solve

A,C,GandI?Please check the editorial and let me know if you have further questions.

for the problem I, I did as below but I didn't get AC:

We can find the shortest distance of a point in 3D space to a triangle in

O(1). at least one of endpoints of the shortest segment that connects two triangles is on edge of one of the triangles (?), then I guess, we can use ternary search to find that point on each of 6 segments.does it right?

btw, how to solve H and F?

My solution for

H: I guessed that the transition is formed by keep rotating clockwise/counterclockwise, which is equivalent. So you can just implement one rotation, the change of positions of # form some cycles, take the least common mulitple of all lengths of the cycles will yield the answer. To compute the LCM, one can just record the power for all primes less than 40000.That's correct. This problem looks daunting at first glance, but ultimately boils down to finding the LCM of all cycle lengths.

However it remained unsolved in the onsite contest: https://algo.codemarshal.org/contests/icpc-dhaka-18/standings

My solution for

F: one observation is that the intersection of two paths is also a path. Let's say the two paths are (u,v) and (uu,vv), then the intersection of the two paths(if they intersect) is the path between the vertices of the four that have largest depth:lca(u,uu),lca(u,vv),lca(v,uu) andlca(v,vv).For I, you can solve it in that way. Although ternary search is not the intended solution here, so you might need some optimizations depending on your implementation. The intended solution has O(1) complexity.

For F, you can simply use bitset. For each node, keep a bitset called

pathcontaining the set of nodes from that node to the root. To find the bitset of any path from nodesa-b, we can now do(path[a] | path[b]) ^ path[lca(a, b)]