Code Jam 2022: ผลรวมเท่ากัน
ไม่ได้เล่นโค้ดแจมรอบที่ผ่านมาเพราะเพิ่งกลับกรุงเทพเลยนัดกินอาหารอินเดียกับแกงค์สัมภาษณ์งาน กินเสร็จกลับมาบ้านแล้วเห็นว่าโจทย์ข้อนี้น่ารักดีเลยลองทำเล่นย้อนหลังดีกว่า
(ใจจริง) โจทย์ (คงอยาก) ให้เซต
ดังนั้นโจทย์จึง (ใจดี) ให้เราเลือกสร้างสมาชิกของเซต
ข้อจำกัดอื่นๆ ได้แก่
ปัญหาบาลานซ์ตาชั่ง
ก่อนที่เราจะแก้โจทย์ข้างต้นอันสุดตื่นเต้น ขอแวะออกนอกเส้นทางหลักไปดูโจทย์สุดคลาสสิกโจทย์หนึ่งที่น่าสนใจไม่แพ้กัน ซึ่งก็คือโจทย์บาลานซ์ตาชั่ง ⚖️ โดยเราจะได้รับตาชั่งแบบโบราณที่ใช้วิธีถ่วงบาลานซ์น้ำหนักสิ่งของที่อยู่บนถาดสองข้างให้เท่ากัน ถ้าเราต้องการหาน้ำหนักของสิ่งของที่บ่งแยกความละเอียดเล็กสุดที่หนึ่งกรัม และมีน้ำหนักไม่เกินหนึ่งกำโลกรัม เราจะมีกลยุทธ์เพื่อสร้างตุ้มน้ำหนักมาถ่วงดุลตาชั่งได้อย่างไร?
หนึ่งในวิธีที่เรียบง่ายตรงไปตรงมาที่สุด ก็คือสร้างตุ้มน้ำหนักขนาดหนึ่งกรัมขึ้นมาหนึ่งพันชิ้นไปเลย 55555
ล้อเล่นนะ ถึงแม้ว่าคำตอบข้างต้นจะไม่ได้ผิดอะไร แต่มันก็ไม่สะดวกที่จะเอาไปใช้งานจริงได้ ถึงตอนนี้เราอาจจะเพิ่มเงื่อนไขบางอย่างที่ว่าจำนวนตุ้มน้ำหนักไม่ควรมีมากเกินไปด้วย
ซึ่งก็คือถ้าเราพยายามแก้โจทย์นี้อย่างชาญฉลาด เราอาจเลือกสร้างตุ้มน้ำหนักให้อยู่ในรูปสามยกกำลังไล่ไปเรื่อยๆ เช่นนี้
หัวใจสำคัญของการออกแบบเช่นนี้ คือเราจะใช้ตุ้มน้ำหนักมาถ่วงดุลกันเอง ไม่ได้ปล่อยให้ข้างหนึ่งของตาชั่งมีแต่ตุ้มน้ำหนักส่วนอีกข้างหนึ่งมีแต่สิ่งของที่เราต้องการเทียบน้ำหนัก ซึ่งเราอาจใช้ความรู้เรื่องเลขฐานสามมาช่วยพิสูจน์ได้ว่าด้วยตุ้มน้ำหนักชุดนี้ เราสามารถชั่งน้ำหนักตั้งแต่หนึ่งกรัมถึงหนึ่งกิโลกรัมได้
อย่างเช่นถ้าเราต้องการชั่งสิ่งของที่มีน้ำหนัก
ซ้าย | ขวา | |
---|---|---|
ก็ดูดี แต่รู้สึกว่าคิดเยอะไปหน่อย ทั้งที่เราอาจใช้เลขฐานสองมาช่วยก็ได้เช่นกัน คือเลือกสร้างตุ้มน้ำหนักในรูปสองยกกำลังแทน
แม้จะใช้ตุ้มน้ำหนักจำนวนเยอะกว่าเทคนิคตุ้มน้ำหนักสามยกกำลังนิดหน่อย แต่ก็ทำให้เราไม่ต้องกังวลกับการย้ายข้างตุ้มน้ำหนักอีกต่อไป เราสามารถปล่อยให้ถาดข้างหนึ่งของตาชั่งมีเพียงสิ่งของที่ต้องการชั่งได้เลย และมันก็รับประกันว่าจะชั่งน้ำหนักภายใต้หนึ่งกิโลกรัมได้ละเอียดถึงหน่วยหนึ่งกรัมเช่นกัน
ซ้าย | ขวา | |
---|---|---|
ทีนี้ถ้าเกิดมีสาเหตุอะไรก็ไม่อาจทราบได้ (พื้นคือลาวา!) ที่ทำให้โจทย์ข้างต้นมีเงื่อนไขเพิ่มเติมขึ้นมาว่า ลูกตุ้มน้ำหนักทั้งหมดที่มี จะต้องอยู่บนถาดตาชั่งข้างใดข้างหนึ่งเท่านั้น ไม่สามารถวางตุ้มน้ำหนักพักไว้นอกตาชั่งได้ แล้วอำนาจการจำแนกน้ำหนักของเราจะเปลี่ยนไปเป็นอย่างไร?
สำหรับการพยายามฉลาดโดยใช้ชุดตุ้มน้ำหนักแบบสามยกกำลังจะให้ผลลัพธ์ที่ชวนงุนงงกลับมา แต่ถ้าเราใช้ตุ้มน้ำหนักชุดสองยกกำลัง เราจะพบกับแพทเทิร์นอันสวยงามเช่นนี้
ซ้าย | ขวา | |
---|---|---|
หรือก็คือแม้เราจะไม่สามารถชั่งน้ำหนักทุกความละเอียดได้ แต่เราก็ยังสามารถชั่งน้ำหนักที่เป็นจำนวนคี่ได้ทั้งหมดอยู่ดีนั่นเอง
ปัญหาพาทิชันเซต
ย้อนกลับมาที่ปัญหาตั้งต้นที่เป็นการพาทิชันเซตให้มีผลรวมเท่ากัน ถึงแม้ปัญหานี้จะยากขั้น NP-complete แต่หากเรายอมอ่อนเงื่อนไขลงมาว่าต้องการหาพาทิชันที่ทั้งสองสับเซตมีผลรวมไม่แตกต่างกันมากจนเกินไป (ต่างกันไม่เกิน
เรายังจะใช้ความสามารถอีกอย่างหนึ่งที่โจทย์ให้มา ซึ่งก็คือการเลือกสมาชิกบางส่วนใน
from random import sample
UPPER_BOUND = 10**9
BINARY_BOUND = len(f'{UPPER_BOUND:b}')
def is_binary(x):
return x == 2**len(f'{x:b}')
def make_binaries():
return [2**i for i in range(BINARY_BOUND)]
def make_unique_random_evens(n):
xs = [2*(r+1) for r in sample(range(UPPER_BOUND//2), n)]
return [x for x in xs if not is_binary(x)][:n-BINARY_BOUND]
def strategic_picking(xs, diff=0):
picks = []
for x in xs:
if diff < 0:
diff += x
else:
diff -= x
picks += [x]
return diff, picks
def balance_with_binaries(odd_diff):
assert odd_diff % 2 == 1
_, picks = strategic_picking(reversed(make_binaries()), odd_diff)
return picks
def ask(n):
assert BINARY_BOUND <= n
xs = make_unique_random_evens(n)
print(' '.join(map(str, xs + make_binaries())))
return xs
def listen():
return [int(x) for x in input().split()]
def answer(xs):
diff, picks = strategic_picking(sorted(xs))
print(' '.join(map(str, picks + balance_with_binaries(diff))))
for _ in range(int(input())):
n = int(input())
xs = ask(n)
xs += listen()
answer(xs)

author