Connection Status:
Competition Arena > ContestScoreboard

ContestScoreboard

SRM 679 · 2016-01-04 · by ltaravilse

SRM 679 · 2016-01-04 · by ltaravilse · String Manipulation, String Parsing
Class Name: ContestScoreboard
Return Type: int[]
Method Name: findWinner
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Some teams have competed in a programming contest. Each team has made one or more submissions. Each submission received some positive score. The total score of a team is the sum of the scores of all their submissions. The scoreboard is computed by sorting the teams according to their total scores. If multiple teams are tied, they are sorted lexicographically, with smaller names being higher in the scoreboard. The team on the top of the scoreboard is winning. (Only one team is winning at any moment, even if there are multiple teams tied for the winning total score.)
The scoreboard contains one line for each team. For each team, the line has the following format: "TeamName S1/T1 S2/T2 ... SN/TN". Here:
  • TeamName is the name of the team
  • N is the number of submissions they made
  • the values S1 through SN are the scores of those submissions
  • the values T1 through TN are times in minutes: submission Si was made after Ti minutes of the contest have elapsed

Different teams may have different numbers of submissions, worth a different number of points, and submitted at different times. The submissions are not necessarily ordered: neither by score, nor by submission time.
You are given a String[] scores: the scores of all teams, generated long after the contest was over. Each element of scores describes one team in the format shown above. The elements of scores are not necessarily ordered: neither by total score, nor by team name.
You would like to know who won the contest. However, this isn't necessarily the team that is currently winning. This is because it is possible that the scoreboard contains some submissions that happened after the end of the contest.
You know that the duration of the contest was an integer between 1 and 10^9, inclusive. Apart from that, you have no information about the exact duration. If the duration of the contest is D minutes, only the submissions that have Ti strictly smaller than D should be counted towards the correct total scores.
Given the content of scores, we say that a team could have won the contest if it was winning for some value of D from the above range. For each team, determine whether that team could have won the contest. Return a int[] with the same number of elements as scores. For each valid i, element i of the return value should be 1 if the team described by scores[i] could have won the contest, or 0 if it couldn't.

Constraints

  • scores will contain between 2 and 100 elements.
  • Each element of scores will have between 7 and 100 characters.
  • The name of each team will have between 3 and 8 characters.
  • All characters in each team name will be uppercase English letters ('A'-'Z').
  • Each team will have at least one submission.
  • The score for each submission will be between 1 and 999, inclusive.
  • The time of each submission will be between 1 and 10^9 - 1, inclusive.
  • All team names will be different.
  • Each element of scores will be formatted as shown in the statement, with a single space used as a separator.
Examples
0)
{"TVG 1/1 1/2 1/3", "AJI 1/4 1/5 1/6"}
Returns: {1, 1 }

If the duration of the contest were D = 1, there would be no valid submissions. Hence, the total score of each team would be zero and team "AJI" would be the winner due to having a lexicographically smaller name. If the duration were D = 2, the only team with a valid submission (and therefore the winner) would be team "TVG". Thus, in this setting each team can be the winner.

