ไม่ได้เล่นโค้ดแจมรอบที่ผ่านมาเพราะเพิ่งกลับกรุงเทพเลยนัดกินอาหารอินเดียกับแกงค์สัมภาษณ์งาน กินเสร็จกลับมาบ้านแล้วเห็นว่าโจทย์ข้อนี้น่ารักดีเลยลองทำเล่นย้อนหลังดีกว่า

(ใจจริง) โจทย์ (คงอยาก) ให้เซต $S$ ซึ่งเก็บเลขจำนวนเต็มบวกหลายๆ ตัวมา แล้วให้เราพาทิชันเซตนี้เป็นสองสับเซตที่มีผลรวมเท่ากันแหละ แต่ถ้าแต่งโจทย์แบบนั้นก็คือเราจะได้ปัญหาผลรวมสับเซตที่ไม่น่ามีใครแก้ได้ทันในเวลาเข้าแข่งขันแทน 😝

ดังนั้นโจทย์จึง (ใจดี) ให้เราเลือกสร้างสมาชิกของเซต $S$ ได้ครึ่งหนึ่ง แล้วอีกครึ่งหนึ่งกรรมการจะให้ตัวเลขอีกชุดที่รับประกันว่า $\sum S$ เป็นจำนวนคู่มา ให้หาวิธีฉลาดๆ ซักหน่อยเพื่อเลือกสมาชิกบางตัวนั้นมาเพื่อสร้างเซต $S$ ที่รับประกันว่าจะพาทิชันออกเป็นสองสับเซต (ที่ไม่จำเป็นต้องมีขนาดเท่ากัน) ที่มีผลรวมเท่ากันได้เสมอ

ข้อจำกัดอื่นๆ ได้แก่ $\left|S\right|=2n$ ซึ่งก็คือให้เราเลือกสมาชิกได้ $n$ ตัว และสมาชิกแต่ละตัวนั้นมีค่าไม่เกิน ${10}^9$ … น่าเสียดายนิดหน่อยที่ว่าโจทย์เลือกที่จะตรึงค่า $n=100$ ไม่ยอมแปรผันให้สนุกสนานในแต่ละเทสเคส 🤔

ปัญหาบาลานซ์ตาชั่ง

ก่อนที่เราจะแก้โจทย์ข้างต้นอันสุดตื่นเต้น ขอแวะออกนอกเส้นทางหลักไปดูโจทย์สุดคลาสสิกโจทย์หนึ่งที่น่าสนใจไม่แพ้กัน ซึ่งก็คือโจทย์บาลานซ์ตาชั่ง ⚖️ โดยเราจะได้รับตาชั่งแบบโบราณที่ใช้วิธีถ่วงบาลานซ์น้ำหนักสิ่งของที่อยู่บนถาดสองข้างให้เท่ากัน ถ้าเราต้องการหาน้ำหนักของสิ่งของที่บ่งแยกความละเอียดเล็กสุดที่หนึ่งกรัม และมีน้ำหนักไม่เกินหนึ่งกำโลกรัม เราจะมีกลยุทธ์เพื่อสร้างตุ้มน้ำหนักมาถ่วงดุลตาชั่งได้อย่างไร?

หนึ่งในวิธีที่เรียบง่ายตรงไปตรงมาที่สุด ก็คือสร้างตุ้มน้ำหนักขนาดหนึ่งกรัมขึ้นมาหนึ่งพันชิ้นไปเลย 55555

ล้อเล่นนะ ถึงแม้ว่าคำตอบข้างต้นจะไม่ได้ผิดอะไร แต่มันก็ไม่สะดวกที่จะเอาไปใช้งานจริงได้ ถึงตอนนี้เราอาจจะเพิ่มเงื่อนไขบางอย่างที่ว่าจำนวนตุ้มน้ำหนักไม่ควรมีมากเกินไปด้วย

ซึ่งก็คือถ้าเราพยายามแก้โจทย์นี้อย่างชาญฉลาด เราอาจเลือกสร้างตุ้มน้ำหนักให้อยู่ในรูปสามยกกำลังไล่ไปเรื่อยๆ เช่นนี้

หัวใจสำคัญของการออกแบบเช่นนี้ คือเราจะใช้ตุ้มน้ำหนักมาถ่วงดุลกันเอง ไม่ได้ปล่อยให้ข้างหนึ่งของตาชั่งมีแต่ตุ้มน้ำหนักส่วนอีกข้างหนึ่งมีแต่สิ่งของที่เราต้องการเทียบน้ำหนัก ซึ่งเราอาจใช้ความรู้เรื่องเลขฐานสามมาช่วยพิสูจน์ได้ว่าด้วยตุ้มน้ำหนักชุดนี้ เราสามารถชั่งน้ำหนักตั้งแต่หนึ่งกรัมถึงหนึ่งกิโลกรัมได้

