很久沒有打比賽後感
250 - code 完後才發現只能 swap adjacent pairs, 一直以為可以任意 swap
基本上整個做法完全不同, 浪費了 5 mins
最後得出 O(N5) 的做法, 可以加速至 O(n4) , 不過為了減低出錯機會選擇了前者
submit 後再試 case, 發現 for loop 的 bound 寫錯了, 要 resubmit
450 - 很明顯的 shortest path, 輕鬆解決
1000 - 只有 tourist 和 wata solve 到
假設數有多少種不同 count fruit 的可能性也不容易, 2n 太慢, dp 也不行
只能 split 開兩邊做 D&C, O(2n/2 * n)
問題是要數 spanning tree 的數目, 而且有很多限制
想了很多方法戳式, 花了很多時間
臨完場 10mins 想到, 根本不用戳式, 而是可以 precompute 所有組合的 spanning tree 數目!
而且最多只有 n 個組合
連計算 determinant, 只要 O(n4)
剩下的便是 standard 的 slide pointer
250 太慢加上沒有 challenge, 不過 450 的高速挽回不少
rating 微升
250 - code 完後才發現只能 swap adjacent pairs, 一直以為可以任意 swap
基本上整個做法完全不同, 浪費了 5 mins
最後得出 O(N5) 的做法, 可以加速至 O(n4) , 不過為了減低出錯機會選擇了前者
submit 後再試 case, 發現 for loop 的 bound 寫錯了, 要 resubmit
450 - 很明顯的 shortest path, 輕鬆解決
1000 - 只有 tourist 和 wata solve 到
假設數有多少種不同 count fruit 的可能性也不容易, 2n 太慢, dp 也不行
只能 split 開兩邊做 D&C, O(2n/2 * n)
問題是要數 spanning tree 的數目, 而且有很多限制
想了很多方法戳式, 花了很多時間
臨完場 10mins 想到, 根本不用戳式, 而是可以 precompute 所有組合的 spanning tree 數目!
而且最多只有 n 個組合
連計算 determinant, 只要 O(n4)
剩下的便是 standard 的 slide pointer
250 太慢加上沒有 challenge, 不過 450 的高速挽回不少
rating 微升
No comments:
Post a Comment