algorithms

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

commit 77f117082080792800f0563ebcfb6433f707df09
parent 05990dee3ecdc3d232b96f48ed1789e551a94e66
Author: Andrew Laack <andrew@laack.co>
Date:   Sun, 15 Nov 2026 10:13:39 -0600

Mex game in  ocaml

Diffstat:
Acomp/mex-game/ex1.in | 11+++++++++++
Acomp/mex-game/main.ml | 39+++++++++++++++++++++++++++++++++++++++
Acomp/mex-game/problem.txt | 105+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 155 insertions(+), 0 deletions(-)

diff --git a/comp/mex-game/ex1.in b/comp/mex-game/ex1.in @@ -0,0 +1,11 @@ +5 +4 1 +2 0 0 1 +4 1 +0 1 0 1 +6 2 +1 2 0 1 0 0 +6 2 +0 0 1 1 2 2 +8 2 +0 1 1 0 0 2 0 1 diff --git a/comp/mex-game/main.ml b/comp/mex-game/main.ml @@ -0,0 +1,39 @@ +let readInt () = + Scanf.scanf " %d" (fun x->x) + +let loadArr arr arrLen = + let rec acc idx = + if idx = arrLen then () + else (arr.(idx) <- readInt (); acc (idx + 1)) + in acc 0 + +let solve arr k = + let n = Array.length arr in + let rec acc minIdx turn target acMexA acMexB = + if minIdx = n || arr.(minIdx) > target then + if acMexA >= k && acMexB >= k + then acc minIdx turn (target + 1) 0 0 + else (acMexA >= k) <> (acMexB >= k) + else if acMexA >= k && acMexB >= k then + acc (minIdx + 1) turn target acMexA acMexB + else if turn then + acc (minIdx + 1) false target (acMexA + 1) acMexB + else + acc (minIdx + 1) true target acMexA (acMexB + 1) + in acc 0 true 0 0 0 + +let handleTestCase () = + let arrLen = readInt () in + let k = readInt () in + let arr = Array.make arrLen 0 in + let () = loadArr arr arrLen in + let () = Array.sort compare arr in + let soln = solve arr k in + if soln then print_endline "YES" else print_endline "NO" + +let () = + let testCases = readInt () in + let rec acc idx = + if idx = testCases then () + else (handleTestCase (); acc (idx+1)) + in acc 0 diff --git a/comp/mex-game/problem.txt b/comp/mex-game/problem.txt @@ -0,0 +1,105 @@ +- given S (multiset) +- positive integer k +- mex_k(S) := smallest non-negative integer that doesn't appears at least k times in S + +- given even integer n +- positive integer k +- n cards +- a_i is ith card + +- alice first + - takes any one of remaining cards + - ends when all cards taken + - A := multiset of integers written on alice's cards + - B := multiset of integers written on bob's cards + - Alice wins iff mex_k(A) != mex_k(B) +- determine whether Alice wins if both players play optimally. + +--- + +k = 1 +S := 2 0 0 1 + +Alice takes 0 +Bob takes 0 +Alice takes 1 +Bob takes 2 + +Alice wins + +Idea: + - do we just take the min value at each step for each person as long as the min value improves our mex? + +0 1 0 1 + +Alice takes 0 +Bob takes 0 +Alice takes 1 +Bob takes 1 + +Bob wins + +Alice takes 1 +Bob takes 1 +Alice takes 0 +Bob takes 0 + +Bob wins + +6 2 +1 2 0 1 0 0 + +Alice takes 0 +Bob takes 0 +Alice takes 0 + +that's it, alice wins + +k = 2 +0 0 1 1 2 2 + +Alice takes 0 +Bob takes 0 +Bob wins + + +k = 2 +0 1 1 0 0 2 0 1 + +Alice takes 0 +bob takes 0 +Alice takes 0 +bob takes 0 + +2 + +Alice takes 1 +Bob takes 1 + +Alice takes 1 +Bob takes 2 + +Alice wins + +--- + +idea: + +do we always just take the smallest values? + +it seems like there might be a case where we wouldn't + +k = 1 +000000000000000000000000000000000000000000000000000000000000000000001 + +alice should take 1 +bob would then have to take 0 + +alice takes 0 +then trade back and forth taking 1's + +alice wins + +if alice takes 0 +bob takes 1 +then they trade I guess alice still wins here because bob has a largest mex