### A. Subarrays Beauty↵
↵
<spoiler summary="Hint 1">↵
Consider each bit on its own since the AND operation is bit-wise.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
For each bit, notice that any sub-array that has a zero bit will add nothing to the answer.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
For each bit, A sub-array of only ones of length $X$ has $\frac{X \times (X+1)}{2}$ sub-array of only ones, and each of them will add $2^{W}$ where $W$ is the Weight of the bit to the answer.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/PL7s1U <br/>↵
[user:Vendetta.,2017-09-29] solution: https://ideone.com/23iukT <br/>↵
**Complexity:** $O(N log(Max(A_i)))$.↵
↵
### B. Array Reconstructing↵
↵
<spoiler summary="Hint 1">↵
You can construct the array from only one known element.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/IDqwCe <br/>↵
**Complexity:** $O(N)$.↵
↵
### C. Large Summation↵
↵
<spoiler summary="Hint 1">↵
All numbers are less than $10^9+7$, so the summation of any 2 numbers is either less than $10^9+7$ or less than $2 \times ( 10^9+7)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Sort the elements and for each element use binary search to handle each of the cases above to find the best answer.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/1mSW7q <br/>↵
[user:Vendetta.,2017-09-29] solution: https://ideone.com/V2wqJT <br/>↵
**Complexity:** $O(N Log(N))$.↵
↵
### D. Counting Test↵
↵
<spoiler summary="Hint 1">↵
To make things easier, use the following concept: Let's make a function $F(N)$ that finds the answer of range $[0, N]$, then the answer of range $[L, R]$ would be: $F(R) - F(L-1)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Make a frequency array of the original string then find how many times the string was repeated from $0$ to $N$, the number of times is $X = \lfloor \frac{N}{|S|} \rfloor$ where $|S|$ is the length of the original string.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
If $N \bmod |S|$ is not zero then we have $N \bmod |S|$ extra characters that doesn't make a full string, we can make 26 frequency arrays for each letter in alphabet and do a prefix sum to get the number of times a specific letter was repeated in the first $N \bmod |S|$ letters of the original string. ↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/BbGc7w <br/>↵
**Complexity:** $O(26 N + Q)$.↵
↵
### E. Game of Dice↵
↵
<spoiler summary="Hint 1">↵
Meet in the middle, divide the dice into 2 groups of equal sizes and brute force each part on it's own and store the $answers \bmod (10^9+7)$ in 2 vectors $V_1$, $V_2$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
For each element in $V_1$, we must find how many elements in $V_2$ satisfies the equality: ${V_1}_i \times {V_2}_j \bmod (10^9+7) = X$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Let's call the element from $V_1$ as $A$ and the element from $V_2$ as $B$ and we want to find the value of $B$: <br/>↵
$A \times B \equiv X \bmod (10^9+7)$. <br/>↵
multiply both sides by $\frac{1}{A}$: <br/>↵
$B \equiv X \times \frac{1}{A} \bmod (10^9+7)$. <br/>↵
where $\frac{1}{A}$ is the inverse of $A$ respective to the mod $10^9+7$. <br/>↵
Since all values of $V_2$ are below $10^9+7$, then there's only one value for $B$ in $V_2$ that satisfies the equality (because all values $B + K(10^9+7)$ satisfies the equality for any natural number $K$). <br/>↵
So we will calculate the value of $B$ and check how many times was it repeated in $V_2$.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/pFtGym <br/>↵
[user:Vendetta.,2017-09-29] solution: https://ideone.com/udraup <br/>↵
**Complexity:** $O(6^{\frac{N}{2}})$. <br/>↵
**Note:** $O(6^N)$ gives TLE because $6^{14}$ is approximately $78 \times 10^9$.↵
↵
### F. Strings and Queries↵
↵
<spoiler summary="Hint 1">↵
Find the number of palindrome sub-strings for each string, using an algorithm that runs worse than $O(L^{2})$ gives TLE where $L$ is the length of the string.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
The problem is now reduces to RMQ (Range Max Query), we can now use data structures like Sparse Table, Segment Tree ... but Sparse Table is preferred as it runs faster than Segment Tree.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
We still have a problem that the queries are given as strings not indices, to solve this we can map the strings to their indices, but using a map of strings will give TLE as the factor for comparing strings isn't small, to solve this was can use Hashing or Trie to get the index of the string fast. <br/>↵
Hashing will take $O(L + log(N))$ per query to hash and look for the hash value in a map of hash values. <br/>↵
Trie will take only $O(L)$ per query to track the string in the Trie, but Trie needs pre-construction of $O(LN)$.↵
</spoiler>↵
↵
Sparse Table with Hashing solution: https://ideone.com/iVZNHd (Running Time: 1621 ms) <br/>↵
Segment Tree with Hashing solution: https://ideone.com/UPsA6o (Running Time: 2042 ms) <br/>↵
**Complexity:** $O(NL^2 + N Log(N) + Q(L + Log(N)))$. <br/>↵
Sparse Table with Trie solution: https://ideone.com/pn4haB (Running Time: 1716 ms) <br/>↵
**Complexity:** $O(NL^2 + N Log(N) + NL + QL)$. <br/>↵
**Note:** You don't need to worry about collision in hashing since you don't need to use $\bmod$ at all, the max hash value will be $4^{30}$ which is approximately $10^18$ which fits into `long long`.↵
↵
### G. Magical Indices↵
↵
<spoiler summary="Hint 1">↵
Construct 2 arrays, $MX$ and $MN$ where $MX_i$ is the maximum value in the range $[1, i]$ and $MN_i$ is the minimum value in range $[i, N]$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
For each element $X$, if the max value before it is less than $X$ and the min value after it is more than $X$ then add one to the answer.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/9SzqJb <br/>↵
**Complexity:** $O(N)$.↵
↵
### H. Corrupted Images↵
↵
<spoiler summary="Hint 1">↵
Count the number of ones on the border, let's call it $Y$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
There are total of $X = N+N+M+M-4$ border cells, the answer is $X - Y$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
There is no solution when the total number of ones in the whole image is less than $X$, then we can't cover the whole border with ones.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/wS5TPl <br/>↵
**Complexity:** $O(NM)$.↵
↵
### I. The Crazy Jumper↵
↵
<spoiler summary="Solution 1">↵
Construct a graph, add edge from cell $i$ to cell $i+1$ and from cell $i$ to cell $j$ where cell $j$ has same color of cell $i$ and there are no cells between $i$ and $j$ that also have the same color.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
Using dynamic programming $dp_i = 1 + min(dp_{i+1}, dp_{next_i})$, try to jump to the next cell or to the first call that has the same color.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solutions: <br/>↵
BFS: https://ideone.com/P2yACH <br/>↵
DP top-down: https://ideone.com/UnBst5 <br/>↵
DP buttom-up: https://ideone.com/ysugUh <br/>↵
**Complexity:** $O(N)$.↵
↵
### J. The Hell Boy↵
↵
<spoiler summary="Solution 1">↵
To be able to find this solution, you need to work on a paper, let's suppose we want to find the answer for 3 numbers, $A$ $B$ and $C$. <br/>↵
The terms of those 3 will be: <br/>↵
$A + B + C + AB + AC + BC + ABC$ <br/>↵
Take $C$ as a common factor from the terms that has $C$: <br/>↵
$A + B + AB + C( 1 + A + B + AB)$ <br/>↵
Notice that if $X = A + B + AB$ then: <br/>↵
$X + C(1 + X)$ <br/>↵
Now take B as a common factor as well: <br/>↵
$A + B(1 + A) + C(1 + A + B(1 + A))$ <br/>↵
Suppose the answer for the problem is $X$, we can notice that if we add a new number $Y$, the answer will be $X + Y(1 + X)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
Using dynamic programming, $dp_i = dp_{i+1} + A_i \times dp_{i+1}$, the DP tries to either take the element or not, we will have to subtract 1 from the answer as the DP will consider the empty sub-set as valid sub-set which will add one to the wanted answer.↵
</spoiler>↵
↵
[user:Vendetta.,2017-09-29] solutions: <br/>↵
Math: https://ideone.com/rYmHOD <br/>↵
DP: https://ideone.com/IDWlkQ <br/>↵
**Complexity:** $O(N)$.↵
↵
### K. Palindromes Building↵
↵
<spoiler summary="Hint 1">↵
If there are more than one letter with odd frequency then we can't make any palindromes.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Since the limits are too small, we can brute force and build all the palindromes, since the first half of the palindrome is the same as the second half but reversed, we can only generate all the palindromes by generating the first half only, make a string containing half of the frequency for each letter in the original string and use `next_permutation` to check how many different permutations you can get.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
There's also another faster solution if the constraints were bigger, to know how many different ways we form a string using half of the letters to make the first half of the palindrome, the answer will be: $\frac{N}{2}!$, to eliminate the repeated permutations we divide by the factorial of half of the frequencies for each letter, basic counting math. ↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] `next_permutation` solution: https://ideone.com/zaXvKc <br/>↵
**Complexity:** $O(\frac{N}{2}!)$. <br/>↵
**Note:** $O(N!)$ gives TLE because $20!$ is approximately $2.4 \times 10^18$. <br/>↵
[user:Vendetta.,2017-09-29] math solution: https://ideone.com/0BNI2r <br/>↵
**Complexity:** $O(N)$.
↵
<spoiler summary="Hint 1">↵
Consider each bit on its own since the AND operation is bit-wise.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
For each bit, notice that any sub-array that has a zero bit will add nothing to the answer.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
For each bit, A sub-array of only ones of length $X$ has $\frac{X \times (X+1)}{2}$ sub-array of only ones, and each of them will add $2^{W}$ where $W$ is the Weight of the bit to the answer.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/PL7s1U <br/>↵
[user:Vendetta.,2017-09-29] solution: https://ideone.com/23iukT <br/>↵
**Complexity:** $O(N log(Max(A_i)))$.↵
↵
### B. Array Reconstructing↵
↵
<spoiler summary="Hint 1">↵
You can construct the array from only one known element.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/IDqwCe <br/>↵
**Complexity:** $O(N)$.↵
↵
### C. Large Summation↵
↵
<spoiler summary="Hint 1">↵
All numbers are less than $10^9+7$, so the summation of any 2 numbers is either less than $10^9+7$ or less than $2 \times ( 10^9+7)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Sort the elements and for each element use binary search to handle each of the cases above to find the best answer.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/1mSW7q <br/>↵
[user:Vendetta.,2017-09-29] solution: https://ideone.com/V2wqJT <br/>↵
**Complexity:** $O(N Log(N))$.↵
↵
### D. Counting Test↵
↵
<spoiler summary="Hint 1">↵
To make things easier, use the following concept: Let's make a function $F(N)$ that finds the answer of range $[0, N]$, then the answer of range $[L, R]$ would be: $F(R) - F(L-1)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Make a frequency array of the original string then find how many times the string was repeated from $0$ to $N$, the number of times is $X = \lfloor \frac{N}{|S|} \rfloor$ where $|S|$ is the length of the original string.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
If $N \bmod |S|$ is not zero then we have $N \bmod |S|$ extra characters that doesn't make a full string, we can make 26 frequency arrays for each letter in alphabet and do a prefix sum to get the number of times a specific letter was repeated in the first $N \bmod |S|$ letters of the original string. ↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/BbGc7w <br/>↵
**Complexity:** $O(26 N + Q)$.↵
↵
### E. Game of Dice↵
↵
<spoiler summary="Hint 1">↵
Meet in the middle, divide the dice into 2 groups of equal sizes and brute force each part on it's own and store the $answers \bmod (10^9+7)$ in 2 vectors $V_1$, $V_2$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
For each element in $V_1$, we must find how many elements in $V_2$ satisfies the equality: ${V_1}_i \times {V_2}_j \bmod (10^9+7) = X$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Let's call the element from $V_1$ as $A$ and the element from $V_2$ as $B$ and we want to find the value of $B$: <br/>↵
$A \times B \equiv X \bmod (10^9+7)$. <br/>↵
multiply both sides by $\frac{1}{A}$: <br/>↵
$B \equiv X \times \frac{1}{A} \bmod (10^9+7)$. <br/>↵
where $\frac{1}{A}$ is the inverse of $A$ respective to the mod $10^9+7$. <br/>↵
Since all values of $V_2$ are below $10^9+7$, then there's only one value for $B$ in $V_2$ that satisfies the equality (because all values $B + K(10^9+7)$ satisfies the equality for any natural number $K$). <br/>↵
So we will calculate the value of $B$ and check how many times was it repeated in $V_2$.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/pFtGym <br/>↵
[user:Vendetta.,2017-09-29] solution: https://ideone.com/udraup <br/>↵
**Complexity:** $O(6^{\frac{N}{2}})$. <br/>↵
**Note:** $O(6^N)$ gives TLE because $6^{14}$ is approximately $78 \times 10^9$.↵
↵
### F. Strings and Queries↵
↵
<spoiler summary="Hint 1">↵
Find the number of palindrome sub-strings for each string, using an algorithm that runs worse than $O(L^{2})$ gives TLE where $L$ is the length of the string.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
The problem is now reduces to RMQ (Range Max Query), we can now use data structures like Sparse Table, Segment Tree ... but Sparse Table is preferred as it runs faster than Segment Tree.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
We still have a problem that the queries are given as strings not indices, to solve this we can map the strings to their indices, but using a map of strings will give TLE as the factor for comparing strings isn't small, to solve this was can use Hashing or Trie to get the index of the string fast. <br/>↵
Hashing will take $O(L + log(N))$ per query to hash and look for the hash value in a map of hash values. <br/>↵
Trie will take only $O(L)$ per query to track the string in the Trie, but Trie needs pre-construction of $O(LN)$.↵
</spoiler>↵
↵
Sparse Table with Hashing solution: https://ideone.com/iVZNHd (Running Time: 1621 ms) <br/>↵
Segment Tree with Hashing solution: https://ideone.com/UPsA6o (Running Time: 2042 ms) <br/>↵
**Complexity:** $O(NL^2 + N Log(N) + Q(L + Log(N)))$. <br/>↵
Sparse Table with Trie solution: https://ideone.com/pn4haB (Running Time: 1716 ms) <br/>↵
**Complexity:** $O(NL^2 + N Log(N) + NL + QL)$. <br/>↵
**Note:** You don't need to worry about collision in hashing since you don't need to use $\bmod$ at all, the max hash value will be $4^{30}$ which is approximately $10^18$ which fits into `long long`.↵
↵
### G. Magical Indices↵
↵
<spoiler summary="Hint 1">↵
Construct 2 arrays, $MX$ and $MN$ where $MX_i$ is the maximum value in the range $[1, i]$ and $MN_i$ is the minimum value in range $[i, N]$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
For each element $X$, if the max value before it is less than $X$ and the min value after it is more than $X$ then add one to the answer.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/9SzqJb <br/>↵
**Complexity:** $O(N)$.↵
↵
### H. Corrupted Images↵
↵
<spoiler summary="Hint 1">↵
Count the number of ones on the border, let's call it $Y$.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
There are total of $X = N+N+M+M-4$ border cells, the answer is $X - Y$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
There is no solution when the total number of ones in the whole image is less than $X$, then we can't cover the whole border with ones.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solution: https://ideone.com/wS5TPl <br/>↵
**Complexity:** $O(NM)$.↵
↵
### I. The Crazy Jumper↵
↵
<spoiler summary="Solution 1">↵
Construct a graph, add edge from cell $i$ to cell $i+1$ and from cell $i$ to cell $j$ where cell $j$ has same color of cell $i$ and there are no cells between $i$ and $j$ that also have the same color.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
Using dynamic programming $dp_i = 1 + min(dp_{i+1}, dp_{next_i})$, try to jump to the next cell or to the first call that has the same color.↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] solutions: <br/>↵
BFS: https://ideone.com/P2yACH <br/>↵
DP top-down: https://ideone.com/UnBst5 <br/>↵
DP buttom-up: https://ideone.com/ysugUh <br/>↵
**Complexity:** $O(N)$.↵
↵
### J. The Hell Boy↵
↵
<spoiler summary="Solution 1">↵
To be able to find this solution, you need to work on a paper, let's suppose we want to find the answer for 3 numbers, $A$ $B$ and $C$. <br/>↵
The terms of those 3 will be: <br/>↵
$A + B + C + AB + AC + BC + ABC$ <br/>↵
Take $C$ as a common factor from the terms that has $C$: <br/>↵
$A + B + AB + C( 1 + A + B + AB)$ <br/>↵
Notice that if $X = A + B + AB$ then: <br/>↵
$X + C(1 + X)$ <br/>↵
Now take B as a common factor as well: <br/>↵
$A + B(1 + A) + C(1 + A + B(1 + A))$ <br/>↵
Suppose the answer for the problem is $X$, we can notice that if we add a new number $Y$, the answer will be $X + Y(1 + X)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
Using dynamic programming, $dp_i = dp_{i+1} + A_i \times dp_{i+1}$, the DP tries to either take the element or not, we will have to subtract 1 from the answer as the DP will consider the empty sub-set as valid sub-set which will add one to the wanted answer.↵
</spoiler>↵
↵
[user:Vendetta.,2017-09-29] solutions: <br/>↵
Math: https://ideone.com/rYmHOD <br/>↵
DP: https://ideone.com/IDWlkQ <br/>↵
**Complexity:** $O(N)$.↵
↵
### K. Palindromes Building↵
↵
<spoiler summary="Hint 1">↵
If there are more than one letter with odd frequency then we can't make any palindromes.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Since the limits are too small, we can brute force and build all the palindromes, since the first half of the palindrome is the same as the second half but reversed, we can only generate all the palindromes by generating the first half only, make a string containing half of the frequency for each letter in the original string and use `next_permutation` to check how many different permutations you can get.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
There's also another faster solution if the constraints were bigger, to know how many different ways we form a string using half of the letters to make the first half of the palindrome, the answer will be: $\frac{N}{2}!$, to eliminate the repeated permutations we divide by the factorial of half of the frequencies for each letter, basic counting math. ↵
</spoiler>↵
↵
[user:justHusam,2017-09-29] `next_permutation` solution: https://ideone.com/zaXvKc <br/>↵
**Complexity:** $O(\frac{N}{2}!)$. <br/>↵
**Note:** $O(N!)$ gives TLE because $20!$ is approximately $2.4 \times 10^18$. <br/>↵
[user:Vendetta.,2017-09-29] math solution: https://ideone.com/0BNI2r <br/>↵
**Complexity:** $O(N)$.
