0w1

Entries from 2016-06-14 to 1 day

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…

TNOJ 333 畢業 ( DP )

DP

TNFSH Online Judge 應該很容易看出來,只有兩個狀態要維護,一個是即將扣學分的狀態和即將加學分的狀態,由左到右一一更新,O( N )。問題是數據規模到千萬,如果單純用scanf會TLE。。原來面對更大的數據時,簡單優化過的cin, cout 會更快是真的。 #include <bits/stdc++.h></bits/stdc++.h>…

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 …