[Gym] 2018 JUST Programming Contest 1.0 — editorial

Revision en3, by Vendetta., 2018-04-18 11:40:10

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/VNyo8h
justHusam solution: https://ideone.com/KChjCF
Complexity: per test case.

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.

J. Gin Passwords

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 English Vendetta. 2018-04-18 11:40:10 0 (published)
en2 English Vendetta. 2018-04-18 10:55:24 165 (saved to drafts)
en1 English Vendetta. 2018-04-18 10:07:52 9643 Initial revision (published)