TDISTS - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Hazem Issa
Tester: Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy

PREREQUISITES:

Tree, Greedy

PROBLEM

You are given two integers x and y. Your task is to construct a tree with the following properties:

  • The number of pairs of vertices with an even distance between them equals x.
  • The number of pairs of vertices with an odd distance between them equals y.

By a pair of vertices, we mean an ordered pair of two (possibly, the same or different) vertices.

EXPLANATION:

The first basic observation that we can draw is that the summation of x and y should be a perfect square.

Why ?

Since every vertex forms a pair with every other vertex of a tree including itself. Hence for any tree of N vertices, the total number of ordered pairs of vertices will be N^2.

As a summation of x and y represent the total number of ordered pairs of vertices which is a perfect square. Hence x+y should be a perfect square.

Now, we are left with finding whether it is possible to have a tree that has x pair of vertices with an even distance between them and y pair of vertices with an odd distance between them.

As its quite clear that any vertex of the tree can either be at an even level or an odd level. Root of the tree being at the even level (0- based indexing). Let’s find out the number of pairs of vertices that have an odd distance between them.

Claim: Any pair of vertices (x, y) has an odd distance between them if the vertices x and y comes from opposite parity levels.

Proof

Let the vertex x is present at an even level and vertex y at an odd level. The distance between two nodes can be obtained in terms of the lowest common ancestor (lca). Below is the formula for the same:

dis(x,y)=dis(root,x)+dis(root,y)-2*dis(root,lca)

Since x is present at even level so dis(root,x) is even while y is at odd level therefore dis(root,y) is odd. Hence we can see:

dis(x,y) = Even + Odd - Even

That means that if the vertices are from opposite parity levels, then the distance between them is odd.

Now let’s calculate the number of pairs of vertices which has an odd distance between them. For odd distances, every vertex that is present at an odd level will form a pair with every vertex that is present at even level and vice versa.

Let us suppose [e_1,e_2,e_3....e_i] and [o_1,o_2,o_3....o_j] are the vertices that are present at even and odd level respectively. Now for every vertex that is present at an even level, it will form a pair with every vertex that is present at the odd level and vice-versa. Hence:

Odd_{pairs}' = e_1*o_1+e_1*o_2+\dots+e_1*o_j+\dots+e_i*o_1+\dots+e_i*o_j
Odd_{pairs}' = (e_1+e_2+e_3+\dots+e_i)*(o_1+o_2+o_3+\dots+o_j)
Odd_{pairs}' = E*O

, where E and O represents the number of nodes that are present at even and odd level respectively.

Since we looking for the ordered pairs of two hence the number of the above pairs will be doubled. As if (x,y) is a pair that has the odd distance between them then (y,x) will also have an odd distance between them. Hence:

Odd_{pairs}= 2*E*O

That means we only care about the number of vertices that are present at even levels and odd levels. The root is the only node that is present at the 0^{th} level, now if we want more nodes at an even level then there must exist at least one vertex at an odd level. Now we can check for every possibility and can find if there exists such an arrangement of vertices that satisfy x and y of the problem. If so, we can output the tree.

TIME COMPLEXITY:

O(sqrt(X+Y)) per test case

SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;

int sqr(int n){ return n*n; }

void solve(){
    int x ,y; //x even ,y odd
    scanf("%d%d",&x,&y);

    int n = 1;
    while(sqr(n) < x+y)
        n++;
    if(sqr(n) != x+y){
        printf("NO\n");
        return;
    }

    for(int i=1; i<n; i++)
        if(sqr(i)+sqr(n-i) == x && 2*i*(n-i) == y)
        {
            printf("YES\n");
            printf("%d\n",n);
            for(int j=1; j<=n-i; j++)
                printf("1 %d\n",j+1);
            for(int j=2; j<=i; j++)
                printf("2 %d\n",n-i+j);
            return;
        }

    printf("NO\n");
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
}

Tester

#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

