This year's Code Jam to I/O for Women contest was the first to feature a
multi-part problem: *Interleaved Output*. In Part 1, the natural greedy
algorithm did work; however, in Part 2, a small change to the setup forced a
more complex solution. We hope that you won't see `I`

s and
`O`

s and `i`

s and `o`

s floating by in your
dreams! An earlier internal version of the problem had `1`

s
and `0`

s instead of the lowercase letters, so at least you didn't
have to parse strings like `I1O0`

...

The first two test sets of *Imbalance Obviation* were perhaps more
approachable than Interleaved Output: Part 2 — indeed, the whole
problem could be solved without prior algorithmic knowledge. (Depending on
your strategy, though, it might have been tricky to handle the odd-length
cases in Test Set 3!) Finally, *Impromptu Outdoor Gallery* was a very
difficult geometry problem about the whims of the art world. Those tickets to
I/O weren't going to come easily this year!

Many contestants plowed through Interleaved Output: Part 1; our first
correct solutions rolled in after only a few minutes. However, the remaining
problems didn't give up their points without a fight! Even picking off
Visible test sets took some work. Every test set did get solved at least
once, but there were no perfect scores. **rediska0123** came closest (93
points, 1:41:21), missing only the third test set of Imbalance Obviation.
**kobus** (76 points, 1:04:13) came in second, with everything but the
last test set of Impromptu Outdoor Gallery. **tap_tapii** (76 points,
1:09:48), the winner of Code Jam to I/O for Women 2019, was not far behind in
third. Just over 2500 contestants submitted something, and about half of
those solved at least one test set.

We hope you had a great time thinking about the problems, and for those of you in the top 150, we'll look forward to seeing you at I/O 2020! To make the top 150, you had to earn at least 41 points (generally by completely solving the first two problems), or earn 39 points with a sufficiently small penalty time. (As usual, we will need a bit of time to finalize the results, so the initial rankings are provisional.)

Thank you, and we'll see you next year with another set of Intriguing Offerings!

**Cast**

*Interleaved Output: Part 1*: Written by Sherry Wu and Pablo Heiber.
Prepared by Jonathan Irvin Gunawan. Analysis by Swetha Srinivasan.

*Imbalance Obviation*: Written by Hsin-Yi Wang. Prepared by Sadia Atique
and Jonathan Irvin Gunawan. Analysis by Sadia Atique.

*Interleaved Output: Part 2*: Written by Sherry Wu and Pablo Heiber.
Prepared by Swetha Srinivasan. Analysis by Swetha Srinivasan.

*Impromptu Outdoor Gallery*: Written by Lin Jin. Prepared by
Timothy Buzzelli and Lin Jin. Analysis by Timothy Buzzelli.

Solutions and other problem preparation and review by Shantam Agarwal, Lena Anyusheva, Bakhodir Ashirmatov, Sadia Atique, Liang Bai, Darcy Best, Timothy Buzzelli, Mingyuan Gao, Divanshu Garg, Jonathan Irvin Gunawan, Md Mahbubul Hasan, Pablo Heiber, Joyce Lee, Lizzie Sapiro, Pi-Hsun Shih, Swetha Srinivasan, Mary Streetzel, Ian Tullis, Hsin-Yi Wang, Sherry Wu, and Diego Gutiérrez Yépiz.

*
You do not need to read the Interleaved Output: Part 2 problem to
be able to solve this problem. Both Part 1 and Part 2 have the same first
two paragraphs (not including this informational text). We have underlined
the critical difference between the two parts.
*

On a distant moon of Jupiter, some developer conference events are about to
happen! They are called `IO`

(uppercase I, uppercase O),
`Io`

(uppercase I, lowercase o), `iO`

(lowercase I,
uppercase O), and `io`

(lowercase I, lowercase O).

The best way to advertise an event is by using special computers that print
the event's name one character at a time, with the output appearing on a
digital display. Each such computer only knows the name of one event, and is
programmed to print its event's name zero or more times. For example, a
computer programmed to print `IO`

twice prints an `I`

,
followed by an `O`

, followed by an `I`

