SUMPRODSEG Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Tejas Pandey
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

1713

PREREQUISITES:

None

PROBLEM:

A segment is a range of non-negative integers L, L + 1, L + 2, \ldots, R, denoted [L, R] where L \leq R.

Chef has a set S consisting of all segments [L, R] such that either L + R = X or L\cdot R = Y.

For example, if X = 5 and Y = 6, then Chef’s set is S = \{[0, 5], [1, 4], [1, 6], [2, 3]\}.

Given the integers X and Y, can you help Chef find two non-intersecting segments from his set S? If it is not possible to find two such non-intersecting segments, print -1. If there are multiple possible answers, you may output any of them.

Note: Two segments are said to be non-intersecting if they have no number in common. For example, [1, 4] and [10, 42] are non-intersecting, while [1, 4] and [4, 6] are not since they have 4 in common.

EXPLANATION:

Observation 1: The smallest interval [L,R] such that L+R = X would be:

[\frac{X}{2},\frac{X}{2}], \;if\;X\;is\;even.
[\frac{X}{2},\frac{X}{2} + 1], \;if\;X\;is\;odd.

Any other interval would overlap the above one.

So we can choose one of the intervals as above and then loop through all possible intervals such that L \times R = Y and for each interval we check if the two intersect each other or not.

TIME COMPLEXITY:

O(\sqrt{N}), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

1 Like
2

Can anyone tell what’s wrong with my solution as my approach is a different one:
https://www.codechef.com/viewsolution/70625464
Thanks!!

3

Can someone please provide the testcase for which this code fails


// ll stands for long long


int div(ll n){
    ll ans = 1;
    for(ll i=2; i*i<=n; i++){
        if(n%i==0){
            ans = i;
        }
    }
    return ans;
}

int main()
{
    test(t){                    // testcases ...
        
        ll x, y; cin>>x>>y;
        
        ll small = div(y);
        ll big1 = y/small;
        ll one = x/2;
        ll two  =x/2;
        if(x%2) two++;

        if(min(one, two)>big1 or max(one, two)<small){
            cout<<one<<" "<<two<<endl;
            cout<<small<<" "<<big1<<endl;
        }
        else print(-1);

    }

    return 0;
}
4

@codechef_admin new page formate during the contest tackes lots of time for loding .Its better to provied old page formate during the contest.

4 Likes
5

The return type of function div should be long long int and not int

1 Like
6

[DELETED]

7

#include<bits/stdc++.h>

#include

#include<string.h>

#define ll long long

using namespace std;

int main()

{

int t=1;

cin>>t;

while(t--)

{

    ll int x,y;

    cin>>x>>y;

    ll int l1,l2,r1,r2;

    if(x%2==0)

    {

        l1=x/2;

        r1=x/2;

    }

    else

    {

        l1=x/2;

        r1=(x/2)+1;

    }

    bool res=false;

    for(int i=1;i<=pow(y,0.5);i++)

    {

        if(y%i==0)

        {

            int c=y/i;

            if((c>r1 && i>r1) || (c<l1 && i<l1))

            {

                l2=min(i,c);

                r2=max(i,c);

                res=true;

                break;

            }

        }

    }

    if(res)

    {

        cout<<l1<<" "<<r1<<endl;

        cout<<l2<<" "<<r2<<endl;

    }

    else

    {

        cout<<-1<<endl;

    }

}

return 0;

}

It is failing 3 test cases , what is the mistake can anyone please make me aware.

8 
import math
for gagroz in range(int(input())):
    x, y = map(int, input().split())
    s = int(math.sqrt(y))
    flag = False
    b = math.ceil(x/2)
    if y == 1 or s<=b:
        print(-1)
    else:
        for i in range(s, b, -1):
            if y % i == 0:
                flag = True
                print(i, y//i)
                print(x-b, b)
                break
        if flag == False:
            print(-1)

3 cases failed can someone help out with what exactly the test case are as debugger is off

9

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<ll, null_type,less, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define mii map<ll,ll>
#define pii pair<ll,ll>
#define vi vector
#define REP(i,a,b) for(ll i=a;i<b;i++)
bool cmps(pii a,pii b)
{
return a.ss<b.ss;
}
void solve()
{
ll x,y;
cin>>x>>y;
pii a;
if(x&1)
{
a.ff=x/2;
a.ss=a.ff+1;
}
else
{
a.ff=x/2;
a.ss=x/2;
}
ll val=sqrt(y);
pii b=make_pair(val,y/(val));
if(b.ff>a.ss)
{
cout<<a.ff<<" “<<a.ss<<endl;
cout<<b.ff<<” “<<b.ss;
return;
}
cout<<-1;
return ;
}
int main()
{
ll t;
cin>>t;
while(t–)
{
solve();
cout<<”\n";
}
return 0;
}

In the above code My approach is → Finding the minimum interval for Product and Multiplication if they intersect that means all intervals will intersect that means output is -1 and if not those interval would be answer