Crop Triangles หลังจากคุณดู Discovery คุณก็อยากจะสร้าง Crop Circles บ้าง แต่ระดับคุณ คุณจะสร้าง Crop Triangles แทน และ Triangle ของคุณต้องไม่ธรรมดา มุมต่างๆ ของสามเหลี่ยม ต้องอยู่บนจุดตัดบน Grid ไม่พอ จุดศูนย์กลางของสามเหลี่ยมจะต้องอยู่บนจุดตัดบน Grid ด้วย สูตรการหาจุดศูนย์กลางคือ (x1 + x2 + x3) / 3, (y1 + y2 + y3) /3 โจทย์จะมีสูตรให้สร้างจุดต่างๆ บน Grid แล้วให้หาว่าเราสามารถสร้าง Crop Triangles ได้กี่แบบ อ่านต่อ ที่นี่ เนื่องจาก large dataset สามารถสร้างจุดได้ถึง 100,000 จุด เราจึงไม่สามารถใช้วิธี brute force ได้ ซึ่งจะต้องหาทั้งหมด 100,000! วิธี แต่จริงๆ พอจะมีทางลัด ถ้า (x1 + x2 + x3) / 3 เป็นจุดตัดบน grid หมายความว่า x1 + x2 + x3 หาร 3 ลงตัว ซึ่งก็หมายความว่า x1 mod 3 + x2 mod 3 + x3 mod 3 หาร 3 ลงตัว เริ่มเลย let solve n A B C D x0 y0 M = n A B C D x0 y0 M เป็น input ที่โจทย์กำหนด unfoldFn ก็เป็น function ที่โจทย์กำหนด เพื่อสร้างจุดต่างๆ ส่วน trees คือจุดต่างๆ let buckets = trees |> Seq.groupBy (fun (x, y) -> (int x % 3)*3 + (int y % 3)) ทีนี้ก็จัดกลุ่มเป็น 9 กลุ่ม (x mod 3) ตัดกับ (y mod 3) แล้วก็นับจำนวนในกลุ่ม let sameBucketCount = buckets |> Seq.map (fun (key, cnt) -> cnt * (cnt-1L) * (cnt-2L) / 6L) ถ้าเป็นกลุ่มเดียวกัน ก็แปลว่าหารลงตัวแน่นอน เรื่องการหาจำนวนในกลุ่ม ใช้สูตร combinatorics หยิบ 3 จาก cnt ตัว อีกแบบคือ คนละกลุ่มหมด แต่หาร 3 ลงตัว let diffBucketCount = seq { คือ ถ้ามาจากคนละกลุ่มหมดเลย และทั้งแกน x และ y หาร 3 ลงตัว ก็เอาจำนวนมาคูณกันได้เลย จบแล้วครับ ได้คำตอบ sameBucketCount + diffBucketCount |> string จบ |