,
followed by an `O`

, for a final string of `IOIO`

.

You know that the conference organizers are using these computers, but you do
not know how many computers are advertising each event. __For each event,
there may be any number of computers (including zero) programmed to print the
event's name.__ Moreover, the computers are not necessarily all programmed
to print the same number of times. For example, it is possible that there are
three computers programmed to print `Io`

once each, and one
computer programmed to print `Io`

twice.

The computers have all finished printing, but unfortunately, they all printed to the same display! Because the computers printed concurrently, event names in the final output string may be interleaved. You are considering the possible ways in which that string could have been produced.

For example, the string `IiOioIoO`

could have been produced by
two computers, as follows:

- A: programmed to print
`Io`

twice - B: programmed to print
`iO`

twice

index: 1 2 3 4 5 6 7 8 A: I . . . o I o . B: . i O i . . . O string: I i O i o I o O

In this interpretation, the `Io`

event was advertised twice, the
`iO`

event was advertised twice, and the other two events were
not advertised at all.

But the string could have also been produced by three computers:

- A: programmed to print
`IO`

twice - B: programmed to print
`io`

once - C: programmed to print
`io`

once

index: 1 2 3 4 5 6 7 8 A: I . O . . I . O B: . i . . o . . . C: . . . i . . o . string: I i O i o I o O

In this interpretation, the `IO`

event was advertised twice, the
`io`

event was advertised twice, and the other two events were not
advertised at all. Notice that this interpretation required two computers
printing `io`

; there could not have been just one computer
printing `io`

twice, because it would have had to print
`i`

twice in a row, which is not allowed.

Given a final output string, what is the maximum possible number of times
that the event `IO`

could have been advertised?

It is guaranteed that the string has at least one valid interpretation.
For example, `oI`

and `IOI`

are not valid inputs.

The first line of the input gives the number of test cases, **T**.
**T** lines follow; each represents a single test case. Each case
consists of a string **S** containing only the characters from the set
`I`

, `O`

, `i`

, and `o`

.

For each test case, output one line containing `Case #x: y`

, where
`x`

is the test case number (starting from 1) and `y`

is the maximum number of times `IO`

could have been advertised, as
described above.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

The length of **S** is even.

For each prefix S' of **S**, the number of `i`

characters plus the number of `I`

characters in S' is not less
than the number of `o`

characters plus the number of
`O`

characters in S'.

The number of `i`

s plus the number of `I`

s in **S**
is equal to the number of `o`

s plus the number of `O`

s
in **S**.

(Notice that the above three conditions guarantee that there is at least one
interpretation of **S** that is consistent with the rules in the problem
statement.)

2 ≤ the length of **S** ≤ 8.

2 ≤ the length of **S** ≤ 100.

Input |
Output |

5 IiOioIoO IiOOIo IoiOiO io IIIIOOOO |
Case #1: 2 Case #2: 1 Case #3: 0 Case #4: 0 Case #5: 4 |

Sample Case #1 is the one described in the problem statement. We saw that
there is an interpretation in which `IO`

was advertised twice.
There are only two `I`

s and two `O`

s in the string,
so the answer cannot be larger than this.

In Sample Case #2, notice that it is not possible that `IO`

was
advertised twice. The only possible interpretations are as follows:

- A: programmed to print
`IO`

once - B: programmed to print
`iO`

once - C: programmed to print
`Io`

once

index: 1 2 3 4 5 6 A: I . . O . . B: . i O . . . C: . . . . I o string: I i O O I o

or the same but with

index: 1 2 3 4 5 6 A: I . O . . . B: . i . O . . C: . . . . I o string: I i O O I o

In either of these interpretations, `IO`

was advertised only
once.

In Sample Case #3, there is no possible interpretation in which
`IO`

was advertised. There must have been one computer programmed
to print `Io`

once, and either one computer printing
`iO`

twice, or two computers printing `iO`

once each.

In Sample Case #4, notice that it is possible that `I`

and/or
`O`

might not even show up in the string.

In Sample Case #5, an interpretation in which `IO`

was advertised
four times requires four computers, each of which was programmed to
print `IO`

