Advanced Seminar on Problem Solving Techniques
Explore various problem-solving techniques such as prefix sum, hash, GCD, LCM, and more in this advanced seminar. Learn how to calculate complex mathematical functions efficiently and sort arrays in linear time complexity. Enhance your problem-solving skills and algorithmic thinking.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
HKBU ICPC Seminar2 Zhu Xuliang
Quiz Calculate: (1) 11 & 7; (2) 11 | 7; (3) 11 ^ 7 (4) 1^2^3^ ^11 Calculate: 3101mod 11 Given X is an integer, round X / 10 without if/else Sort a1, a2, , an in O(n), where 1 <= ai <= n
Answer (1) 3 (2) 15 (3) 12 (4) 0 3 (X + 5) / 10 Step1: Use cnt[x] to store the number of ai = x; Step2: Output cnt[x] times of x from 1 to n;
Outlines Prefix sum Hash GCD & LCM
Problem How to calculate f(n) = 1^2^3^ ^n in O(1)?
Problem How to calculate f(n) = 1^2^3^ ^n in O(1)? f(n) = 0 (n % 4 == 3) f(n) = n (n % 4 == 0) f(n) = 1 (n % 4 == 1) f(n) = n + 1 (n % 4 == 2)
Problem How to calculate f(x, y) = x^(x+1)^(x+2)^ ^y in O(1)?
Problem How to calculate f(x, y) = x^(x+1)^(x+2)^ ^y in O(1)? x^(x+1)^(x+2)^ ^y = f(y) ^ f(x-1)
Prefix sum Given an array a1, a2, , an, and Q queries of q(x, y) to calculate ax + ax+1+ + ayin O(n + Q)
Prefix sum Given an array a1, a2, , an, and Q queries of q(x, y) to calculate ax + ax+1+ + ayin O(n + Q) sum[i] = a1+ a2+ + ai q(x, y) = sum[y] sum[x - 1]
Prefix sum Given an array a1, a2, , an, and Q queries of q(x, y) to calculate ax + ax+1+ + ayin O(n + Q) sum[i] = a1+ a2+ + ai q(x, y) = sum[y] sum[x - 1] sum / xor / count max / min /
Problem Sort a1, a2, , an in O(n), where 1 <= ai <= n Step1: Use cnt[x] to store the number of ai = x; Step2: Output cnt[x] times of x from 1 to n; Bucket sort
Problem Given a list of string s1, s2, , sn, count the number of different strings.
Problem Given a list of string s1, s2, , sn, count the number of different strings. Map string si -> int ai Cnt[ai]++
Hash function If si = sj, Hash(si) = Hash(sj) If si != sj, Hash(si) != Hash(sj) Hash(s) = (s[0] a ) * 260+ (s[1] a ) * 261 + + (s[n] a ) * 26n Is it true?
Hash function If si = sj, Hash(si) = Hash(sj) If si != sj, Hash(si) != Hash(sj) Hash(s) = (s[0] a ) * 270+ (s[1] a ) * 271 + + (s[n] a ) * 27n Hash(s) maybe too large Mod a large prime number
Hash collision If si != sj, Hash(si) maybe equal Hash(sj) Double Hash si = sj <==> Hash1(si) = Hash1(sj) and Hash2(si) = Hash2(sj) si != sj <==> Hash1(si) != Hash1(sj) or Hash2(si) != Hash2(sj)
Hash table Hash table: unordered_map (C++) / hashmap (java) Red-Black tree: map (C++) / treemap (java)
GCD & LCM greatest common divisor (GCD for short)
GCD & LCM greatest common divisor (GCD for short) Euclidean algorithm ( ) GCD(x, 0) = x GCD(9, 24) = GCD(9, 6) = GCD(3, 6) = GCD(3, 0) = 3
GCD & LCM greatest common divisor (GCD for short) Euclidean algorithm ( ) (Time complexity: Log(n)) least common multiple (LCM for short)
GCD & LCM greatest common divisor (GCD for short) Euclidean algorithm ( ) (Time complexity: Log(n)) least common multiple (LCM for short) LCM(a, b) = ab / GCD(a, b)
GCD & LCM GCD(a1, a2, a3, , an) = ? LCM(a1, a2, a3, , an) = ? GCD(a1, a2, a3, , an) = GCD(GCD(a1, a2), a3) LCM(a1, a2, a3, , an) =GCD * (a1 / GCD) * (a2 / GCD) *
