Consider this problem statement: 13B - Letter A

As far as I understand it, the following input does not represent a letter A because the angle between the first and second segments is equal to zero.

1
0 4 0 0
0 4 0 0
0 1 0 2

Yet I have a passing submission that prints "YES" for the input above: 10215631

I also have a passing submission that prints "NO" for the above: 10215660

The only difference between the two submissions is the last line of the function goodAngle.

This yields true for the case above:

return ax*bx + ay*by >= 0

This yields false:

return ax*by != bx*ay && ax*bx + ay*by >= 0

I believe the correct result is false and the input case shown above should result in "NO". Therefore, either the system tests missed all such cases or this case is considered invalid for some reason.

Which is it? Does anyone else think the system tests are incomplete?

"Yaroslav and Sequence" appears in Codeforces Round 182 (Div. 2) as problem C and in Codeforces Round 182 (Div. 1) as problem A.

Sereja's tutorial mentions depth-first search, which may well be the fastest way to write a solution. I think of this as a brute-force approach because it explores every possible state of the array. Wait a minute, I hear you saying, won't that time out? If we have a hundred elements, each one of which can be positive or negative, doesn't that make 2¹⁰⁰ states? It does if you include the position of each negative value. But if all you care about is the number of negative values, the number of states is linear in n.

We can disregard the positions of the negative values because if you have an array with exactly x negative values at some positions, you can transform it into an array with exactly x negative values at the positions of your choice. To see why this is so, consider the problem of moving a single negative sign to another position. Suppose we have the following state of affairs:

 a  b  c  d  e
 +  ?  ?  ?  -

The above illustrates a case where n = 3, so we have 2×3 − 1 = 5 values in all. The first element, a, is positive. The last element, e, is negative. The remaining values can be negative, positive, or zero. All we care about is transforming the array so that a is negative, e is positive, and the remaining values have the same sign as at present. We can accomplish this in two steps.

First, we reverse the sign of e and n−1 = 2 other elements that are not a. Let's choose c and d to be these two other elements:

 a  b -c -d -e
 +  ?  ?  ?  +

Now let's reverse the sign of a and the same n−1 elements that we chose before:

-a  b  c  d -e
 -  ?  ?  ?  +

And there you have it. In two steps, we can move a negative sign from one position to any other position. If we want to move several negative signs, we can repeat the same sequence of steps for each one. You can probably see how to improve on this by changing the signs of several target elements in each step.

The upshot is that we don't have to worry about the positions of the negative values. We'll just look for an array with the minimal number of negative values, and then we can distribute the minus signs in the most favorable way. Since the overall objective is to achieve the largest possible sum, we'll assign minus signs to the elements with the smallest absolute values.

Let's consider the implementation details of the brute-force approach to finding the smallest possible number of negative values. First, we characterize the array with a pair of values:

(negative, positive)

For example, the state (3, 1) means that the array has three negative values and one positive value.

Next, we define a recursive function that takes a state and applies the sign-reversal operation in as many ways as possible. If we're going to reverse the signs of n elements, how many do we draw from the negative elements of the array, how many from the zero elements, and how many from the positive elements? Let's call these numbers i, j, and k:

i = number of negative elements
j = number of zero elements
k = number of positive elements

It's clear that i+j+k = n must hold in order for the operation to be valid. Furthermore, each number is constrained by the state of the array. For example, the number of negative elements in the array is an upper bound on the value of i.

In my Python solution, I iterate over the possibilities as follows:

    for i in range(min(n, negative)+1):
        for j in range(min(n-i, zero)+1):
            k = n-i-j
            if k <= positive:
                go(negative-i+k, positive-k+i)

After we have visited every possible state, which is to say every possible (negative, positive) tuple, we know the minimum number of negative values. The final steps are to change every element in the array to its absolute value, assign the requisite number of negative signs to the smallest values, and compute the sum.

This approach is straightforward to implement once you see the idea of the state space and figure out how to deal with zero values. However, it resembles every other state-space search. In implementing it, you don't learn much about the nature of optimal solutions because you're making the code do all the work.

If you run the algorithm on a number of test cases, it will become apparent that the solutions have a peculiar nature. It turns out that in the optimal state, an array has no more than one negative value. To see why that's so, let's solve an example by hand.

Suppose we have a problem instance that looks like this:

- - - - - - - - - - - + +

That's a whole bunch of negative values and a few positive ones. It's obvious that we can improve the situation by reversing the signs of n negative values. To be precise, we have n = 7, making a total of 2×7 − 1 = 13 values, among which we have 2 pluses and 11 minuses. We can go from 11 minuses to 11−7 = 4 minuses:

- - - - + + + + + + + + +

In general, if there are more than n negative values, it makes sense to immediately reverse the sign of n of them. At most there can be 2n−1 negative values, which we can change to 2n−1 − n = n−1 in one step. Thus, we already have an upper bound of n−1 for the minimum number of negative values.

Let's continue with our example. We have 4 minuses and we'd like to have fewer. First, let's divide the minuses into two halves. To make this clear visually, let's rearrange the elements without changing the number of pluses and minuses:

- - + + + + + + + + + - -

Now let's change the sign of the first n = 7 elements:

+ + - - - - - + + + + - -

Notice that there are exactly two plus signs among the first n elements and exactly two minus signs among the last n−1 elements. To see how we can exploit this circumstance, let's swap the first two and last two elements:

- - - - - - - + + + + + +

All that remains is to reverse the signs of the first n elements:

+ + + + + + + + + + + + +

The same strategy can be applied to other numbers of minuses. Given an array with exactly x minuses where x ≤ n−1, we reverse the signs of x/2 minuses along with n − x/2 pluses. That results in n − x/2 new minuses, making a total of x/2 + n − x/2 = n minuses. One more operation leaves us with an array containing no minuses.

But that only works if x is an even number. If x is odd, what can we do? Suppose n is an odd number. Then n−x has the opposite parity of x. We can exploit this fact by reversing the signs of the x negative numbers and n−x positive numbers to arrive at n−x negative numbers. Thus, we can go from an odd number of minuses to an even number of minuses as long as n is odd.

If n is even and x is odd, is there anything we can do to get rid of the remaining minus? Yes, we can get rid of it as long as there is at least one zero. That's because we can let a zero value stand in as a minus, then perform the divide-in-half trick to get rid of the minuses. That work is unnecessary, though. We can keep the lone minus sign and assign it to a zero element, which means that it has no effect on the sum of the array.

In the end, all that matters is the parity of n and the parity of x. If n is odd, we can always contrive to make an even number of minuses, which we can then eliminate altogether. If n is even, we have to consider the parity of x, the number of minuses: if it's even, we're fine, and if it's odd, we end up with a lone minus.

The resulting implementation is much shorter than the brute-force approach, yet its correctness is only apparent if you have thought through the case analysis. If you're wondering where my code deals with cases where x ≥ n, it's implicit in the parity checks. Suppose n is even: then x−n has the same parity as x, so we can consider the parity of x instead of the parity of x−n. Suppose n is odd: then the parity of x−n doesn't matter. To make the last point more evident, observe that we can go from x−n minuses to n−(x−n) = 2n−x minuses with one sign-reversal operation, and that x−n and 2n−x have opposite parity when n is odd.