once.

You have a special balance scale, with two pans (left and right) that are
both initially empty. You also have a box of identical 1-gram marbles. There
are **N** of these marbles, and the marbles are numbered from 1 to
**N**.

Your scale is very sensitive, and you know that if the total weight on the left pan and the total weight on the right pan ever differ by strictly more than 1 gram, the scale will break. For example, if at some point there are 4 marbles in one of the pans, there must be either 3, 4, or 5 marbles in the other pan.

Your friend Libra has challenged you to do the following, without breaking the scale at any point:

- First, put all of the marbles on the scale one at a time, in numerical
order: marble 1, then marble 2, and so on up to marble
**N**. For each marble, you choose whether to place it on the left pan or on the right pan. - Then, remove all of the marbles from the scale one at a time, in an
order
**A**,_{1}**A**, ...,_{2}**A**specified by your friend. This order is a permutation of 1, 2, ...,_{N}**N**. The i-th marble you remove must be the marble numbered**A**._{i}

Can you find a way to do this?

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each test case begins with one line with an
integer **N**: the number of marbles. Then, there is one more line with
**N** integers
**A _{1}**,

For each test case, output one line containing `Case #x: y`

,
where `x`

is the test case number (starting from 1) and
`y`

is a string of **N** characters. The i-th of these
characters (counting starting from 1) should be uppercase `L`

if
the i-th numbered marble should be put on the left pan, or uppercase
`R`

if it should be put on the right pan.

It is guaranteed that at least one answer exists. If there are multiple valid answers, you may output any one of them.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

1 ≤ **A _{i}** ≤

2 ≤ **N** ≤ 16.

**N** is even.

2 ≤ **N** ≤ 1000.

**N** is even.

1 ≤ **N** ≤ 1000.

Input |
Output |

2 4 3 1 2 4 4 1 2 3 4 |
Case #1: LRRL Case #2: LRLR |

In Sample Case #1, we will put marble 1 on the left pan, then put marble 2 on the right pan, then put marble 3 on the right pan, then put marble 4 on the left pan. Notice that the total weights on the left and right pans — (1, 0), (1, 1), (1, 2), and (2, 2) — never differ by more than 1 throughout this process.

Then, we must remove the marbles in the order 3, 1, 2, 4. Again, the total weights on the left and right pans — (2, 1), (1, 1), (1, 0), (0, 0) — never differ by more than 1 at any point. We have succeeded!

Also notice that `RLLR`

would be a valid answer for this case, per
the same reasoning above (but with the two pans swapped).

Notice that the following are examples of invalid answers for this case:

`LLRR`

: breaks the scale when placing marble 2`LRLR`

: breaks the scale when removing marble 1 (which is the second marble to be removed)

Although there are no samples with odd **N** (since that is only possible
in Test Set 3), here are some examples:

`1`

: Either`L`

or`R`

would be acceptable.`2 3 1`

:`LRR`

and`RLL`

are the only acceptable answers.`LLL`

,`LLR`

,`RRL`

, and`RRR`

would break the scale during the placement phase.`LRL`

and`RLR`

would break the scale during the removal phase.

*
You do not need to read the Interleaved Output: Part 1 problem to
be able to solve this problem. Both Part 1 and Part 2 have the same first
two paragraphs (not including this informational text). We have underlined
the critical difference between the two parts.
*

On a distant moon of Jupiter, some developer conference events are about to
happen! They are called `IO`

(uppercase I, uppercase O),
`Io`

(uppercase I, lowercase o), `iO`

(lowercase I,
uppercase O), and `io`

(lowercase I, lowercase O).

The best way to advertise an event is by using special computers that print
the event's name one character at a time, with the output appearing on a
digital display. Each such computer only knows the name of one event, and is
programmed to print its event's name zero or more times. For example, a
computer programmed to print `IO`

twice prints an `I`

,
followed by an `O`

, followed by an `I`

,
followed by an `O`

, for a final string of `IOIO`

.

You know that the conference organizers are using
__exactly one computer to advertise each event__. Each printer may print
its event name zero or more times. Moreover, the computers are not
necessarily all programmed to print the same number of times.

