Vendetta.'s blog

By Vendetta., history, 8 months ago, In English,

A. Subarrays Beauty

Hint 1
Hint 2
Hint 3

justHusam solution: https://ideone.com/PL7s1U
Vendetta. solution: https://ideone.com/23iukT
Complexity: O(Nlog(Max(Ai))).

B. Array Reconstructing

Hint 1

justHusam solution: https://ideone.com/IDqwCe
Complexity: O(N).

C. Large Summation

Hint 1
Hint 2

justHusam solution: https://ideone.com/1mSW7q
Vendetta. solution: https://ideone.com/V2wqJT
Complexity: O(NLog(N)).

D. Counting Test

Hint 1
Hint 2
Hint 3

justHusam solution: https://ideone.com/BbGc7w
Complexity: O(26N + Q).

E. Game of Dice

Hint 1
Hint 2
Hint 3

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

Hint 1
Hint 2
Hint 3

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

Hint 1
Hint 2

justHusam solution: https://ideone.com/9SzqJb
Complexity: O(N).

H. Corrupted Images

Hint 1
Hint 2
Hint 3

justHusam solution: https://ideone.com/wS5TPl
Complexity: O(NM).

I. The Crazy Jumper

Solution 1
Solution 2

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

Solution 1
Solution 2

Vendetta. solutions:
Math: https://ideone.com/rYmHOD
DP: https://ideone.com/IDWlkQ
Complexity: O(N).

K. Palindromes Building

Hint 1
Hint 2
Hint 3

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).

 
 
 
 
  • Vote: I like it  
  • +32
  • Vote: I do not like it  

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in Problem k i use next_permutation for half string and i get ac 33950913

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Vendetta. (previous revision, new revision, compare).