1
$\begingroup$

There are two strings A and B. Initially, some strings A’ and B’ are written on the sheet of paper. A’ is always a substring of A and B’ is always a substring of B. A move consists of appending a letter to exactly one of these strings: either to A’ or to B’. After the move the constraint of A’ being a substring of A and B’ is a substring of B should still be satisfied. Players take their moves alternately. We call a pair (A’, B’) a position.

Two players are playing this game optimally. That means that if a player has a move that leads to his/her victory, he/she will definitely use this move. If a player is unable to make a move, he loses.

Alice and Bob are playing this game. Alice makes the first move. As always, she wants to win and this time she does a clever trick. She wants the starting position to be the Kth lexicographically winning position for the first player (i.e. her). Consider two positions (A’1, B’1) and (A’2, B’2). We consider the first position lexicographically smaller than the second if A1 is lexicographically smaller than A2, or if A1 is equal to A2 and B1 is lexicographically smaller than B2.

What will be such a position, knowing the strings A, B and the integer K.

Note : Some of these strings can be empty. If there’s no such pair, we need to tell that their is “no solution” .

EXAMPLE : Length of A=2 , Length of B=2 and say K=5 .The strings be

ab
cd

Here answer will be :

a
cd
$\endgroup$
  • $\begingroup$ I don't see the point of this game. As you can always append a letter to a (proper) substring to get another substring, and you append 1 letter each move, the winning player only depends of the number (odd or even) of letters to append. Or does append means "at the end" only ? $\endgroup$ – Xoff Feb 24 '14 at 10:31
  • $\begingroup$ @Xoff append means at end only $\endgroup$ – user3001932 Feb 24 '14 at 10:39
  • $\begingroup$ This sounds like the game Nim with two heaps, think of the stones lying in a row "covering" the letters of $A$ and $B$, and appending a substring would correspond to removing the stones covering said substring. $\endgroup$ – Arthur Feb 24 '14 at 10:42
  • $\begingroup$ @Arthur, except you can do nasty things with some words like "coconuts". I like this game :) $\endgroup$ – Xoff Feb 24 '14 at 10:43
  • 1
    $\begingroup$ @Arthur Nim values will growth with repetition, as you can have some choice of your move. This makes winning positions more complex to compute. Coconuts is not really useful, as the choice does not change anything, but Barbarian is more fun. And the empty substring from Barbarian has nim value $*3$. $\endgroup$ – Xoff Feb 24 '14 at 10:54
0
$\begingroup$

Your game is fun, and it's a nim game, so you can compute the nim value of each substring using the mex. But to compute the $k$th winning position in lexicographic order is no more simple than computing all winning positions and sorting them in lexicographic order. So you can do a small program that does all the needed computations.

