### 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*(2^{N} × *N*) per test case.

**Complexity:** *O*(2^{N} × *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*(*N*^{2} × *Max*(*A*_{i})) for construction and *O*(*Max*(*A*_{i})) per query.

justHusam solution: https://ideone.com/WEkeVH

**Complexity:** per test case: *O*(*N*^{2} × *Max*(*A*_{i})) 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*(*g*_{n})) per test case where *g*_{n} is the *n*^{th} 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.

Auto comment: topic has been updated by Vendetta. (previous revision, new revision, compare).Why is the following approach wrong for problem D. Help Conan?

1) Let

d(i,j) denote the shortest path between two nodesiandjin the original graph.2) Build a new weighted graph consisting of only important nodes and weight between two nodes

iandjto bed(i,j).3) Find MST of this new graph.

That is an interesting solution, unfortunately it fails in cases like this:

Test CaseConsider 2, 3 and 4 to be important, the new shortest paths will be:

2 3 2

3 4 2

2 4 2

MST for that is to take any 2 edges which will be of cost 4, but if you take all the original edges in the graph the cost is 3.

The problem with this solution is you take same edges multiple times, thus get more than the optimal solution.

I think, with the problem B, we just calculate the min((a-1)*2 + 1, n) if a <= (10^9)/2 else we calculate the min((10^9-a)*2 + 1, n) ?? So that is O(1) solution.

Does that work with the test cases?

It will fail on this case:

`10 3`

because`min((3-1)*2+1, 10)`

is`5`

.But the optimal solution is

`6`

, example:`1 2 3 4 5 6 1 1 1 6`

.Hi Vendetta! Would you mind sharing test data for "A. Will he Die?"? I hit Runtime Error on server, but locally code works just fine (I even ran test with all possible inputs, -2e5 <= n <= 2e5, 0 <= m <= 2e5. Approach basically same like in editorials, except that instead of calculation of modulo inverse through Euler's totient function I used extended Euler's algorithm.

I just read your comment sorry for the late response, you are using arrays of size 2 × 10

^{4}instead of 2 × 10^{5}, thus you access memory out of the array which is leading to Run Time Error.Wow, thx ^^