A. Subarrays Beauty
justHusam solution: https://ideone.com/PL7s1U
Vendetta. solution: https://ideone.com/23iukT
Complexity: O(Nlog(Max(Ai))).
B. Array Reconstructing
justHusam solution: https://ideone.com/IDqwCe
Complexity: O(N).
C. Large Summation
justHusam solution: https://ideone.com/1mSW7q
Vendetta. solution: https://ideone.com/V2wqJT
Complexity: O(NLog(N)).
D. Counting Test
justHusam solution: https://ideone.com/BbGc7w
Complexity: O(26N + Q).
E. Game of Dice
justHusam solution: https://ideone.com/pFtGym
Vendetta. solution: https://ideone.com/udraup
Complexity: .
Note: O(6N) gives TLE because 614 is approximately 78 × 109.
F. Strings and Queries
Sparse Table with Hashing solution: https://ideone.com/iVZNHd (Running Time: 1621 ms)
Segment Tree with Hashing solution: https://ideone.com/UPsA6o (Running Time: 2042 ms)
Complexity: O(NL2 + NLog(N) + Q(L + Log(N))).
Sparse Table with Trie solution: https://ideone.com/pn4haB (Running Time: 1716 ms)
Complexity: O(NL2 + NLog(N) + NL + QL).
Note: You don't need to worry about collision in hashing since you don't need to use at all, the max hash value will be 430 which is approximately 1018 which fits into long long
.
G. Magical Indices
justHusam solution: https://ideone.com/9SzqJb
Complexity: O(N).
H. Corrupted Images
justHusam solution: https://ideone.com/wS5TPl
Complexity: O(NM).
I. The Crazy Jumper
justHusam solutions:
BFS: https://ideone.com/P2yACH
DP top-down: https://ideone.com/UnBst5
DP buttom-up: https://ideone.com/ysugUh
Complexity: O(N).
J. The Hell Boy
Vendetta. solutions:
Math: https://ideone.com/rYmHOD
DP: https://ideone.com/IDWlkQ
Complexity: O(N).
K. Palindromes Building
justHusam next_permutation
solution: https://ideone.com/zaXvKc
Complexity: .
Note: O(N!) gives TLE because 20! is approximately 2.4 × 1018.
Vendetta. math solution: https://ideone.com/0BNI2r
Complexity: O(N).