Connection Status:
Competition Arena > LittleElephantAndIntervalsDiv2

LittleElephantAndIntervalsDiv2

SRM 595 · 2013-06-25 · by Witaliy

SRM 595 · 2013-06-25 · by Witaliy · Brute Force
Class Name: LittleElephantAndIntervalsDiv2
Return Type: int
Method Name: getNumber
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

Problem Statement

Little Elephant from the Zoo of Lviv has some balls arranged in a row. Each ball can be painted in one of two possible colors: black or white. Initially all the balls are painted white.

You are given an int M, which represents the number of balls in the row. The balls are numbered from left to right, starting from 1. You are also given two int[]s L and R. To repaint balls, Little Elephant wants to use a robot. The robot will paint the balls in several consecutive stages. For each i, the i-th stage (1-based index) will look as follows: First, the robot will choose one of the two colors: white or black. Then, the robot will paint the balls with indices from L[i-1] to R[i-1], inclusive, using the chosen color. (Painting a ball covers all previous layers of paint.)

Return the number of different colorings Little Elephant can get after the last stage. (Two colorings are considered different if there exists some ball that is white in one coloring and black in the other one).

Constraints

  • M will be between 1 and 100, inclusive.
  • L will contain between 1 and 10 elements, inclusive.
  • R will contain the same number of elements as L.
  • Each element of R will be between 1 and M, inclusive.
  • i-th element of L will be between 1 and R[i], inclusive.
Examples
0)
4
{1, 2, 3}
{1, 2, 3}
Returns: 8

In the three stages the robot will choose the color for balls number 1, 2, and 3. The choices are independent of each other. The last, fourth ball will always remain white. Thus there are 2*2*2 = 8 different colorings.

1)
3
{1, 1, 2}
{3, 1, 3}
Returns: 4

In the first stage the robot colors all three balls. The color chosen for the first stage does not matter, because in the second stage the robot will repaint ball 1, and in the third stage it will repaint balls 2 and 3.

2)
100
{47}
{74}
Returns: 2
3)
100
{10, 20, 50}
{20, 50, 100}
Returns: 8
4)
1
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: 2

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

Coding Area

Language: C++17 · define a public class LittleElephantAndIntervalsDiv2 with a public method int getNumber(int M, vector<int> L, vector<int> R) · 62 test cases · 2 s / 256 MB per case

Submitting as anonymous