×

# CHEFSIGN - Editorial

Author: Dmytro Berezin
Primary Tester: Misha Chorniy
Editorialist: Hussain Kara Fallah

Cakewalk

None

# PROBLEM:

Given a sequence of N arithmetic signs ( = , + , - ) between N+1 unknown integers. You are allowed to fix these integers using numbers in the range [1,P] such that the expression is true when you read it from left to right. (Numbers don't violate the signs). You are asked to calculate minimum possible P such you can construct a valid expression.

# EXPLANATION:

First of all, it's clear that we can drop all '=' signs and pretend that they never existed, because each number which follows an '=' sign would be identical to the number preceding this sign. So these signs aren't affecting our answer at all. After discarding all '=' signs our answer would be :

P = max(maximum number of consecutive '<' signs, maximum number of consecutive '>' signs) + 1

Let's process our expression from left to right, If we are facing X (X ≤ P-1) consecutive '<' signs, our starting number would be P-X, and we increment our last number by 1 after each sign,so the number after the last sign would be exactly P (which will be followed by '>' sign). Our last number will be followed by Y consecutive '>' signs, so we assign the next number to Y (Y < P) and we decrement the last number by 1 by each '>' sign we process. The number after the last sign would be 1. (In case our expression starts with '>' the situation would just be reversed). After that we would have another block of Z consecutive '<' signs, so we assign the next number to P-Z (P-Z ≥ 1) so the number after the last sign would be P and we continue....

Following this approach, the last number after a block of consecutive '<' signs would be P (the maximal value), and the last number after a block of consecutive '>' signs would be 1 (the minimal value). So according to our bold assumption below we can assign values using numbers in the range [1,P] without violating the signs.

Let's take an example:

<<<=>=>=>>><<>>>><<<<<>><<>>

After removing = signs our sequence would be

<<< >>>>> << >>>> << >>>>>

(Blocks are separated by spaces for clarity)

here P = max(3 , 5 , 2 , 4 , 5 , 2 , 2 , 2) + 1 = 6

Our sequence would be

3 < 4 < 5 < 6 > 5 > 4 > 3 > 2 > 1 < 5 < 6 > 4 > 3 > 2 > 1 < 5 < 6 > 5 > 4 > 3 > 2 > 1

# AUTHOR'S AND TESTER'S SOLUTIONS:

TESTER's solution: Will be found here
EDITORIALIST's solution: Will be found here

1181234
accept rate: 0%

19.8k350498541

 1 Yes, In both of your codes, you guys are assuming that the numbers increase or decrease by 1, which is not always the case. Consider this, str = '><<<><<' Your code will give the answer as 5. your answer == 2>1<2<3<4>3<4<5 but the actual answer would be 4 == 2>1<2<3<4>1<2<3 like this. answered 18 Jul '17, 04:35 14●1 accept rate: 0%
 0 could any one tell why this gives WA https://www.codechef.com/viewsolution/14569995 answered 17 Jul '17, 22:47 1●1 accept rate: 0%
 0 I am also getting few of the testcases accepted and others wrong answer. https://www.codechef.com/viewsolution/14563406 Please help me find my mistake! #include #define lli long long int using namespace std; int main(void) { int t; cin >> t; while(t--){ char s[100011]; lli tmp = 1, pmax = 1, pmin = 1; lli i; lli ans; cin >> s; for(i = 0; s[i] != '\0'; i++){ if(s[i] == '<'){ tmp++; } else if(s[i] == '>'){ tmp--; } if(pmax < tmp) pmax = tmp; if(pmin > tmp) pmin = tmp; } //cout << pmax << " " << pmin << endl; if(pmin < 1) { ans = pmax - pmin + 1; } else { ans = pmax; } cout << ans << endl; } return 0; }  answered 17 Jul '17, 23:33 1 accept rate: 0%
 0 Here is my code ... what do you think is wrong about it. Please, help me find my mistakes #include using namespace std; #define fast_cin ios_base::sync_with_stdio(false) typedef long long ll; int main() { fast_cin; ll t; cin >> t; while(t--){ string s; cin >> s; ll in = 1, ans = 0; for (int i = 0; i < s.size(); ++i) { if (s[i] == '<') { in++; ans = max(ans,in); } else if (s[i] == '>') { in = 1; } } cout << ans << endl; } return 0; }  It is giving current answer for string s = '<<<=>=>=>>><<>>>><<<<<>><<>>'or '><<<><<' answered 18 Jul '17, 20:47 1 accept rate: 0%
 0 can any one pls tell me why am i not able to pass 2 cases in main task... ? i have my code and screen shot of my result here... https://pastebin.com/6QJRau0v http://i64.tinypic.com/2rmwima.png answered 18 Jul '17, 20:57 1 accept rate: 0%
 0 Can anybody tell me what's wrong with it. https://www.codechef.com/viewsolution/14523196 answered 20 Jul '17, 17:12 2★anchal24 -3●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,688
×1,024
×968
×229
×22

question asked: 15 Jul '17, 06:48

question was seen: 2,044 times

last updated: 20 Jul '17, 17:12