0w1

Hacker Earth

HE Zulu visits Wonderland ( DP )

https://www.hackerearth.com/challenge/competitive/may-circuits-17/algorithm/zulu-visits-wonderla-1/題意: N 層的地下迷宮,M 種物品。 在時間 x,你能拿第 i 個物品若且唯若所有 Level 比 Level[ i ] 小的物品的過期時間不早於 x,並且 x + Time[ i ]…

HE Zulu and Alarm Clock ( MCMF )

https://www.hackerearth.com/problem/algorithm/zulu-and-alarm-clock-1/題意: T 筆測資。 N 個鬧鐘,K 個時間。 你要把 K 個鬧鐘調成這 K 個時間。 你可以上下調整時、秒、分,會進位退位。 問最小調整次數。制約: 1≤T≤2 1≤N≤50 1≤K≤17解法: 可以用遮罩…

HE XOR queries ( Persistent Segment Tree on BIT, XOR, Online, Kth )

XOR queries | Segment Trees & Data Structures Practice Problems | HackerEarth題意: 給一個數列 A。要求在線處理 Q 筆詢問: 第一種: __將 A[ i ] 改為 x 第二種: __問 A[ l, r ] 排序後,其中 [ i, j ] 間的 xor 值為何。制約: N, Q ≤ 5e4 1 ≤ A[ i…

HE Dexter's Random Generator ( LCA, Persistent, Trie, XOR or Mo's ( TLE ) )

Dexter's Random Generator | Trie (Keyword Tree) & Data Structures Practice Problems | HackerEarth題意: 給一棵節點帶權的樹。每次詢問一條路徑,問路徑其中一個端點和路徑中任意節點的最大 XOR 值是多少。制約: 1 ≤ N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法…

HE Numbers Summation ( OEIS, Math, Square Root Decomposition )

https://www.hackerearth.com/challenge/competitive/april-circuits-17/algorithm/numbers-summation/題意: 給 N,求 S 對 1e9 + 7 取模。制約: 1 ≤ N ≤ 1e15解法: 無恥怒查 OEIS。 如果想認真解起來,要領應該跟這個是一樣的。時間 / 空間複雜度: O( N…

HE Filler Game ( SG )

Filler Game | Dynamic Programming and Bit Masking & Algorithms Practice Problems | HackerEarth題意: 一個 N * M 的棋盤,一開始也許會有障礙物。輪流操作放置一個障礙物,一個格子可以放障礙物若且唯若它是空的,而且它有一個相鄰的格子是空的。問先…

HE Fredo and Maths ( Math, Totient function )

Fredo and Maths | Totient Function & Math Practice Problems | HackerEarth題意: T 筆詢問。問 x^x^x^x^x^x... % M,其中有 K 個 x,為多少。制約: 1 ≤ T ≤ 1e5 1 ≤ M ≤ 1e7 1 ≤ K ≤ 1e18 M 解法: 利用尤拉定理可以知道,x^phi( M ) % M == 1,利用這…

HE Help Fredo ( Math, Binary Search )

Help Fredo | Binary Search & Algorithms Practice Problems | HackerEarth題意: 給 N 個元素,問最小的 x ,使得 A[ 0 ] * A[ 1 ] * A[ 2 ] .. A[ N - 1 ] 制約: 1 ≤ N ≤ 1e5 1 ≤ A[ i ] ≤ 1e10解法: 經典題,開 log 比較,二分搜 x。時間 / 空間複雜度…

HE April Circuits 3B - Bear and Special Dfs ( Timestamp + Segment Tree + Modular Inverse )

https://www.hackerearth.com/april-circuits/algorithm/utkarsh-and-special-dfs/ Modifying some node u, changing a[ u ] to some new value x, the vis count of each node of subtree of u will be divided by the original a[ u ], and multiplied by …

HE April Circuits 3A - Bear and Vectors ( Math )

https://www.hackerearth.com/april-circuits/algorithm/circ-bear-and-vectors/ Two vectors v1( a1, b1 ), v2( a2, b2 ) are perpendicular to each other iff ( v1 dot v2 ) = a1 * a2 + b1 * b2 = 0. And since ( ka, kb ) = k( a, b ) is parallel to (…

HE April Circuits 2B - Bear and Walk ( Left / RIght hand rule )

https://www.hackerearth.com/april-circuits/approximate/2b-bear-and-walk-1/ It is not difficult to come up to the maze solving left / right hand rule. www.youtube.com Since the path is connected, it will work. However, there are several dif…

HE April Circuits 2A - Bear and All Permutations ( Bigint )

https://www.hackerearth.com/april-circuits/algorithm/2a-bear-and-all-permutations-1/ We can simply simulate for each answer since n is only up to 12. However, it still takes a lot of time, and the number is extremely large, we will have to…

HE April Circuits 1B - Bear and Leaderboard ( RBST )

https://www.hackerearth.com/april-circuits/algorithm/circ-bear-and-leaderboard-1/ For clarity, everything here concerning to index will be 0 based. For example rank of some participant will be equal to the number of participants having sco…

HE April Circuits 1A - Bear and Vowels ( Simulation )

https://www.hackerearth.com/april-circuits/algorithm/circ-bear-and-vowels-2/ Simply simulate as the description provides. #include <bits/stdc++.h> using namespace std; const int MAXS = 50 + 2; const string vowel = "aeiouy"; string s; void solve(){ int vo</bits/stdc++.h>…