Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

[Gym] 2017 JUST Programming Contest 4.0 — editorial

Revision en2, by Vendetta., 2018-03-13 17:46:13

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Vendetta. 2018-03-13 17:46:13 1 Tiny change: 'frac{N}{2})$. <br/>\' -> 'frac{N}{2}!)$. <br/>\'
en1 English Vendetta. 2017-09-29 18:35:23 9656 Initial revision (published)