The computers have all finished printing, but unfortunately, they all printed to the same display! Because the computers printed concurrently, event names in the final output string may be interleaved. You are considering the possible ways in which that string could have been produced.

For example, the string `IiOioIoO`

could have been produced
as follows:

index: 1 2 3 4 5 6 7 8 IO: . . . . . . . . Io: I . . . o I o . iO: . i O i . . . O io: . . . . . . . . string: I i O i o I o O

In this interpretation, the `Io`

event was advertised twice, the
`iO`

event was advertised twice, and the other two events were
not advertised at all.

Notice that there is no valid interpretation of this string in which the
`IO`

computer advertised its event twice. In that case, the
remaining output, `iioo`

, would have had to have come from the
`io`

computer, but that is impossible — that computer would
have had to have printed `i`

twice in a row, which is not allowed.

However, it is possible that the `IO`

computer advertised its
event once, as in the following interpretation:

index: 1 2 3 4 5 6 7 8 IO: . . . . . I . O Io: I . . . o . . . iO: . i O . . . . . io: . . . i . . o . string: I i O i o I o O

Given a final output string, what is the maximum possible number of times
that the event `IO`

could have been advertised?

It is guaranteed that the string has at least one valid interpretation.
For example, `oI`

, `IOI`

, and `IIOO`

are not
valid inputs.

The first line of the input gives the number of test cases, **T**.
**T** lines follow; each represents a single test case. Each case
consists of a string **S** containing only the characters from the set
`I`

, `O`

, `i`

, and `o`

.

For each test case, output one line containing `Case #x: y`

, where
`x`

is the test case number (starting from 1) and `y`

is the maximum number of times `IO`

could have been advertised, as
described above.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **T** ≤ 100.

The length of **S** is even.

There is at least one interpretation of the string that is consistent with
the rules above. (That is, there is some way to assign each character to one
of the four computers, such that the substring corresponding to each computer
consists of zero or more repeats of that computer's event's name.)

2 ≤ the length of **S** ≤ 8.

2 ≤ the length of **S** ≤ 100.

Input |
Output |

5 IiOioIoO IIOiOo IoiOiO io IiOIOIoO |
Case #1: 1 Case #2: 1 Case #3: 0 Case #4: 0 Case #5: 3 |

Sample Case #1 is the one described in the problem statement. (If you have read Interleaved Output: Part 1, notice that it is the same input as in the first sample case in that problem, but the output is different.)

In Sample Case #2, it is not possible that `IO`

was advertised
twice, because then the `IO`

computer would have had to print
two `I`

s in a row. However, it is possible that `IO`

was advertised once, e.g.:

index: 1 2 3 4 5 6 IO: I . O . . . Io: . I . . . o iO: . . . i O . io: . . . . . . string: I I O i O o

In Sample Case #3, notice that it is not possible that `IO`

was
advertised. The second character, `o`

, must have been printed by
the same computer that printed the first character `I`

.

In Sample Case #4, notice that it is possible that `I`

and/or
`O`

might not even show up in the string.

In Sample Case #5, it is possible that `IO`

was advertised as
many as three times (and in that case, `io`

was advertised once).

The artist Cody-Jamal recently decided to out-hip all of his hipster friends by showing his latest paintings in an impromptu outdoor gallery. He is going to show up in a field, put up some paintings, and display them.

The field has **N** posts in it, with no subset of 3 of them being
collinear (which also implies that no two posts are in the same place).
Cody-Jamal is going to choose four of them — call them p_{1},
p_{2}, p_{3}, and p_{4}. He will then string velvet
ropes between p_{1} and p_{2}, p_{2} and
p_{3}, p_{3} and p_{4}, and finally, p_{4}
and p_{1}. He must choose the four ordered posts such that no two
ropes cross, effectively forming a
simple quadrilateral
p_{1}p_{2}p_{3}p_{4}. The quadrilateral may be
convex or concave.
He will then hang his paintings inside the perimeter delimited by the ropes.