อย่างเช่นถ้าเราต้องการชั่งสิ่งของที่มีน้ำหนัก $x=300$ กรัม เราจะจัดตาชั่งได้เช่นนี้

ก็ดูดี แต่รู้สึกว่าคิดเยอะไปหน่อย ทั้งที่เราอาจใช้เลขฐานสองมาช่วยก็ได้เช่นกัน คือเลือกสร้างตุ้มน้ำหนักในรูปสองยกกำลังแทน

แม้จะใช้ตุ้มน้ำหนักจำนวนเยอะกว่าเทคนิคตุ้มน้ำหนักสามยกกำลังนิดหน่อย แต่ก็ทำให้เราไม่ต้องกังวลกับการย้ายข้างตุ้มน้ำหนักอีกต่อไป เราสามารถปล่อยให้ถาดข้างหนึ่งของตาชั่งมีเพียงสิ่งของที่ต้องการชั่งได้เลย และมันก็รับประกันว่าจะชั่งน้ำหนักภายใต้หนึ่งกิโลกรัมได้ละเอียดถึงหน่วยหนึ่งกรัมเช่นกัน

ทีนี้ถ้าเกิดมีสาเหตุอะไรก็ไม่อาจทราบได้ (พื้นคือลาวา!) ที่ทำให้โจทย์ข้างต้นมีเงื่อนไขเพิ่มเติมขึ้นมาว่า ลูกตุ้มน้ำหนักทั้งหมดที่มี จะต้องอยู่บนถาดตาชั่งข้างใดข้างหนึ่งเท่านั้น ไม่สามารถวางตุ้มน้ำหนักพักไว้นอกตาชั่งได้ แล้วอำนาจการจำแนกน้ำหนักของเราจะเปลี่ยนไปเป็นอย่างไร?

สำหรับการพยายามฉลาดโดยใช้ชุดตุ้มน้ำหนักแบบสามยกกำลังจะให้ผลลัพธ์ที่ชวนงุนงงกลับมา แต่ถ้าเราใช้ตุ้มน้ำหนักชุดสองยกกำลัง เราจะพบกับแพทเทิร์นอันสวยงามเช่นนี้

หรือก็คือแม้เราจะไม่สามารถชั่งน้ำหนักทุกความละเอียดได้ แต่เราก็ยังสามารถชั่งน้ำหนักที่เป็นจำนวนคี่ได้ทั้งหมดอยู่ดีนั่นเอง

ปัญหาพาทิชันเซต

ย้อนกลับมาที่ปัญหาตั้งต้นที่เป็นการพาทิชันเซตให้มีผลรวมเท่ากัน ถึงแม้ปัญหานี้จะยากขั้น NP-complete แต่หากเรายอมอ่อนเงื่อนไขลงมาว่าต้องการหาพาทิชันที่ทั้งสองสับเซตมีผลรวมไม่แตกต่างกันมากจนเกินไป (ต่างกันไม่เกิน ${10}^9$) เราก็จะสามารถแก้ปัญหานี้ได้อย่างมีประสิทธิภาพเลยทันที ซึ่งก็ทำได้ผ่านการดูสมาชิกแต่ละตัวใน $S$ ที่เรียงลำดับแล้ว หลังจากนั้นค่อยๆ หยิบสมาชิกมาเลือกว่าจะใส่ไปยังข้างซ้ายหรือขวาของพาทิชัน โดยพยายามบาลานซ์ผลรวมให้แตกต่างกันไม่มากเกินไป ทั้งยังระลึกไว้ว่าเราต้องการให้ผลต่างเป็นจำนวนคี่อีกด้วย

เรายังจะใช้ความสามารถอีกอย่างหนึ่งที่โจทย์ให้มา ซึ่งก็คือการเลือกสมาชิกบางส่วนใน $S$ ได้เพื่อจองพื้นที่ไว้ให้ชุดตัวเลขที่อยู่ในรูปสองยกกำลัง (ไม่ต้องเอาเลขชุดนี้ไปบาลานซ์ในตอนต้น) หลังจากที่เราเห็นแล้วว่าฝั่งไหนของพาทิชันหนักกว่า เราก็จะใส่ตัวเลขชุดที่เหลือนี้ลงไปเพื่อดุลสองข้างของพาทิชันให้มีผลรวมเท่ากันเป๊ะนั่นเอง

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)

neizod

author