Connection Status:
Competition Arena > LittleElephantAndBoard

LittleElephantAndBoard

SRM 597 · 2013-06-25 · by Witaliy

SRM 597 · 2013-06-25 · by Witaliy · Dynamic Programming, Math
Class Name: LittleElephantAndBoard
Return Type: int
Method Name: getNumber
Arg Types: (int, int, int, int)
Problem Statement

Problem Statement

Little Elephant from the Zoo of Lviv has a board with 2 rows and M columns. Each cell of the board must be painted in one of three colors: red, green, or blue.

The board is called magical if and only if it has the following properties:

  • No two adjacent cells share the same color. (Two cells are adjacent if they share an edge.)
  • Every 2x2 block contains at least one cell of each of the three colors.

You are given four ints M, R, G and B. Let X be the total number of different magical boards with 2 rows and M columns that contain exactly R red cells, G green cells, and B blue cells. Return the value (X modulo 1,000,000,007).

Constraints

  • M will be between 2 and 1,000,000, inclusive.
  • R, G and B will each be between 0 and 1,000,000, inclusive.
  • R+G+B will be equal to 2M.
Examples
0)
2
2
1
1
Returns: 4

The following 4 different magical boards are possible in this case:

1)
2
2
2
0
Returns: 0

No magical board is possible in this case.

2)
10
7
7
6
Returns: 496
3)
474
250
300
398
Returns: 969878317
4)
1000000
500000
1000000
500000
Returns: 4

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

Coding Area

Language: C++17 · define a public class LittleElephantAndBoard with a public method int getNumber(int M, int R, int G, int B) · 48 test cases · 2 s / 256 MB per case

Submitting as anonymous