Vendetta.'s blog

By Vendetta., history, 6 years ago, In English

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.

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

| Write comment?
»
6 years 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).

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Why is the following approach wrong for problem D. Help Conan?
1) Let d(i, j) denote the shortest path between two nodes i and j in the original graph.
2) Build a new weighted graph consisting of only important nodes and weight between two nodes i and j to be d(i, j).
3) Find MST of this new graph.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    Test Case

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

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Does that work with the test cases?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just read your comment sorry for the late response, you are using arrays of size 2 × 104 instead of 2 × 105, thus you access memory out of the array which is leading to Run Time Error.