Google Code Jam Archive — Code Jam to I/O for Women 2020 problems
Overview
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 Is and
Os and is and os floating by in your
dreams! An earlier internal version of the problem had 1s
and 0s 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.
A. Interleaved Output: Part 1
Problem
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
Iotwice - B: programmed to print
iOtwice
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
IOtwice - B: programmed to print
ioonce - C: programmed to print
ioonce
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.
Input
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.
Output
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.
Limits
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 is plus the number of Is in S
is equal to the number of os plus the number of Os
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.)
Test set 1 (Visible Verdict)
2 ≤ the length of S ≤ 8.
Test set 2 (Hidden Verdict)
2 ≤ the length of S ≤ 100.
Sample
|
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 Is and two Os 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
IOonce - B: programmed to print
iOonce - C: programmed to print
Ioonce
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.
B. Imbalance Obviation
Problem
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 A1, A2, ..., AN specified by your friend. This order is a permutation of 1, 2, ..., N. The i-th marble you remove must be the marble numbered Ai.
Can you find a way to do this?
Input
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 A1, A2, ..., AN, which constitute a permutation of the first N natural numbers. The marble numbered Ai must be the i-th marble that you remove in the removal phase.
Output
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.
Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ai ≤ N, for all i.
Ai ≠ Aj for all i ≠ j.
Test set 1 (Visible Verdict)
2 ≤ N ≤ 16.
N is even.
Test set 2 (Hidden Verdict)
2 ≤ N ≤ 1000.
N is even.
Test set 3 (Hidden Verdict)
1 ≤ N ≤ 1000.
Sample
|
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 2LRLR: 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: EitherLorRwould be acceptable.2 3 1:LRRandRLLare the only acceptable answers.LLL,LLR,RRL, andRRRwould break the scale during the placement phase.LRLandRLRwould break the scale during the removal phase.
C. Interleaved Output: Part 2
Problem
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.
Input
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.
Output
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.
Limits
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.)
Test set 1 (Visible Verdict)
2 ≤ the length of S ≤ 8.
Test set 2 (Hidden Verdict)
2 ≤ the length of S ≤ 100.
Sample
|
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 Is 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).
D. Impromptu Outdoor Gallery
Problem
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 p1, p2, p3, and p4. He will then string velvet ropes between p1 and p2, p2 and p3, p3 and p4, and finally, p4 and p1. He must choose the four ordered posts such that no two ropes cross, effectively forming a simple quadrilateral p1p2p3p4. 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 p1, p2, p3 and p4 to minimize the area of the quadrilateral p1p2p3p4, and thus minimize the cost (in artcoins) of the refreshments service. What is the minimum such cost?
Input
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 Xi and Yi, representing the coordinates, in meters from an arbitrary origin, of the i-th post.
Output
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.
Limits
Memory limit: 1GB.
-109 ≤ Xi ≤ 109,
for all i.
-109 ≤ Yi ≤ 109,
for all i.
No three points in the input are collinear.
Test set 1 (Visible Verdict)
Time limit: 20 seconds.
1 ≤ T ≤ 50.
4 ≤ N ≤ 25.
Test set 2 (Hidden Verdict)
Time limit: 60 seconds.
1 ≤ T ≤ 30.
4 ≤ N ≤ 1200.
Sample
|
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.
Analysis — A. Interleaved Output: Part 1
Test Set 1
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.
Test Set 2
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
Owith an uppercaseI, rather than with a lowercasei - Preferentially pair a lowercase
owith a lowercasei, rather than with an uppercaseI
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
O1 — that we can match to either some previous unmatched
uppercase I — call it Iprev — or some
previous unmatched lowercase i — call it iprev. Suppose we choose to match O1 with iprev. Then we must
eventually match Iprev 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 O2. We will obtain 1 "point" (i.e. we
will be able to claim that an IO computer advertised its event
once) if O2 is uppercase, and 0 points if O2 is
lowercase.
But then observe that we could have instead matched the uppercase
O1 with Iprev (scoring 1 point
for sure), and matched the lowercase iprev with the same
O2. This argument holds true no matter which O2 we
picked. So preferentially matching with the Iprev 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 iprev.
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
Is and one previous lowercase i, but then it does
not matter which of the uppercase Is 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: CI, the number of
unmatched uppercase Is seen so far, and Ci, the
number of unmatched lowercase is seen so far. When we encounter
an uppercase O, score one point and decrement CI if
CI is positive, or otherwise decrement Ci. When we
encounter a lowercase o, decrement Ci if
Ci is positive, or otherwise decrement CI. 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.
Analysis — B. Imbalance Obviation
Test Set 1
For Test Set 1, we can enumerate all 2N possible strings of
length N composed only of Ls and/or Rs, 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×2N) for each test case, which is fast enough for this test set.
Test Set 2
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 A2i-1 and A2i 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.
Test Set 3
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 A1 (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 A2i-1 and A2i must go on different pans, for every i ≥ 1") with: marbles A2i and A2i+1 must go on different pans, for every i ≥ 1. (If we write this as "marbles AN-2i+2 and AN-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, A1, must come from the heaviest pan. We know that marble N is in the heaviest pan, so one way to represent this constraint is to replace both A1 and 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 A1 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.
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 note on 2-SAT
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.
Analysis — C. Interleaved Output: Part 2
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 24 = 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 × 2E.)
Analysis — D. Impromptu Outdoor Gallery
We can start by making the observation that for every valid quadrilateral, p1p2p3p4, 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 p1 and p3 splits the quadrilateral into two triangles. This means that points p2 and p4 are on opposite sides of the infinite line through p1 and p3 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 p1p2p3p4 is equal to the sum of the areas of the two triangles p1p3p2 and p1p3p4. These areas are equal to half of the product of the distance between p1 and p3 and the distance between p2 (or p4) and the line through p1 and p3. Therefore, if we choose two points to be p1 and p3 in our quadrilateral, we can find the minimum area using those two points by getting the closest point to the line through p1 and p3 on each side of the line.
Test set 1
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 p1 and p3, and then, for each pair, loop through the remaining points to find the closest on each side. There are O(N2) 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(N3).
Test set 2
In test set 2 we have significantly more points to choose from that a time complexity of O(N3) 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 p1 and p3, the closest points to the line p1p3 must be ones which are adjacent to either p1 or p3 in the sorted list (because p1 and p3 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 p2 and p4.
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(N2) 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(N2 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(N2 log N).