Statistics

Problem Statement for "Dating"

Problem Statement

The dating ritual can be pretty complex. Here is how it works at a certain cocktail party. All the men and women stand around in a circle, making chitchat. Eventually someone gets up his or her nerve and chooses the most desirable remaining person of the opposite sex and those 2 go off and discuss world affairs privately. This continues until either everyone has left, or only one gender remains and they all go home.

The original circle is described by a String circle containing lowercase letters for women and uppercase letters for men. The last one in circle is actually adjacent to the first one. Starting with the first person in circle, we count from 1 to k around the circle, letting the k-th person be the first chooser. Letters nearer the beginning of the alphabet represent hotter individuals, and the chooser always chooses the hottest remaining member of the opposite sex. Starting with the next remaining person after the last chooser we again count from one to k (counting only people who still remain in the circle) to determine the next chooser. This continues until the party breaks up.

Create a class Dating that contains a method dates that is given circle and k and returns a String showing all the dates. The return should list each date as a 2 letter sequence, with the chooser before the chosen. The dates should appear in the order in which they were made, and with a single space between adjacent dates. There must be no leading or trailing spaces in the return.

Definition

Class:
Dating
Method:
dates
Parameters:
String, int
Returns:
String
Method signature:
String dates(String circle, int k)
(be sure your method is public)

Constraints

  • circle will contain between 1 and 50 characters, inclusive, all letters 'A'-'Z' or 'a'-'z'.
  • The characters in circle will be distinct.
  • k will be between 1 and 100, inclusive.

