Creative Snap
Contest: CodeCraft-19 and Codeforces Round 537 (Div. 2)
Difficulty rating: 1700
Tags: binary search, brute force, divide and conquer, math

Thanos wants to destroy the avengers base, but he needs to destroy the avengers along with their base.

Let we represent their base with an array, where each position can be occupied by many avengers, but one avenger can occupy only one position. Length of their base is a perfect power of $$$2$$$. Thanos wants to destroy the base using minimum power. He starts with the whole base and in one step he can do either of following:

- if the current length is at least $$$2$$$, divide the base into $$$2$$$ equal halves and destroy them separately, or
- burn the current base. If it contains no avenger in it, it takes $$$A$$$ amount of power, otherwise it takes his $$$B \cdot n_a \cdot l$$$ amount of power, where $$$n_a$$$ is the number of avengers and $$$l$$$ is the length of the current base.

Input format:
The first line contains four integers $$$n$$$, $$$k$$$, $$$A$$$ and $$$B$$$ ($$$1 \leq n \leq 30$$$, $$$1 \leq k \leq 10^5$$$, $$$1 \leq A,B \leq 10^4$$$), where $$$2^n$$$ is the length of the base, $$$k$$$ is the number of avengers and $$$A$$$ and $$$B$$$ are the constants explained in the question.

The second line contains $$$k$$$ integers $$$a_{1}, a_{2}, a_{3}, \ldots, a_{k}$$$ ($$$1 \leq a_{i} \leq 2^n$$$), where $$$a_{i}$$$ represents the position of avenger in the base.

Output format:
Output one integer — the minimum power needed to destroy the avengers base.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Consider the first example.

One option for Thanos is to burn the whole base $$$1-4$$$ with power $$$2 \cdot 2 \cdot 4 = 16$$$.

Otherwise he can divide the base into two parts $$$1-2$$$ and $$$3-4$$$.

For base $$$1-2$$$, he can either burn it with power $$$2 \cdot 1 \cdot 2 = 4$$$ or divide it into $$$2$$$ parts $$$1-1$$$ and $$$2-2$$$.

For base $$$1-1$$$, he can burn it with power $$$2 \cdot 1 \cdot 1 = 2$$$. For $$$2-2$$$, he can destroy it with power $$$1$$$, as there are no avengers. So, the total power for destroying $$$1-2$$$ is $$$2 + 1 = 3$$$, which is less than $$$4$$$.

Similarly, he needs $$$3$$$ power to destroy $$$3-4$$$. The total minimum power needed is $$$6$$$.

Example input:
2 2 1 2
1 3

Example output:
6

Example input:
3 2 1 2
1 7

Example output:
8

Editorial:
Make a recursive function rec($$$l,r$$$) where l and r are start and end indexes of subarray to be considered. Start with $$$l=1$$$ and $$$r=2^n$$$. If there is no avenger in l to r return A (power consumed). Else either power consumed to burn it directly is $$$b*x*len$$$ (where x is number of avengers in l to r and len is length of array ($$$r-l+1$$$) ) or by dividing the array is the result of recursion($$$l,mid$$$) + recursion($$$mid+1,r$$$) where $$$mid=(l+r)/2$$$. Return the minimum power consumed. If l is equal to r then do not go into recursion further, return power consumed according to first operation. One thing is remaining, the value of x, given l and r. Sort the array containing indices of avengers and then find positions of l and r in that array using binary search. Difference is positions of l and r in array will give x. Time Complexity : $$$O(n*k*log(k))$$$. Explanation : Reaching any subarray will take maximum of n operations and we can have maximum k subarrays (each having one avenger), it will take $$$O(n*k)$$$. $$$O(log(k))$$$ time needed for binary search (calculating x). So net complexity is $$$O(n*k*log(k))$$$.