DPAIRS - EDITORIAL

Everybody has figured that out - no need to SCREAM. xD

i have a question that whats the logic behind using if n != 10 condition can u explain…plzz

No logic. The condition allows the test cases to be passed. That illustrates how weak they are.

could u tell how to know that for this reason i am getting the wrong aswer…plzz?

I did the same thing but I get WA on 3 testcases , AC on 4 and TLE on subtask 2

@manasi2399 You don’t need to use container except vector that too for storing the sequence. Read the problem statement carefully. Although people have already gave an idea about how you can solve the problem easily with just a small observation.

Yes I read the editorial and realise I dont need another container. However I expected that the logic I applied (even though inefficient) shouldn’t give WA on atleast subtask 1. It would be great if I could see the testcases on which it fails :frowning:

Well if it is giving WA then you are certainly missing something. Share your code with brief explanation about what your have done.

@striker22
I figured out my mistake . I was doing i+j instead of a[i] + b[j] . I can be really stupid sometimes. Thanks for your help !

What @semantycs is correct. You’re printing new indices.

Why do we need to atleast find minimum or maximum? , as all the pairs are distinct the first element of a will always give m distinct pairs with b

First element will always give m distinct pairs with b but what after that ?
We need to find n+m-1 pairs. You might face some issues when you try to find another n-1 pairs.

a b c d ( sorted in increasing order) 
x y z  ( sorted in increasing order)
a+x a+y a+z 
(a+z) b+z c+z d+z 
if a = min(a,b,c) and x = max(x,y,z) 
  a+x < a+y < a+z < b+z < c+z < d+z 

Hence all n+m-1 will always be distinct. Actually we do not need to sort the arrays.

2 Likes

Ohkay got it ! Thankyou !!

Welcome

Hey, “pairwise distinct” in the constraints is just a fancy way of saying no two values are same

The following code:

using System;
using System.Collections.Generic;
using System.Text;

public class Test
{
    public static void Main()
    {
        List<(int, int)> solutiions = new List<(int, int)>();
        string[] vars = Console.ReadLine().Split(' ');
        int N = int.Parse(vars[0]);
        int M = int.Parse(vars[1]);
        int[] a = new int[N];
        int[] b = new int[M];
        vars = Console.ReadLine().Split(' ');
        for (int i = 0; i < N; i++) a[i] = int.Parse(vars[i]);
        vars = Console.ReadLine().Split(' ');
        for (int i = 0; i < M; i++) b[i] = int.Parse(vars[i]);
        int[] sums = new int[N + M - 1];
        for (int i = 0; i < N + M - 1; i++) sums[i] = -1;
        int sumCount = 0;
        int aIndex = 0;
        while (aIndex < a.Length)
        {
            int bIndex = 0;
            while (bIndex < b.Length)
            {
                int sum = a[aIndex] + b[bIndex];
                if (!Array.Exists(sums, e => e == sum))
                {
                    Console.WriteLine(sumCount);
                    sums[sumCount++] = sum;
                    solutiions.Add((aIndex, bIndex));
                    if (sumCount == N + M - 1) break;
                }
                bIndex++;
            }

            if (sumCount == N + M - 1) break;
            aIndex++;
        }
        StringBuilder sb = new StringBuilder();
        solutiions.ForEach(s => sb.AppendLine($"{s.Item1} {s.Item2}"));
        Console.WriteLine(sb.ToString());
    }
}

compiles without issue in Visual Studio under .NET 4.7.2. Yet when I try to run it I get:

prog.cs(9,17): error CS1525: Unexpected symbol `,', expecting `.'
prog.cs(33,42): error CS1026: Unexpected symbol `,', expecting `)'
Compilation failed: 2 error(s), 0 warnings

I thought tuples were okay in 4.6.2. Could someone please explain to me what the issue is?

my binary search approach

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main()

{

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

#endif

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int n, m;

    cin >> n >> m;

    vector<pair<int, int>> vn(n);

    vector<pair<int, int>> vm(m);

    for (int i = 0; i < n; i++)

    {

        cin >> vn[i].first;

        vn[i].second = i;

    }

    sort(vn.begin(), vn.end());

    for (int i = 0; i < m; i++)

    {

        cin >> vm[i].first;

        vm[i].second = i;

    }

    sort(vm.begin(), vm.end());

    unordered_map<int, pair<int, int>> my_set;

    int ini = 0;

    int sum = vn[0].first + vm[0].first;

    my_set[sum] = {vn[0].second, vm[0].second};

    while (true)

    {

        if (my_set.size() == n + m - 1)

        {

            break;

        }

        int start = 0;

        int end = vm.size() - 1;

        while (end - start > 1)

        {

            int mid = (start + end) / 2;

            if (vm[mid].first <= sum - vn[ini].first)

            {

                start = mid + 1;

            }

            else

            {

                end = mid;

            }

        }

        int my_ind;

        if (start < vm.size() && vm[start].first > sum - vn[ini].first)

        {

            my_ind = start;

        }

        else if (end < vm.size() && vm[end].first > sum - vn[ini].first)

        {

            my_ind = end;

        }

        else

        {

            my_ind = -1;

        }

        if (my_ind == -1)

        {

            ini++;

            if (my_set.size() == n + m - 1)

            {

                break;

            }

        }

        else

        {

            sum = vm[my_ind].first + vn[ini].first;

            my_set[sum] = {vn[ini].second, vm[my_ind].second};

            if (my_set.size() == n + m - 1)

            {

                break;

            }

        }

    }

    for (auto x : my_set)

    {

        cout << x.second.first << " " << x.second.second << endl;

    }

    return 0;

}