### A. Will he Die?↵
↵
<spoiler summary="Hint 1">↵
Due to symmetry, the answer of `n m` is equal to the answer of `-n m`, so work with the absolute value of $n$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
We are looking for the probability of starting at position $0$ and ending at $n$ positions to the right, using $m$ moves.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
A move goes to Right with probability $\frac{1}{2}$ and Left with probability $\frac{1}{2}$, we can imagine we have a binary string of instructions of length $m$ (executed one by one), where $0$ means go left and $1$ means go right. because of this discrete uniform distribution, every unique binary string of length $m$ will have a probability of $\frac{1}{2^m}$ as we have $2^m$ different strings.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
So the answer will be the number of such strings that $x-y=n$ where $x$ is the number of $1$'s and $y$ is the number of $0$'s, with some work on paper you can find that $x=n+\frac{m-n}{2}$. Now the probability will be $\frac{mCx}{2^m}$ where $mCx$ means $m$ Choose $x$.↵
You can handle the output format using the multiplicative inverse.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
If $m-n$ is odd or negative then the answer is 0.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/N8WC9O <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/oAPb42 <br/>↵
**Complexity:** $O(N)$ for pre-calculating factorials and $O(\log{N})$ per test case for the multiplicative inverse.↵
↵
### B. Ran and the Lock Code↵
↵
<spoiler summary="Hint 1">↵
We need $n$ numbers that sums up to $n \times a$ so that their average is equal to $a$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
To choose the numbers to be the most distinct, we want to include as many smaller distinct number as possible so we will take numbers: 1, 2, 3 ..., $x$ so that their summation is $n \times a$, we can find $x$ using Binary Search. <br/>↵
Why is it better to choose smaller numbers? because if we replace a small number with a bigger number, then we get closer to $n \times a$ thus less chances to use more distinct numbers.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
A problem arise when there is no summation from 1 to $x$ that is equal to $n \times a$, so we choose a summation less than $n \times a$, and what's left will be equal to $n \times a - \frac{ x \times (x+1) }{2}$ which will be distributed on $n-x$ unused numbers (because we already used $x$ numbers). <br/>↵
So at least we can give each of the $n-x$ numbers a value of 1 since values must be positive, so $n \times a - \frac{ x \times (x+1) }{2}$ must be at least equal to $n-x$ which will be our Binary Search condition which makes $x$ a valid answer.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/VNyo8h <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/KChjCF <br/>↵
**Complexity:** $O(\log{N})$ per test case.↵
↵
### C. Professor Agasa Lab↵
↵
<spoiler summary="Hint 1">↵
The answer is the number of possible values for $a$ multiplied by the number of possible values for $b$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
We can see that we can use any value for $b$ from $1$ to $m-1$, thus $m-1$ possible values for $b$, as for $a$, we can only use a value $x$ that has a multiplicative inverse in respect to the module $m$ which means $x$ and $m$ are co-primes, and the number of positive numbers co-primes with $m$ less than $m$ are calculated using the totient function. so the final answer is $(m-1)\timesTotient(m)$.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/Vz5u8p <br/>↵
**Complexity:** $O(N \log{( \log{N} )})$ for pre-calculating totient and $O(1)$ per test case. <br/>↵
[user:justHusam,2018-04-14] solution 1: https://ideone.com/yXLv7v <br/>↵
[user:justHusam,2018-04-14] solution 2: https://ideone.com/s4EdLm↵
↵
↵
### D. Help Conan↵
↵
<spoiler summary="Hint 1">↵
Since the number of nodes are so low, you can work on all different subsets of nodes.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
One solution is a minimization Dynamic Programming, with state holding only a mask telling which nodes are already included in the spanning tree, and try to include any un-included node that can connect directly to one of the included nodes until all the important nodes are in the tree. ↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Another slower solution is to find all the subsets of nodes that include all the important nodes, and do an MST for each of them and take the minimum.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/g6gcKd <br/>↵
**Complexity:** $O(2^{N} \times N)$ per test case. <br/>↵
**Complexity:** $O(2^{N} \times M)$ for the other slower solution per test case. <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/uXfZUV (A bit different solution) <br/>↵
↵
### E. Rescue Haibara↵
↵
<spoiler summary="Hint 1">↵
Minimize when the condition mentioned in the statement applies :)↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/bF0axw <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/LxK1PD <br/>↵
**Complexity:** $O(N)$ per test case.↵
↵
### F. Median and Queries↵
↵
<spoiler summary="Hint 1">↵
Since values are small, as well as the grid size, we can make a frequency array for every cell in a grid and make a 2D cumulative summation on every frequency array, this way we can get the frequency of a number in the sub-rectangle in $O(1)$. ↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
For every query, loop over each number from 1 to 500 and find its frequency in that sub-rectangle, as we count the sum of the frequencies we know the median is at the element that makes the sum exceed half the size of the rectangle.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
The solution above gets AC, but to make the solution faster, we can do a cumulative summation on the frequency arrays so then we can binary search the point where the sum exceeds half the size of the sub-rectangle instead of looping over them.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/3EZ1SY <br/>↵
**Complexity:** per test case: $O(N^2\timesMax(A_i))$ for construction and $O(Max(A_i))$ per query. <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/WEkeVH <br/>↵
**Complexity:** per test case: $O(N^2\timesMax(A_i))$ for construction and $O(\log{(Max(A_i))})$ per query.↵
↵
↵
### G. Preparing for Exams↵
↵
<spoiler summary="Hint 1">↵
Notice that $abcd$ is a cyclic quadrilateral, which means its vertices all lie on a single circle.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
A property for cyclic quadrilateral is that its opposite angles are supplementary.↵
https://en.wikipedia.org/wiki/Cyclic_quadrilateral#Characterizations↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
With some work on paper we can find that the 2 triangles which areas are given are similar, thus the similarity ratio can be calculated using the areas: $\sqrt{ \frac{A_1}{A_2} }$, from which we can find $\overline{oa}$ and $\overline{ob}$ then $x$ and $y$.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/yKYgb9 <br/>↵
[user:justHusam,2018-04-14] solution 1: https://ideone.com/u8xofZ <br/>↵
[user:justHusam,2018-04-14] solution 2: https://ideone.com/XNvyX9 <br/>↵
**Complexity:** $O(\log{L} + \log{K} )$ per test case since $sqrt(x)$ complexity is $\log{x}$.↵
↵
### H. Genta Game↵
↵
<spoiler summary="Hint 1">↵
Keep track of the number of different opposite characters, and at the end of each query add 1 to the answer if the number of different opposite characters is zero.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/C6X94O <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/YYrF7f <br/>↵
**Complexity:** $O(1)$ per query.↵
↵
### I. UEFA Champions League↵
↵
<spoiler summary="Hint 1">↵
Read problem statement carefully to handle the cases where both teams have the same number of goals overall.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/NWtBvZ <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/c7m35z <br/>↵
**Complexity:** $O(1)$ per test case.↵
↵
### J. Gin Passwords↵
↵
<spoiler summary="Hint 1">↵
You can solve this problem by brute forcing on the numbers from $b$ down to $a$ until you find a solution, this solution is valid and won't cause a Time Limit Exceeded.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Why no TLE? because the biggest gap between any 2 consecutive 9 digits primes (half of the given number) is less than $320$, so at most you will loop 320 times and find the second half of the number to be a prime and the GCD between a prime and any other number is 1, unless the other number is a multiple of that prime. but even if it is, the next prime number below that will work because if the first half is a multiple of both primes then it can't only be 9 digits (must be 18 digits if both primes are 9 digits).↵
https://en.wikipedia.org/wiki/Prime_gap#Numerical_results ↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/bLV0UI <br/>↵
**Complexity:** $O(Max(g_n))$ per test case where $g_n$ is the $n^{th}$ prime gap.↵
↵
### K. Conan and Scoreboard↵
↵
<spoiler summary="Hint 1">↵
Show me your implementation powers :P↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/0bLR7c <br/>↵
**Complexity:** $O( N \times M + K \log{K})$ per test case. <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/aBKduB <br/>↵
**Complexity:** $O(N + K \log{K})$ per test case.↵
↵
<spoiler summary="Hint 1">↵
Due to symmetry, the answer of `n m` is equal to the answer of `-n m`, so work with the absolute value of $n$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
We are looking for the probability of starting at position $0$ and ending at $n$ positions to the right, using $m$ moves.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
A move goes to Right with probability $\frac{1}{2}$ and Left with probability $\frac{1}{2}$, we can imagine we have a binary string of instructions of length $m$ (executed one by one), where $0$ means go left and $1$ means go right. because of this discrete uniform distribution, every unique binary string of length $m$ will have a probability of $\frac{1}{2^m}$ as we have $2^m$ different strings.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
So the answer will be the number of such strings that $x-y=n$ where $x$ is the number of $1$'s and $y$ is the number of $0$'s, with some work on paper you can find that $x=n+\frac{m-n}{2}$. Now the probability will be $\frac{mCx}{2^m}$ where $mCx$ means $m$ Choose $x$.↵
You can handle the output format using the multiplicative inverse.↵
</spoiler>↵
↵
<spoiler summary="Hint 5">↵
If $m-n$ is odd or negative then the answer is 0.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/N8WC9O <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/oAPb42 <br/>↵
**Complexity:** $O(N)$ for pre-calculating factorials and $O(\log{N})$ per test case for the multiplicative inverse.↵
↵
### B. Ran and the Lock Code↵
↵
<spoiler summary="Hint 1">↵
We need $n$ numbers that sums up to $n \times a$ so that their average is equal to $a$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
To choose the numbers to be the most distinct, we want to include as many smaller distinct number as possible so we will take numbers: 1, 2, 3 ..., $x$ so that their summation is $n \times a$, we can find $x$ using Binary Search. <br/>↵
Why is it better to choose smaller numbers? because if we replace a small number with a bigger number, then we get closer to $n \times a$ thus less chances to use more distinct numbers.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
A problem arise when there is no summation from 1 to $x$ that is equal to $n \times a$, so we choose a summation less than $n \times a$, and what's left will be equal to $n \times a - \frac{ x \times (x+1) }{2}$ which will be distributed on $n-x$ unused numbers (because we already used $x$ numbers). <br/>↵
So at least we can give each of the $n-x$ numbers a value of 1 since values must be positive, so $n \times a - \frac{ x \times (x+1) }{2}$ must be at least equal to $n-x$ which will be our Binary Search condition which makes $x$ a valid answer.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/VNyo8h <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/KChjCF <br/>↵
**Complexity:** $O(\log{N})$ per test case.↵
↵
### C. Professor Agasa Lab↵
↵
<spoiler summary="Hint 1">↵
The answer is the number of possible values for $a$ multiplied by the number of possible values for $b$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
We can see that we can use any value for $b$ from $1$ to $m-1$, thus $m-1$ possible values for $b$, as for $a$, we can only use a value $x$ that has a multiplicative inverse in respect to the module $m$ which means $x$ and $m$ are co-primes, and the number of positive numbers co-primes with $m$ less than $m$ are calculated using the totient function. so the final answer is $(m-1)\timesTotient(m)$.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/Vz5u8p <br/>↵
**Complexity:** $O(N \log{( \log{N} )})$ for pre-calculating totient and $O(1)$ per test case. <br/>↵
[user:justHusam,2018-04-14] solution 1: https://ideone.com/yXLv7v <br/>↵
[user:justHusam,2018-04-14] solution 2: https://ideone.com/s4EdLm↵
↵
↵
### D. Help Conan↵
↵
<spoiler summary="Hint 1">↵
Since the number of nodes are so low, you can work on all different subsets of nodes.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
One solution is a minimization Dynamic Programming, with state holding only a mask telling which nodes are already included in the spanning tree, and try to include any un-included node that can connect directly to one of the included nodes until all the important nodes are in the tree. ↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Another slower solution is to find all the subsets of nodes that include all the important nodes, and do an MST for each of them and take the minimum.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/g6gcKd <br/>↵
**Complexity:** $O(2^{N} \times N)$ per test case. <br/>↵
**Complexity:** $O(2^{N} \times M)$ for the other slower solution per test case. <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/uXfZUV (A bit different solution) <br/>↵
↵
### E. Rescue Haibara↵
↵
<spoiler summary="Hint 1">↵
Minimize when the condition mentioned in the statement applies :)↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/bF0axw <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/LxK1PD <br/>↵
**Complexity:** $O(N)$ per test case.↵
↵
### F. Median and Queries↵
↵
<spoiler summary="Hint 1">↵
Since values are small, as well as the grid size, we can make a frequency array for every cell in a grid and make a 2D cumulative summation on every frequency array, this way we can get the frequency of a number in the sub-rectangle in $O(1)$. ↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
For every query, loop over each number from 1 to 500 and find its frequency in that sub-rectangle, as we count the sum of the frequencies we know the median is at the element that makes the sum exceed half the size of the rectangle.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
The solution above gets AC, but to make the solution faster, we can do a cumulative summation on the frequency arrays so then we can binary search the point where the sum exceeds half the size of the sub-rectangle instead of looping over them.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/3EZ1SY <br/>↵
**Complexity:** per test case: $O(N^2\timesMax(A_i))$ for construction and $O(Max(A_i))$ per query. <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/WEkeVH <br/>↵
**Complexity:** per test case: $O(N^2\timesMax(A_i))$ for construction and $O(\log{(Max(A_i))})$ per query.↵
↵
↵
### G. Preparing for Exams↵
↵
<spoiler summary="Hint 1">↵
Notice that $abcd$ is a cyclic quadrilateral, which means its vertices all lie on a single circle.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
A property for cyclic quadrilateral is that its opposite angles are supplementary.↵
https://en.wikipedia.org/wiki/Cyclic_quadrilateral#Characterizations↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
With some work on paper we can find that the 2 triangles which areas are given are similar, thus the similarity ratio can be calculated using the areas: $\sqrt{ \frac{A_1}{A_2} }$, from which we can find $\overline{oa}$ and $\overline{ob}$ then $x$ and $y$.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/yKYgb9 <br/>↵
[user:justHusam,2018-04-14] solution 1: https://ideone.com/u8xofZ <br/>↵
[user:justHusam,2018-04-14] solution 2: https://ideone.com/XNvyX9 <br/>↵
**Complexity:** $O(\log{L} + \log{K} )$ per test case since $sqrt(x)$ complexity is $\log{x}$.↵
↵
### H. Genta Game↵
↵
<spoiler summary="Hint 1">↵
Keep track of the number of different opposite characters, and at the end of each query add 1 to the answer if the number of different opposite characters is zero.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/C6X94O <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/YYrF7f <br/>↵
**Complexity:** $O(1)$ per query.↵
↵
### I. UEFA Champions League↵
↵
<spoiler summary="Hint 1">↵
Read problem statement carefully to handle the cases where both teams have the same number of goals overall.↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/NWtBvZ <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/c7m35z <br/>↵
**Complexity:** $O(1)$ per test case.↵
↵
### J. Gin Passwords↵
↵
<spoiler summary="Hint 1">↵
You can solve this problem by brute forcing on the numbers from $b$ down to $a$ until you find a solution, this solution is valid and won't cause a Time Limit Exceeded.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Why no TLE? because the biggest gap between any 2 consecutive 9 digits primes (half of the given number) is less than $320$, so at most you will loop 320 times and find the second half of the number to be a prime and the GCD between a prime and any other number is 1, unless the other number is a multiple of that prime. but even if it is, the next prime number below that will work because if the first half is a multiple of both primes then it can't only be 9 digits (must be 18 digits if both primes are 9 digits).↵
https://en.wikipedia.org/wiki/Prime_gap#Numerical_results ↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/bLV0UI <br/>↵
**Complexity:** $O(Max(g_n))$ per test case where $g_n$ is the $n^{th}$ prime gap.↵
↵
### K. Conan and Scoreboard↵
↵
<spoiler summary="Hint 1">↵
Show me your implementation powers :P↵
</spoiler>↵
↵
[user:Vendetta.,2018-04-14] solution: https://ideone.com/0bLR7c <br/>↵
**Complexity:** $O( N \times M + K \log{K})$ per test case. <br/>↵
[user:justHusam,2018-04-14] solution: https://ideone.com/aBKduB <br/>↵
**Complexity:** $O(N + K \log{K})$ per test case.↵
