sgtlaugh's blog

By sgtlaugh, history, 9 months ago, In English,

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

 
 
 
 
  • Vote: I like it
  • +89
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it +32 Vote: I do not like it

How to solve A, C, G and I?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please check the editorial and let me know if you have further questions.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +37 Vote: I do not like it

    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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    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).

  • »
    »
    9 months ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sgtlaugh bhaiya, shouldn't it be (path[a] or path[b]) xor path[parent[lca(a, b)]] ?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I get all the test cases for problem E?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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
    
»
9 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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 1
Step 2
Step 3
Step 4
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.