Motarack's blog

By Motarack, history, 5 years ago, In English

Hello Everyone!

The problem set of AICCSA, which was held last Saturday, will be available in Codeforces Gym tomorrow, Oct/30/2018 19:00 (Moscow time)

The problems were prepared by Hasan0540, Hiasat, Dark and Motarack. We would like to thank MikeMirzayanov for Codeforces and Polygon, and ifsmirnov for Jngen.

The contest duration is 5 hours, and it is intended for teams of three. We believe the difficulty is suitable for people with rating in the range [1600, 2600].

We hope that you enjoy the problems, and we welcome any feedback.

UPD: Tutorial link

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

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

Contest starts in about 15 minutes.

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

Where can I find the solutions for these problems ?

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

How to solve E?

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

    First, find the number of connected components, c. Now, there are 5 cases.

    1. c > 3: There is no solution.
    2. c = 1: The graph is already connected, so the result is 0.
    3. c = 3, cycles in different components: Let's say the components are A, B, and C and the cycles are in A and B. To make graph connected, there are three ways, , or . By , I mean to erase an edge from X which is part of a cycle and connect either of its endpoints to Y. To find an optimal way, you can iterate on edges which are part of the cycle in X, store nodes of Y in sorted order and find the nearest node.
    4. c = 3, cycles in the same component: Let's say the components are A, B, and C and the cycles are in A. Say S and T are the sets of edges of two (simple) cycles and P = S - T, Q = T - S, . The possible way is to choose two edges, each from distinct sets (among P, Q, and R), erase them and connect either of their vertices to B and C. So, there are 6 ways basically.
    5. c = 2: The components are A and B and the cycle is in A. You can choose an edge from the cycle, erase it and connect either of its vertices to a node in B. There is another possible way, too. Remove an edge from the cycle, join either of its endpoints to a vertex in the trees dangling from the nodes in the cycle, thus, enlarging the cycle. This will give you access to more edges which will be part of the new cycle. For example in the graph here, optimal way is to remove edge (5, 4) and connect (5, 3) instead and then remove (6, 2) and join (6, 1). This will have cost 2.

    Accepted solution: 45389010