void solve() {
    ll x, y;
    cin >> x >> y;
    ll n = 1;
    while(n * n < x + y) n++;
    if(n * n != x + y) {
        cout << "NO\n";
        return;
    }
    // (a, b)
    // a + b = n
    // 2ab = y
    // a <= b
    for(ll a = 1; 2 * a * a <= y; a++) {
        ll b = n - a;
        if(1 <= a && a <= n && 1 <= b && b <= n && 2 * a * b == y) {
            cout << "YES\n";
            cout << n << '\n';
            // 1..a red nodes, a+1..n blue nodes
            for(ll i = a + 1; i <= n; i++) {
                cout << 1 << ' ' << i << '\n';
            }
            for(ll i = 2; i <= a; i++) {
                cout << a + 1 << ' ' << i << '\n';
            }
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
  int x,y;
  cin>>x>>y;

  int n=1;

  while(n*n<x+y)
    n++;

  if(n*n!=x+y)
  {
    cout<<"NO"<<"\n";
    return;
  }

  if(n==1)
  {
    if(x==1)
    {
      cout<<"YES"<<"\n";
      cout<<1<<"\n";
    }
    else
      cout<<"NO"<<"\n";

    return;
  }

  int even_lev=1,odd_lev=n-1;
  int flag=0;

  while(odd_lev>=1)
  {
    int odd_pairs=even_lev*odd_lev*2;
    if(odd_pairs==y)
    {
      flag=1;
      break;
    }
    even_lev++;
    odd_lev--;
  }

  if(!flag)
  {
    cout<<"NO"<<"\n";
    return;
  }

  cout<<"YES"<<"\n";
  cout<<n<<"\n";

  for(int i=1;i<=odd_lev;i++)
    cout<<1<<" "<<i+1<<"\n";

  for(int i=1;i<even_lev;i++)
    cout<<2<<" "<<odd_lev+i+1<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

23 Likes

Thanks for such detailed editorial .

4 Likes

I derived the result that for the answer to be tree 2*(x-1)>=y then it is a Yes else NO is my way of thinking correct

Nice Editorial.

2 Likes

I think that result is incorrect. Since it fails for simple cases (5,8) and (5,7). Even I tried but couldn’t find any direct relation between x and y. I think the only correct results were y = 2*E*O and x = E^{2} + O^{2}.

1 Like

It follows from the fact that N = E+O, and (E+O)^2 = (E^2 + O^2) + (2 * E * O), and x and y should be deducible from this.

1 Like

Got TLE during contest just because of using cout<< <<endl; instead of cout<< <<"\n" ; in C++.
Fast I/O is very important.

7 Likes

+1 got accepted due to this. :stuck_out_tongue:

1 Like

Loved the editorial… and I must say these written editorials feels way better than video editorials.

4 Likes

I found that odd+even must be a perfect square,
now consider no of vertices n = sqrt(odd+even) ,
Then possible values of odd distances are - { 2*(n-1), 2*(n-1)+2*(n-3), 2*(n-1)+2*(n-3)+2*(n-5)…}
My submission

1 Like

Thank You, very well written editorial.

1 Like

Not Sure if worth noting but I also used similar idea with only difference that I directly calculate the value of even or odd nodes instead of looping over it.

Basic idea: Check if valid n by simply summing the odd and even length and see if they are perfect square. If yes n is root of sum

consider the tree to be like a bipartitite graph(Don’t be alrmed with term not using anything complicated) with two sets of vertices even and odd level vertices.
Now one can easily form an equation for even pairs and odd pairs. Lets say I choose even length pairs then

no of even length pairs= even level* even level + odd level*odd level
(Idea is odd level to odd level require even number of edge and even to even require even number of edge)
now we know lhs and we can choose even level=n-odd level then it will reduce to a simple quadratic equation.
solve equation and check for both soution if any solution gets a valid odd even combination and if yes then we know the odd level and evel level nodes in a tree
Now you just need to create a tree with those nodes.

For tree construction I always think that no of levels doesn’t matter you can always choose to create tree of max 3 level with 1 as root with (even level count) childs and then remaining odd level childs in third level. Construct with same

Here is a submitted solution

https://www.codechef.com/viewsolution/45252281

Although taking O(n) for printing it calc the x and y in O(1) (assuming sqrt and other operations constant)

1 Like

Instead of considering odd pairs, is it possible to construct similarly for even pairs alone ?

Yes !! Why not ? Just take care that even pairs will also be formed by itself too i.e. pair (x, x) is considered as even pair

can anyone help me be telling the mistake in my code
def main():
t = int(input())
for k in range(t):
x,y = map(int, input().split())
n = (x+y)**0.5
if x<y or n%1 != 0 or (x-y)**0.5 % 1 != 0 :
print(“NO”)
continue
i = 1
j = 2
print(“YES”)
print(int(n))
while j<=n:
print(i,j)
j += 1
if j<=n :
print(i,j)
j += 1
i += 1
main()

thankyu in advance

thx for this