ติว สอวน คอมพิวเตอร์ โดยพี่ๆ ผู้แทน สสวท

ใครเตรียมใจจะไปแข่ง TOI 22 เชิญทางนี้ 🔥
ในสนามแข่งจริง มันจะมีข้อจำกัดมากมาย ทั้งเวลาที่จำกัด จำนวนโจทย์ที่จำกัด เวลาคิดที่จำกัด อุปกรณ์ที่จำกัด
ถ้าไม่อยากเสียเชิงตอนแข่งจริง แนะนำให้ลงสนามซ้อมไว้หน่อยนะ

เผื่อใครงงการทำงานระหว่าง compiled language (c, c++) กับ interpreted language (python, javascript)

นี้แหละวิดีโออธิบาย จริงๆลองเขียน interpreted เล่นๆของตัวเองดูก็สนุกดีนะ เขียนไม่ได้ยากขนาดนั้น ถ้าเงื่อนไขเราไม่มาก 555

How Real Projects Mix Compiled and Interpreted Languages 👉Get Rust training from Let’s Get Rusty: https://letsgetrusty.com/start-with-jorgeIn this video we cover how compiled languages can be mixed with interprete...

ใครเตรียมใจจะไปแข่ง TOI 21 เชิญทางนี้ 🔥
ในสนามแข่งจริง มันจะมีข้อจำกัดมากมาย ทั้งเวลาที่จำกัด จำนวนโจทย์ที่จำกัด เวลาคิดที่จำกัด อุปกรณ์ที่จำกัด
ถ้าไม่อยากเสียเชิงตอนแข่งจริง แนะนำให้ลงสนามซ้อมไว้หน่อยนะ

Pre TOI 21 by Gean Dev แหะ ๆ จัดวันที่ 6 และ 7 May ๒๐๒๕ บน ซีเอ็มS แบบเดียวกับ toi และ IOI 🥳🥳 มาทำกันด้วยนะ ๆๆ https://pre-toi21.geandev.dev/ (click this link!!!)

พลังแห่ง Matrix Exponentiation
แค่เขียน matrix ถูก คุณก็จะหาของ step ที่ n ได้ใน log(n)
เช่น f(n) = 3 * f(n-2) + 2 * f(n-1) + 4
หาวิธีคำนวน f(n) จะทำยังไง
ก็ตั้ง matrix
[f(0) f(1) 1] * ([0 1 0, 3 2 4, 0 0 1] ** n)
ส่วนการยกกำลังก็ใช้ การ divide and conquer เอาใน log(n)
pow(mat, n) = (n % 1 ? mat : 1) * pow(mat, n / 2) ** 2
เพราะงั้นการหาสมการคล้ายๆแบบข้างบนคือหวานเจี๊ยบ!!

ส่วนข้างล่างเป็ยมุขว่า matrix นี้คูณไปก็ไม่ได้อะไรหรอก ได้แต่ [0 0, 0 0]

https://codeforces.com/blog/entry/67776
https://www.geeksforgeeks.org/write-an-iterative-olog-y-function-for-powx-y/

Modulo การหาร!!??
ในโลกของการ mod เราสามารถ mod การบวกลบคูณได้ง่ายๆโดยใช้สมบัติการเปลี่ยนหมู่ แต่สำหรับการหามันไม่ตรงตัวขนาดนั้น เช่น

(a + b + c) % mod = (((a + b) % mod) + c) % mod
(a * b * c) % mod = (((a * b) % mod) * c) % mod

แต่ว่าสำหรับการหาร เราแจกแจงแบบนั้นไม่ได้
(a / b) % mod !== (a % mod) / (b % mod)

ตัวอย่างเช่น
(16 / 4) % 7 = 4
(16 % 7) / (4 % 7) = 2 / 4 = 0.5??? เป็นทศนิยมไปแล้วสมการใช้ไม่ได้

เพราะถ้ามองในการหาร จริงๆก็คือยกกำลังตัวลบ (ยกกำลัง -1)
a / b = a * (b**-1)

คำถามคือเราสามารถหาค่ายกกำลังตัวลบในระบบ Modulo ได้ไหม

คำตอบคือ ได้!! โดยมีเงื่อนไขว่า
จะหาค่า (b ** -1) จาก (b ** -1) % mod ได้ถ้า b เป็น coprime กับ mod (gcd(b, mod) == 1)

