Vendetta.'s blog

[Gym] 2018 ACM Amman Collegiate Programming Contest
By Vendetta., 6 years ago, In English

Hello Codeforces,

I would like to invite you all to participate in the 2018 ACM Amman Collegiate Programming Contest (AmmanCPC 2018). The contest was originally held on the 5th of May, and it will launch in Codeforces Gym on Saturday, 2 June 2018 10:00 UTC.

The problems were prepared by alfadel (Ali Fadel), Vendetta. (Ibraheem Tuffaha) and The-Legend (Abdulmajeed Alzoubi).

Thanks to flerynn (Yosef Darwish), M.Dawwas (Mohammad Abu Dawwas), customer101 (Abdalrhman Ali) and Qumair (Fares Obaid) for sharing the ideas of four problems, to Motarack (Motasem AL-Kayed), customer101 (Abdalrhman Ali) and SAFWAN.K (Safwan Olaimat) for testing some of the problems and to Ownography (Eyad Hajja) for reviewing problem statements.

Also a big thanks to Um_nik (Alex Danilyuk) for sharing the solution idea for a problem and to Hasan0540 (Hasan Alhamsh) and justHusam (Husam Musleh) for the contest wouldn't have been possible without their help. :)

The duration of the contest is 5 hours, and the registration will be open 6 hours before the start of the contest.

Good luck for everyone, and I wish you all Accepted solutions.

UPD: Tutorial

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

Comments Comments (19)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.com/gyms

→ Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

It was a nice contest, thanks! will there be any tutorial?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    Thanks, Glad you liked it. and yes there will be a tutorial which will hopefully be posted in the next 24 hours, sorry for the delay.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Tutorial is up.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve M?

What I actually did is:
1) for each query x and y find the lca of them.
2) ans = cost of going from x upto lca + cost of going from lca down to y + for any node on the path between x and y maximum possible cost of going from this node to any leaf node (which not in the path between x and y) and cost of coming back from that leaf to that node.

I maintained 2^i th max cost along with 2^i th parent and used binary lifting (lca style) to find the maximum double traversal cost.

But I stuck in: how to maintain that maximum double traversal cost which is not in the path between x and y ?

Can anyone help me? Or share your idea how you solved this problem?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Well the solution is pretty simple

    Consider sum = sum of ALL costs.

    Now since we can go over any edge twice, when we move from X to Y we can traverse ALL the edges twice except the edges on the path from X to Y. Root tree at 1. So just store this data:

    Cost of moving from root to node let it be A[i] for ith node

    Cost of moving from root to node but considering the reversed cost. let it be B[i] for ith node

    Finding LCA is a standard task. let L = LCA(x,y)

    answer = sum -(A[x]-A[L])-(B[y]-B[L]) (just remove the costs of edge we cannot traverse).

    So you dont have to maintain "maximum double traversal cost" because ALL edges can be traversed except the ones on the path from x to y.

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

      Ohh ! I got it.

      I considered to traverse twice only any single path whose sum is maximal. But I can traverse any edge twich other than those are in the path between x and y.

      Now found my mistake. Thanks you so much !

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

How to solve A and J?

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

    A: optimal segment begins where one of the segment begins or ends when one of the segment ends.

    J: case bashing basically, depending on most significant bit of A, B and V. Key observation: 2^k OR (2^k — 1) is (2 ^ (K + 1) — 1). If A, B and V have the same most significant bit, we can apply recursion. Be careful on tight TL

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

      Thanks for the reply. Can you elaborate a bit more on A?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        lets say the segment we have to form is A to B (B-A+1=k)

        now consider if A lies within some given segment.

        Where can B be? it can be " not in any segment " in this case we shud just move A to left till B is not in any segment. since doing so will only increase our answer.

        now lets say B is at the end of some segment and A is still between some segment.

        If value of the segment B is in, is less than the value of segment A is in, then we should continue moving A to the left till A reaches the beginning of that segment(note that our answer will still increase only.) but if the value is larger then we should not move A(because our answer will decrease)

        Try to do this analysis.

        Now We know that optimal segment will either always start at starting of some given segment or will end at ending of some given segment.

        So we only consider such segments using two pointer or line sweep or whatever you call it, and then return the maximum value.

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

    Tutorial is up.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the model complexity in G and L? Vendetta.?

Also, time limits in M and J were quite tough imho. I got TLE quite a few times being punished for too slow I/O.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    O(K × A3) for G where A = 26, and O(N2 × M × N!) for L.
    As for the limits they were at least double the time needed for the judge main solution to run using fast I/O for all problems.
    Didn't get the chance to check on I/O efficiency and add notes, sorry for that.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Hmm, I think I know how to solve G in AK log A :D

      And it seems my idea for L is far from intended. Thanks :)

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

        For problem G, there are probably ways to improve the solution whether using more greedy approaches than what we did or improving the implementation. As for L there is another solution which probably runs O((N - 1)!3 * log(M)) using Matrix Exponentiation.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Tutorial is up.

        → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there some place I can access the data to debug?

→ Reply