HackerRank Lovely Triplets Problem Solution
In this post, we will solve HackerRank Lovely Triplets Problem Solution.
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.
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, u, and v describing an edge between nodes u, and .
Your output must satisfy the following conditions:
0 < N, M≤ 100
1 < uj, vj ≤ N
If there is more than one correct answer, print any one of them.
Sample Input
3 2
Sample Output
7 7
1 2
2 3
3 4
4 5
5 6
6 1
1 7
Lovely Triplets C Solution
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char** split_string(char*);
int** makeGraph(int p, int q, int startv, int *result_count){
if(p == 0){
*result_count = 1;
int** toreturn = malloc(sizeof(int*));
toreturn[0] = malloc(2*sizeof(int));
toreturn[0][0] = 0;
toreturn[0][1] = 0;
return toreturn;
}
if(q == 2){
int numspokes = 3;
while(numspokes*(numspokes - 1)*(numspokes - 2) <= 6*p){
numspokes++;
}
numspokes--;
int tempresult_count;
int** graph = makeGraph(p - (numspokes*(numspokes - 1)*(numspokes - 2))/6, q, startv + 1 + numspokes, &tempresult_count);
*result_count = tempresult_count + numspokes;
graph = realloc(graph, (*result_count)*sizeof(int*));
for(int i = 0; i < numspokes; i++){
graph[tempresult_count + i] = malloc(2*sizeof(int));
graph[tempresult_count + i][0] = startv + 1;
graph[tempresult_count + i][1] = startv + i + 2;
}
graph[0][0] += numspokes + 1;
graph[0][1] += numspokes;
return graph;
}
else{
int factor1[q - 2];
int factor2[q - 2];
int factor3[q - 2];
int currp = p;
int extranum = 3*(q - 2);
for(int i = 0; i < q - 2; i++){
if(currp == 0){
factor1[i] = 0;
factor2[i] = 0;
factor3[i] = 0;
}
else{
factor1[i] = 1;
while(factor1[i]*factor1[i]*factor1[i] <= currp){
factor1[i]++;
}
factor1[i]--;
factor2[i] = factor1[i];
while(factor1[i]*factor2[i]*factor2[i] <= currp){
factor2[i]++;
}
factor2[i]--;
factor3[i] = factor2[i];
while(factor1[i]*factor2[i]*factor3[i] <= currp){
factor3[i]++;
}
factor3[i]--;
currp -= factor1[i]*factor2[i]*factor3[i];
extranum += factor1[i] + factor2[i] + factor3[i];
}
}
int tempresult_count;
int** graph = makeGraph(currp, q, startv + extranum, &tempresult_count);
*result_count = tempresult_count + extranum;
graph = realloc(graph, (*result_count)*sizeof(int*));
graph[tempresult_count] = malloc(2*sizeof(int));
graph[tempresult_count][0] = startv + 1;
graph[tempresult_count][1] = startv + 3*(q - 2);
for(int i = 0; i < 3*(q - 2) - 1; i++){
graph[tempresult_count + i + 1] = malloc(2*sizeof(int));
graph[tempresult_count + i + 1][0] = startv + i + 1;
graph[tempresult_count + i + 1][1] = startv + i + 2;
}
int index = tempresult_count + 3*(q - 2);
int numvertex = 3*(q - 2);
for(int i = 0; i < q - 2; i++){
for(int j = 0; j < factor1[i]; j++){
graph[index] = malloc(2*sizeof(int));
graph[index][0] = startv + i + 1;
graph[index][1] = startv + numvertex + 1;
index++;
numvertex++;
}
for(int j = 0; j < factor2[i]; j++){
graph[index] = malloc(2*sizeof(int));
graph[index][0] = startv + (q - 2) + i + 1;
graph[index][1] = startv + numvertex + 1;
index++;
numvertex++;
}
for(int j = 0; j < factor3[i]; j++){
graph[index] = malloc(2*sizeof(int));
graph[index][0] = startv + 2*(q - 2) + i + 1;
graph[index][1] = startv + numvertex + 1;
index++;
numvertex++;
}
}
graph[0][0] += extranum;
graph[0][1] += extranum;
return graph;
}
}
int main()
{
char** PQ = split_string(readline());
char* P_endptr;
char* P_str = PQ[0];
int P = strtol(P_str, &P_endptr, 10);
if (P_endptr == P_str || *P_endptr != '\0') { exit(EXIT_FAILURE); }
char* Q_endptr;
char* Q_str = PQ[1];
int Q = strtol(Q_str, &Q_endptr, 10);
if (Q_endptr == Q_str || *Q_endptr != '\0') { exit(EXIT_FAILURE); }
int result_count;
int** result = makeGraph(P, Q, 0, &result_count);
for(int i = 0; i < result_count; i++){
printf("%d %d\n", result[i][0], result[i][1]);
}
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}Lovely Triplets C++ Solution
/* nice editorial !! */
#include <bits/stdc++.h>
//#define debug
#define fie(i,start,stop) for ( int i = start ; i < stop ; i ++ )
#define f first
#define s second
#define pii pair < int , int >
#define vpii vector < pii >
#define vi vector < int >
#define pb push_back
#define mp make_pair
using namespace std ;
vpii nc3 ;
vi x ( 5001 , INT_MAX ) ;
vi y ( 5001 , INT_MAX ) ;
vi z ( 5001 , INT_MAX ) ;
vpii dp ( 5001 , mp ( INT_MAX , INT_MAX ) ) ;
int nc3_size = 0 ;
int p , d , n = 0 , m = 0 ;
vpii edges ( 100 ) ;
int l , mid , r ;
void build_even ()
{
#ifdef debug
cout << "building even" << endl ;
#endif
int root = n + 1 ;
int nodes = ( d - 2 ) / 2 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 2 ;
edges [ m ++ ].s = n + i + 3 ;
}
n += nodes + 1 ;
l = n ;
edges [ m ].f = root ;
edges [ m ++ ].s = n + 1 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 1 ;
edges [ m ++ ].s = n + i + 2 ;
}
n += nodes ;
mid = n ;
edges [ m ].f = root ;
edges [ m ++ ].s = n + 1 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 1 ;
edges [ m ++ ].s = n + i + 2 ;
}
n += nodes ;
r = n ;
}
void build_odd ()
{
#ifdef debug
cout << "building odd" << endl ;
#endif
if ( d == 3 )
{
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 3 ;
edges [ m ].f = n + 2 ;
edges [ m ++ ].s = n + 3 ;
l = n + 1 ;
mid = n + 2 ;
r = n + 3 ;
n += 3 ;
return ;
}
int nodes = ( d - 3 ) / 2 ;
int root1 = n + 1 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 2 ;
edges [ m ++ ].s = n + i + 3 ;
}
n += nodes + 1 ;
l = n ;
int root2 = n + 1 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 2 ;
edges [ m ++ ].s = n + i + 3 ;
}
n += nodes + 1 ;
mid = n ;
int root3 = n + 1 ;
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + 2 ;
fie ( i , 0 , nodes - 1 )
{
edges [ m ].f = n + i + 2 ;
edges [ m ++ ].s = n + i + 3 ;
}
n += nodes + 1 ;
r = n ;
edges [ m ].f = root1 ;
edges [ m ++ ].s = root2 ;
edges [ m ].f = root1 ;
edges [ m ++ ].s = root3 ;
edges [ m ].f = root2 ;
edges [ m ++ ].s = root3 ;
}
void add_edge ( int no_l , int no_mid , int no_r )
{
#ifdef debug
cout << "adding edge " << no_l << " " << no_mid << " " << no_r << endl ;
#endif
if ( d % 2 )
{
build_odd () ;
}
else
{
build_even () ;
}
fie ( i , 0 , no_l )
{
edges [ m ].f = l ;
edges [ m ++ ].s = n + i + 1 ;
}
n += no_l ;
fie ( i , 0 , no_mid )
{
edges [ m ].f = mid ;
edges [ m ++ ].s = n + i + 1 ;
}
n += no_mid ;
fie ( i , 0 , no_r )
{
edges [ m ].f = r ;
edges [ m ++ ].s = n + i + 1 ;
}
n += no_r ;
}
void solve ()
{
while ( p )
{
#ifdef debug
cout << "component of size " << dp [ p ].f << endl ;
#endif
add_edge ( x [ dp [ p ].f ] , y [ dp [ p ].f ] , z [ dp [ p ].f ] ) ;
p -= dp [ p ].f ;
}
}
void add_edge2 ( int no_of_nodes )
{
#ifdef debug
cout << "adding edge for dist 2 " << no_of_nodes << endl ;
#endif
fie ( i , 0 , no_of_nodes )
{
edges [ m ].f = n + 1 ;
edges [ m ++ ].s = n + i + 2 ;
}
n += no_of_nodes + 1 ;
}
void solve2 ()
{
int idx = nc3_size - 1 ;
while ( p )
{
if ( nc3 [ idx ].f <= p )
{
add_edge2 ( nc3 [ idx ].s ) ;
p -= nc3 [ idx ].f ;
}
else
{
idx -- ;
}
}
}
void precal ()
{
fie ( i , 1 , 100 )
{
fie ( j , i , 100 )
{
if ( i * j > 5000 || i + j > 93 )
{
break ;
}
fie ( k , j , 100 )
{
if ( i * j * k > 5000 || i + j + k > 94 )
{
break ;
}
int mul = i * j * k ;
if ( x [ mul ] == INT_MAX || ( ( x [ mul ] + y [ mul ] + z [ mul ] ) > ( i + j + k ) ) )
{
x [ mul ] = i ;
y [ mul ] = j ;
z [ mul ] = k ;
}
}
}
}
fie ( i , 0 , 5001 )
{
fie ( j , 1 , 5001 )
{
if ( i + j <= 5000 && x [ j ] != INT_MAX && ( dp [ i + j ].s > dp [ i ].s + x [ j ] + y [ j ] + z [ j ] ) )
{
dp [ i + j ].f = j ;
dp [ i + j ].s = dp [ i ].s + x [ j ] + y [ j ] + z [ j ] ;
}
}
}
int no = 3 ;
while ( true )
{
int prod = no * ( no - 1 ) * ( no - 2 ) ;
prod /= 6 ;
if ( prod <= 5000 )
{
nc3.pb ( mp ( prod , no ++ ) ) ;
#ifdef debug
//cout << "nc3 " << no - 1 << " " << prod << endl ;
#endif
}
else
{
break ;
}
}
nc3_size = nc3.size () ;
}
int main ()
{
precal () ;
cin >> p >> d ;
if ( d == 2 )
{
solve2 () ;
}
else
{
solve () ;
}
cout << n << " " << m << endl ;
fie ( i , 0 , m )
{
cout << edges [ i ].f << " " << edges [ i ].s << endl ;
}
return 0 ;
}Lovely Triplets C Sharp Solution
using Newtonsoft.Json;
using Newtonsoft.Json.Linq;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Dynamic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Media;
using System.Reflection;
using System.Security.AccessControl;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using System.Threading.Tasks;
namespace _mtTest.ABC
{
class Program
{
public static void Main()
{
new Program().Run();
}
class CGraph
{
public int V { get; set; } = 0;
public List<int[]> E { get; set; } = new List<int[]>();
}
int Product(IEnumerable<int> xs)
{
var y = 1;
foreach (var x in xs)
{
y *= x;
}
return y;
}
static IEnumerable<int> GeneratePrimes(int n)
{
var p = new bool[n + 1];
for (int i = 0; i < p.Length; i++)
{
p[i] = true;
}
p[0] = false;
p[1] = false;
for (int i = 0; i < p.Length; i++)
{
if (!p[i])
continue;
yield return i;
for (int j = 2 * i; j <= n; j += i)
p[j] = false;
}
}
List<int> _primes = GeneratePrimes(5000).ToList();
IEnumerable<int> Factorize(int n)
{
List<int> qs = new List<int>();
foreach (var p in _primes)
{
if (p * p > n)
break;
while (n % p == 0)
{
qs.Add(p);
n /= p;
}
}
if (n != 1)
qs.Add(n);
return qs;
}
int CoreSize(int q)
{
var v1 = q % 2 == 1 ? 3 : 1;
var v2 = q / 2 - 1;
return v1 + v2;
}
Tuple<int[], int> SelectFactors(int p, int q, int width, Dictionary<int, Tuple<int[], int>> memo)
{
if (p == 0)
return Tuple.Create(new[] { 0, 0, 0 }, 0);
if (memo.ContainsKey(p))
return memo[p];
var qs = new[] { p, 1, 1 };
var qv = CoreSize(q) + qs.Sum();
var minWP = Math.Min(width, p);
for (int i = 0; i < minWP; i++)
{
var ps = new[] { 1, 1, 1 };
var factors = Factorize(p - i);
foreach (var r in factors)
{
var minIndex = 0;
var minValue = ps.Min();
for (int k = 0; k < ps.Length; k++)
{
if (ps[k] != minValue)
continue;
minIndex = k;
break;
}
ps[minIndex] *= r;
}
var pv = CoreSize(q) + ps.Sum();
var npv = SelectFactors(p - Product(ps), q, width, memo).Item2;
pv += npv;
if (pv < qv)
{
qs = ps;
qv = pv;
}
}
memo[p] = Tuple.Create(qs, qv);
return memo[p];
}
void BuildCoreQN(CGraph graph, int q, int[] ps)
{
int[] xs;
if (q % 2 == 1)
{
xs = new[] { graph.V, graph.V + 1, graph.V + 2 };
graph.V += 3;
for (int i = 0; i < 3; i++)
{
graph.E.Add(new[] { xs[i], xs[(i + 1) % 3] });
}
}
else
{
xs = new[] { graph.V, graph.V, graph.V };
graph.V += 1;
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < q / 2 - 1; j++)
{
graph.E.Add(new[] { xs[i], graph.V });
xs[i] = graph.V;
graph.V += 1;
}
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < ps[i]; j++)
{
graph.E.Add(new[] { xs[i], graph.V });
graph.V++;
}
}
}
void BuildCoreQ2(CGraph graph, int vLocal)
{
for (int i = 0; i < vLocal; i++)
{
graph.E.Add(new[] { graph.V, graph.V + i + 1 });
}
graph.V += vLocal + 1;
}
void Run()
{
var inputs = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();
var p = inputs[0];
var q = inputs[1];
CGraph graph = new CGraph();
if (q == 2)
{
Func<int, int> combination3 = n => n * (n - 1) * (n - 2) / 6;
while (p > 0)
{
var vLocalIsolated = 3;
while (true)
{
var pDiff = combination3(vLocalIsolated + 1);
if (pDiff > p)
break;
vLocalIsolated++;
}
p -= combination3(vLocalIsolated);
BuildCoreQ2(graph, vLocalIsolated);
}
}
else
{
while (p > 0)
{
var factors = SelectFactors(p, q, width: 500, memo: new Dictionary<int, Tuple<int[], int>>());
var ps = factors.Item1;
BuildCoreQN(graph, q, ps);
p -= Product(ps);
}
}
PrintGraph(graph);
Console.WriteLine();
//CheckGraph(q, graph);
}
//static void CheckGraph(int q, CGraph cgraph)
//{
// var graph = new Graph() { Q = q };
// foreach (var ei in cgraph.E)
// {
// graph.AddEdge(ei[0] + 1, ei[1] + 1);
// }
// Console.WriteLine(graph.GetTripletsCount());
//}
static void PrintGraph(CGraph cgraph)
{
Console.WriteLine($"{cgraph.V} {cgraph.E.Count}");
foreach (var ei in cgraph.E)
{
Console.WriteLine($"{ei[0] + 1} {ei[1] + 1}");
}
}
//public void RunX()
//{
// var graph = new Graph() { Q = 2 };
// graph.AddEdge(1, 2);
// graph.AddEdge(1, 3);
// graph.AddEdge(1, 4);
// graph.AddEdge(1, 5);
// graph.AddEdge(1, 6);
// graph.AddEdge(1, 7);
// graph.AddEdge(1, 8);
// //graph.AddEdge(1, 5);
// Console.WriteLine(graph.GetTripletsCount());
//}
}
}
//graph.AddEdge(1, 2);
//graph.AddEdge(2, 3);
//graph.AddEdge(3, 4);
//graph.AddEdge(4, 5);
//graph.AddEdge(5, 6);
//graph.AddEdge(6, 1);
//graph.AddEdge(1, 7);
//graph.AddEdge(7, 5);Lovely Triplets Java Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class LovelyTriplets {
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) 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) 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) {
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;
}
}
}Lovely Triplets JavaScript Solution
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
function main() {
var P_temp = readLine().split(' ');
var P = parseInt(P_temp[0]);
var Q = parseInt(P_temp[1]);
var N = 0;
var M = 0;
var E = []
if (Q == 2) {
while ( P > 0 ) {
var hub = N;
var spars = 0
N++;
E.push([hub,N]);
N++;
M++;
spars++;
E.push([hub,N]);
N++;
M++;
spars++;
E.push([hub,N]);
N++;
M++;
spars++;
P--;
while ((spars*(spars-1)/2) <= P) {
P -= (spars*(spars-1)/2);
E.push([hub,N]);
N++;
M++;
spars++;
}
}
} else {
while ( P>0) {
var start = N;
N++;
for (var j=1; j<3*(Q-2); j++) {
E.push([start+j-1,start+j]);
M++;
N++;
}
E.push([start+(3*(Q-2))-1,start]);
M++;
var nub = 0;
while (P>0 && nub < Q-2) {
var spars_0 = 0;
var spars_1 = 0;
var spars_2 = 0;
while (P >= (spars_0+1)*(spars_1+1)*(spars_2+1)) {
E.push([start+nub,N]);
N++;
M++;
spars_0++;
E.push([start+nub+Q-2,N]);
N++;
M++;
spars_1++;
E.push([start+nub+Q+Q-4,N]);
N++;
M++;
spars_2++;
}
while (P >= (spars_0+1)*(spars_1+1)*(spars_2)) {
E.push([start+nub,N]);
N++;
M++;
spars_0++;
E.push([start+nub+Q-2,N]);
N++;
M++;
spars_1++;
}
while (P >= (spars_0+1)*(spars_1)*(spars_2)) {
E.push([start+nub,N]);
N++;
M++;
spars_0++;
}
P -= spars_0*spars_1*spars_2
nub++;
}
}
}
console.log([N,M].join(' '));
for(var i=0; i<M; i++) {
console.log(E[i].map(x=>x+1).join(' '));
}
}Lovely Triplets Python Solution
#!/usr/bin/env 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)
