ช่วงนี้กำลังคลั่งไคล้ Python ครับ แต่ถ้าคลั่งไคล้อย่างเดียวแต่ไม่ได้ทำแลบเปียกเลยก็คงเขียนไม่คล่องซักที เลยลองเอา Python ไปทำโจทย์เก่าที่เคยทำด้วย C# ของ Google Code Jam ปีที่แล้วดู ทำเสร็จแล้วดองไว้ที่บ้านก็ไม่ดี เอามาเฉลยดีกว่า เผื่อใครอยากลองแข่งปีนี้ (รอบ QR วันที่ 2 กันยายน 2009)
โจทย์ข้อนี้มาจาก Qualification Round 2008 โดยย่อ โจทย์จะให้รายชื่อ Search Engine มาทั้งหมด S อัน และคำค้นหาอีก Q อัน คำค้นหาจะถูกประมวลผลเรียงตามลำดับที่ได้รับเข้ามา โดยในเวลาใดเวลาหนึ่งจะมี Search Engine ทำงานอยู่ได้เพียงตัวเดียว
ถ้าคำค้นหาตรงกับชื่อ Search Engine จะทำให้ Search Engine ระเบิด! ดังนั้นจึงอนุญาตให้ “สลับ” Search Engine จากตัวหนึ่งไปอีกตัวหนึ่งได้ คำถามคือ จากรายชื่อ SE และคำค้นหาที่ให้มา จำเป็นจะต้องใช้การสลับอย่างน้อยสุดกี่ครั้ง จึงจะประมวลผลการค้นหาทั้งหมดได้
ตัวอย่าง
มี SE
- Googol Vietnam
- Googol Jersey
- Googol Ethiopi
มีคำค้นหา
- Googol Jersey
- Googol Vietnam
- Googol Jersey
- Googol Jersey
- Googol Jersey
- Googol Jersey
- Googol Ethiopia
- Googol Ethiopia
- Googol Ethiopia
- Googol Ethiopia
- Googol Vietnam
- Googol Ethiopi
ตอบ 1 ครั้ง
เฉลย
ข้อนี้แก้ได้ด้วยวิธีแบบ Greedy ครับ คำอธิบายยาวๆลองไปดู E-learning ของอาจารย์สมชาย แล้วกัน :)
แต่สั้นๆคือ “ทำอะไรที่เห็นตรงหน้าให้ดีที่สุดไว้ก่อน”
ข้อนี้ก็เริ่มจากการหา Search Engine ที่จะ process query ได้เยอะที่สุดโดยไม่ต้องสลับ ซึ่งก็หาได้โดยดู query จากต้นไปเรื่อยๆ จนกว่าจะพบ query ที่เป็นชื่อ Search Engine ครบหมดทุกตัว ตัวสุดท้ายที่พบ (ตัวที่ทำให้บรรลุเงื่อนไข “พบหมดทุกตัว”) จะเป็น Search Engine ตัวที่ทำให้ process query ได้เยอะที่สุดตัวแรก ซึ่งก่อนที่จะ process query อันสุดท้ายนี้ เราจำเป็นอย่างหลีกเลี่ยงไมได้ ต้องทำการ “สลับ” เสียก่อน หลังจากสลับแล้ว query อันสุดท้ายนี้ก็จะนับเป็น Search Engine ที่เราได้ “พบ” แล้วอีกตัวหนึ่ง ก่อนที่จะทำการมอง query ต่อไปเรื่อยๆจนจบ
ประเด็นที่น่าจะยากสำหรับมือใหม่คือการเช็คว่า “พบ Search Engine ครบทุกตัว” แล้วหรือยัง ??
วิธีที่ผมใช้คือเอาชื่อ Search Engine ใส่พวก Map/Dictionary แล้วตอนได้รับ Query มาก็ตรวจดูว่ามี key อันนี้แล้วหรือยัง ถ้ามี และยังไม่เคยพบ ก็จะเซ็ตให้เป็น True (แปลว่าพบ) แล้วก็ใช้ counter อีกตัวนึงคอยนับว่าเจอครบทุกตัวแล้วหรือยัง
โค้ดใน Python ตามนี้
if __name__ == '__main__':
filename = "A-small-practice.in"
filename = "A-large-practice.in"
out_filename = "A-small.out"
out_filename = "A-large.out"
file = open(filename, 'r')
num_cases = int(file.readline())
out_file = open(out_filename, 'w')
for c in range(0,num_cases):
# For each case
num_switch = 0
# To check for dupplicate search engine names
dict = {}
num_engine = int(file.readline())
found_engine = 0
for e in range(0,num_engine):
engine = file.readline()
dict[engine] = False
num_q = int(file.readline())
for q in range(0,num_q):
query = file.readline()
if dict.has_key(query):
if dict[query] == False:
found_engine = found_engine + 1
dict[query] = True
# Check if there is no possibility of not switching
# all search engines are used up
if found_engine == num_engine:
num_switch = num_switch + 1
found_engine = 1
for (k,v) in dict.items():
if query != k:
dict[k] = False
out_file.write("Case #%d: %d\n" % (c+1, num_switch))
out_file.close()
ครั้งนี้เหมือนโยนหินถามทางครับ~
ถ้า Feed back ดีอาจมีตอนต่อ :)
Tags: google, code jam, algorithm, python