### sgtlaugh's blog

By sgtlaugh, history, 12 months ago, ,

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.

• +89

 » 12 months ago, # |   0 Auto comment: topic has been updated by sgtlaugh (previous revision, new revision, compare).
 » 12 months ago, # |   +32 How to solve A, C, G and I?
•  » » 12 months ago, # ^ |   0 Please check the editorial and let me know if you have further questions.
 » 12 months ago, # |   0 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?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +37 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.
•  » » » 12 months ago, # ^ |   +5 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
•  » » 12 months ago, # ^ |   +37 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) and lca(v, vv).
•  » » 12 months ago, # ^ | ← Rev. 4 →   +5 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 path containing the set of nodes from that node to the root. To find the bitset of any path from nodes a-b, we can now do (path[a] or path[b]) xor path[lca(a, b)], and set lca(a, b) explicitly
•  » » » 4 months ago, # ^ |   0 sgtlaugh bhaiya, shouldn't it be (path[a] or path[b]) xor path[parent[lca(a, b)]] ?
•  » » » » 4 months ago, # ^ |   0 Yeah sure, but I left out that part intentionally since the parent may not always exist (if the lca is root). Updated the comment, should be clearer now.
•  » » » 2 months ago, # ^ |   0 Can you explain, how F will not give TLE?
•  » » » » 6 weeks ago, # ^ |   0 You mean the bitset approach?The overall complexity for the bitset approach will be O(N^2/32) + O(Q*N/32) per test case. There can be at most 50 cases, and N and Q can be at most 10,000. So even in the very worst case, you don't need to do more than ((10000^2/32) + (10000*10000/32)) * 50 operations, which is roughly 3*10^8.This should run well under 1 second since the operations are very simple. And the time limit is 3 seconds so that should be more than enough.
 » 12 months ago, # |   0 Can I get all the test cases for problem E?
•  » » 12 months ago, # ^ |   +8 No you cannot.However, this is the case for which your latest code fails.Input: 3 D:08:04:38:16:41:01 D:14:25:02:22:40:07 D:01:29:08:08:50:32 Correct output: 2 Point(s) Deducted 
•  » » » 12 months ago, # ^ |   0 Thanks. Now I fix my mistake.
 » 12 months ago, # |   +16 Problem I is a well known 3D geometry exercise, which I like cause it have beautiful solution. I'd like to use this opportunity to write some more detailed solution. Checking out this problem will be also helpful. Step 1If both points strictly lies inside of triangle, you can always move toward a direction with non-increasing distance. Now, one of them is in triangle, and one of them is in line segment.If one point strictly lies inside of triangle, and one point is not an endpoint of line segment, you can again find a good direction. Now, you should calculate 6 point-triangle distance, and 9 segment-segment distance. Step 2Point-triangle distance could be easily checked. If it's orthogonal projection lies in a triangle, you can just calculate the distance between plane and point. Otherwise, it's a point-line distance which is also easy. Then, what about segment-segment distance? Step 3Now we should calculate the distance between segment and segment, which is the meat of the problem.First idea is to parametrize the segment and do nested ternary search, which is actually OK as TLs are lenient and you don't need exact numbers. But it's boring. Second idea is to parametrize the segment and calculate partial derivative by hand, which is O(1) and gives an exact number. But it's boring and disgusting.Having a nice geometrical model like Step 2 is desirable, but how? Hint: Parametrization actually helps. Step 4Let the endpoint of both segment be (S1, E1) and (S2, E2). What you actually want is Plot all areas with coordinate X + Yt + Zu. How does it look like? A parallelogram, which is a union of two triangles. Then, you should calculate the minimum distance between (0, 0) and two triangles, which is what we exactly did in Step 2.
 » 5 months ago, # |   0 How to solve F?How to build the logic where we can increment each node from given path and at the end just count which node has value k?
 » 4 months ago, # |   0 Can I get the test case for F. My approach is similar to what RoundGod mentioned here, but I am not able to figure out what's wrong in my code.
•  » » 4 months ago, # ^ |   +5 Sure you can, send me your email via DM and I'll share the package. You should be able to see the cases from coach mode in gym too.
•  » » » 4 months ago, # ^ |   0 Thanks.