To attract wealthy art lovers that might purchase his paintings, Cody-Jamal
is hiring waitstaff to go around and serve refreshments to visitors. The cost
of the refreshments is fixed, but the cost of the waitstaff is proportional
to the area they will have to walk. Specifically, they charge 2 artcoins per
square meter. Therefore, Cody-Jamal wants to choose
p_{1}, p_{2}, p_{3} and p_{4} to minimize the
area of the quadrilateral
p_{1}p_{2}p_{3}p_{4}, and thus minimize the
cost (in artcoins) of the refreshments service. What is the minimum such cost?

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each test case begins with a line containing a
single integer **N**: the number of posts in the field. **N** more
lines follow, each containing two integers **X _{i}** and

For each test case, output one line containing `Case #x: y`

, where
`x`

is the test case number (starting from 1) and `y`

is the minimum number of artcoins Cody-Jamal will have to pay — or, in
other words, twice the area (in square meters) of a smallest simple
quadrilateral that has four of the input points as vertices.

Memory limit: 1GB.

-10^{9} ≤ ** X_{i}** ≤ 10

-10

No three points in the input are collinear.

Time limit: 20 seconds.

1 ≤ **T** ≤ 50.

4 ≤ **N** ≤ 25.

Time limit: 60 seconds.

1 ≤ **T** ≤ 30.

4 ≤ **N** ≤ 1200.

Input |
Output |

4 4 -5 5 -5 -5 5 5 5 -5 5 -5 5 -5 -5 5 5 5 -5 4 2 5 -5 5 -5 -4 5 5 5 -5 4 2 4 -1000000000 -1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000 1000000000 |
Case #1: 200 Case #2: 30 Case #3: 31 Case #4: 8000000000000000000 |

In Case #1, there are only 4 points in the input, and the only orderings that can be chosen to form a simple quadrilateral yield a square of side length 10.

In Cases #2 and #3, an optimal choice is to leave the first point out and use the last four, in the order given in the input.

One way of approaching this test set is to try all ways of assigning pairs of
characters in the string (an uppercase `I`

or lowercase
`i`

followed by an uppercase `O`

or lowercase
`o`

) to particular computers, and in each case, recursively check
whether the remaining string could have been produced. If, at any point during
our check, our string starts with an uppercase `O`

or lowercase
`o`

, then the string is invalid and we can abandon that branch
of the search.

For example, if we have `IoiO`

, we can try assigning the
uppercase `I`

and the uppercase `O`

to an
`IO`

computer, then recursively check the remaining
`oi`

and find that it's invalid, then try instead assigning the
uppercase `I`

and lowercase `o`

to an `Io`

computer, and so on. Finally, find the largest possible number of
advertisements of `IO`

, across all valid assignments.

The above strategy is too slow for Test Set 2 because there are too many possible pairs to check. Let's look for a simpler strategy.

As we scan through a string, whenever we encounter an uppercase or lowercase
O, we must find a previous unused uppercase or lowercase I to pair it with
(implicitly claiming that a particular computer printed both of those
characters). Intuitively, to find an interpretation that maximizes the number
of times `IO`

is advertised, we would like to do the following as
much as possible:

- Preferentially pair an uppercase
`O`

with an uppercase`I`

, rather than with a lowercase`i`

- Preferentially pair a lowercase
`o`

with a lowercase`i`

, rather than with an uppercase`I`

However, we may not always be able to get what we want! For example, suppose
we are scanning through the input `IoiO`

. When we reach the
lowercase `o`

, we have no choice but to pair it with the preceding
`I`

.

We can prove, though, that if we adhere to the above preferences whenever we
have a choice, we will find the correct answer. Suppose we are carrying out
this method, and we reach an uppercase `O`

— call it
O_{1} — that we can match to either some previous unmatched
uppercase `I`

— call it I_{prev} — or some
previous unmatched lowercase `i`

— call it i_{prev}. Suppose we choose to match O_{1} with i_{prev}. Then we must
eventually match I_{prev} with some later uppercase or lowercase O.
(It is guaranteed that at least one of these exists because the input
satisfies a balanced parentheses constraint, as outlined in the Limits
section.) Call that later O O_{2}. We will obtain 1 "point" (i.e. we
will be able to claim that an `IO`

computer advertised its event
once) if O_{2} is uppercase, and 0 points if O_{2} is
lowercase.

