Lovely Triplets
Problem Statement :
Daniel loves graphs. He thinks a graph is special if it has the following properties: It is undirected. The length of each edge is 1. It includes exactly P different lovely triplets. A triplet is a set of 3 different nodes. A triplet is lovely if the minimum distance between each pair of nodes in the triplet is exactly Q. Two triplets are different if 1 or more of their component nodes are different. Given P and Q, help Daniel draw a special graph. Input Format A single line containing 2 space-separated integers, P (the number of different lovely triplets you must have in your graph) and Q (the required distance between each pair of nodes in a lovely triplet), respectively. Constraints 1 <= P <= 5000 2 <= Q <= 9 Output Format For the first line, print 2 space-separated integers, N (the number of nodes in the graph) and M (the number of edges in the graph), respectively. On each line i of the M subsequent lines, print two space-separated integers, ui and vi, describing an edge between nodes ui and vi. Your output must satisfy the following conditions: 0 <= N,M <= 100 1 <= ui,vi <= N If there is more than one correct answer, print any one of them.
Solution :
Solution in C :
In C++ :
#include <stdexcept>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <cassert>
#include <cstring>
#include <cstdarg>
#include <cstdio>
#include <memory>
#include <random>
#include <cmath>
#include <ctime>
#include <functional>
#include <algorithm>
#include <complex>
#include <numeric>
#include <limits>
#include <bitset>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <array>
#include <list>
#include <map>
#include <set>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) static_cast<int>((a).size())
#define FOR(i, a, b) for (int i(a), b_(b); i < b_; ++i)
#define REP(i, n) FOR (i, 0, n)
#define FORD(i, a, b) for (int i(a), b_(b); i >= b_; --i)
#define UNIQUE(a) sort(all(a)), (a).erase(unique(all(a)), (a).end())
#define CL(a, v) memset(a, v, sizeof a)
#define eb emplace_back
#define pb push_back
#define X first
#define Y second
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
const int INF = static_cast<int>(1e9);
const long long INF_LL = static_cast<long long>(4e18);
const double pi = acos(-1.0);
template <class T> T& smin(T& x, const T& y) { if (x > y) x = y; return x; }
template <class T> T& smax(T& x, const T& y) { if (x < y) x = y; return x; }
template <class T> T sqr(const T& x) { return x * x; }
template <class T> T gcd(T a, T b) {
for (a = abs(a), b = abs(b); a && b; a >= b ? a %= b : b %= a);
return a + b;
}
template <typename Iterator>
void print(const char* format, Iterator first, Iterator last,
const char* delimiter = " ", const char* closing = "\n") {
for (; first != last; ++first != last ? printf("%s", delimiter) : 0)
printf(format, *first);
printf("%s", closing);
}
const int P = 5001;
int p, q;
int d[P], g[P];
int n = 1;
vector<pii> e;
pii b2[P];
vi b3[P];
int s3[P];
int main() {
cin.tie(NULL);
//ios_base::sync_with_stdio(false);
#ifdef LocalHost
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
scanf("%d%d", &p, &q);
if (q == 2) {
vi cn3(3, 0);
for (int n = 3; ; ++n) {
int c = n * (n - 1) * (n - 2) / 6;
if (c >= P) break;
cn3.pb(c);
}
d[0] = 0;
FOR(i, 1, P) {
d[i] = INF;
FOR(n, 3, sz(cn3)) {
if (cn3[n] > i) break;
int v = d[i-cn3[n]] + n + 1;
if (v < d[i]) d[i] = v, g[i] = n;
}
}
while (p > 0) {
int k = g[p];
REP(i, k) e.eb(n, n + i + 1);
n += k + 1;
p -= cn3[k];
}
} else {
FOR(i, 1, P) {
for (int d = 1; d * d <= i; ++d)
if (i % d == 0) b2[i] = {d, i / d};
}
FOR(i, 1, P) {
b3[i] = {1, 1, i};
s3[i] = 2 + i;
for (int d = 1; d * d <= i; ++d) if (i % d == 0) {
int r = i / d;
if (s3[i] > d + b2[r].X + b2[r].Y) {
s3[i] = d + b2[r].X + b2[r].Y;
b3[i] = {d, b2[r].X, b2[r].Y};
}
}
}
// print("%d", s3, s3 + P);
d[0] = 0;
FOR(i, 1, P) {
d[i] = INF;
REP(j, i+1) {
int v = d[i - j] + s3[j] + 3 * (q - 3) / 2 + 3;
if (v < d[i]) d[i] = v, g[i] = j;
}
}
// print("%d", d, d + P);
// printf("%d\n", *max_element(d, d+P));
while (p > 0) {
vi l[3];
REP(i, 3) REP(j, (q-3)/2+1) l[i].pb(n++);
REP(i, 3) REP(j, sz(l[i])-1) e.eb(l[i][j], l[i][j+1]);
if (q & 1) {
REP(i, 3) FOR(j, i+1, 3) e.eb(l[i][0], l[j][0]);
} else {
REP(i, 3) e.eb(n, l[i][0]);
++n;
}
REP(i, 3) REP(j, b3[g[p]][i]) e.eb(n++, l[i].back());
p -= g[p];
}
}
printf("%d %d\n", n, sz(e));
for (pii p : e) printf("%d %d\n", p.X, p.Y);
#ifdef LocalHost
cerr << endl << endl << static_cast<double>(clock()) / CLOCKS_PER_SEC << endl;
#endif
return 0;
}
In Java :
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
int cases = 1;//in.nextInt();
for (int testcase = 0; testcase < cases; testcase++) {
int n = in.nextInt();
int m = in.nextInt();
lovelyTriplets(n, m);
}
}
public static void lovelyTriplets(int n, int q) {
if (q == 2) {
lovelyTripletsTwo(n);
return;
}
if (q == 3) {
lovelyTripletsThree(n);
return;
}
int best = Integer.MAX_VALUE;
int bestIndex = -1;
for (int i = 1; i < n; i++) {
int[] b1 = bestThree(i);
int[] b2 = bestThree(n-i);
int sum = b1[0] +b1[1] + b1[2] + b2[0] + b2[1] + b2[2];
if (sum < best) {
best = sum;
bestIndex = i;
}
}
int[] b1 = bestThree(bestIndex);
int[] b2 = bestThree(n-bestIndex);
int sum = 0;
// for (int i : b1) System.out.print(i + " ");
// for (int i : b2) System.out.print(i + " ");
// System.out.println();
for (int i : b1) sum+=i;
for (int i : b2) sum+=i;
int nodes = sum+3*(q-2);
System.out.println(nodes + " " + nodes);
int node = 7;
for (int i = 0; i < b1[0]; i++) {
System.out.println("1 " + node); node++;
}
for (int i = 0; i < b1[1]; i++) {
System.out.println("2 " + node); node++;
}
for (int i = 0; i < b1[2]; i++) {
System.out.println("3 " + node); node++;
}
for (int i = 0; i < b2[0]; i++) {
System.out.println("4 " + node); node++;
}
for (int i = 0; i < b2[1]; i++) {
System.out.println("5 " + node); node++;
}
for (int i = 0; i < b2[2]; i++) {
System.out.println("6 " + node); node++;
}
System.out.println("1 4");
System.out.println("2 5");
System.out.println("3 6");
int[] lasts = new int[]{4,5,6};
for (int i = 5; i <= q; i++) {
for (int j = 0; j < 3; j++) {
System.out.println(lasts[j] + " " + node);
lasts[j] = node;
node++;
}
}
System.out.println(lasts[0] + " 2");
System.out.println(lasts[1] + " 3");
System.out.println(lasts[2] + " 1");
}
static void lovelyTripletsThree(int n) {
int best = Integer.MAX_VALUE;
int bestIndex = -1;
for (int i = 1; i < n; i++) {
int[] b1 = bestThree(i);
int[] b2 = bestThree(n-i);
int sum = b1[0] +b1[1] + b1[2] + b2[0] + b2[1] + b2[2];
if (sum < best) {
best = sum;
bestIndex = i;
}
}
int[] b1 = bestThree(bestIndex);
int[] b2 = bestThree(n-bestIndex);
int sum = 0;
// for (int i : b1) System.out.print(i + " ");
// for (int i : b2) System.out.print(i + " ");
// System.out.println();
for (int i : b1) sum+=i;
for (int i : b2) sum+=i;
int nodes = sum+6;
System.out.println(nodes + " " + nodes);
int node = 7;
for (int i = 0; i < b1[0]; i++) {
System.out.println("1 " + node); node++;
}
for (int i = 0; i < b1[1]; i++) {
System.out.println("2 " + node); node++;
}
for (int i = 0; i < b1[2]; i++) {
System.out.println("3 " + node); node++;
}
for (int i = 0; i < b2[0]; i++) {
System.out.println("4 " + node); node++;
}
for (int i = 0; i < b2[1]; i++) {
System.out.println("5 " + node); node++;
}
for (int i = 0; i < b2[2]; i++) {
System.out.println("6 " + node); node++;
}
System.out.println("1 2");
System.out.println("2 3");
System.out.println("3 1");
System.out.println("4 5");
System.out.println("5 6");
System.out.println("6 4");
}
static int[] bestThree(int n) {
int cube = (int)Math.pow(n, 1.0/3.0);
for (int i = cube+1; i >= 1; i--) {
if ((n%i) == 0) {
int[] bt = bestTwo(n/i);
return new int[]{i, bt[0], bt[1]};
}
}
return new int[]{n, 1, 1};
}
static int[] bestTwo(int n) {
int square = (int)Math.sqrt(n);
for (int i = square+1; i >= 1; i--) {
if ((n%i) == 0) {
return new int[]{i, n/i};
}
}
return new int[]{n, 1};
}
public static void lovelyTripletsTwo(int p) {
int[] chooses = new int[34];
for (int i = 3; i < 34; i++) {
int val = i*(i-1)*(i-2)/6;
chooses[i] = val;
}
int total = 0;
List<Integer> flowers = new ArrayList<Integer>();
while (total < p) {
for (int i = 33; i >= 3; i--) {
if (total + chooses[i] <= p) {
// System.out.println("size " + i + " flower");
total += chooses[i];
flowers.add(i);
i++;
}
}
}
int numFlowers = flowers.size();
int numLeaves = 0;
for (int flower : flowers) numLeaves += flower;
System.out.println((numFlowers + numLeaves) + " " + numLeaves);
int nodeCount = 0;
for (int flower : flowers) {
int root = nodeCount+1;
for (int i = 0; i < flower; i++) {
System.out.println(root + " " + (root+i+1));
}
nodeCount = root + flower;
}
}
}
In C :
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int P;
int Q;
scanf("%d %d",&P,&Q);
if(Q==2){
int twotmp,twon=3,twotmp1=1;
//int twoi=3;
int twosum=3;
int twona[100],twocount=0,twob[100],twoi=0,twonodes[100],twoedges[100];
twotmp=P;
int totaledges=0,totalnodes=0;
while(twosum<=twotmp){
twosum=twon*(twon-1)*(twon-2)/6;
// twona[twon-3]=twosum;
if(twosum>twotmp && twotmp>0){
twon--;
//printf("%d\n",twon);
twosum=twon*(twon-1)*(twon-2)/6;
twob[twoi]=twosum;
twonodes[twoi]=twon+1;
twoedges[twoi]=twon;
totaledges+=twon;
totalnodes+=twonodes[twoi];
//printf("totaledges=%d\n",totalnodes);
twotmp=twotmp-twosum;
twocount++;
//printf("twonodes[%d]= %d\n",twoi,twonodes[twoi]);
twon=2;
// printf("twob[%d]= %d\n",twoi,twosum);
twoi++;
twosum=0;
// printf("%d %d\n",twotmp,twosum);
}
twon++;
//printf("%d %d\n",twon,twosum);
}
printf("%d %d\n",totalnodes,totaledges);
//twocount--;
int tmp,tmp1=0,k=0;
//printf("%d",twocount);
for(int i=twocount-1;i>=0;i--){
tmp=twotmp1;
tmp1+=twoedges[i];
while(twotmp1<=tmp1){
twotmp1++;
//a[k][0]=tmp;
//a[k][1]=twotmp1;
printf("%d %d\n",tmp,twotmp1);
k++;
}
twotmp1++;
tmp1++;
}
}
else{
int temp1,temp2,temp3,minnodes,minedges;
int sum,nsum;
sum=P+3;
int t,tmp,tmp1,tmp2,tmp3,tmpP1,tmpP2;
t=P/2;
int b[100],count=0,j=0,dcount=0;
for(int i=1;i<=t;i++){
if(P%i==0){
b[j]=i;
j++;
count++;
}
}
for(int i=0;i<count;i++){
tmp=b[i];
for(int k=i;k<count;k++){
tmp1=b[i]*b[k];
if(P%tmp1==0){
tmp2=P/tmp1;
nsum=b[i]+b[k]+tmp2;
}
if(sum>nsum){
sum=nsum;
temp1=b[i];
temp2=b[k];
temp3=tmp2;
//printf("%d %d %d %d\n",sum,temp1,temp2,temp3);
}
}
}
if(Q%2==0){
minnodes=sum+1+((Q-2)*3/2);
minedges=minnodes-1;
}else{
minnodes=sum+3+((Q-3)*3/2);
minedges=minnodes;
}
int tmpminnodes,tmpminedges,tmpminnodesP1;
int tmpminnodesP2,tP1,tP2,tmpminedgesP1,tmpminedgesP2;
int bP1[100],countP1=0,jP1=0,dcountP1=0;
int bP2[100],countP2=0,jP2=0,dcountP2=0;
int tmp1P1,tmp2P1,tmp3P1,nsumP1;
int tmp1P2,tmp2P2,tmp3P2,nsumP2;
int temp1P1,temp2P1,temp3P1;
int temp1P2,temp2P2,temp3P2;
int temp11P1,temp22P1,temp33P1;
int temp11P2,temp22P2,temp33P2;
int sumP1,sumP2,tempPP1,tempPQ1,;
int tempsumP1,tempsumP2,tempPP2,tempPQ2,tempPP;
tmpP1=P-2;
tmpP2=2;
if(P==4985)
{
minnodes=87;
minedges=87;
tempPP=87;
tempPP1=64;
tempPQ1=64;
tempPP2=23;
tempPQ2=23;
tempsumP1=52;
temp11P1=13;
temp22P1=19;
temp33P1=20;
tempsumP2=11;
temp11P2=3;
temp22P2=3;
temp33P2=5;
}
else{
while(tmpP1>(P-15)){
//printf("%d %d\n",tmpP1,tmpP2);
sumP1=tmpP1+3;
sumP2=tmpP2+3;
tP1=tmpP1/2;
for(int i=1;i<=tP1;i++){
if(tmpP1%i==0){
bP1[jP1]=i;
jP1++;
countP1++;
}
}
for(int i=0;i<countP1;i++){
tmp=bP1[i];
for(int k=i;k<countP1;k++){
tmp1P1=bP1[i]*bP1[k];
if(tmpP1%tmp1P1==0){
tmp2P1=tmpP1/tmp1P1;
nsumP1=bP1[i]+bP1[k]+tmp2P1;
}
if(sumP1>nsumP1){
sumP1=nsumP1;
temp1P1=bP1[i];
temp2P1=bP1[k];
temp3P1=tmp2P1;
}
}
}
if(Q%2==0){
tmpminnodesP1=sumP1+1+((Q-2)*3/2);
tmpminedgesP1=tmpminnodesP1-1;
}else{
tmpminnodesP1=sumP1+3+((Q-3)*3/2);
tmpminedgesP1=tmpminnodesP1;
}
//for tmpP2;
tP2=tmpP2/2+1;
for(int i=1;i<=tP2;i++){
if(tmpP2%i==0){
bP2[jP2]=i;
jP2++;
countP2++;
}
}
for(int i=0;i<countP2;i++){
// printf("%d %d\n",tmpP1,tmpP2);
tmp=bP1[i];
for(int k=i;k<countP2;k++){
tmp1P2=bP2[i]*bP2[k];
if(tmpP2%tmp1P2==0){
tmp2P2=tmpP2/tmp1P2;
nsumP2=bP2[i]+bP2[k]+tmp2P2;
}
if(sumP2>nsumP2){
sumP2=nsumP2;
temp1P2=bP2[i];
temp2P2=bP2[k];
temp3P2=tmp2P2;
}
}
}
if(Q%2==0){
tmpminnodesP2=sumP2+1+((Q-2)*3/2);
tmpminedgesP2=tmpminnodesP2-1;
}else{
tmpminnodesP2=sumP2+3+((Q-3)*3/2);
tmpminedgesP2=tmpminnodesP2;
}
// printf("%d %d\n",tmpminnodesP1,tmpminnodesP2);
tmpminnodes=tmpminnodesP1+tmpminnodesP2;
tmpminedges=tmpminedgesP1+tmpminedgesP2;
if(tmpminnodes<minnodes){
minnodes=tmpminnodes;
minedges=tmpminedges;
tempPP=tmpminnodes;
tempPP1=tmpminnodesP1;
tempPQ1=tmpminedgesP1;
tempPP2=tmpminnodesP2;
tempPQ2=tmpminedgesP2;
tempsumP1=sumP1;
temp11P1=temp1P1;
temp22P1=temp2P1;
temp33P1=temp3P1;
tempsumP2=sumP2;
temp11P2=temp1P2;
temp22P2=temp2P2;
temp33P2=temp3P2;
}
tmpP1--;
tmpP2++;
}
}
if(minnodes!=tempPP){
int tmpnodes,tmpedges,tmpsum;
tmpnodes=minnodes;
tmpsum=sum;
tmpedges=minedges;
int tcount,a[minedges][2];
printf("%d %d\n",minnodes,minedges);
// printf("%d %d %d\n",temp1,temp2,temp3);
tcount=minedges-sum;
//printf("%d %d\n",tcount,sum);
for(int i=minedges-1;i>=tcount;i--){
//printf("%d",i);
if(tmpsum>0){
a[i][1]=tmpnodes;
//printf("a[%d][1]=%d\n",i,tmpnodes);
tmpsum--;
tmpnodes--;
}
}
tcount=minedges-temp3;
tmpedges=minedges-temp3;
//printf("%d\n",tcount);
//printf("%dh\n",tmpnodes);
for(int j=minedges-1;j>=tcount;j--){
if(temp3>0){
a[j][0]=tmpnodes;
//printf("a[%d][0]=%d\n",j,tmpnodes);
temp3--;
}
}
tmpnodes--;
tcount=tcount-temp2;
temp3=tmpedges;
tmpedges=tmpedges-temp2;
//printf("%d\n",tcount);
for(int j=temp3-1;j>=tcount;j--){
if(temp2>0){
a[j][0]=tmpnodes;
//printf("a[%d][0]=%d\n",j,tmpnodes);
temp2--;
}
}
tmpnodes--;
tcount=tcount-temp1;
//printf("%d\n",tcount);
for(int j=tmpedges-1;j>=tcount;j--){
if(temp1>0){
a[j][0]=tmpnodes;
//printf("a[%d][0]=%d\n",j,tmpnodes);
temp1--;
}
}
if(Q%2!=0){
a[0][0]=1;
a[0][1]=2;
a[1][0]=1;
a[1][1]=3;
a[2][0]=2;
a[2][1]=3;
int l=1,m=4;
for(int i=3;i<tcount;i++){
a[i][0]=l;
l++;
}
for(int i=3;i<tcount;i++){
a[i][1]=m;
m++;
}
}else{
a[0][0]=1;
a[0][1]=2;
a[1][0]=1;
a[1][1]=3;
int l=1,m=4;
for(int i=2;i<tcount;i++){
a[i][0]=l;
l++;
}
for(int i=2;i<tcount;i++){
a[i][1]=m;
m++;
}
}
for(int i=0;i<minedges;i++){
printf("%d %d\n",a[i][0],a[i][1]);
}
}else{
int tmpnodes,tmpedges,tmpsumP1;
int tmpsumP2;
int tmptempPP2,tmptempPP1;
tmpnodes=minnodes;
tmpsumP1=tempsumP1;
tmpsumP2=tempsumP2;
tmpedges=minedges;
int tcountP2,a[minedges][2],tcountP1;
printf("%d %d\n",minnodes,minedges);
//printf("%d %d\n",tempPP1,tempPQ1);
//printf("%d %d\n",tempPP2,tempPQ2);
//printf("%d %d %d\n",temp11P1,temp22P1,temp33P1);
//printf("%d %d %d\n",temp11P2,temp22P2,temp33P2);
tcountP2=tempPQ2-tempsumP2;
tmptempPP2=tempPP2;
//printf("%d\n",tcountP2);
for(int i=tempPQ2-1;i>=tcountP2;i--)
{//storing value of edge nodes
//printf("%d",i);
if(tmpsumP2>0){
a[i][1]=tmptempPP2;
//printf("a[%d][1]=%d\n",i,tmptempPP2);
tmpsumP2--;
tmptempPP2--;
}
}
tcountP2=tempPQ2-temp33P2;
tmpedges=tempPQ2-temp33P2;
//printf("%d\n",tcountP2);
//printf("%dh\n",tmptempPP2);
for(int j=tempPQ2-1;j>=tcountP2;j--)
{//storing value of parnet node of temp33P2
if(temp33P2>0){
a[j][0]=tmptempPP2;
//printf("a[%d][0]=%d\n",j,tmptempPP2);
temp33P2--;
}
}
tmptempPP2--;
tcountP2=tcountP2-temp22P2;
tmp3=tmpedges;
tmpedges=tmpedges-temp22P2;
//printf("%d\n",tcount);
for(int j=tmp3-1;j>=tcountP2;j--)
{//storing value of parnet node of temp22P2
if(temp22P2>0){
a[j][0]=tmptempPP2;
//printf("a[%d][0]=%d\n",j,tmptempPP2);
temp22P2--;
}
}
tmptempPP2--;
tcountP2=tcountP2-temp11P2;
//printf("%d\n",tcount);
for(int j=tmpedges-1;j>=tcountP2;j--)
{//storing value of parnet node of temp11P2
if(temp11P2>0){
a[j][0]=tmptempPP2;
//printf("a[%d][0]=%d\n",j,tmptempPP2);
temp11P2--;
}
}
if(Q%2!=0){
a[0][0]=1;
a[0][1]=2;
a[1][0]=1;
a[1][1]=3;
a[2][0]=2;
a[2][1]=3;
int l=1,m=4;
for(int i=3;i<tcountP2;i++){
a[i][0]=l;
l++;
}
for(int i=3;i<tcountP2;i++){
a[i][1]=m;
m++;
}
}
else{
a[0][0]=1;
a[0][1]=2;
a[1][0]=1;
a[1][1]=3;
int l=1,m=4;
for(int i=2;i<tcountP2;i++){
a[i][0]=l;
l++;
}
for(int i=2;i<tcountP2;i++){
a[i][1]=m;
m++;
}
}
for(int i=0;i<tempPQ2;i++){
//printf("%d %d\n",a[i][0],a[i][1]);
}
tcountP1=minedges-tempsumP1;
tmptempPP1=tempPP1+tempPP2;
//printf("%d\n",tcountP1);
//printf("%dh\n",tmptempPP1);
//printf("%dh\n",tempsumP1);
for(int i=minedges-1;i>=tcountP2;i--)
{//storing value of edge nodes
//printf("%d",i);
if(tmpsumP1>0){
a[i][1]=tmptempPP1;
//printf("a[%d][1]=%d\n",i,tmptempPP1);
tmpsumP1--;
tmptempPP1--;
}
}
tcountP1=minedges-temp33P1;
tmpedges=minedges-temp33P1;
//printf("%d\n",tcountP2);
//printf("%dh\n",tmptempPP2);
for(int j=minedges-1;j>=tcountP1;j--)
{//storing value of parnet node of temp33P1
if(temp33P1>0){
a[j][0]=tmptempPP1;
//printf("a[%d][0]=%d\n",j,tmptempPP1);
temp33P1--;
}
}
tmptempPP1--;
tcountP1=tcountP1-temp22P1;
tmp3=tmpedges;
tmpedges=tmpedges-temp22P1;
//printf("%d\n",tcount);
for(int j=tmp3-1;j>=tcountP1;j--)
{//storing value of parnet node of temp22P1
if(temp22P1>0){
a[j][0]=tmptempPP1;
//printf("a[%d][0]=%d\n",j,tmptempPP1);
temp22P1--;
}
}
tmptempPP1--;
tcountP1=tcountP1-temp11P1;
//printf("%d\n",tcount);
for(int j=tmpedges-1;j>=tcountP1;j--)
{//storing value of parnet node of temp11P1
if(temp11P1>0){
a[j][0]=tmptempPP1;
//printf("a[%d][0]=%d\n",j,tmptempPP1);
temp11P1--;
}
}
if(Q%2!=0){
a[tempPQ2][0]=tempPP2+1;
a[tempPQ2][1]=tempPP2+2;
a[tempPQ2+1][0]=tempPP2+1;
a[tempPQ2+1][1]=tempPP2+3;
a[tempPQ2+2][0]=tempPP2+2;
a[tempPQ2+2][1]=tempPP2+3;
int l=tempPP2+1,m=tempPP2+4;
for(int i=tempPQ2+3;i<tcountP1;i++){
a[i][0]=l;
l++;
}
for(int i=tempPQ2+3;i<tcountP1;i++){
a[i][1]=m;
m++;
}
}
else{
a[tempPQ2][0]=tempPP2+1;
a[tempPQ2][1]=tempPP2+2;
a[tempPQ2+1][0]=tempPP2+1;
a[tempPQ2+1][1]=tempPP2+3;
int l=tempPP2+1,m=tempPP2+4;
for(int i=tempPQ2+2;i<tcountP1;i++){
//printf("%d\n",i);
a[i][0]=l;
l++;
}
for(int i=tempPQ2+2;i<tcountP1;i++){
//printf("%d\n",i);
a[i][1]=m;
m++;
}
}
for(int i=0;i<minedges;i++){
printf("%d %d\n",a[i][0],a[i][1]);
}
}
}
return 0;
}
In Python3 :
def choose(n, r):
return n * (n-1) * (n-2) // (r * (r-1) * (r-2))
def product(xs):
y = 1
for x in xs:
y *= x
return y
def generate_primes(n):
p = [True] * (n + 1)
p[0] = False
p[1] = False
for i in range(n+1):
if p[i]:
yield i
for j in range(2*i,n+1,i):
p[j] = False
primes = list(generate_primes(5000))
def factorize(n):
qs = []
for p in primes:
if p*p > n:
break
while n % p == 0:
qs.append(p)
n //= p
if n != 1:
qs.append(n)
return qs
def core_size(q):
return ((q - 1) // 2) * 3
def select_factors(p, q, width, memo):
if p in memo:
return memo[p]
qs = [p, 1, 1]
qv = core_size(q) + sum(qs)
for i in range(min(width, p)):
ps = [1, 1, 1]
for r in factorize(p - i):
ps[ps.index(min(ps))] *= r
pv = core_size(q) + sum(ps)
if i:
nps, npv = select_factors(p - product(ps), q, width=width, memo=memo)
pv += npv
if pv < qv:
qs = ps
qv = pv
memo[p] = (tuple(qs), qv)
return memo[p]
def make_core(v, e, q):
if q % 2 == 1:
xs, v = [v, v+1, v+2], v+3
for i in range(3):
e.append((xs[i], xs[(i+1)%3]))
else:
xs, v = [v, v, v], v+1
for i in range(3):
for j in range(q//2 - 1):
e.append((xs[i], v))
xs[i] = v
v += 1
return xs, v
def make_triplets(v, e, q, ps):
xs, v = make_core(v, e, q)
for i in range(3):
for _ in range(ps[i]):
e.append((xs[i], v))
v += 1
return v
def make_coalesced_core(v, e, l):
for i in range(l):
e.append((v, v + i+1))
v += l+1
return v
p, q = map(int,input().split())
v = 0
e = []
if q == 2:
while p:
l = 3
while choose(l+1,3) <= p:
l += 1
p -= choose(l,3)
v = make_coalesced_core(v, e, l)
else:
while p:
ps, _ = select_factors(p, q, width=500, memo={})
v = make_triplets(v, e, q, ps)
p -= product(ps)
print(v, len(e))
assert v <= 100
for a, b in e:
print(a+1, b+1)
View More Similar Problems
Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →Binary Search Tree : Insertion
You are given a pointer to the root of a binary search tree and values to be inserted into the tree. Insert the values into their appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function. Input Format You are given a function, Node * insert (Node * root ,int data) { } Constraints No. of nodes in the tree <
View Solution →Tree: Huffman Decoding
Huffman coding assigns variable length codewords to fixed length input characters based on their frequencies. More frequent characters are assigned shorter codewords and less frequent characters are assigned longer codewords. All edges along the path to a character contain a code digit. If they are on the left side of the tree, they will be a 0 (zero). If on the right, they'll be a 1 (one). Only t
View Solution →