FrameBall | Topcoder Archive

Problem Statement

Snooker is a cue sport. It is played on a rectangular table covered with a green cloth. The table has pockets at each of the four corners and in the middle of each long side. Using a cue stick, players must strike the white ball ("cue ball") and use it to get other balls of various colors into the pockets ("pot the balls"). Players accumulate points for successfully potting the balls, and the one with a bigger total wins.

Balls that are potted can be divided into two basic groups: the "reds" and the "colors". At the beginning of a game of snooker ("a frame"), there are:

R identical red balls ("reds"), worth 1 points each. (The number R won't be given in this problem.)
C pairwise distinct balls of other colors ("colors"), worth 2, 3, ..., C+1 points respectively.

The balls must be potted in a correct sequence. The rules are as follows:

At any moment, one of the two players is at the table. This player can play until they either finish the frame by clearing the table, or until they make a mistake.
With each shot the current player must pot exactly one ball.
If there are still red balls on the table, the ball potted by the first shot must be red. A successfully potted red ball is removed from the game.
After potting a red ball the player must always pot one of the colors. A colored ball successfully potted this way is returned to the table.
The game continues this way (with the player alternately potting a red and a color) until all red balls are gone. After the last red ball the player does still have to pot a color that will returned to the table.
Finally, the player must finish the frame by potting the colors in increasing score order. The colors potted during this phase are no longer replaced on the table.

For example, suppose you just arrived at the table and there are three reds (1 point each), a yellow, a green, a brown, a blue, a pink, and a black ball (2 to 7 points) on the table. The maximum score in this situation is obtained by potting the balls in the order red, black (replaced), red, black (replaced), red, black (replaced), yellow, green, brown, blue, pink, black. Your total score for these balls would be 1 + 7 + 1 + 7 + 1 + 7 + 2 + 3 + 4 + 5 + 6 + 7 = 51

From that same situation, if you only pot a single red and then make a mistake, your opponent will then be able to score at most 43 points. (Note that it's 43, not 50: your opponent also has to start their turn by potting a red.)

You just started your turn at the table. There are N balls left on the table. (If N <= C the balls are the N colors worth the most points, otherwise the balls on the table are all the colors and N-C reds.) Your score so far (from your previous stays at the table) is yourScore. Your opponent has accumulated oppScore points so far.

Find and return the smallest non-negative integer X with the following property: it is possible to pot the next X balls in such a way that you'll create a situation in which you are guaranteed to win the frame. If you cannot win the frame at all, return -1 instead.

(Ball number X is called a frame ball, because if you play perfectly until and including the frame ball, you will decide the frame for yourself.)

You are actually given multiple queries to answer: C, N, yourScore and oppScore are actually arrays, all of the same length L. Return a long[] with L elements. For each i, element i of the return value should be the answer to the query given by the i-th elements of the input arrays.

Definition

Class:: FrameBall
Method:: solve
Parameters:: int[], int[], long[], long[]
Returns:: long[]
Method signature:: long[] solve(int[] C, int[] N, long[] yourScore, long[] oppScore)
(be sure your method is public)

Notes

The problem presents a necessarily simplified set of rules of snooker. The discrepancies should not matter, but if there is a difference, the version of rules given in the statement is the one that should be used.
(For example, the actual rules of snooker also contain other ways to gain points (penalties), but these are not taken into account anyway when a frame ball is determined.)
A frame can end in a tie (see Examples), and a tie is not a win for you.

Constraints

L will be between 1 and 50, inclusive.
C, N, yourScore and oppScore will each have exactly L elements.
Each element of C will be between 1 and 10^9, inclusive.
Each element of N will be between 1 and 10^9, inclusive.
Each element of yourScore will be between 0 and 10^18, inclusive.
Each element of oppScore will be between 0 and 10^18, inclusive.

Examples

```
{6}
```
```
{3}
```
```
{60}
```
```
{50}
```
```
Returns: {1 }
```
Initially there were C = 6 colored balls, worth 2 through 7 points. The N = 3 most expensive balls (blue worth 5 points, pink worth 6, and black worth 7) are still on the table. You are ahead by 10 points (you have 60, your opponent has 50). The blue ball is the frame ball. After potting it, you will be ahead by 15 points and even if you then make a mistake and let your opponent play, the best they can do is score 6+7 = 13 points.
```
{6}
```
```
{3}
```
```
{60}
```
```
{0}
```
```
Returns: {0 }
```
The same situation as before, but now you are very far ahead. The frame ball has already been played, you are guaranteed to win. Hence, the smallest X with the property from the statement is X = 0, which is what you should return.
```
{6}
```
```
{3}
```
```
{10}
```
```
{100}
```
```
Returns: {-1 }
```
This time your opponent is so far ahead that there is no chance to win this frame.
```
{6}
```
```
{3}
```
```
{58}
```
```
{50}
```
```
Returns: {2 }
```
Here the frame ball is the pink ball. After potting the blue the score would be 63:50, which still does not guarantee you a win - the opponent could still tie the game by potting the other two balls. You need to pot both the blue and the pink to be guaranteed a win.
```
{6, 6, 6, 6, 6}
```
```
{3, 3, 3, 3, 3}
```
```
{60, 60, 10, 58, 0}
```
```
{50, 0, 100, 50, 18}
```
```
Returns: {1, 0, -1, 2, -1 }
```
All four previous examples as a single test case. The last, fifth test case shows a situation in which the best you can do is equal your opponent's score - still not good enough for a win.
```
{6}
```
```
{21}
```
```
{0}
```
```
{0}
```
```
Returns: {19 }
```
This is the beginning of a regular game of snooker, with 21 - 6 = 15 reds and 6 colors on the table. Suppose you correctly pot 9 reds, each followed by a black. At this point you have 9 + 9*7 = 72 points. If you were to make a mistake now, the opponent would be given a table with 6 reds and all the colors, and they could score up to 75 points, which would still beat you. Thus, the first eighteen balls were not the frame ball yet. The next (tenth) red is the frame ball. You can have 73 points after potting this ball. Now assume you make a mistake when potting the next (colored) ball and you let your opponent play. They now have a table with just 5 reds and 6 colors. Remember that they are not continuing your turn but starting a new one, which means that they must now start by potting one of the reds. The best score your opponent can get from this situation is just 67 points, which does not beat your 73. Thus, ball #19 is the frame ball. If you pot the first 19 balls perfectly, you are guaranteed to win the frame.
```
{500000000, 500000000, 1}
```
```
{1000000000, 1000000000, 1}
```
```
{47, 1, 0}
```
```
{123456789123456789, 375000001750000000, 0}
```
```
Returns: {996913578, 1500000000, 1 }
```
The first two queries are about a huge game: 500 million reds and 500 million colors are still on the table. For the first query you are slightly more than 10^17 points behind at the moment, so you are going to need to play for a long time. The frame ball is ball number 996913578. In the first 996913578 balls the biggest score you can get is 249,228,395,496,913,578. And if your opponent comes to the table immediately afterwards, the best they can do from that situation is score another 125,771,606,253,086,422 points. This would put the final score of the frame at 249228395496913625 : 249228395376543211, meaning that you won by 120,370,414 points. The second query is even worse: your opponent's lead is so big that you need to clear the entire table in order to win. This requires potting 1,500,000,000 balls and gives you the win by a single point. The third query illustrates that different queries can have different values of C and N.

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.