1)
{"GLP 1/114 1/195 1/171 1/19 1/146 1/29","BKPF 1/57 1/187 1/277 1/21 1/223 1/35"}
Returns: {1, 1 }
2)
{"AAA 248/2 495/5 993/7","BBB 244/6 493/7 990/10", "CCC 248/2 495/5 993/10"}
Returns: {1, 0, 0 }
3)
{"UBA 10/2 30/4 25/3 999/1000", "UNC 1/3 3/20 40/50", "UNLP 2/2 3/3 4/4 100/100", "UNR 999/1000000 999/999999", "UNS 999/100000000"}
Returns: {1, 0, 1, 1, 0 }
4)
{"LRBB 904/387 254/650 869/363","QCO 520/689 993/918","IICFSK 51/530 40/47 84/798 317/991 286/34 717/498","JJDDNTG 630/55 18/99 710/82 998/517 595/232 266/797 185/339","UTP 930/560 377/11 365/225 349/540 141/379","CVOG 208/342 233/353 564/512 330/518 437/84 420/113 16/507 469/668 287/490 399/155","KPHC 36/288 421/644 401/743","FBFJKNC 831/166 210/303 589/80 896/548 449/485","NFNB 848/169 629/814","UFNNX 515/498 838/539 290/140 625/471 73/393 843/543 607/534 696/744 488/551 380/486 419/721","FDUPL 754/961 810/800 790/230 363/629 792/800 184/590 615/877 962/767 951/985 381/760 249/777","OQJ 407/876 569/925","FAM 281/338 373/316 474/618 278/999 101/781 965/7 706/36","KIJK 606/669 468/147","QALWDT 976/565 64/53 442/369 165/433 526/431 12/467 808/305","GHR 484/900 73/764 530/20 783/513 611/255","HBCTCB 742/426 144/636 933/406 694/606","WLUD 553/163 67/455 819/520 58/770 472/185 583/250 342/502 280/448 997/784 294/513 493/608 946/697","VVU 476/442 234/398 975/414 18/487 394/102 237/903 185/746 208/324 814/457 360/126 268/9 710/123","UKFJJ 978/348 463/395","NCY 810/683 731/89 703/367 685/358","HFOOO 280/223 667/753 654/90 775/872 25/19","PWX 342/308 253/395 663/844 146/754 788/980 265/468 557/941 852/75","RCA 517/866","JCLJ 876/265 95/631 557/710 299/638 252/23 532/102 51/227","DVAZJ 78/539 945/399 112/216 503/513 631/682 740/323 715/27 936/418 883/822 697/701","QFLPQL 549/523 849/330 225/606 159/55 898/605 289/463","ZEYVKR 578/546 989/752 117/481 284/822","KBT 116/680 750/894 610/286 957/395 594/258","QCBT 896/76","JMUKYEX 403/990 425/587 516/924 360/227","SGMC 147/704 332/687 519/913 921/799 940/177 128/181 272/772 868/476","YVI 515/987 411/670 948/600 604/79 242/966 327/846 942/889 199/123 381/881 982/93 243/488 56/611","AYH 562/378 254/607","PGWK 849/889 211/508 199/306 297/445 252/473 335/501 599/377 991/996 975/128","SIUFKV 814/884 708/915 668/734 932/850 221/344 972/486 493/28","QYNJLCH 518/622 279/798 624/406 421/969 17/490 213/732 732/698 116/928","VDY 381/898 106/124 359/625 934/88 820/477 80/677 717/924 26/785","YHBI 764/817 450/932 356/26 222/792 300/51","NCKID 557/553 575/768 100/904 517/732","MSUD 818/813","ZATTFI 860/302 575/868 431/123 445/934 953/909 154/777 301/705 729/973 724/611 915/255","AIVYR 404/653","RHUVA 437/555 218/535 159/162 551/336 300/227 986/450 903/209 391/140 922/775 91/997 676/829 804/395","NMO 574/387 484/976","OIB 512/922 398/309 621/614","EBV 236/809 521/115","WSUCE 592/646 167/105","YLQHSEU 645/256 672/294 267/210 14/608 330/578 138/418 627/617 98/7","NCBIEDU 881/230 284/576 748/725 624/262 346/508","LXD 922/881 485/251 555/790 566/179","WYNWQ 964/664 669/339 360/230 475/164 577/116 492/856 699/961 594/663 809/42 24/683","GOTE 287/519 688/898 223/162 374/787 734/431 288/962 735/228 68/873 520/333 765/979 814/651","BACXK 472/944 700/726 653/432","ZHNZV 353/336 317/196 502/691 86/385 572/380 439/738 806/853 943/77 673/221 240/874 708/865","RCRER 475/666 530/100 440/237 341/660 427/570","HAJKOJ 655/92 964/589 940/572 768/863 963/902 515/131 896/696 603/268 571/451 504/800","CHPPIUY 460/107 524/450 836/968 596/680 525/305 562/855 709/214 445/213 986/114 678/677 947/604","AVIYL 481/970 969/211 593/986 852/256","IXULBJM 102/888 705/331 70/678 758/96 965/824 741/607 832/924 611/605 274/666 37/792","VECJ 849/851 892/948 451/718 716/132 951/107","ZFYYF 902/774 512/653 524/913 855/957 750/192 147/590 187/18 722/688 467/198","GNFHPNE 115/340 38/60 631/579 697/628 185/960 924/932 906/667 409/157","ASNWBX 199/812 585/844 826/305 685/127 844/116","RXM 552/37 942/520 584/690 198/761 701/473 975/902 699/134","ZOIF 309/338 730/275 545/541 223/810 46/872 771/863 766/320 630/575 509/664 604/809 967/457","TOGJMCA 242/60 760/40 745/503 740/984 196/948 600/875 93/368 589/223 799/100","OKDQLX 514/30 638/517 179/156 516/610 105/371 106/689","LCKFP 350/565 282/13 957/386 305/30 395/291 782/427 429/264 547/565","VIONST 576/949 226/392 215/392 177/583 87/626 650/861","VWNOUIL 184/339 322/648 453/280 132/752","PDWPV 775/949 377/383 232/375 544/852 862/111","AQVZB 625/680 177/218 296/688 153/157 595/585 12/172 317/181 7/612 438/622 275/640 497/488 993/208","FXDGO 160/596","QSFA 988/466 248/526 658/68 636/859","MQMFCJ 346/700 484/932 615/623 490/447 795/351 187/885","GYBI 908/134 627/456 487/216 590/730 177/605 127/481","TPUPXKZ 280/330 816/22 57/986 336/427 365/60 48/284 965/316 914/941","YBJCXF 936/350 46/758","EZENWKI 458/870 528/805 893/352 341/445 912/64 500/496 606/63","HTP 917/451 770/101 904/754 519/221 954/891 434/777 170/503 861/905","KXECQUO 22/808 712/94 884/222 782/430 515/733 580/112 586/477 856/584 489/355 9/563 101/237","YFHZC 863/660 627/984 975/660 890/244 55/717 136/922","APEZ 160/290 943/407 812/283 797/698"}
Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 }

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

Coding Area

Language: C++17 · define a public class ContestScoreboard with a public method vector<int> findWinner(vector<string> scores) · 44 test cases · 2 s / 256 MB per case

Submitting as anonymous