Examples

  1. "abXCd"

    2

    Returns: "bC dX"

    Starting at the beginning we count 'a' as 1 and 'b' as 2 so 'b' chooses 'C' since 'C' is a lot hotter than 'X'. Then we count 'X' as 1 and 'd' as 2 (since 'C' is off discussing world affairs with 'b') so 'd' chooses 'X'. At this point only 'a' is left so the party breaks up.

  2. "abXCd"

    8

    Returns: "Xa dC"

    We count all the way around the circle and arrive at 'X' as the first to choose. The next chooser is 'd' since we count all the way around the circle more than twice (since there are only 3 people left at this point).

  3. "ABC"

    2

    Returns: ""

  4. "HGFhgfz"

    1

    Returns: "Hf Gg Fh"

  5. "DiuwSFab"

    98

    Returns: "iD wF aS"

  6. "ABCDEFGHIJKLMNOPQRSTUVWXYabcdefghijklmnopqrstuvwxy"

    100

    Returns: "yA Ea Mb Yc sB Sd xC nD kF pG Ke jH Xf lI Og Nh oJ uL wP Ui Tm rQ Vq Rt vW"

    Let's assume that the original circle is described with a String containing lowercase letters for women and uppercase letters for men. The last one in the String is actually adjacent to the first one thus forming the circle. The k-th person counting around the circle makes the first choice. Letters nearer the beginning of the alphabet represent hotter individuals, and the chooser always chooses the hottest remaining member of the opposite sex. The next choice is made by the k-th person with the count continuing from the last chooser's position, only counting those who are still in the circle. This continues until the party breaks up.

  7. "DiuwSFablmnoLMNOA"

    53

    Returns: "iA mD nF aL wM oN Sb Ol"

  8. "abcdefghijklmnopqrstuvwxyABCDEFGHIJKLMNOPQRSTUVWXY"

    1

    Returns: "aA bB cC dD eE fF gG hH iI jJ kK lL mM nN oO pP qQ rR sS tT uU vV wW xX yY"

  9. "ZzYyXxWwvVUuTtSsQqBbMmr"

    12

    Returns: "uB zM Sb wQ yT Zm Yq Wr sU xV Xt"

  10. "ABCDEFGHIJkLMNOPQRSTUVWXYZ"

    26

    Returns: "Zk"

  11. "ABCDEFGHIJkLMNOPQRSTUVWXYZ"

    25

    Returns: "Yk"

  12. "ABCDEFGHIJkLMNOPQRSTUVWXYZ"

    37

    Returns: "kA"

  13. "GHKJghkjYOIUerytX"

    2

    Returns: "He Jg kG Yh Ij rK tO Uy"

  14. "XmOxgzjAMqlfevnNpkKoywrZTbiVh"

    25

    Returns: "Tb wA yK Ze Xf jM oN qO gV"

  15. "kCGIfnpMtrmgONcUwPxWhLsEiVXFdZQJHRYTqeKvA"

    80

    Returns: "Kc Ad nC wE He Uf pF Gg mI Xh Wi Zk Nq Vr Js Tt Rv Ox"

  16. "mOVoEfHenNMPRrZtkXsDpduagljhGYUv"

    85

    Returns: "pD rE Za gG eH Od Nf Uh nM Pj Rk lV tX sY"

  17. "EubxqfgocnyzUSpIeWliQCjdhrk"

    74

    Returns: "iC Wb hE yI oQ pS zU"

  18. "yNaxcSMYnfpuqVdezvZkogQmHLb"

    2

    Returns: "Na cH Mb nL pQ qS dV zY Ze"

  19. "cqPEKxhTHakiYjAougbrtCFlnNezwypV"

    47

    Returns: "Aa Vb Cc jE iF uH eK Yg Th lN rP"

  20. "joFHLzriJxNYPSfyOKspMtuqlQBIhmwdacEVkXg"

    13

    Returns: "Pa Qc oB yE wF xH lI Jd hK Sf jL mM tN pO qV zX kY"

  21. "VgXLMjnFywHlqRYDUdzvhOsbcNSoiBEfmkexAa"

    23

    Returns: "sA yB kD Oa qE jF gH xL Vb nM Uc oN Yd lR hS zX"

  22. "OAyNpDdZKLtIzxlfbBShEMJiQTjoVFGnPgRWuXsa"

    1

    Returns: "Oa Ab yB Nd pD Zf Kg Lh tE Ii zF xG lJ Sj Mn Qo Ts Vu"

  23. "mgUJxeXnwdPRHcsaquWCDvjSfIhN"

    12

    Returns: "Ra fC wD Ic Pd gH jJ uN qS vU eW xX"

  24. "njxiyktugvhecoqzabmfl"

    82

    Returns: ""

  25. "ljcfhznIMgTJvOuwtSXdksomFaRUE"

    41

    Returns: "Ja Rc wE Md nF Tf kI Og tS hU sX"

  26. "yimsqwjegopvzfdNnUxt"

    78

    Returns: "Ud sN"

  27. "RlQOfAFBkXPYKiEqUWDdVCzaHMrJIgNZSGLT"

    90

    Returns: "Wa fA Gd Sg Oi Vk Pl Kq Ir Jz"

  28. "FbmQiPCMENHOfUqXnKYJRZgvWALseGTDo"

    27

    Returns: "Lb Ze Yf Kg Ri sA mC Un Fo Wq Gv"

  29. "SkIYJNHKMbjAwGzCgcPdZQVnyX"

    79

    Returns: "Sb Kc Vd Zg Yj kA Cn Nw Iy Qz"

  30. "iDsnfvtburTgwYeOkdyBlxj"

    37

    Returns: "Yb tB fD rO yT"

  31. "hxfdzaep"

    20

    Returns: ""

  32. "rSEzTtVLIDfmkwihbuseUqMxYcGvFn"

    75

    Returns: "iD zE Fb Sc wG Ve fI vL mM uT Yh tU"

  33. "reSZpdlcYqfFxnkamLCIKObwgoWit"

    15

    Returns: "kC eF Ia lK iL bO xS fW mY tZ"

  34. "CXwhJzWkLabxvBfDIROyHjcNUSPlE"

    48

    Returns: "Oa xB kC bD Hc hE Pf wI Nj Xl Wv Jy Rz"

  35. "EsDxCvRWSVNIgwHoXTMFZOQ"

    32

    Returns: "Sg Zo Is Wv Nw Ox"

  36. "xlbyjaimMzpvshnugqWNYdrt"

    84

    Returns: "vM aN pW lY"

  37. "mPYNBiTbtXoIxLsApejuEKcSCzkGVRgFwyrdQZUMa"

    13

    Returns: "xA kB Ma sC gE iF cG Pb Kd Ne Rj Im Yo Qp rL Ut Su Tw Vy Zz"

  38. "nOzefQswgBvTI"

    99

    Returns: "wB sI Qe gO zT"

  39. "HGFhgfz"

    1

    Returns: "Hf Gg Fh"

  40. "ABCDEfghiJKLmnopQrstuVWXYzabcd"

    5

    Returns: "Ea Jb oA tB Yc fC Ld rD Xg mK uQ iV zW"

  41. "a"

    1

    Returns: ""

  42. "ABCDE"

    21

    Returns: ""

  43. "abXCd"

    8

    Returns: "Xa dC"

  44. "HxyGFaZMnPo"

    7

    Returns: "Za yF xG nH Po"

  45. "ABCDEFGd"

    2

    Returns: "Bd"

  46. "aA"

    1

    Returns: "aA"

  47. "asdGHJoiuLK"

    7

    Returns: "oG dH sJ uK La"

  48. "PnFeCDabhKLMotzwx"

    4

    Returns: "eC hD oF xK bL wM tP"

  49. "abcdefghijklmnopqrstuvwxyz"

    100

    Returns: ""

  50. "ab"

    1

    Returns: ""

  51. "ABCDEFGabcdefgHIJKhijkLMNOPQRSYTzyxWv"

    99

    Returns: "Na Kb Jc Md vA Pe Lf zB kC Sg jD Eh Ri Qx Oy"

  52. "abcDEF"

    6

    Returns: "Fa cD bE"

  53. "AZ"

    1

    Returns: ""

  54. "kAbBaEdDeFfgGhHiIjJK"

    99

    Returns: "Ja eA gB Gb iD hE jF dH Kf kI"

  55. "AB"

    2

    Returns: ""

  56. "ABCD"

    2

    Returns: ""

  57. "aB"

    1

    Returns: "aB"

  58. "aqwertyuiopPOIUYTREQAmnblkMNBLKJ"

    6

    Returns: "tA Pa Rb kB qE iI Te Nl yJ Ym wK Un oL uM Op rQ"

  59. "ABD"

    2

    Returns: ""

  60. "ABCDEFG"

    5

    Returns: ""

  61. "dguftweEWhHr"

    1

    Returns: "dE gH uW"

  62. "abAB"

    1

    Returns: "aA bB"

  63. "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    100

    Returns: ""

  64. "abXCd"

    100

    Returns: "dC aX"

  65. "abcdefghijklmnOPQRSTWXVzytpqCBA"

    99

    Returns: "fA Ra hB eC nO dP kQ cS Vb jT iW gX"

  66. "npIgGDLxAtasOouEqPfwMCbFrNjivHQkKmcBlhedJ"

    60

    Returns: "fA dB Fa sC Ib Jc pD Oe jE xG hH Lg Ni rK oM vP tQ"

  67. "ABCDEFGHIJKLMNOPQRSTUVWXYyxwvutsrqponmlkjihgfedcba"

    1

    Returns: "Aa Bb Cc Dd Ee Ff Gg Hh Ii Jj Kk Ll Mm Nn Oo Pp Qq Rr Ss Tt Uu Vv Ww Xx Yy"

  68. "a"

    11

    Returns: ""

  69. "Aa"

    1

    Returns: "Aa"

  70. "abcdefghijkABCDEF"

    3

    Returns: "cA fB iC Da bE gF"

  71. "abcdefg"

    2

    Returns: ""

  72. "ab"

    2

    Returns: ""

  73. "YZyz"

    1

    Returns: "Yy Zz"

  74. "zFJxSchKLgfdEYmRretyuioQWTUqwPADnIHasGZXMvblOkjNCB"

    94

    Returns: "lA Ma bB zC fD Wc Fd qE eG mH yI sJ rK gL oN Sh uO Yi Xj Pk xQ nR Tt wU vZ"

  75. "AB"

    3

    Returns: ""

  76. "ABC"

    34

    Returns: ""

  77. "abXCd"

    5

    Returns: "dC bX"

  78. "aAbBcC"

    3

    Returns: "bA Ca Bc"

  79. "abXCd"

    2

    Returns: "bC dX"

  80. "abcdA"

    1

    Returns: "aA"

  81. "abcdefghijXZ"

    12

    Returns: "Za cX"

  82. "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuU"

    1

    Returns: "aA bB cC dD eE fF gG hH iI jJ kK lL mM nN oO pP qQ rR sS tT uU"

  83. "PnFrgqjSeRCDabhKLMotzwx"

    5

    Returns: "gC Ra Lb wD rF hK xM Se nP"

  84. "abcd"

    2

    Returns: ""

  85. "ABCDEFG"

    100

    Returns: ""

  86. "abcdefG"

    98

    Returns: "Ga"

  87. "abc"

    2

    Returns: ""

  88. "HGFhgfzIopPMTL"

    10

    Returns: "pF zG fH oI Lg Ph"

  89. "aAbdefSDIF"

    1

    Returns: "aA bD dF eI fS"

  90. "aBcDeF"

    4

    Returns: "Da cB Fe"

  91. "abcd"

    1

    Returns: ""

  92. "HGFhgfzabcdywe"

    34

    Returns: "fF Ga bH"

  93. "bAaBcCdD"

    3

    Returns: "aA Cb Bc dD"

  94. "RZpz"

    99

    Returns: "pR zZ"

  95. "ABCDEFGabcdrtyuhgfjklvMPZ"

    99

    Returns: "Pa Fb Mc Cd vA uB Df Zg lE Gh"

  96. "ABCDEFGHIJKLMNOPQRSTUVWXYabcdefghijklmnopqrstuvwxy"

    100

    Returns: "yA Ea Mb Yc sB Sd xC nD kF pG Ke jH Xf lI Og Nh oJ uL wP Ui Tm rQ Vq Rt vW"

  97. "alksdjfhOWAEIFJqwerVNM"

    7

    Returns: "fA Ja Md We Vh Ej lF rI Nk qO"

  98. "CfPaTQVRSbUedW"

    99

    Returns: "Ca Tb fP Rd eQ"

  99. "abc"

    1

    Returns: ""

  100. "HGFhgfzk"

    1

    Returns: "Hf Gg Fh"

  101. "abcdEABCDef"

    10

    Returns: "eA fB cC bD dE"

  102. "abcdefgh"

    100

    Returns: ""

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: