Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

New answers tagged

3

Consider $n$ axis-parallel squares of equal size shifted along the line $y = x$ such that the bottom-left corners of the squares all fit within the first square. E.g. for $n = 4$: Then you have $2(n - 1)$ external intersection points but $(n-1)(n-2)$ internal ones (and thus $n(n-1)$ total).


0

W.l.o.g. assume the integers are ordered such that $x_1 \geq \cdots \geq x_n$. @Laakeri presented an algorithm for finding a partition $(A,B)$ that satisfies: $\sum_B + x_1 \geq \sum_A \geq \sum_B - x_1$ His algorithm can be used to finding a partition that satisfies the stronger condition: $\sum_B + \max_{A} \geq \sum_A \geq \sum_B - \max_{B}$ The ...


1

My paper (Reducing 3SUM to Convolution-3SUM, to be published in SOSA 2020) studied a relevant version of your problem. Basically the result we get is we can solve 3SUMx1 deterministically with the same deterministic running time as for 3SUMx3. (However this does not directly give any results in your oracle description.)


3

There is an $O(n \log n)$ algorithm for this problem. To formalize, lets say that the task is to partition $n$ given integers into two partitions $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. Denote the maximum integer with $M$ and the sums of integers in $A$ and $B$ with $\sum_A$ and $\sum_B$. The partitions should satisfy that $|\...


0

Keys are uniformly distributed means that they are drawn from a space with equal probability. So if we set the hash function to be $h(k)=\lfloor{km}\rfloor$, then each given element is equally likely to hash into any of the $m$ slots. (Refer to the definition of simple uniform hashing in page 259 CLRS) Yes, it is true that each element with key $k$ will be ...


4

There are several issues with your question but perhaps I can clarify some issues. First off you assume $f(1) = 1.999...$ and also that no $x \in \mathbb{N}$ exists such that $f(x) = 2$ but that's a contradiction in terms because $1.999... = 2$ and thus $f(1) = 2$. Why does $1.999... = 2$? Well there's an easy answer but not fulfilling answer and a more ...


0

Hint: $A \land \lnot A$ is always False, no matter whether $A$ is True or False.


0

First you can write down the truth table of your circuit, in this case it will be entirely composed of $0$s. Then you will build up a Boolean expression in the form you prefer (if you have no limitations) which reproduces the behavior (relation input/output) observed in the truth table. Note that every operator of your boolean expression correspond to a ...


Top 50 recent answers are included