algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

problem.txt (1539B)


      1 - given S (multiset)
      2 - positive integer k
      3 - mex_k(S) := smallest non-negative integer that doesn't appears at least k times in S
      4 
      5 - given even integer n
      6 - positive integer k
      7 - n cards
      8 - a_i is ith card
      9 
     10 - alice first
     11     - takes any one of remaining cards
     12     - ends when all cards taken
     13     - A := multiset of integers written on alice's cards 
     14     - B := multiset of integers written on bob's cards 
     15     - Alice wins iff mex_k(A) != mex_k(B)
     16 - determine whether Alice wins if both players play optimally.
     17 
     18 ---
     19 
     20 k = 1
     21 S := 2 0 0 1
     22 
     23 Alice takes 0
     24 Bob takes 0
     25 Alice takes 1
     26 Bob takes 2
     27 
     28 Alice wins
     29 
     30 Idea:
     31     - do we just take the min value at each step for each person as long as the min value improves our mex?
     32 
     33 0 1 0 1
     34 
     35 Alice takes 0
     36 Bob takes 0
     37 Alice takes 1
     38 Bob takes 1
     39 
     40 Bob wins
     41 
     42 Alice takes 1
     43 Bob takes 1
     44 Alice takes 0
     45 Bob takes 0
     46 
     47 Bob wins
     48 
     49 6 2
     50 1 2 0 1 0 0
     51 
     52 Alice takes 0
     53 Bob takes 0
     54 Alice takes 0
     55 
     56 that's it, alice wins
     57 
     58 k = 2
     59 0 0 1 1 2 2
     60 
     61 Alice takes 0
     62 Bob takes 0
     63 Bob wins
     64 
     65 
     66 k = 2
     67 0 1 1 0 0 2 0 1
     68 
     69 Alice takes 0
     70 bob takes 0
     71 Alice takes 0
     72 bob takes 0
     73 
     74 2
     75 
     76 Alice takes 1
     77 Bob takes 1
     78 
     79 Alice takes 1
     80 Bob takes 2
     81 
     82 Alice wins
     83 
     84 ---
     85 
     86 idea:
     87 
     88 do we always just take the smallest values?
     89 
     90 it seems like there might be a case where we wouldn't
     91 
     92 k = 1
     93 000000000000000000000000000000000000000000000000000000000000000000001
     94 
     95 alice should take 1
     96 bob would then have to take 0
     97 
     98 alice takes 0
     99 then trade back and forth taking 1's
    100 
    101 alice wins
    102 
    103 if alice takes 0
    104 bob takes 1
    105 then they trade I guess alice still wins here because bob has a largest mex