But then observe that we could have instead matched the uppercase
`O`

_{1} with I_{prev} (scoring 1 point
*for sure*), and matched the lowercase i_{prev} with the same
O_{2}. This argument holds true no matter which O_{2} we
picked. So preferentially matching with the I_{prev} is no worse, and
may be better.

A similar argument holds for the situation in which we reach a lowercase
`o`

that we can match to either a previous uppercase
`I`

or a previous lowercase `i`

, and it tells us to
preferentially match with the i_{prev}.

We have covered the only two cases in which we can make a decision. Since no
other strategy is better in either case, our strategy is an optimal one. It
is possible that we may have a choice of e.g. two previous uppercase
`I`

s and one previous lowercase `i`

, but then it does
not matter which of the uppercase `I`

s we pick, since whichever
one we don't use will still be "previous" for the purposes of later
decisions.

A simpler way to frame this strategy is as follows: scan through the string
from left to right, keeping two counts: C_{I}, the number of
unmatched uppercase `I`

s seen so far, and C_{i}, the
number of unmatched lowercase `i`

s seen so far. When we encounter
an uppercase `O`

, score one point and decrement C_{I} if
C_{I} is positive, or otherwise decrement C_{i}. When we
encounter a lowercase `o`

, decrement C_{i} if
C_{i} is positive, or otherwise decrement C_{I}. Notice that
the rules of the problem guarantee that these counts will never
simultaneously become zero at the time we encounter an uppercase
`O`

or lowercase `o`

.

For Test Set 1, we can enumerate all 2^{N} possible strings of
length **N** composed only of `L`

s and/or `R`

s, and
check whether each one would break the scale, by simulating the process
explained in the problem statement. We can then output any one string that
works; the statement guarantees that at least one exists.

This process has a time complexity of O(**N**×2^{N})
for each test case, which is fast enough for this test set.

Suppose we've placed our first marble on one of the pans. Then the second marble must go on the other pan. Now we are effectively back in the same situation — the scale is balanced and we have our choice of pan again, but then that choice forces the next choice, and so on.

Similarly, if the number of marbles is even (as is always the case in this test set), the scale is balanced before we start to remove marbles. This means we can remove the first marble from either pan, but the second marble we remove must come from the other one. The third marble can be removed from either one again, but the fourth must be removed from the other one, and so on.

We can formalize the first observation by saying that marbles 2i and 2i-1
must go on different pans, for every i ≥ 1. We can formalize the second
observation by saying that marbles **A**_{2i-1} and
**A**_{2i} must go on different pans, for every i ≥ 1.

