EXERCISE PROBLEM COOKOFF

can anyone share the approach to this problem?
@l_returns

3 Likes

What I do I kept record of min and max value for every unknown number from it’s previous number in array and according to sign in the given string that is of >,= or < and maintain a flag wherever condition according to questions failed.
This is link to my solution.

https://www.codechef.com/viewsolution/26732288

2 Likes
  1. Make groups (overlapping by one number) having following format :
    number -1 -1 … -1 number
    Or
    number number
  2. now for each group count number of ‘>’ , ‘<’ and ‘=’
    i) now if > and < both are present a group then it’s always possible. (= Doesn’t make any difference)
    ii) now if > is there and < is not there then check 5 > > > 2 is not possible but 5 > > 2 and 5 > > 0 are possible. Jo just compare count,5,2 appropriately. ( = Doesn’t matter)
    iii) if < is present and > is not present.
    Same logic as point ii
    iv) now if > is not present as well as < is not present and only = is present. Then check if both numbers are equal or not.
    Now this is it. You have almost (90%) solved it.

Corner cases : check prefix and suffix.
example < < 2 is possible ( 0 1 2)
But <<< 2 is not possible ( -1 0 1 2) and -1 is invalid.
Also check suffix with same logic ( check if it’s doesn’t get -1).
One more example can be <=> <<<2 ( still not possible because it will be -1). ( This would only happen in prefix and suffix)
One extra simple corner case is all are -1.
https://www.codechef.com/viewsolution/26731902

1 Like

https://www.codechef.com/viewsolution/26730111

1 Like

@paras1810 @l_returns @ssrivastava990 thanks bhailog

1 Like

@l_returns bro congratulation 6 star…:heart_eyes:

1 Like

Thanks :smiley: \hspace{0mm}

@l_returns bro your fb account link or insta?

Find me on fb :stuck_out_tongue: \hspace{0mm}

friend request sent :joy:

1 Like

@paras1810 bro i didnt get that use of min max can you please explain it clearly

For your first case, consider the example 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 and the string is > > > > > < < < < < < . I think this string is not possible.
In my opinion for the case A -1 -1 … B, if you do a one step walk from A (up or down depending on the sign) and end up at a point less than B, then it is always possible.
For the other case, if you end up x units above B, then you need to see whether you can go x more steps down in between. That is wherever the sign changes from > to <, summation of values at those index(which is calculated using one step walk) should be more than equal to x.
Please correct me if I am wrong.