Approach for spoj problem BTCODE_C

general
, ,
1

I am trying to solve this spoj problem BTCODE__C I have no clue on how to start. There are a couple of solutions submitted by other users, I am not able to get anything out of that too!. I am not expecting any code from you guys. Just a few pointers or a rough idea would be of immense help! Thanks in advance!

1 Like
2

Here is a rough idea for this problem:

First we need to make four different arrays for all the types of inequalities.

Now declare a variable max which stores the maximum no of elements satisfying the inequalities. This max variable should be updated by checking all the cases.

A basic case might be that all the n elements are of one same type only. Thus max would be the maximum of the size of all the arrays, except for array of equality sign,because a value ‘x’ cannot be simultaneously equal to all th different elements.

First just assume that only two inequalities, less than and greater than are present. Now for this three cases are possible:

  1. Min(Less than) < Max(Greater than) and The value ‘x’ is greater than the maximum of all elements for inequality of type ‘greater than’, but also greater than maximum of all elements for inequality of type ‘less than’. In this case, the number of inequalities satisfied would be equal to number of elements present in the type ‘greater than’.

  2. Min(Less than) < Max(Greater than) and The value ‘x’ is less than even the minimum of all elements of type ‘less than’, but also less than the minimum of all elements of type ‘greater than’. In this case, the number of inequalities satisfied would be equal to the number of elements present in the type ‘less than’.

  3. Min(Less than) > Max(Greater than) and the value of ‘x’ lies between them. In this case, the number of inequalities satisfied would be equal to the number of elements lying between Max(Greater than) and Min(Less than).

From this, the maximum inequalities satisfied among all the cases can be found.

Now for the original question, for equality sign find out number of duplicate elements for this type. This would be the maximum possible number of equalities which can be satisfied for a given value of ‘x’.
You may add this value, and also record this value.

Finally, for inequality sign all the elements would satisfy. Thus, this should be considered at last, and not a lot of elements would be rejected from this. In this, we may find out number of duplicates which would be rejected when we select a case for one particular value of ‘x’. This should also be considered.

For finding number of duplicates, the concept of hashing can be used.

Also look out for boundary conditions.

2 Likes