sgtlaugh's blog

By sgtlaugh, history, 5 years 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

| Write comment?
»
5 years 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).

»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

How to solve A, C, G and I?

  • »
    »
    5 years 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.

»
5 years 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?

  • »
    »
    5 years 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.

  • »
    »
    5 years 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).

  • »
    »
    5 years 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

    • »
      »
      »
      4 years 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)]] ?

      • »
        »
        »
        »
        4 years 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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain, how F will not give TLE?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I get all the test cases for problem E?

  • »
    »
    5 years 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
    
»
5 years 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
»
4 years 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.

  • »
    »
    4 years 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.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone explain how to solve B. I read the editorial but I am not clearly getting what would be the formula for counting the number of inversions.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    I think that my solution is a bit differ from solution in the editorial but I'll try to explain how I compute number of inversions.

    Spoiler
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is actually more intuitive and clear. Thanks a lot.

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

      Nice! We can solve the problem with standard digit DP as well. To calculate the value any particular digit adds to the inversion, we only need to know how many digits greater than it were placed before. As such we can have the frequency of each digits as a state in DP (this number won't be very large) and apply standard digit DP as usual.

      Solution

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I thought of this but we have a lot of queries also. The sum of frequencies won't exceed 14, but isn't it still very high? How were you able to calculate the total number of states?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 3   Vote: I like it +8 Vote: I do not like it

          Isn't that just the stars and bars problem for a fixed length $$$N$$$ with $$$D$$$ (here $$$D=10$$$) digits to choose from? For $$$N=14,$$$ there are $$${14 + 10 - 1}\choose{10}$$$ or $$$1144066$$$ unique states.

          https://oeis.org/A001287

          And you can apply memoization for multiple queries. You don't need to compute the whole thing over and over again, but just for each prefix. It's a fairly common trick in digit DP problems.

»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Can anyone explain solution to Problem G. I read the editorial but couldn't understand how the type 3 queries can be solved using centroid decomposition and segment tree..

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    I don't use mentioned in editorial lca technique in my solution.

    First, we convert each type 3 query into $$$M$$$ queries (we skip companies that have 0 shops now):

    Given vertex $$$V$$$ in a tree and a range $$$[L_i, ..., R_i]$$$. Find the distance from $$$V$$$ to the nearest vertex from this range.

    What if L = R?
    Back to the general case