ANTHILL - Editorial

vijju123 · February 2, 2020, 2:50pm

PROBLEM LINK:

Setter- Alei Reyes
Tester- Encho Mishinev
Editorialist- Abhishek Pandey

DIFFICULTY:

CHALLENGE

PRE-REQUISITES:

Basic Graph Theory, Power of Graphs , Clique finding (you can refer here , here (useful to find 3 cliques etc) and here )

PROBLEM:

Given a graph with N nodes and M edges, you have to make this graph from an empty graph using following 2 operations:

1\ K\ E- Put the given K edges (if not already there) and square it. Squaring the graph means that, if there are three nodes u,v,w such that u and v are connected AND v and w is connected, then connect u and w as well.
2 \ u \ v- Remove edge (u,v) for R coins.

Try to minimize the cost of making the given graph G.

QUICK-EXPLANATION:

Key to AC- Heuristics to find square of graph, making clique by finding star etc. seemed to work out.

There are many heuristics you can use to get a good score, like-

Without edge deletion, the problem is finding square root of a graph. Heuristics used there can be applied.
One could find the cliques in graph and generate them, by say, squaring a star.
Many participants also tried finding 3-clique and 4-clique to get more points than brute force.

EXPLANATION:

So this is another challenge problem here. We will discuss the following:

Meaning behind test generation plan. How to frame strategies?
How Brute Force fared and possible optimizations
Other good solutions.

With agenda clear, lets get started.

Interpretting the test-generation plan

First thing to see is that N=512. This means M \leq 512*511/2 = 130816.
Next, A is 10 and R=2. This means that 5 deletions are worth generating 1 edge with operation 1. Its actually not that simple because operation 1 can generate more than K edges as well - but as a very lose upper bound, it seems we are in profit if number of edge deletions is <5*K.
Now, to easily interpret S and L, take it as follow:
- We got S sets with each set having L roads. We execute first operation for each of these sets.
- Then we remove D roads out of the graph and generate the anthill.

The above means that the ANTHILL can potentially have lots of cliques, because in a just one set of size say 100 we are introducing 4950 edges, while D is at most 2048.

This means that graphs like line graph etc are pretty rare to be in test cases. The graph in test cases would have lots, lets say, “connectivity” in the sense that we would be able to find cliques or rather “almost-cliques” in it.

The TL is also generously 5 seconds, so that means we can do a lot of analysis on the graph to check what strategy to best apply.

Brute force and possible optimizations

There are multiple brute forces for this problem.
One of them is, generating all n \choose 2 edges and removing them one by one. This will cost A*N + ( n \choose 2 -M)*R.
Another brute force is to use operation 1 M times to generate just the required edge. The cost for this is A*N and is significantly better than previous solution. This was the brute force used by multiple candidates and got 48.7 points in div2 and 43.7 in div1. Brief code for it is below:

Code

cin >> n >> m >> a >> r;
	cout << m << '\n';
	for(ll i = 0; i < m; i++) {
		cin >> u >> v;
		cout << "1 1 " << u << ' ' << v << '\n';
	}

An improvement to the above is using 3 or 4 cliques to generate the graph. In 3 clique, the surplus edge added is atmost 1, while in 4 clique it really depends on the graph - but it is VERY probable for it to be less than 5 (because there are only 6 edges in it XD). So this solution gets some profit. I saw a LOT of variance in points for this approach. Like, even the 48 point solution in div1 used this approach, and so did the 58.6 solutions. The difference lied in how much you analyzed and used 4 cliques to advantage, and not doing some blunderous errors.
One example of blunderous error was immediately removing surplus edge once generated. It is advisable to remove all surplus edges in last to avoid deleting same edge multiple times.
The highest points achieved by this approach were hard to check but I did saw this logic getting 60+ points - or at least being used in those solutions.

SOLUTION

I would like to link to some of the understandable codes I found while analyzing solutions for this problem:

Brute Force by @who_jeetu here
Small Clique finding solutions by @ashish99hanny here and @tyg3r here
One of the easy to understand top solutions by @arjan_bal here and @zhouyuyang here

CHEF VIJJU’S CORNER

One thing I want to stress on is - WHY ONLY 190 SUBMISSIONS IN DIV2? Clearly a LOT of people got carried away and duped the question thinking that “It is something tough”. The brute force gave 48 points in div2, which is absolutely nuts! 50 points can make a hell of a difference in rank and ratings - so do not shy away from giving the brute force solutions! I once got Laddus for top challenge scorers by just using various brute forces and printing the best out of them. So do not hesitate!

Setter's Notes

Setter notes:

Without edge deletions the problem is like finding the square root of a graph which is an open problem
One idea is to find small subgraphs that can be obtained by squaring, and then cover the original graph with those subgraphs.
Also is possible to find the square root of some kind of graphs like chordals, square of trees, etc.
Using my super-duper sixth sense and my sharp, uncontested competitive coding skills along with my cute Barbie-Baby Yoda magic, I see that brute force will get 43-48 points in Div1 and Div2.
(Lol joke, I added this line here )