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

HackerRank Lovely Triplets Problem Solution

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)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python