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