4

If $k>N$, this cannot be done (as $\forall p_1,\dots, p_k\geq 0,\sum_{i=1}^k 2^{p_i}\geq k>N$) If $k\leq N$: Write $N$ in binary, and denote by $n$ the number of $1$s. We have written $N$ as a sum of $n$ powers of two (which happen to all be distinct). If $n\leq k$, then you can always split some of the powers of two (iteratively if needed) in order ...


4

As an exercise to the reader, two lemmas: Lemma 1. If $a, b$ are strings of symbols with a partial order, and $\text{numinv}$ counts the number of inversions in a string of symbols then $$\text{numinv}(ab) = \text{numinv}(a) + \text{numinv}(b) + \text{crossinv}(a, b)$$ where $$\text{crossinv}(a, b) = |\{(i,j) \in \{1,\dots,|a|\}\times\{1,\dots,|b|\} ...


4

This is only a sketch of solution (there might be some off-by-ones) Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and ...


2

For every $i \in \{0,\ldots,n\}$ (where $n$ is the length of the array) and for every $a,b,c \in \{0,\ldots,15\}$, we determine whether it is possible to partition the first $i$ elements of the array into four subsets, the first three of which XOR to $a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for $i = n$, we can ...


2

Note that $\lceil \log(2^n) \rceil = n$. An algorithm that uses $n$ bits to represent the set would be fine (it would count as a succinct data structure). An algorithm that uses $n + 2 \sqrt{n}$ bits would also be fine. An algorithm that uses $2n$ bits to represent the set would not be fine (it would not count as a succinct data structure). Similarly, an ...


2

Any line can be represented in the form $\{p + xv : x \in \mathbb{R}\}$, or in other words, by a point $p$ on the line and a vector $v$ parallel to the line. Without loss of generality, we can take $v$ to have norm 1 (if not, replace $v$ with $v/\|v\|_2$). Also, if we ignore lines where the $z$-component of $v$ is zero, then without loss of generality we ...


2

For this problem I recommend to solve first for trees with simpler structures that can be generalized afterwards with data structures that run on top of trees (there are plenty of them). Let's build an idea of what are the dynamics of the problem before jumping to the answer. We have the array A = [N0, N1, N2, N3]. An let's say after each second numbers at ...


1

What you ask is impossible, assuming you don't really mean sets (as sets are orderless), but ordered tuples. Consider $j=2$, then you effectively have $k$-length binary strings. And those require $\Omega(k)$ storage.


1

I think of divisibility mostly in terms of decomposition into prime factors: to be divisible by a query integer $q$, an integer $a_i$ has to be divisible by at least the same power of each prime in $q$s decomposition. Divisibility by different primes is independent: I think of this (divisibility of integers from a set that can be preprocessed) as a ...


1

Your attempt runs into a huge problem with the input [1, 2, $2^{63}$]. Either your numbers are so small that it doesn’t matter. Otherwise, you start with a solution, find its speed and why it is slow, and then iteratively improve it. That’s usually a much better method than hoping that someone does the work for you. For this specific problem, I think ...


1

Since there are no updates there is a rather simple solution. Store a map of key -> array of pairs, such that for every element in your original vector (value, key) at position pos, you store in the vector associated with given key in the map the pair (position, value). Keep every vector sorted by position. For example in the input array: $$[(3, 1), (2, 3), ...


1

You could look at the answers to this question on SO: https://stackoverflow.com/questions/19372991/number-of-n-element-permutations-with-exactly-k-inversions (in particular the part about Mahonian numbers) Additionally, it seems that dynamic programming with memoisation runs in $\mathcal{O}(N\cdot k)$ [NB: I didn't actually check this, it's in one of the ...


1

1 For the first case, you had the right idea, but just had some algebra mistakes. for i=1..n j=1 while j*j <= i: j = j + 1 Let $T(n)$ be the time complexity. $$T(n) = \sum_{i=1}^n\sum_{j=1}^\sqrt{i}1\leq \sum_{i=1}^n\sqrt{n}=\leq n^{3/2}$$ $$= O(n^{3/2})$$ 2 I'm assuming you meant the pseudocode below since it is more analogous to ...


1

I won't go into the details of your specific case but try to answer the general problem. In the unrestricted case there is a mapping from each of the $n$ (=512) input states to one of 2 output states and you want to restrict the function as follows: Create a partitioning of the initial $n$ input states into subsets. Your adapted function maps each of these ...


1

Let $T$ be a tree rooted at $r$ with $n > 2$ leaves, and let $\ell(u)$ denote the number of leaves in the subtree of $T$ rooted at node $u$. Initially let $v=r$, then proceeds as follows: If $\ell(v) \le \frac{2n}{3}$ then return $v$. Otherwise, let $u$ be one of the children of $v$ with the largest $\ell(u)$, set $v=u$ and repeat from the first step. ...


1

Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates? No. In revision 8, it constructs a valid search tree on $y$. The check in step 2 will almost always yield not satisfied. The best I thought up, ignoring non-unique priority values: Proceed the complete binary search tree ...


1

Is there a way to make PST in O(N) The simple is answer is No. It will take a minimum $O(NlogN)$ time to construct the tree. Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates. No, the algorithm you mentioned will fail when you try to maintain the min-heap property based on $x-...


1

I don't think that it is possible to balance a tree in logarithmic time: An algorithm has to determine somehow, when it is finished In this case, establishing that the tree is balanced is necessary This operation alone is $\mathcal O(n)$ (count the height of left/right subtree) Therefore, $\mathcal O(n)$ will be a lower bound for your algorithm and there ...


1

Do an inorder traversal of the BST...and store it in an array the array will be sorted. next construct a balanced binary search tree from this array. 1) Get the Middle of the array and make it root. 2) Recursively do same for left half and right half. a) Get the middle of left half and make it left child of the root created in step 1. b) ...


1

Another possibility would be to store all the words in an array, sort it, and then do lookups on it using binary-search. Disadvantages compared to a Trie: Worse asymptotic time complexity for lookups ($O(\mathrm{log}\ n)$ average where n is the number of entries). Probably less efficient to insert additional entries, as the array will need to be resized. ...


Only top voted, non community-wiki answers of a minimum length are eligible