Help needed

general
1

Hello everyone,

Recently , I came across this question:

We will be given an array consisting of only 0’s and 1’s.We need to make array empty by doing this operation:

In one move,you can select some consecutive equal elements from this array and remove them.The remaining part of the array(if there are more than one)just get attached back together.For example,if you remove [0,0] from [1,0,0,1],the resulting array is [1,1]

Determine the minimum number of moves required to remove all elements.

Note:Elements can be removed one by one if no consecutive equal numbers are found.

Sample testcase1:

input: [1,0,0,1] output:2

explanation: remove [0,0] from array,then array would be [1,1]. Removing [1,1] makes array length=0 hence two operations.

Sample testcase2:

input:[0,1,0,1] output:3

explanation:The steps are [0,1,0,1]->[1,0,1]->[1,1]->[] Therefore the answer is 3.

Can anyone help me in approaching this problem and how to solve such type of problems?

2

I guess this is some ad-hoc type problem.

The first observation is, the array could be of two types :

  • 1111111…000000… (or) 000000…1111111… That is, it could be all ones followed by all zeros or all zeros followed by all ones. In this case, the answer is simply 2.
  • The other case would be multiple instances of the previous case. For example 10100100111 could be an array.

Now the only thing left to be solved is how to find out answer in the second case. To understand that, let us take an example as : 10100100111

  • If you carefully notice, both the sub-arrays [00111] (from indices 6 - 10) and [100111] (from indices 5 - 10), can be made empty in 2 steps.
  • The first sub-array is simply corresponds to the first type, so the answer is 2 for that. But it is the same for the second sub-array as well. (Delete the intermediate zeros, and then delete all the ones).

So, it would be beneficial for us to find, sub-arrays of the second type (00…1111…00 or 11…00.0.11) . Then this problem could be solved greedily to get the required answer.
Working with the example array, we can empty the array in 4 steps as

10100100111 -> 1000100111 -> 100000111 -> 1111 -> NULL

This way we can solve the problem by grouping zeros and ones, and removing sub-arrays of the second type and find the answer.

1 Like
3

1.take the given numbers in the std::list.
2.call its method,list.unique() which will remove its consecutive duplicates.
3.Take variables n=0 and m=0 ,then count 1’s in current list as n and 0’s is m.
4.answer will be (1+ min(n,m))

1 Like
4

Thank you for helping. But how do you come across such approaches? I get stuck in such type of problems. Can you provide me concept behind such approaches.

5

what if it is 1001001001?
list.unique() will give 0,1
so ur ans will be 2 but actual ans will be 4
as we remove all 00 in 3 moves and the left over 1’s in next move,
moreover unique is a method in numpy and I dont think we can import numpy in python in codechef.

6

for 1001001001,list.unique() will give 1010101(not 0,1).Thus,output is 1+3=4.unique function removes consecutive duplicates in this manner.Also,I was talking about c++ STL and not numpy :smiley: :sweat_smile:

7

Just practice more and give more contests(both rated & unrated) .then you will definitely see results and more thinking level :+1:

8

Thank you for your advice. But I would like to know,under which concept this question(which I have posted here) comes? So that I can practice more on that concept