The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

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

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|\} ... 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 qs 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

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