# SUMPRODSEG Editorial

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

1713

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:

1 Like

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

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;
}


@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

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

1 Like

[DELETED]

#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.

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

#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