Connection Status:
Competition Arena > LittleElephantAndIntervalsDiv1

LittleElephantAndIntervalsDiv1

SRM 595 · 2013-06-25 · by Witaliy

SRM 595 · 2013-06-25 · by Witaliy · Brute Force
Class Name: LittleElephantAndIntervalsDiv1
Return Type: long
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 1,000, inclusive.
  • L will contain between 1 and 50 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
2)
1000
{47}
{747}
Returns: 2
3)
1000
{1, 50, 100}
{50, 100, 200}
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 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

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

Submitting as anonymous