ComparerInator | Topcoder Archive

Problem Statement

Comparer-inator is a very simple language that is specialized in comparisons. It takes an expression and returns the result. There are only two kinds of expressions: a variable name or a tertiary operator inspired by C syntax (which is also used in many languages like Java, C++, and C#). We are interested to use this language to process two int[]s, A and B to generate the int[] wanted as a result. We have previously found that there are four candidate programs that could be an optimal way to solve the issue we have. Each of the programs takes two arguments a and b.

"a" : This program will return the given argument a.
"b" : This program will return the given argument b.
"a<b?a:b" : If a is less than b, the program will return a, else it will return b.
"a<b?b:a" : If a is less than b, the program will return b, else it will return a.

Given int[] A, B and wanted find the shortest of the four candidate programs that, for every index i, will return wanted[i] after being provided a=A[i] and b=B[i] as arguments. Return the length of the shortest program. If no candidate program can do the required job, return -1 instead.

Definition

Class:: ComparerInator
Method:: makeProgram
Parameters:: int[], int[], int[]
Returns:: int
Method signature:: int makeProgram(int[] A, int[] B, int[] wanted)
(be sure your method is public)

Constraints

A will contain between 1 and 50 elements, inclusive.
B and wanted will each contain the same number of elements as A.
Each element of A, B and wanted will be between 1 and 1000, inclusive.

Examples

```
{1}
```
```
{2}
```
```
{2}
```
```
Returns: 1
```
"b" and "a<b?b:a" (quotes for clarity) are the two programs that will return 2 after being given a=1, b=2 as arguments. "b" is the shortest of them.
```
{1,3}
```
```
{2,1}
```
```
{2,3}
```
```
Returns: 7
```
"a<b?b:a" is the only program that will return 2 after being provided a=1, b=2 and will also return 3 after being provided a=3, b=1.
```
{1,3,5}
```
```
{2,1,7}
```
```
{2,3,5}
```
```
Returns: -1
```
None of the four programs can do the job correctly.
```
{1,3,5}
```
```
{2,1,7}
```
```
{1,3,5}
```
```
Returns: 1
```

{1,2,3,4,5,6,7,8,9,10,11}

{5,4,7,8,3,1,1,2,3,4,6}

{1,2,3,4,3,1,1,2,3,4,6}

Returns: 7

```
{1,5,6,7,8}
```
```
{1,5,6,7,8}
```
```
{1,5,6,7,8}
```
```
Returns: 1
```
"a", "b", "a<b?a:b" and "a<b?b:a" are all valid programs that will give the wanted result. "a" and "b" are the shortest.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.