The link to problem:- https://codeforces.com/problemset/problem/229/C
Basically, we are given a complete graph of N vertices. This complete graph is divided into two subgraphs like this:-
Few edges(let this number be x) are given which will go into subgraph G1 and the remaining { n(n-1)/2 - x } edges will go into subgraph G2.
The task is to find the sum of triangles in G1 and G2.
I was getting time limit exceed in this problem because I was counting the number of triangles in each component separately and then added them.My triangle counting algorithm takes O(N^3) complexity.
The expected solution is to be run in O(V+x). I am not getting any clue on how to do that.
I also saw explanation/solution but it only tells what to do and doesn't explain why they are doing it. Link:- https://codeforces.com/blog/entry/5437 ( see Div. 1C-Triangles)
Please explain that solution and/or provide a different approach if you can.