For example for the words "barbarian" and "baggage" you will obtain :

   1 : ""          ""      
   2 : ""          "a"     
   3 : ""          "ag"    
   4 : ""          "age"   
   5 : ""          "agg"   
   6 : ""          "agga"  
   7 : ""          "aggag" 
   8 : ""          "aggage"
   9 : ""          "b"     
  10 : ""          "ba"    
  11 : ""          "bag"   
  12 : ""          "bagg"  
  13 : ""          "bagga" 
  14 : ""          "baggag"
  15 : ""          "baggage"
  16 : ""          "e"     
  17 : ""          "g"     
  18 : ""          "ga"    
  19 : ""          "gag"   
  20 : ""          "gage"  
  21 : ""          "ge"    
  22 : ""          "gg"    
  23 : ""          "gga"   
  24 : ""          "ggag"  
  25 : ""          "ggage" 
  26 : "a"         "a"     
  27 : "a"         "ag"    
  28 : "a"         "age"   
  29 : "a"         "agga"  
  30 : "a"         "aggage"
  31 : "a"         "b"     
  32 : "a"         "bag"   
  33 : "a"         "bagga" 
  34 : "a"         "baggage"
  35 : "a"         "e"     
  36 : "a"         "g"     
  37 : "a"         "ga"    
  38 : "a"         "gage"  
  39 : "a"         "ge"    
  40 : "a"         "gga"   
  41 : "a"         "ggage" 
  42 : "an"        ""      
  43 : "an"        "ag"    
  44 : "an"        "agg"   
  45 : "an"        "aggag" 
  46 : "an"        "ba"    
  47 : "an"        "bagg"  
  48 : "an"        "baggag"
  49 : "an"        "g"     
  50 : "an"        "gag"   
  51 : "an"        "gg"    
  52 : "an"        "ggag"  
  53 : "ar"        ""      
  54 : "ar"        "a"     
  55 : "ar"        "age"   
  56 : "ar"        "agg"   
  57 : "ar"        "agga"  
  58 : "ar"        "aggag" 
  59 : "ar"        "aggage"
  60 : "ar"        "b"     
  61 : "ar"        "ba"    
  62 : "ar"        "bag"   
  63 : "ar"        "bagg"  
  64 : "ar"        "bagga" 
  65 : "ar"        "baggag"
  66 : "ar"        "baggage"
  67 : "ar"        "e"     
  68 : "ar"        "ga"    
  69 : "ar"        "gag"   
  70 : "ar"        "gage"  
  71 : "ar"        "ge"    
  72 : "ar"        "gg"    
  73 : "ar"        "gga"   
  74 : "ar"        "ggag"  
  75 : "ar"        "ggage" 
  76 : "arb"       "a"     
  77 : "arb"       "ag"    
  78 : "arb"       "age"   
  79 : "arb"       "agga"  
  80 : "arb"       "aggage"
  81 : "arb"       "b"     
  82 : "arb"       "bag"   
  83 : "arb"       "bagga" 
  84 : "arb"       "baggage"
  85 : "arb"       "e"     
  86 : "arb"       "g"     
  87 : "arb"       "ga"    
  88 : "arb"       "gage"  
  89 : "arb"       "ge"    
  90 : "arb"       "gga"   
  91 : "arb"       "ggage" 
  92 : "arba"      ""      
  93 : "arba"      "ag"    
  94 : "arba"      "agg"   
  95 : "arba"      "aggag" 
  96 : "arba"      "ba"    
  97 : "arba"      "bagg"  
  98 : "arba"      "baggag"
  99 : "arba"      "g"     
 100 : "arba"      "gag"   
 101 : "arba"      "gg"    
 102 : "arba"      "ggag"  
 103 : "arbar"     "a"     
 104 : "arbar"     "ag"    
 105 : "arbar"     "age"   
 106 : "arbar"     "agga"  
 107 : "arbar"     "aggage"
 108 : "arbar"     "b"     
 109 : "arbar"     "bag"   
 110 : "arbar"     "bagga" 
 111 : "arbar"     "baggage"
 112 : "arbar"     "e"     
 113 : "arbar"     "g"     
 114 : "arbar"     "ga"    
 115 : "arbar"     "gage"  
 116 : "arbar"     "ge"    
 117 : "arbar"     "gga"   
 118 : "arbar"     "ggage" 
 119 : "arbari"    ""      
 120 : "arbari"    "ag"    
 121 : "arbari"    "agg"   
 122 : "arbari"    "aggag" 
 123 : "arbari"    "ba"    
 124 : "arbari"    "bagg"  
 125 : "arbari"    "baggag"
 126 : "arbari"    "g"     
 127 : "arbari"    "gag"   
 128 : "arbari"    "gg"    
 129 : "arbari"    "ggag"  
 130 : "arbaria"   "a"     
 131 : "arbaria"   "ag"    
 132 : "arbaria"   "age"   
 133 : "arbaria"   "agga"  
 134 : "arbaria"   "aggage"
 135 : "arbaria"   "b"     
 136 : "arbaria"   "bag"   
 137 : "arbaria"   "bagga" 
 138 : "arbaria"   "baggage"
 139 : "arbaria"   "e"     
 140 : "arbaria"   "g"     
 141 : "arbaria"   "ga"    
 142 : "arbaria"   "gage"  
 143 : "arbaria"   "ge"    
 144 : "arbaria"   "gga"   
 145 : "arbaria"   "ggage" 
 146 : "arbarian"  ""      
 147 : "arbarian"  "ag"    
 148 : "arbarian"  "agg"   
 149 : "arbarian"  "aggag" 
 150 : "arbarian"  "ba"    
 151 : "arbarian"  "bagg"  
 152 : "arbarian"  "baggag"
 153 : "arbarian"  "g"     
 154 : "arbarian"  "gag"   
 155 : "arbarian"  "gg"    
 156 : "arbarian"  "ggag"  
 157 : "ari"       ""      
 158 : "ari"       "ag"    
 159 : "ari"       "agg"   
 160 : "ari"       "aggag" 
 161 : "ari"       "ba"    
 162 : "ari"       "bagg"  
 163 : "ari"       "baggag"
 164 : "ari"       "g"     
 165 : "ari"       "gag"   
 166 : "ari"       "gg"    
 167 : "ari"       "ggag"  
 168 : "aria"      "a"     
 169 : "aria"      "ag"    
 170 : "aria"      "age"   
 171 : "aria"      "agga"  
 172 : "aria"      "aggage"
 173 : "aria"      "b"     
 174 : "aria"      "bag"   
 175 : "aria"      "bagga" 
 176 : "aria"      "baggage"
 177 : "aria"      "e"     
 178 : "aria"      "g"     
 179 : "aria"      "ga"    
 180 : "aria"      "gage"  
 181 : "aria"      "ge"    
 182 : "aria"      "gga"   
 183 : "aria"      "ggage" 
 184 : "arian"     ""      
 185 : "arian"     "ag"    
 186 : "arian"     "agg"   
 187 : "arian"     "aggag" 
 188 : "arian"     "ba"    
 189 : "arian"     "bagg"  
 190 : "arian"     "baggag"
 191 : "arian"     "g"     
 192 : "arian"     "gag"   
 193 : "arian"     "gg"    
 194 : "arian"     "ggag"  
 195 : "b"         "a"     
 196 : "b"         "ag"    
 197 : "b"         "age"   
 198 : "b"         "agga"  
 199 : "b"         "aggage"
 200 : "b"         "b"     
 201 : "b"         "bag"   
 202 : "b"         "bagga" 
 203 : "b"         "baggage"
 204 : "b"         "e"     
 205 : "b"         "g"     
 206 : "b"         "ga"    
 207 : "b"         "gage"  
 208 : "b"         "ge"    
 209 : "b"         "gga"   
 210 : "b"         "ggage" 
 211 : "ba"        ""      
 212 : "ba"        "ag"    
 213 : "ba"        "agg"   
 214 : "ba"        "aggag" 
 215 : "ba"        "ba"    
 216 : "ba"        "bagg"  
 217 : "ba"        "baggag"
 218 : "ba"        "g"     
 219 : "ba"        "gag"   
 220 : "ba"        "gg"    
 221 : "ba"        "ggag"  
 222 : "bar"       ""      
 223 : "bar"       "a"     
 224 : "bar"       "age"   
 225 : "bar"       "agg"   
 226 : "bar"       "agga"  
 227 : "bar"       "aggag" 
 228 : "bar"       "aggage"
 229 : "bar"       "b"     
 230 : "bar"       "ba"    
 231 : "bar"       "bag"   
 232 : "bar"       "bagg"  
 233 : "bar"       "bagga" 
 234 : "bar"       "baggag"
 235 : "bar"       "baggage"
 236 : "bar"       "e"     
 237 : "bar"       "ga"    
 238 : "bar"       "gag"   
 239 : "bar"       "gage"  
 240 : "bar"       "ge"    
 241 : "bar"       "gg"    
 242 : "bar"       "gga"   
 243 : "bar"       "ggag"  
 244 : "bar"       "ggage" 
 245 : "barb"      "a"     
 246 : "barb"      "ag"    
 247 : "barb"      "age"   
 248 : "barb"      "agga"  
 249 : "barb"      "aggage"
 250 : "barb"      "b"     
 251 : "barb"      "bag"   
 252 : "barb"      "bagga" 
 253 : "barb"      "baggage"
 254 : "barb"      "e"     
 255 : "barb"      "g"     
 256 : "barb"      "ga"    
 257 : "barb"      "gage"  
 258 : "barb"      "ge"    
 259 : "barb"      "gga"   
 260 : "barb"      "ggage" 
 261 : "barba"     ""      
 262 : "barba"     "ag"    
 263 : "barba"     "agg"   
 264 : "barba"     "aggag" 
 265 : "barba"     "ba"    
 266 : "barba"     "bagg"  
 267 : "barba"     "baggag"
 268 : "barba"     "g"     
 269 : "barba"     "gag"   
 270 : "barba"     "gg"    
 271 : "barba"     "ggag"  
 272 : "barbar"    "a"     
 273 : "barbar"    "ag"    
 274 : "barbar"    "age"   
 275 : "barbar"    "agga"  
 276 : "barbar"    "aggage"
 277 : "barbar"    "b"     
 278 : "barbar"    "bag"   
 279 : "barbar"    "bagga" 
 280 : "barbar"    "baggage"
 281 : "barbar"    "e"     
 282 : "barbar"    "g"     
 283 : "barbar"    "ga"    
 284 : "barbar"    "gage"  
 285 : "barbar"    "ge"    
 286 : "barbar"    "gga"   
 287 : "barbar"    "ggage" 
 288 : "barbari"   ""      
 289 : "barbari"   "ag"    
 290 : "barbari"   "agg"   
 291 : "barbari"   "aggag" 
 292 : "barbari"   "ba"    
 293 : "barbari"   "bagg"  
 294 : "barbari"   "baggag"
 295 : "barbari"   "g"     
 296 : "barbari"   "gag"   
 297 : "barbari"   "gg"    
 298 : "barbari"   "ggag"  
 299 : "barbaria"  "a"     
 300 : "barbaria"  "ag"    
 301 : "barbaria"  "age"   
 302 : "barbaria"  "agga"  
 303 : "barbaria"  "aggage"
 304 : "barbaria"  "b"     
 305 : "barbaria"  "bag"   
 306 : "barbaria"  "bagga" 
 307 : "barbaria"  "baggage"
 308 : "barbaria"  "e"     
 309 : "barbaria"  "g"     
 310 : "barbaria"  "ga"    
 311 : "barbaria"  "gage"  
 312 : "barbaria"  "ge"    
 313 : "barbaria"  "gga"   
 314 : "barbaria"  "ggage" 
 315 : "barbarian" ""      
 316 : "barbarian" "ag"    
 317 : "barbarian" "agg"   
 318 : "barbarian" "aggag" 
 319 : "barbarian" "ba"    
 320 : "barbarian" "bagg"  
 321 : "barbarian" "baggag"
 322 : "barbarian" "g"     
 323 : "barbarian" "gag"   
 324 : "barbarian" "gg"    
 325 : "barbarian" "ggag"  
 326 : "bari"      ""      
 327 : "bari"      "ag"    
 328 : "bari"      "agg"   
 329 : "bari"      "aggag" 
 330 : "bari"      "ba"    
 331 : "bari"      "bagg"  
 332 : "bari"      "baggag"
 333 : "bari"      "g"     
 334 : "bari"      "gag"   
 335 : "bari"      "gg"    
 336 : "bari"      "ggag"  
 337 : "baria"     "a"     
 338 : "baria"     "ag"    
 339 : "baria"     "age"   
 340 : "baria"     "agga"  
 341 : "baria"     "aggage"
 342 : "baria"     "b"     
 343 : "baria"     "bag"   
 344 : "baria"     "bagga" 
 345 : "baria"     "baggage"
 346 : "baria"     "e"     
 347 : "baria"     "g"     
 348 : "baria"     "ga"    
 349 : "baria"     "gage"  
 350 : "baria"     "ge"    
 351 : "baria"     "gga"   
 352 : "baria"     "ggage" 
 353 : "barian"    ""      
 354 : "barian"    "ag"    
 355 : "barian"    "agg"   
 356 : "barian"    "aggag" 
 357 : "barian"    "ba"    
 358 : "barian"    "bagg"  
 359 : "barian"    "baggag"
 360 : "barian"    "g"     
 361 : "barian"    "gag"   
 362 : "barian"    "gg"    
 363 : "barian"    "ggag"  
 364 : "i"         ""      
 365 : "i"         "ag"    
 366 : "i"         "agg"   
 367 : "i"         "aggag" 
 368 : "i"         "ba"    
 369 : "i"         "bagg"  
 370 : "i"         "baggag"
 371 : "i"         "g"     
 372 : "i"         "gag"   
 373 : "i"         "gg"    
 374 : "i"         "ggag"  
 375 : "ia"        "a"     
 376 : "ia"        "ag"    
 377 : "ia"        "age"   
 378 : "ia"        "agga"  
 379 : "ia"        "aggage"
 380 : "ia"        "b"     
 381 : "ia"        "bag"   
 382 : "ia"        "bagga" 
 383 : "ia"        "baggage"
 384 : "ia"        "e"     
 385 : "ia"        "g"     
 386 : "ia"        "ga"    
 387 : "ia"        "gage"  
 388 : "ia"        "ge"    
 389 : "ia"        "gga"   
 390 : "ia"        "ggage" 
 391 : "ian"       ""      
 392 : "ian"       "ag"    
 393 : "ian"       "agg"   
 394 : "ian"       "aggag" 
 395 : "ian"       "ba"    
 396 : "ian"       "bagg"  
 397 : "ian"       "baggag"
 398 : "ian"       "g"     
 399 : "ian"       "gag"   
 400 : "ian"       "gg"    
 401 : "ian"       "ggag"  
 402 : "n"         ""      
 403 : "n"         "ag"    
 404 : "n"         "agg"   
 405 : "n"         "aggag" 
 406 : "n"         "ba"    
 407 : "n"         "bagg"  
 408 : "n"         "baggag"
 409 : "n"         "g"     
 410 : "n"         "gag"   
 411 : "n"         "gg"    
 412 : "n"         "ggag"  
 413 : "r"         ""      
 414 : "r"         "a"     
 415 : "r"         "age"   
 416 : "r"         "agg"   
 417 : "r"         "agga"  
 418 : "r"         "aggag" 
 419 : "r"         "aggage"
 420 : "r"         "b"     
 421 : "r"         "ba"    
 422 : "r"         "bag"   
 423 : "r"         "bagg"  
 424 : "r"         "bagga" 
 425 : "r"         "baggag"
 426 : "r"         "baggage"
 427 : "r"         "e"     
 428 : "r"         "ga"    
 429 : "r"         "gag"   
 430 : "r"         "gage"  
 431 : "r"         "ge"    
 432 : "r"         "gg"    
 433 : "r"         "gga"   
 434 : "r"         "ggag"  
 435 : "r"         "ggage" 
 436 : "rb"        "a"     
 437 : "rb"        "ag"    
 438 : "rb"        "age"   
 439 : "rb"        "agga"  
 440 : "rb"        "aggage"
 441 : "rb"        "b"     
 442 : "rb"        "bag"   
 443 : "rb"        "bagga" 
 444 : "rb"        "baggage"
 445 : "rb"        "e"     
 446 : "rb"        "g"     
 447 : "rb"        "ga"    
 448 : "rb"        "gage"  
 449 : "rb"        "ge"    
 450 : "rb"        "gga"   
 451 : "rb"        "ggage" 
 452 : "rba"       ""      
 453 : "rba"       "ag"    
 454 : "rba"       "agg"   
 455 : "rba"       "aggag" 
 456 : "rba"       "ba"    
 457 : "rba"       "bagg"  
 458 : "rba"       "baggag"
 459 : "rba"       "g"     
 460 : "rba"       "gag"   
 461 : "rba"       "gg"    
 462 : "rba"       "ggag"  
 463 : "rbar"      "a"     
 464 : "rbar"      "ag"    
 465 : "rbar"      "age"   
 466 : "rbar"      "agga"  
 467 : "rbar"      "aggage"
 468 : "rbar"      "b"     
 469 : "rbar"      "bag"   
 470 : "rbar"      "bagga" 
 471 : "rbar"      "baggage"
 472 : "rbar"      "e"     
 473 : "rbar"      "g"     
 474 : "rbar"      "ga"    
 475 : "rbar"      "gage"  
 476 : "rbar"      "ge"    
 477 : "rbar"      "gga"   
 478 : "rbar"      "ggage" 
 479 : "rbari"     ""      
 480 : "rbari"     "ag"    
 481 : "rbari"     "agg"   
 482 : "rbari"     "aggag" 
 483 : "rbari"     "ba"    
 484 : "rbari"     "bagg"  
 485 : "rbari"     "baggag"
 486 : "rbari"     "g"     
 487 : "rbari"     "gag"   
 488 : "rbari"     "gg"    
 489 : "rbari"     "ggag"  
 490 : "rbaria"    "a"     
 491 : "rbaria"    "ag"    
 492 : "rbaria"    "age"   
 493 : "rbaria"    "agga"  
 494 : "rbaria"    "aggage"
 495 : "rbaria"    "b"     
 496 : "rbaria"    "bag"   
 497 : "rbaria"    "bagga" 
 498 : "rbaria"    "baggage"
 499 : "rbaria"    "e"     
 500 : "rbaria"    "g"     
 501 : "rbaria"    "ga"    
 502 : "rbaria"    "gage"  
 503 : "rbaria"    "ge"    
 504 : "rbaria"    "gga"   
 505 : "rbaria"    "ggage" 
 506 : "rbarian"   ""      
 507 : "rbarian"   "ag"    
 508 : "rbarian"   "agg"   
 509 : "rbarian"   "aggag" 
 510 : "rbarian"   "ba"    
 511 : "rbarian"   "bagg"  
 512 : "rbarian"   "baggag"
 513 : "rbarian"   "g"     
 514 : "rbarian"   "gag"   
 515 : "rbarian"   "gg"    
 516 : "rbarian"   "ggag"  
 517 : "ri"        ""      
 518 : "ri"        "ag"    
 519 : "ri"        "agg"   
 520 : "ri"        "aggag" 
 521 : "ri"        "ba"    
 522 : "ri"        "bagg"  
 523 : "ri"        "baggag"
 524 : "ri"        "g"     
 525 : "ri"        "gag"   
 526 : "ri"        "gg"    
 527 : "ri"        "ggag"  
 528 : "ria"       "a"     
 529 : "ria"       "ag"    
 530 : "ria"       "age"   
 531 : "ria"       "agga"  
 532 : "ria"       "aggage"
 533 : "ria"       "b"     
 534 : "ria"       "bag"   
 535 : "ria"       "bagga" 
 536 : "ria"       "baggage"
 537 : "ria"       "e"     
 538 : "ria"       "g"     
 539 : "ria"       "ga"    
 540 : "ria"       "gage"  
 541 : "ria"       "ge"    
 542 : "ria"       "gga"   
 543 : "ria"       "ggage" 
 544 : "rian"      ""      
 545 : "rian"      "ag"    
 546 : "rian"      "agg"   
 547 : "rian"      "aggag" 
 548 : "rian"      "ba"    
 549 : "rian"      "bagg"  
 550 : "rian"      "baggag"
 551 : "rian"      "g"     
 552 : "rian"      "gag"   
 553 : "rian"      "gg"    
 554 : "rian"      "ggag"

which is not that simple. I don't think there is a direct general and simple way to compute the kth winning position.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.