What was your approach for these two problems ? Especially people scoring more than 70 pts
Anthill:
Try to greedily find cliques in the graph. We can use operation 1 on a star graph with n nodes to create a clique of size n. This gives ~ 80 points.
To improve, randomly find spanning trees in the graph, and choose the ones give the best ratio of edges create to cost.
Chefarmy:
You can get like 80/90 points with the following greedy:
For each node u, replace it with a chain of s[u] nodes. Then create x groups, where x is the depth of the tree. Put a node v in group depth[v].
You can get more points with a DFS which combines the results for subtrees in a similar way I described above. Before combining, sort the group by the number of generals made angry.
Lastly, note that the problem can be modeled as linear programming. We can get a few points by using simplex after we perform the greedy algorithm.
so, for each clique, you use operation 1 with k edges as edges of spanning tree of the clique ? And then use more operation 1 to join the cliques (if that is required ) ?
Yes, after I choose a clique, I perform operation 1 and remove it from the graph. I repeat until all edges are gone.
so, for each level, you find all nodes that belong to that level, and print them together ?
can you explain a little more about simplex method ?
What I tried was for each node, check from all remaining nodes which aren’t ancesstors of current node. But I dont understand why it gives less points .
so, for each level, you find all nodes that belong to that level, and print them together ?
yes
can you explain a little more about simplex method ?
These resources should help:
So with a greedy approach, we will get approx 80 points (because of TLE in some cases??). Also, In this approach, we are not using operation 2 at all. Correct me if I am wrong.
ANTHILL:
I found out all the cliques of the given graph , but could find cliques with max 16 nodes above which my algorithm gives a TLE and removed them in decreasing order of size .
I made two processes and calculated the cost and printed the best among them.
in first process i removed the cliques (size = 16)
in second process i did not remove the cliques so if there are two overlapping cliques ( i calculated if it is profitable to output two overlapping cliques)
My only drawback was i could not implement a better algorithm to find maximal cliques.
This gave me 79 points
CHEFARMY :
I do not know why this works but i completely ignored the anger of generals .
I made the tree. Took all the leaf nodes and gave the minimum number of coins to them in one query and deleted the node which went zero .
I made some modifications with the amount given and i tried to keep the maximum element every time i made the query .
This gave me 89 points.
There is no TLE, my solution was simply less efficient. Operation 2 is used after the first greedy approach.