# 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 …