All Tracks Problem

Monkey and Ball Game
Tag(s):

Game Theory, Graph Theory, Hard, Probability

Problem
Editorial
Analytics

For given integers N let’s consider the following single player game played with a box, N black and N white balls. Initially the box is empty and in one move the player can:

  • throw any ball not currently in the box into it
  • take out any ball currently in the box
  • if the box is empty, in one move he can put all \(2 \cdot N\) balls inside
  • if the box contains \(2 \cdot N\) balls, he can take away all of them in one move

Moreover, there are additional \(2 \cdot Q_v\) different valid moves given by \(Q_v\) rules and each single rule is given by 4 integers:

\(b, w, \delta_b, \delta_w\)

and means that if there are exactly b black balls and exactly w white balls in the box, then in one move the player can add/remove balls in such a way that after the move there are \(b + \delta_b\) black and \(w + \delta_w\) white balls in the box. In addition, the reverse operation is also a valid move, which means that if there are exactly \(b + \delta_b\) black and exactly \(w + \delta_w\) white balls in the box, the player can in one move add/remove balls in such a way that after the move there are exactly b black and exactly w white balls in the box.

Moreover, there are \(2 \cdot Q_f\) different forbidden moves given by \(Q_f\) rules and each such rule is given by 3 values:

\(b_f, w_f, c\)

where \(0 \leq b_f, w_f < N\) and denotes that if there are exactly \(b_f\) black and exactly \(w_f\) white balls in the box, the player cannot add to the box a ball of color c. In addition, the reverse operation is also a forbidden move, which means that for example if c is \(WHITE\) then the player cannot add a white ball to the box if there are exactly \(b_f\) black and exactly \(w_f\) white balls already there, and moreover, he cannot remove a white ball from the box if there are exactly \(b_f\) black and exactly \(w_f\) white balls already there.

Now let’s consider any valid state of the box during the game with exactly b black and w white balls inside. The evaluation of then box is then defined as \(b \cdot w\).

Next let’s consider a monkey playing the game forever. Monkey knows all the rules and makes only allowed moves. However, she doesn’t know what’s the best move in any situation, so she choses any of possible moves uniformly at random and performs it.

The goal of this problem is to find the greatest sum of evaluations of two boxes \(X, Y\) that can be produced during the game played by monkey, such that monkey can move from X to Y in a single move and she can move from Y to X in a single move also, and the expected number of moves the monkey will make in order to transform the box X to box Y and then back to X is an integer divisible by the number of all possible different moves monkey can make during the game. Two moves are the same if and only if they transform the same current state to the same state using the same operation including the same number of balls of every color.

If there are no two such boxes, then the answer is 1.

Constraints:

  • \(1 \leq N \leq 300\)
  • \(0 \leq Q_v \leq 100\)
  • \(0 \leq Q_f \leq 1000\)
  • \(0 < |\delta_b|, |\delta_w| < N\)
  • \(0 \leq b + \delta_b, w + \delta_w \leq N\)
  • for any \(0 \leq w, b \leq N\) the box containing b black and w white balls can be produces by a sequence of valid moves
  • c is either \(BLACK\) or \(WHITE\)
  • \(0 \leq b_f, w_f < N\)
  • all additional moves are unique and all of them are different than standard valid moves given at the beginning of the statement
  • all forbidden moves are unique
  • for a forbidden move the number of black balls in the box before and after the move cannot be both N
  • for a forbidden move the number of white balls in the box before and after the move cannot be both 0

Subtask 1 (10 pts):

  • \(N \leq 10\)

Subtask 2 (30 pts):

  • \(N \leq 50\)

Subtask 3 (60 pts):

  • \(N \leq 300\)

Input format:

In the first line there are three space separated integers \(N, Q_v, Q_f\) denoting the number of balls of each colors, the number of rules describing additional valid moves and the number of rules describing forbidden moves. Then \(Q_v\) lines follow and in each of them there are 4 space separated integers \(b, w, \delta_b, \delta_w\) denoting a rule describing two additional valid moves. After that \(Q_f\) lines follow and in each of them there are 3 space separated values \(b_f, w_f, c\) denoting a rule describing two forbidden moves.

Output format:

In a single line output one integer denoting the greatest sum of evaluations of two boxes \(X, Y\) during the game played by monkey, such that monkey can move from X to Y in a single move and she can move from Y to X in a single move also, and the expected number of moves the monkey will make in order to transform the box X to box Y and then back to X is an integer divisible by the number of all possible different moves monkey can make during the game. If there are any such boxes, print 1 in a single line.

SAMPLE INPUT
1 0 1
0 0 WHITE
SAMPLE OUTPUT
1
Explanation

There are only 1 black and 1 white ball in the game and a total of 8 different possible valid moves. The only pair of boxes X, Y for which the wanted constraints is fulfilled is:

  • box X contains exactly 1 white ball and no black balls
  • box Y contains exactly 1 black and exactly 1 white ball

The answer is 1, because the evaluation of box X is \(1 \cdot 0 = 0\), the evaluation of box Y is \(1 \cdot 1 = 1\), and the sum of these evaluations is 1.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

May Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?