0w1

Hacker Rank

HR Permutation Happiness

Problem Description: Happiness is a value defined upon a permutation, where it is given by the number of values with at least one value higher than itself that is adjacent. Given Q queries, output number of size n permutation with at least…

HR Nominating Group Leaders ( Mo's Algorithm, Sqrt Decomposition )

Programming Problems and Competitions :: HackerRank題意: N 個人排成一排,每個人對人投一個票。Q 筆詢問,問 [ L, R ] 中,是否有恰好得到 X 票的人,如果有,輸出其中編號最小的。制約: 1 ≤ T ≤ 5 1 ≤ N, Q ≤ 1e5 N 的總和和 Q 的總和不超過 3e5。解…

HR Colliding Circles ( Math, Expectation )

Programming Problems and Competitions :: HackerRank題意: 有 N 個線段,用長度描述。每一秒以均等機率有兩個線段合併 ( 長度變為總和 )。問期望上 K 秒後,每個線斷所成的圓面積總和為何。制約: 1 ≤ N ≤ 1e5 0 ≤ K ≤ N - 1 0 ≤ R[ i ] ≤ 1e4解法: 首先…

HR Spanning Tree Fraction ( 最優比例生成樹, Binary Search, Spanning Tree )

Programming Problems and Competitions :: HackerRank題意: N 個點 M 個邊,第 i 個邊用 a[ i ], b[ i ] 描述。求一個生成樹,使得 sum( a ) / sum( b ) 最大。制約: 2 ≤ N ≤ 1e5 N - 1≤ M ≤ 1e5 1 ≤ a[ i ], b[ i ] ≤ 100解法: 裸的最優比例生成樹。 聽…

HR Hyperrectangle GCD ( Mobius Inversion )

https://www.hackerrank.com/challenges/hyperrectangle-gcd題意: 有 K 個箱子,裡面分別有 [ 1, N[ i ] ] 的數字。現在要從每個箱子里抽一個數字,求其最大公因數。問所有取法可以產生的最大公因數總和。資料規模: Constraints 1 2 1 p.s. T * nk * K 明…

HR Find the Seed ( DP + Matrix Inverse - Gauss Elimination )

https://www.hackerrank.com/challenges/find-the-seed F( n ) = c( 1 ) * F( n - 1 ) + c( 2 ) * F( n - 2 ) .. + c( n ) * F( 0 ) => c( n ) * F( 0 ) = F( n ) - c( 1 ) * F( n - 1 ) - c( 2 ) * F( n - 2 ) .. - c( n - 1 ) * F( 1 ) => F( 0 ) = invers…

HR Equal ( Greedy )

https://www.hackerrank.com/challenges/equal An important observation to make, is to realise that "adding value x to all elements except element y" is equivalent to "decreasing value x from element y". Once this is made clear, it will be ob…

HR Mr K marsh ( DP )

https://www.hackerrank.com/challenges/mr-k-marsh First, precompute the leftmost and uppermost cell each cell can reach to. Then, enumerate 2 rows each time, push each column where it the vertical fence could be built into a vector. Then, u…

HR Grid Walking ( DP )

https://www.hackerrank.com/challenges/grid-walking We should first determine the number of paths with some particular number of moves on each dimension separately, let's have wdm[ i ][ j ] = number of paths on dimension i, with length j. T…

HR Far Vertices ( Greedy )

https://www.hackerrank.com/challenges/far-vertices Let's find out all pairs of ( u, v ) where dis( u, v ) > K, put them into a set, and change the question to: "How many nodes should be removed, so that u and v do not coexist in any pairs …