BORW - Black or White

It’s Black, It’s White, It’s Tough For You To Get By
Michael Jackson (1958-2009)

You have a sequence of integers. You can paint each of the integers black or white, or leave
it unpainted. The black integers must appear in ascending order and the white integers
must appear in descending order. The ascending/descending order must be strict, that
is, two integers painted with the same color cannot be equal. Paint the sequence so as to
minimize the number of unpainted integers.


The input contains several test cases, each one described in exactly two lines. The first line
contains an integer N indicating the number of elements in the sequence (1 ≤ N ≤ 200).
The second line contains N integers Xi separated by single spaces, representing the
sequence to paint (1 ≤ Xi ≤ 106 for 1 ≤ i ≤ N ). The last line of the input contains a
single −1 and should not be processed as a test case.


For each test case output a single line with an integer representing the minimum number
of unpainted elements of the sequence, when the sequence is painted optimally following
the rules described above.


1 4 2 3 3 2 4 1
7 8 1 2 4 6 3 5 2 1 8 7

Output: 0

hide comments
sanjay_singh: 2021-05-04 10:31:58

@wk1948 come on side, need to talk XD

Rafail Loizou: 2020-11-15 14:21:54

top down will work now worries

may_007: 2020-10-10 14:27:32

AC in one go!

yash_490: 2020-09-13 21:53:06

getting TLE in python

dhairya_2000: 2019-12-10 17:50:15

AC in 1 go !!

kd2636: 2019-09-28 12:47:08

I need more help on this. I constructed a backtracking solution but it's getting tle. Any hint how shuld I optimize it. My recursive function does not return therefore I am not able to do any memorization.

amannegi227: 2019-07-11 13:56:29

what about Palindromic Pattern ?

akibk001: 2019-04-17 11:12:35

weak test cases
3 5 4 1 2
ans should be 1 but my accepted solution gives 0

Last edit: 2019-04-17 11:13:10
ab_biswas09: 2019-03-17 19:14:07

AC in one Go => 1.91 s

f00zz: 2019-03-16 22:33:03

Forget about trying to solve it in Python...

Added by:Pablo Ariel Heiber
Time limit:9.584s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2009