Connection Status:
Competition Arena > CirclesGame

CirclesGame

SRM 561 · 2012-06-05 · by cgy4ever

SRM 561 · 2012-06-05 · by cgy4ever · Advanced Math, Geometry, Graph Theory
Class Name: CirclesGame
Return Type: String
Method Name: whoCanWin
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Alice is playing a game with her old friend, Bob.
There are n circles on a paper. The center of the i-th circle is (x[i], y[i]), and the radius is r[i]. No two different circles share a common point on their boundary. However, it is allowed for circles to be located entirely within other circles. In the game, the players take alternating turns. Alice starts. In each move, the current player must:
  1. Choose a circle such that there is no red point strictly inside the circle.
  2. Pick one point that is strictly inside the chosen circle and color it red.
If a player can't do such a move, he/she loses the game.
You are given the int[]s x, y, and r that describe a set of circles with the above property. Return "Alice" (quotes for clarity) if Alice has a winning strategy for the given set of circles. Otherwise, return "Bob".

Notes

  • Points located on the boundary of a circle are not considered to be strictly inside that circle.

Constraints

  • x will contain between 1 and 50 elements, inclusive.
  • x, y, and r will each contain the same number of elements.
  • Each element in x will be between -10,000 and 10,000, inclusive.
  • Each element in y will be between -10,000 and 10,000, inclusive.
  • Each element in r will be between 1 and 10,000, inclusive.
  • No two circles intersect. That is, the boundaries of the given circles are pairwise disjoint.
Examples
0)
{0}
{0}
{1}
Returns: "Alice"

This test case has just one circle. Alice draws a red point anywhere inside the circle and Bob has no valid move.

1)
{0, 3}
{0, 0}
{1, 1}
Returns: "Bob"

Two separate circles. Alice draws a red point in one of them, Bob draws a red point in another one, then Alice has no valid moves.

2)
{0, 0, 5}
{0, 0, 0}
{1, 2, 1}
Returns: "Alice"

In her first move, Alice should draw a point within the circle 1, but so that it's not within the circle 0. (Both indices are 0-based.)

3)
{0, 0, 0, 10, 10, 20}
{0, 0, 0, 0, 0, 0}
{1, 2, 3, 1, 2, 1}
Returns: "Bob"
4)
{10,20,30,40,50,60,70,80}
{8,7,6,5,4,3,2,1}
{2,2,2,2,2,2,2,2}
Returns: "Bob"

Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CirclesGame with a public method string whoCanWin(vector<int> x, vector<int> y, vector<int> r) · 86 test cases · 2 s / 256 MB per case

Submitting as anonymous