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, Light 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

Contest starts in about 15 minutes.

Where can I find the solutions for these problems ?

Updated post.

How to solve E?

First, find the number of connected components,

c. Now, there are 5 cases.c> 3: There is no solution.c= 1: The graph is already connected, so the result is 0.c= 3, cycles in different components: Let's say the components areA,B, andCand the cycles are inAandB. To make graph connected, there are three ways, , or . By , I mean to erase an edge fromXwhich is part of a cycle and connect either of its endpoints toY. To find an optimal way, you can iterate on edges which are part of the cycle inX, store nodes ofYin sorted order and find the nearest node.c= 3, cycles in the same component: Let's say the components areA,B, andCand the cycles are inA. SaySandTare the sets of edges of two (simple) cycles andP=S-T,Q=T-S, . The possible way is to choose two edges, each from distinct sets (amongP,Q, andR), erase them and connect either of their vertices toBandC. So, there are 6 ways basically.c= 2: The components areAandBand the cycle is inA. You can choose an edge from the cycle, erase it and connect either of its vertices to a node inB. 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