Connection Status:
Competition Arena > CMajor

CMajor

SRM 289 · 2006-02-14 · by brett1479

SRM 289 · 2006-02-14 · by brett1479 · Dynamic Programming, Search
Class Name: CMajor
Return Type: int
Method Name: getLongest
Arg Types: (vector<string>)
Problem Statement

Problem Statement

A musician has composed several melody fragments and wants you to make a program to create a complete melody by appending those fragments. A fragment is described as a sequence of key jumps on a piano keyboard. A piano keyboard looks like this:

For instance, to go from the leftmost C key to the F key, a jump of 5 keys is needed (note that the black keys are counted), and to go back requires a jump of -5 keys. A fragment does not specify a starting position. It could be "2 3 -1" meaning that after the initial key we should move two keys to the right, then three and finally one to the left.

But there is a problem: the musician has set the restriction that the resulting melody must not use (including the starting position) black keys. Then, the fragment shown above could be used either starting on a G key (and then A, C and B) or starting on a C key (and then D, F and E). Each fragment can be used only once in the melody and cannot be used partially.

You are given a String[] fragments, the melody fragments, and you must return the number of fragments in the longest melody that can be created by appending those fragments.

Notes

  • Assume that the piano keyboard is infinite.

Constraints

  • fragments will contain between 1 and 19 elements, inclusive.
  • Each element of fragments will contain between 1 and 50 characters, inclusive.
  • Each element of fragments will be a list of integers, each separated by a single space, with no additional leading or trailing spaces.
  • Each integer in fragments will be between -10000 and 10000, inclusive, with no leading zeros.
Examples
0)
{"2 2 1 2 2 2 1","2 1 2 2 2 1 2"}
Returns: 1

The first fragment can only be played starting from C and ending on the next C, and the second fragment can only be played starting from D and ending on the next D. Therefore, they cannot be appended.

1)
{"2","2","1","2","2","2","1","2","2","1","2","2","2","1","2","2","1","2","2"}
Returns: 19

All these fragments can be played in order starting from a C key.

2)
{"2 2 2 2","1 1","5 -4 12 -11","0 2 -2 5 -1 -4 2 -2 7 -2"}
Returns: 1

The only fragment that can be played, without using black keys, is the last one.

3)
{"2 0 2 0 -2 -2 -1 5 1 2 2 2 1"}
Returns: 1
4)
{"5748 -4385 -790 5294 3349","-3279 -1783 3768 -2459 6066 2556 -8138 -4982 1435",
 "2951","-2405 2104 3756","5578 -5040 -9497 -4868 7407 9305 -6701",
 "-3339 9514 -787 7209 7467 -4467", "7496 3011 9941 -8340 3012"}
Returns: 4
104)
{"2 2 2 2","1 1","5 -4 12 -11","0 2 -2 5 -1 -4 2 -2 7 -2"}
Returns: 1

The only fragment that can be played, without using black keys, is the last one.

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

Coding Area

Language: C++17 · define a public class CMajor with a public method int getLongest(vector<string> fragments) · 131 test cases · 2 s / 256 MB per case

Submitting as anonymous