The rules above help to reduce this problem to
graph coloring
. In our graph, each node represents a marble, and each pair of marbles that
are required to be on different pans is connected by an edge. The resulting
graph has **N** nodes and at most **N** edges, and each of the nodes is
connected to at most 2 other nodes. If we can 2-color the graph, we can use
one of the colors (it doesn't matter which one) to represent the left pan and
the other to represent the right pan, and then we will have our desired
assignment of marbles to pans. Better yet, 2-coloring takes at most linear
time!

How can be sure that a 2-coloring is possible, apart from the assurances in the problem statement that a solution always exists? Well, this is possible if and only if there are no cycles of odd length — can we show that?

The constraints from the marble-adding phase pair up nodes 1 and 2, 3 and 4,
etc. Call these the "original pairs". Any additional constraint from the
marble-removing phase (that is, from the input permutation **A**) can do
one of the following: match an original pair's edge, in which case that pair
cannot have other connections to the rest of the graph and is not a cycle, or
add an edge that connects two of the original pairs. Then, any path that does
not repeat edges alternates between edges connecting original pairs and edges
from the marble-removing phase that do not connect original pairs. Therefore,
any cycle formed is of even length, or else it would have two edges of the
same type one after the other.

So, the resulting graph is bipartite and our strategy will always find a solution.

Let's reconsider the above strategy and see if we can make it work for odd
**N**:

- The first rule ("marbles 2i and 2i-1 must go on different pans, for
every i ≥ 1") is still fine — the pans will be balanced right
before we place marble
**N**, so it does not matter where we put that marble. - After we remove the marble
**A**(more on that in a moment), the pans will be balanced again, so we need our second and third marbles to be removed from opposite sides, and then our fourth and fifth, and so on. We can replace the second rule above ("marbles_{1}**A**_{2i-1}and**A**_{2i}must go on different pans, for every i ≥ 1") with: marbles**A**_{2i}and**A**_{2i+1}must go on different pans, for every i ≥ 1. (If we write this as "marbles**A**_{N-2i+2}and**A**_{N-2i+1}must go on different pans, for every i ≥ 1", then the condition is the same as in the even-**N**case.) - Finally, the first marble removed,
**A**, must come from the heaviest pan. We know that marble_{1}**N**is in the heaviest pan, so one way to represent this constraint is to replace both**A**and_{1}**N**in the graph with a new "node" that represents them both. We can do this because we know that marble**N**has no constraints arising from the marble-adding phase, and marble**A**has no constraints arising from the marble-removing phase. So the argument from earlier about no odd cycles still holds; this new "node" can only be entered via one type of constraint and exited via another._{1}

A less complex version of the above idea is: we can introduce an imaginary
extra marble that we add last and remove first, making the total number of
marbles even again. We can add **N** + 1 to the end of the identity
permutation, and to the beginning of the input permutation (since it was the
last marble added, it's always safe to remove it first, restoring a previous
valid state). Then we can solve the problem as in the even version above, and
finally chop off the last character of the sequence. This gives us the same
O(**N**) time complexity as in Test Set 2.

A more abstract view of the same solution is to represent each marble as a Boolean variable (where true corresponds to assignment to one pan and false to assignment to the other pan), and then encode the requirements explained above as two implications of literals, which are in turn disjunctions of literals. The conjunction of all those requirements is a valid input to 2-satisfiability (2-SAT). Notice that the graph created in the typical 2-SAT algorithm is exactly 2 copies of the graph mentioned for the solution above, so the algorithm ends up being the same in both cases.

An important difference between this problem and the Part 1 version is that
in this version, for each of the events, there is only a single computer that
can print it. That is, there are only four computers printing simultaneously
for the four events, `IO`

, `io`

, `Io`

and
`iO`

. Our optimal greedy strategy from the Part 1 analysis is not
compatible with this constraint.

For example, consider the sample input `IiOioIoO`

. Our
Part 1 strategy would find an interpretation in which `IO`

was advertised twice. But this interpretation requires two separate computers
to have printed `io`

, since one computer cannot print an
`i`

followed by another `i`

... and in Part 2, we only
have one `io`

computer.

Let us find a way to turn this new constraint into an advantage. Regardless
of how many times each computer ends up advertising its event, each computer
can be in only one of two states at any given time: either it is about to
print its first character, or about to print its second character. So, at any
point, the system of 4 computers is in one of 2^{4} = 16 states. This
situation, in which we have only a limited number of states to consider,
is ideal for a
dynamic programming
approach in which we step through the string and keep track of the best
option seen so far for each of those states.

Let us describe our 16 states in terms of which computers are about to print
their *second* characters. For example, the state
{`IO`

, `iO`

} means that the `IO`

and
`iO`

computers need to print their second character
(`O`

) next, and the `io`

and `Io`

computers
need to print their first character (`I`

or `i`

)
next.

We will also define the "score" of a prefix of the input string p and a state
s as the number of completed `IO`

events designated after
processing p ending in state s. Since scores only increase, we only
care about the maximum score for each combination. The final answer to the
problem is the score for p = **S** and s = {}, that is, when we have
processed the entire string and no computer has printing pending.
We will also define the "score" of a partial string as the number of
completed `IO`

events designated so far in that string.

Consider the input string `IiOioIoO`

. When we process the first
`I`

, we must decide which computer printed that character —
that is, after that choice, we can either be in the state {`IO`

}
or the state {`Io`

}. With dynamic programming, we simultaneously
keep track of all of these possible worlds; we are not actually committing to
a particular choice. After we process the next character, depending on our
interpretation, we can be in one of four states: {`IO, iO`

},
{`IO, io`

}, {`Io, iO`

}, or {`Io, io`

}.
Then, moving on to the next `O`

, we find that
{`Io, io`

} is inconsistent, and the possible states become
{`IO`

} (with a score of 0 so far), {`iO`

} (with a score
of 1), {`io`

} (with a score of 0), or {`Io`

} (with a
score of 0). We continue this until we have finished processing the string,
and then we have our answer.

Our dynamic programming approach has O(L) stages (where L is the input string
length), and each stage has a constant processing time since there are
no more than 16 states to consider. This results in an overall time
complexity of O(L), but notice that we have only been able to wave away a
constant factor because the number of events/computers was small. With E
possible events, the complexity would be O(L × 2^{E}.)

We can start by making the observation that for every valid quadrilateral,
p_{1}p_{2}p_{3}p_{4}, at least one of the
two diagonals divides the quadrilateral into two triangles. We can order
the points in the quadrilateral such that the diagonal formed by points
p_{1} and p_{3} splits the quadrilateral into two triangles.
This means that points p_{2} and p_{4} are on opposite sides
of the infinite line through p_{1} and p_{3} or vice versa.
Without loss of generality, we can assume the former, since it is just a renaming
of the same set of points in the same order.
The area of p_{1}p_{2}p_{3}p_{4} is equal to
the sum of the areas of the two triangles
p_{1}p_{3}p_{2} and
p_{1}p_{3}p_{4}.
These areas are equal to half of the product of the distance between
p_{1} and p_{3} and the distance between p_{2}
(or p_{4}) and the line through p_{1} and p_{3}.
Therefore, if we choose two points to be p_{1} and p_{3} in
our quadrilateral, we can find the minimum area using those two points by
getting the closest point to the line through p_{1} and p_{3}
on each side of the line.

With only 25 points, we can test every set of 4 points in every order. To make sure a specific order defines a simple polygon, it suffices to check the sign of the signed area of both triangles is positive. This can be done by checking the sign of the cross product when computing the area of the two triangles that make up the quadrilateral.

We could also can loop over all possible pairs of points to use as p_{1}
and p_{3}, and then, for each pair, loop through the remaining points
to find the closest on each side.
There are O(**N**^{2}) unique pairs of points and for each pair, we
check O(**N**) other points to find the closest on each side. This gives
an overall time complexity of O(**N**^{3}).

In test set 2 we have significantly more points to choose from that a time
complexity of O(**N**^{3}) will not work for the given time limit.
We can, however, precompute all lines formed by unique pairs of points
and do a circular
sweep line,
processing those lines in order of their slopes; this will make it much faster to
find the closest points to the lines. As we rotate, we keep the points in a list sorted
by their distance to the line.

We can add the horizontal line to the set of stop points, and use it as the starting angle
for the sweep line. This simplifies initialization because sorting the points by distance
to this line is simply sorting by y-coordinate.
Then, for any p_{1} and p_{3}, the closest points to the line
p_{1}p_{3} must be ones which are adjacent to either
p_{1} or p_{3} in the sorted list (because p_{1} and p_{3}
have a distance of 0). There is a constant number of candidates, so we can check them
all in constant time to find the best p_{2} and p_{4}.

As we rotate our orientation to line up with the next smallest sloped line, we can see that the only points that change their ordering in the sorted list are the two points of the line segment being looked at. Taking advantage of this, we can maintain our sorted list of points by just swapping the adjacent pairs of each line after we consider them in order of slope.

Because we still have O(**N**^{2}) unique lines and we need to sort
them by their slopes, the initial time complexity to generate the sorted list
of lines and the initial ordering of the points is
O(**N**^{2} log **N**). After we have all the line segments
sorted, we can maintain the sorted list and go through each line in order and
find the closest points in O(1) per line. This results in an overall time
complexity of O(**N**^{2} log **N**).