Topcoder SRM 624
題目非常 standard, 估計是為了測試 TopCoder 終於肯 support 大於 50 的 vector input
加上不久前開始 support special judge TopCoder 支援的題目類型終於可以跟其它 OJ 相提並論
E 在 system test fail 了, 不過憑著 5 棍 hack 和 RP 仍然保住 T-shirt 一件
終極 fail
Task H: 構造 integers input 使得 C++, Java 的 hash table (對應為 unordered_set 和 hashset) insert n 個 integer 的時間為 O(n2)
Contest 時沒有做, 不過若不是這題也未必會知道 C++/Java hash table 的 implementation
兩個 language 的 hash table 也是用 chaining, insert 時會 search 一次整個 bucket, 所以只要不斷 hash key collision 就可以退化為 O(n2)
然後跟據題解的不斷 dig into source code, 就可以發現:
- C++ 的 hash table size 必為 prime, 並 default 在 load factor = 1 時 double hash table size; 而 hash function 則為 modulo 現在的 hash table size
- Java 的 hash table size 為 2's power, load factor = 3/4 時兩倍化, hash function 則是用 shift bit
知道實際的數字就可以輕鬆殺掉 unordered_set 和 hashset! 所以以後 CodeForces 繼 anti Java Quicksort 後可能會出現 anti hashtable..
Task M: 求 s-t maxflow, 額外限制: 每條 s-t flow 長度不長於 L. Small: L ≤ 3, Large: L ≤ 6
Small 的話可以很容易 model 做 maxflow, 很 standard
Large 解題報告用了一個例子去說明很可能沒有 "一般" maxflow 的做法, 因為當 L > 3 存在 integral capacity graph 但答案不是 integer
但其實不難發現可以 model 為一個 O(L|E|) 個 variables 的 LP, 相當於 60000 個 variables.. 於是放棄之
Contest 過後看題解, 原來這個就是 intended solution! 不得不說 simplex 真是奇妙的東西
題解 booklet
Contest 時沒有做, 不過若不是這題也未必會知道 C++/Java hash table 的 implementation
兩個 language 的 hash table 也是用 chaining, insert 時會 search 一次整個 bucket, 所以只要不斷 hash key collision 就可以退化為 O(n2)
然後跟據題解的不斷 dig into source code, 就可以發現:
- C++ 的 hash table size 必為 prime, 並 default 在 load factor = 1 時 double hash table size; 而 hash function 則為 modulo 現在的 hash table size
- Java 的 hash table size 為 2's power, load factor = 3/4 時兩倍化, hash function 則是用 shift bit
知道實際的數字就可以輕鬆殺掉 unordered_set 和 hashset! 所以以後 CodeForces 繼 anti Java Quicksort 後可能會出現 anti hashtable..
Task M: 求 s-t maxflow, 額外限制: 每條 s-t flow 長度不長於 L. Small: L ≤ 3, Large: L ≤ 6
Small 的話可以很容易 model 做 maxflow, 很 standard
Large 解題報告用了一個例子去說明很可能沒有 "一般" maxflow 的做法, 因為當 L > 3 存在 integral capacity graph 但答案不是 integer
但其實不難發現可以 model 為一個 O(L|E|) 個 variables 的 LP, 相當於 60000 個 variables.. 於是放棄之
Contest 過後看題解, 原來這個就是 intended solution! 不得不說 simplex 真是奇妙的東西
題解 booklet
