₦airaland Forum

turmacs:
If you hate/don't know math, kindly close this thread now
For those of you that hope to work at Hedge fund companies, Jane Street, Citadel or other trading firms, expect stuff's like these at your interviews

If you can't solve it and would like to know how to solve it, kindly quote me so I'd know that somebody is interested in the solution and I would drop the solution with explanations here.

Problem statement
Let us call the Euclidean mean of a permutation P the value of the expression |P1 - 1| + |P2 - 2| +....+ |Pn - n|.
As an example, for the permutation [1,2,3], the Euclidean mean is |1 - 1| + |2 - 2| + |3 - 3| = 0, and for the permutation [3,1,2],
the Euclidean mean is |3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4.

Given two whole numbers n and k, as inputs, Find a permutation P of length n such that it's Euclidean mean is equal
to k, or report that no such permutation exists.

A permutation of length n is an array of n distinct integers that contains integers from 1 to n in random
order. For example [2,4,1,3] is a permutation of length 4, but [3,3,1] is not a permutation because 3 appears
twice in the array, and [1,3,7] is also not a permutation because n = 3 but there is 7 in the array.
Also note that |x - y| represents the absolute value of x - y.

Input
The first line consists of an integer t (1 ≤ t ≤ 10⁴) ---- The number of test cases.
The only line of each test case consists of two integers n and k (1 ≤ n ≤ 2⋅10⁵, 0 ≤ k ≤ 10¹²), the length
of the permutation and the required Euclidean mean.

Output
For each test case if no such permutation exits, output "No". Otherwise, in the first line, output "Yes", and in the second line, output
n distinct integers P1,P2,…,Pn (1 ≤ pi ≤ n) ----- A suitable permutation..
If there are multiple solutions, you can output any of them.

Example
Input
8
3 4
4 5
7 0
5 16
8 14
112 777
5 12
5 2
Output
Yes
3 1 2
No
Yes
1 2 3 4 5 6 7
No
Yes
8 2 3 4 5 6 1 7
No
Yes
5 4 3 1 2
Yes
2 1 3 4 5

xokol8:
The answer?

turmacs:
You can also use chatgpt to convert the solution to any programming language you want so that you can understand it

MindHacker9009:
That's not Software Development but A/Level maths. Software Development is when you take your maths problem and make it available through a secure API for display on users web browsers with authentication and authorisation and also save and retrieve the data securely from a database or datastore with optimisation.

danielclerkson:
You are so far off.
Check online for DSAs, i hate to agree with turmacs but this is inevitable if you want to go far in Software Developement

MindHacker9009:
DSA can be applied to all software development projects and it's not only for mathematician's problems, so you are the one so far off. Most complex programming projects you'll find in the real world will be something like this one below and not A/Level maths or Bsc Maths problems.

Programming only require good logical thinking and not A/Level Maths or Bsc Maths.

Implement a piece of online software suitable for use by a cinema. The system should be
capable of providing information about films currently showing, and of the availability
of seats in the cinema. The system should allow for seats to be booked either
individually or as a block. For example a block of 5 seats would require 3 adjacent
seats to be booked together.

danielclerkson:
Whats up with you and this problem, you just keep bringing it on (hope i am not talking to some kinda bot)

MindHacker9009:
I should be asking you instead. All these Maths bots on Nairaland that has no where else to use that Maths they have been cramming, but have decided to come and be disturbing us real programmers here. If you beleive you are a good Mathematician go and invent the next super operating system better than Windows or Linux and leave us real programmers and Software Engineers alone to face real life programming projects.

danielclerkson:
I admit i may not be Alan turing, but atleast i know well enough to proofread and spell check everything before i post

MindHacker9009:
Okay you are now the spell checker bot on Nairaland.

danielclerkson:
Sorry Sir, if you are so knowledgeable I don't think you would have made such a mistake oh

danielclerkson:
But cross platform language actually are very advantageous to new systems

danielclerkson:
Very Innovative thinking. The main way to find a security but is through an SQL inject or just PHP, Javascript is limited

using System;
using System.Collections.Generic;

namespace EuclideanMean
{
    internal class Program
    {
        static void Main(string[] args)
        {
            // Example usage
            // Sample input: t = 2, n and k pairs are (3, 2), (4, 6), (5, 11), (6, 16),  (7, 22) and (8, 29)
            int t = 2;
            var inputs = new List<(int, int)>
        {
        (3, 2),   // Should return Yes
        (4, 6),   // Should return Yes
        (5, 11),  // Should return No (max for n=5 is 10)
        (6, 16),  // Should return No (max for n=6 is 15)
        (7, 22),  // Should return No (max for n=7 is 21)
        (8, 29)   // Should return No (max for n=8 is 28)
        };

            Solve(t, inputs);
        }

        static void Solve(int t, List<(int n, int k)> testCases)
        {
            List<string> results = new List<string>();

            foreach (var (n, k) in testCases)
            {
                int maxPossibleMean = n * (n - 1) / 2;

                if (k > maxPossibleMean)
                {
                    results.Add("No";
                }
                else
                {
                    results.Add("Yes";
                    int[] P = new int[n];
                    for (int i = 0; i < n; i++)
                    {
                        P[i] = i + 1;
                    }

                    int currentMean = 0;
                    for (int i = n - 1; i >= 0; i--)
                    {
                        if (currentMean + (n - 1 - i) <= k)
                        {
                            P[i] = n - (n - 1 - i);
                            currentMean += (n - 1 - i);
                        }
                        else
                        {
                            P[i] = i + 1;
                        }
                    }

                    results.Add(string.Join(" ", P));
                }
            }

            Console.WriteLine(string.Join(Environment.NewLine, results));
            Console.Read();
        }
    }
}