และถ้าตัว mod เป็น prime ก็จะสามารถหา inverse ได้ทุกตัวเลย

โดยเทคนิคที่ใช้กันจะมี 2 ท่าหลักๆเพื่อหาค่า inv[i] ที่
(inv[i] * i) % p = 1

1. Euler's theorem (เคสพิเศษเมื่อ p เป็น prime number)
inv[i] = pow(i, p - 2) % mod
เหมาะแก่การหาเลขตัวเดียวใช้เวลา O(log p)

2. Euclidean Division
เริ่มจากตั้งสมการการ mod ให้รูปแบบการหารเอาเศษก่อนแต่คราวนี้เราเอา p เป็นตัวตั้งและเอา i เป็นตัว mod แทน
p % i = p - (floor(p / i) * i)
แล้วค่อย mod ทั้งสองข้างด้วย p
(p % i) % p = p % p - (floor(p / i) * i) % p
(p % i) % p = - (floor(p / i) * i) % p
แล้วในคูณ inv[i]*inv[p%i] ลงไปข้างในสมการ mod เพราะว่าถ้า f(x) = g(x) แปลว่า f(h(x)) = g(h(x))

{ inv[i]*inv[p%i] * (p % i) } % p = { -1 * (floor(p / i) * i * inv[i]*inv[p%i] } % p

{ inv[i] * 1 } % p = { -1 * (floor(p / i) * 1 *inv[p%i] } % p
inv[i] % p = { -1 * (floor(p / i) * 1 * inv[p%i] } % p
แล้วเราก็แก้ค่าติดลบ โดยให้ +p ไปข้างหน้าเพราะ x % p == (x + p) % p

inv[i] = p - { (floor(p / i) * inv[p%i] } % p

เป็นสมการที่ magic สุดๆแต่ก็จะได้ formular magic แบบนี้มาใช้แทนหละ 555 แต่ละตัวใช้เวลา O(1) แต่ว่าต้องอ้างอิงตัวก่อนหน้าเป็น dynamic programming เพราะงั้นถ้าจะหาค่าถึง n ก็จะเป็น O(n)
เหมาะกับการใช้หาเลขทุกตัวจาก 1 ถึง n

และสิ่งนี้จะมีประโยชน์ในการคำนวน factorial และ combination ของเลขเยอะๆมาก
fac[i] = i * fac[i-1]
inv[i] = p - { (floor(p / i) * inv[p%i] } % p
ifac[i] = fac[i] * inv[i]

combi(n, k)
=> fac[n] / (fac[k] * fac[n-k]) % p
=> fac[n] * ifac[k] * fac[n-k] % p

เพราะงั้นลองไปทำโจทย์ข้อนี้ดูฮะเป็น combi on tree แต่ว่าเลขมันเยอะ
https://leetcode.com/problems/count-ways-to-build-rooms-in-an-ant-colony
(โคดเฉลย อย่ารีบอ่านนะ 😡https://gist.github.com/krist7599555/e551e7dfa7069f4ffc7bdcaf5a8e2687 )

อ่านเพิ่มเรื่อง inverse mod
https://cp-algorithms.com/algebra/module-inverse.html

มุขยากอยู่นะ 555
เฉลย: 91 = 13 x 7

ถ้าใครต้องคำนวนหาตารางค่า prime ไว้เยอะๆใช้ Sieve of Eratosthenes ได้ O(N log (log N)) ( https://www.youtube.com/watch?v=ghCufDWR30I

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

เสาร์นี้มาซ้อมมือกันครับ ทบทวน Algorithm กันหน่อย
[PPPPP-P][PP-][PP-]

🎉🎉🎉 ตอนนี้ก็ถึงเวลาครบรอบสามปีของ Crack 'n' Code Thailand แล้วซึ่งจะมาพร้อมกับการแข่งขัน 3rd Anniversary Contest ที่จะจัดขึ้นวันที่ 6 กรกฎาคม 2024 เวลา 19.00-22.00 (UTC+7) สามารถสมัครก่อนเวลาแข่งขัน 6 ชั่วโมงที่เว็บไซต์ crackncode.org นะครับ มาสมัครกันเยอะๆนะครับ 🥺

troublingDoubling

averageJavaHaterExperience