PROBLEM LINK:
Setter Alei Reyes
Tester Encho Mishinev
Editorialist Abhishek Pandey
DIFFICULTY:
CHALLENGE
PREREQUISITES:
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.
QUICKEXPLANATION:
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 3clique and 4clique 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 testgeneration 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 â€śalmostcliquesâ€ť 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.
Other good solutions
 Clique finding gave 7080 points.
 What we could vaguely make out was, participants chose some integer K. They now found a clique of size \leq K [clique finding is NP hard so one needs to decide K appropriately!]. Once the clique was found, it was eliminated from the graph and the process was repeated till no cliques were seen. There were some heuristics used to make it better, like outputting even â€śnearcliquesâ€ť or combining 2 â€śnear cliquesâ€ť &etc which resulted in variance in points.
 But in general, the score was higher for participants who set K higher as number of edges generated in clique rise quadratically with number of vertices.
 This approach also agrees with the test data generation  because the graph generated is not just any random graph  we discussed already on how it favours having a lot of cliques/â€śalmostcliquesâ€ť.
As usual, no challenge editorial is complete without participants explaining their approach  hence, I will want to invite EVERYONE to discuss their approaches and how many points they got
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 superduper sixth sense and my sharp, uncontested competitive coding skills along with my cute BarbieBaby Yoda magic, I see that brute force will get 4348 points in Div1 and Div2.
(Lol joke, I added this line here )
Related Problems
 Kali and Devdas
 Tom and Jerry  Get your clique finding skills to good use
 Clique Problem