EVALMAS - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Testers: tabr, yash_daga
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N and X, construct a string of length N using the characters +, -, * such that upon evaluation with N+1 ones, the result is X.
Multiplication is performed first, addition second, and subtraction last.

EXPLANATION:

Let’s think about the maximum and minimum values we can achieve.
Clearly, since there are no parentheses,

  • The maximum is 1+1+1+\ldots + 1 = N+1
  • The minimum is 1-1-1-\ldots - 1 = 1-N

So, if X \gt N+1 or X \lt 1-N, the answer is immediately -1.
Let’s solve for the remaining numbers.

Starting with 1+1+\ldots + 1, notice that replacing one + with a * essentially allows us to ‘combine’ two ones into a single one, thereby reducing the sum by 1.
For example,

  • 1+1+1+1 = 4
  • 1+1+1*1 = 3
  • 1+1*1*1 = 2
  • 1*1*1*1 = 1

Notice that this allows to create every X between 1 and N+1, by using X-1 occurrences of + and N-X occurrences of *.

A similar logic applies to the non-positive numbers, where we can start with 1-1-1-\ldots -1, and replace a - with a * to increase the sum by 1. For example,

  • 1-1-1-1 = -2
  • 1-1-1*1 = -1
  • 1-1*1*1 = 0

In particular, -X can be obtained using X+1 occurrences of - and N-X-1 occurrences of *.

This means we can obtain every X in the range [1-N, N+1], and so we’re done.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    if x > 0:
        if x > n+1: print(-1)
        else: print('*'*(n-x+1) + '+'*(x-1))
    else:
        x = -x
        if x > n-1: print(-1)
        else: print('-'*(1+x) + '*'*(n-1-x))
2

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

string sum_zero(int pos)
{
string s;
if(pos&1)
{
s.push_back(’*’);
pos–;
}
pos/=2;
while(pos–)
{
s.push_back(’+’);
s.push_back(’-’);
}
return s;
}

int main() {
// your code goes here
long long int t,n,i,x,tmp,res;
string s;
cin>>t;
while(t–)
{
cin>>n>>x;
res=0;
s="";
long long int max,min,cnt,pos,tmp;
max=n+1;
min=1-n;
if(x<=max && x>=min)
{
res=1;
if(x>0)
{
x–;
pos=n-x;
while(x–) s.push_back(’+’);
if(pos!=0) s+=sum_zero(pos);
}
else if(x<0)
{
s.push_back(’-’);
n–;
tmp=abs(x);
pos=n-tmp;
while(tmp–) s.push_back(’-’);
if(pos!=0) s+=sum_zero(pos);
}
else s+=sum_zero(n+1);

    }
    if(res==0) cout<<"-1";
    else cout<<s;
    cout<<endl;
    
}
return 0;

}

I am getting wrong answer on the #task2 exccept this all are passed .Please anyone help in figuring out the type of testcase where my code doesn’t work …Thank You