Connection Status:
Competition Arena > RedChart

RedChart

SRM 131 · 2003-01-30 · by pmadden

SRM 131 · 2003-01-30 · by pmadden
Class Name: RedChart
Return Type: int
Method Name: area
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Coder rankings rise and fall; not everyone who gets into the "red" stays there. For the TopCoder web site, we need to draw a chart that shows the time and duration of red ranking for each coder, but we want to minimize the size of the chart. Our chart will have horizontal bars to show the span (series of consecutive TopCoder events) where each coder has a red ranking.

For example, we might have the following coders who are "red" for a series of SRMs indicated. These spans are inclusive.

  • Coder "L" is red from SRM 97 to SRM 104, drops in ranking, and then is red again from SRM 110 to 119
  • Coder "Z" is red from SRM 107 to SRM 110
  • Coder "B" is red from SRM 100 to SRM 109

       11111111111111111111
    99900000000001111111111  SRM numbers (vertical)
    78901234567890123456789
    LLLLLLLL  ZZZZ         | Actual chart area; two lines, and SRM range
       BBBBBBBBBBLLLLLLLLLL| of 97 to 119 gives 23 columns.  Area = 2*23 = 46.

The length of the coder's handle does not impact how the graph is drawn. Single letter handles are used in this example for clarity; the desired answer would be the same no matter how long the handles were.

There are a few simple rules that govern where we can list a coder in the chart.

  • If a coder is red for a consecutive set of events, from SRM x to SRM y, they must occupy a single horizontal row in the chart from x to y.
  • A coder may have multiple spans in which they are red, but the spans do not need to occupy the same horizontal row ("L" above is an example of this). The spans for a coder must be separated by at least one SRM; thus, a span for coder "Z" from 107 to 110, and a second span from 111 to 115 will not be allowed by the constraints on the input.
  • No two coders can overlap in any position, but they may be adjacent (as is shown for "B" and "L" in the example).

To minimize area, we need to minimize the number of rows in the chart. Create a class RedChart that contains a method area that takes a String[] coders; each element of coders contains a coder handle and the start and end SRM numbers of a span for which the coder is "red." The method returns an int representing the total area of the chart.

Constraints

  • coders will contain between 0 and 50 elements inclusive.
  • Each element of coders will be at most 50 characters long.
  • Each element of coders will consist of the alphanumeric coder handle ('a'-'z', 'A'-'Z', and '0'-'9' are the only allowed characters), followed by a single space, the SRM number for the start of a span, another single space, and the SRM number for the end of a span.
  • Each coder handle will contain between 1 and 46 characters, inclusive.
  • The SRM numbers will not have leading zeros.
  • The SRM numbers will be integers between 1 and 1000000 (inclusive).
  • The start of an SRM span will be less than or equal to the end of an SRM span.
  • The spans for a coder must be separated by at least one SRM.
Examples
0)
{"L 110 119", "Z 107 110", "B 100 109", "L 97 104"}
Returns: 46

This is the illustrated example.

1)
{"A 1 10", "B 11 20", "C 21 30", "D 1 30"}
Returns: 60
2)
{"Abcdefg 1 3", "Abcdefg 5 6", "xyzzy 1 6"}
Returns: 12
3)
{"C0 289383 320269","C1 692777 729692","C2 747793 786128","C3 885386 945878","C4 516649 558070","C5 202362 292389","C6 368690 388749","C7 897763 911689","C8 180540 263966","C9 89172 144908","C10 5211 100579","C11 702567 758996","C12 465782 487312","C13 722862 787985","C14 174067 177202","C15 513929 593731","C16 634022 657080","C17 133069 231236","C18 961393 979849","C19 175011 253053","C20 176229 253602","C21 484421 529340","C22 413784 512321","C23 575198 669522","C24 798315 862685","C25 566413 569939","C26 776091 845071","C27 759956 801829","C28 806862 906032","C29 906996 1000000","C30 702305 723230","C31 477084 513411","C32 660336 686841","C33 750846 772575","C34 661313 687170","C35 616124 670019","C36 819582 820127","C37 898814 932181","C38 515434 605798","C39 344043 357793","C40 171087 197895","C41 117276 164454","C42 695788 789372","C43 705403 708054","C44 392754 405153","C45 999932 1000000","C46 549676 643044","C47 947739 957751","C48 636226 734812","C49 348094 445633"}
Returns: 5968740
4)
{"C0 140795 221365","C1 651434 711812","C2 97467 164068","C3 710097 722999","C4 573317 643809","C5 926652 987408","C6 997301 1000000","C7 724286 733727","C8 953865 983554","C9 228444 275063","C10 558440 603169","C11 958031 966148","C12 738097 743868","C13 834481 925156","C14 120709 219636","C15 704567 782423","C16 179497 251850","C17 254586 331551","C18 455306 519989","C19 406219 434843","C20 51528 84399","C21 805732 854561","C22 409503 439522","C23 258270 321638","C24 959708 1000000","C25 226340 244489","C26 747796 748519","C27 142618 144863","C28 122846 216297","C29 892921 936476","C30 192379 289867","C31 537764 625992","C32 469841 562191","C33 165193 206693","C34 757034 844798","C35 470124 495038","C36 936987 1000000","C37 373743 420234","C38 322227 370592","C39 709859 791795","C40 151432 203983","C41 316437 415665","C42 153275 228682","C43 901474 977595","C44 468858 563253","C45 36029 97266","C46 908235 982028","C47 65818 160246","C48 366143 397154","C49 335928 375457"}
Returns: 7711776

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

Coding Area

Language: C++17 · define a public class RedChart with a public method int area(vector<string> coders) · 29 test cases · 2 s / 256 MB per case

Submitting as anonymous