Quite similar to the problem called chemical table, from CF 1012, EJOI 2018. Trying that first can help to understand why to use DSU.

DSU

upper bound of k is (n-2)*(n-1)/2 This is a single vertex (n) is connected to all n-1 vertices. Now if we want to decrease this value to reach k we need to choose a vertex and connect it to unconnected vertices (each edge decreases number of pairs by one) so perform this operation till we reach value k. https://atcoder.jp/contests/abc131/submissions/6072403 my submission.

So let's find the maximal value of k: it is (1+2+..+n-2).

Why? Because with this graph then k will be maximized:

1-2 1-3 1-4 1-... 1-n

As there will be 2-1-3, 2-1-4, 2-1-5, .. 2-1-n, 3-1-4, 3-1-5 ... (n-1)-1-n road of distance 2.

So if k>mx (mx=1+2+..+n-2). Print -1

else if k==mx we will print the above edges

else if k<mx we will reduce the road of distance 2 by make the edge from 2 to 3 (in order to eliminate road 2-1-3) and 2 to 4 and 2 to ... until the remain roads of distance 2 equal k.

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> ii;
vector<ii> ans;
int n,k,mx=0;
int main()
{
    cin >> n >> k;
    for (int i=1;i<=n-2;i++) mx+=i;
    if (k>mx)
    {
        cout << "-1";
        return 0;
    }
    if (1)
    {
        for (int i=2;i<=n;i++) ans.push_back(ii(1,i));
        int d=mx-k;
        for (int i=2;i<n;i++)
            for (int j=i+1;j<=n;j++)
            {
                if (d==0)
                {
                    cout << ans.size() << "\n";
                    for (ii v:ans) cout << v.first << " " << v.second << "\n";
                    return 0;
                }
                ans.push_back(ii(i,j));
                d--;
            }
        cout << ans.size() << "\n";
        for (ii v:ans) cout << v.first << " " << v.second << "\n";
        return 0;
    }
}

Maximum number of pairs can be (n-1)*(n-2)/2, this will happen when the graph is a tree and a single node is connected to all other nodes and hence the answer (n-1)C2, if k is greater than this value then our output will be "-1", now let there be n*(n-1)/2 edges in the graph so this will be the answer for case k=0, now consider a node say "2" if we start removing its edges one by one then the value of k will increase by one with every removal,so we have the answer for k=0 to k= n-2 because we can remove atmost (n-2) edges because the graph should be connected, now lets say that we don't remove the edge (1,2) in the above step and now consider node 3, if we start removing its edges one by one(except the edge that is connected to 1) the value of k starts increasing by 1 with every removal, we can remove atmost (n-3) edges from this node, so we have the answer for k=n-1 to k=2*n-5, similarly you can remove edges for node 4, 5 and so on, you can maintain an adjacency matrix to implement the above algo, here is the link to my code.

I hope this helps :)

first of all , lets see what is the maximum number of pairs that can be formed with distance equal to 2 ,if k exceeds that value simply return -1. Max_dist_2 = ((n-1)*(n-2))/2; Now , edges_to_draw = n-1 + (Max_dist_2 -k); Now start drawing edges from node 1 to all (now decrease edges_to_draw by n-1), then for every edge you draw between two consecutive node decrease edge_to_draw by 1 .Repeat this till edges_to_draw becomes 0. BAM....Your Graph is Ready!!!!

There are a lot of method . I will tell about my solution. If there are n verticles so we have n*(n-1)/2 pairs that theoretically can have a short distance 2 ,but graph must be connected . So i constructed a graph where all edges are 1 j (2<=j<=n) . This graph will have (n*(n-1)/2)-(n-1) pairs and their distance are 2 . It is maximal number of pairs can be. So if k>(n*(n-1)/2)-(n-1) answer is -1 . if k<(n*(n-1)/2)-(n-1) we must create ((n*(n-1)/2)-(n-1))-k triangles (cycles) .

from math import gcd -:: python 3.5 or above from fractions import gcd -:: python 3.4 I think this is the problem.

They have a solution in brainf**k for problem A lmao

Consider the graph where the given points are vertices and two vertices are connected if and only if their corresponding points have the same X-coordinate or the same Y-coordinate. The answer is the result when N is subtracted from the sum over all connected components in this graph of the product of the numbers of distinct X and Y coordinates represented in that component.

Proving that the connected components are independent is fairly easy. Then, the number of points created based on the starting points in each connected component is the product of the numbers of distinct X-coordinates and Y-coordinates in the component. We can prove by induction that we can always create all of these points.

Note that we cannot construct the entire graph, since it could have O(N^2) edges. However, since we just need to run a BFS to construct connected components, this doesn't turn out to be a huge obstacle--we just store lists of points at each X or Y coordinate and use those lists to deal with transitions rather than building an adjacency list.

As an aside, this was essentially an easier version of this problem. The same idea is outlined in the beginning of its editorial.

Seems to be a precision issue. To calculate $$$\lceil\frac{A}{B}\rceil$$$ without converting to doubles you can do (A+B-1)/B.

A number X is evenly divisible by another number Y if X can be divided by Y with no remainder. (In programming terms, this is equivalent to X % Y == 0.)

Thx, I've just solved it.

The answer is: B-A+1 — (# integers of that are divisible by C or D)

The last term = (# integers that are divisible by C) + (# integers that are divisible by D)

- (# integers that are divisible by C and D <==> divisible by lcm(C,D))

Here's my submission: https://atcoder.jp/contests/abc131/submissions/6064511

Good day to you:

Problem D: Sort the jobs by "deadline" and approach from end. For each job, let the TIME be minimum of "TIME-work" and "deadline-work". As you can see, if you end with TIME >= 0, you could do the job

Problem F: Observe that if two points have two same X (or vice versa Y) coordinate, then for each point with same Y coordinate as one of them, there will be a new point (well so basically statement ;-) ). So we would like to "group" all points with same X coordinate and with same Y coordinate (which could be done by — for example — two DSU's). Now we only need to check, the number of points in each union of partition: This mean for every partition of one coordinate, check all partitions of second coordinate, and multiply the cardinalities (obviously in the end we subtract the number of points on input ;-) )

Good Luck & Wish you a nice day!