[Gym] 2018 JUST Programming Contest 1.0 — editorial

Revision en1, by Vendetta., 2018-04-18 10:07:52

### A. Will he Die?

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5

Vendetta. solution: https://ideone.com/N8WC9O
justHusam solution: https://ideone.com/oAPb42
Complexity: O(N) for pre-calculating factorials and per test case for the multiplicative inverse.

### B. Ran and the Lock Code

Hint 1
Hint 2
Hint 3

Vendetta. solution: https://ideone.com/0fdUbN
Complexity: per test case where M is the complexity to do multiplication for large numbers in Python.

### C. Professor Agasa Lab

Hint 1
Hint 2

Vendetta. solution: https://ideone.com/Vz5u8p
Complexity: for pre-calculating totient and O(1) per test case.
justHusam solution 1: https://ideone.com/yXLv7v
justHusam solution 2: https://ideone.com/s4EdLm

### D. Help Conan

Hint 1
Hint 2
Hint 3

Vendetta. solution: https://ideone.com/g6gcKd
Complexity: O(2N × N) per test case.
Complexity: O(2N × M) for the other slower solution per test case.
justHusam solution: https://ideone.com/uXfZUV (A bit different solution)

### E. Rescue Haibara

Hint 1

Vendetta. solution: https://ideone.com/bF0axw
justHusam solution: https://ideone.com/LxK1PD
Complexity: O(N) per test case.

### F. Median and Queries

Hint 1
Hint 2
Hint 3

Vendetta. solution: https://ideone.com/3EZ1SY
Complexity: per test case: O(N2 × Max(Ai)) for construction and O(Max(Ai)) per query.
justHusam solution: https://ideone.com/WEkeVH
Complexity: per test case: O(N2 × Max(Ai)) for construction and per query.

### G. Preparing for Exams

Hint 1
Hint 2
Hint 3

Vendetta. solution: https://ideone.com/yKYgb9
justHusam solution 1: https://ideone.com/u8xofZ
justHusam solution 2: https://ideone.com/XNvyX9
Complexity: per test case since sqrt(x) complexity is .

### H. Genta Game

Hint 1

Vendetta. solution: https://ideone.com/C6X94O
justHusam solution: https://ideone.com/YYrF7f
Complexity: O(1) per query.

### I. UEFA Champions League

Hint 1

Vendetta. solution: https://ideone.com/NWtBvZ
justHusam solution: https://ideone.com/c7m35z
Complexity: O(1) per test case.

Hint 1
Hint 2

Vendetta. solution: https://ideone.com/bLV0UI
Complexity: O(Max(gn)) per test case where gn is the nth prime gap.

### K. Conan and Scoreboard

Hint 1

Vendetta. solution: https://ideone.com/0bLR7c
Complexity: per test case.
justHusam solution: https://ideone.com/aBKduB
Complexity: per test case.

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 Vendetta. 2018-04-18 11:40:10 0 (published)
en2 Vendetta. 2018-04-18 10:55:24 165 (saved to drafts)
en1 Vendetta. 2018-04-18 10:07:52 9643 Initial revision (published)