Tag Info

Hot answers tagged

3

As you say, $C(j)=1$ iff there is a $k<j$ such that $C(k)=1$ and $\operatorname{dict}(a_{k+1}\ldots a_j)=1$. This is the case iff there is a $k<j$ such that $C(k)\operatorname{dict}(a_{k+1}\ldots a_j)=1$. That product is always $0$ or $1$, so $$C(j)=\max_{0\le k<j}\big(C(k)\operatorname{dict}(a_{k+1}\ldots a_j)\big)\;,$$ where we define $C(0)=1$. ...


2

If $A$ has $n$ elements, $B$ has $m$ elements, $p$ are just in $B$, then $m-p$ are in both; and $n-(m-p)$ are just in $A$.


1

The answer is no - the complexity class $\mathcal P$ consists of all problems that can be solved in polynomial time. In other words, a problem $P$ is in $\mathcal P$ if $$P(n) \in \bigcup_{k=1}^\infty O\left(n^k\right). $$ Suppose $f$ is a function defined on the positive integers with $f(n)\in O(n^k)$ for some $k>1$, but $f(n)\notin O(n^j)$ for $j<k$. ...


1

Let $(a, b,c)$ be the cities your algorithm finds. Let $(u,v,w)$ be an optimal solution (also ordered by decreasing population). Claim. $z_a=z_u$. Proof. Assume otherwise. Then $z_a>z_u\ge z_v\ge z_w$ and $(a,v,w)$ would be strictly better, which is absurd; hence $a,v,w$ are collinear. But then $(u,a,w)$ would be strictly better than $(u,v,w)$, qea. ...


1

Managed to find an answer that fits and seems to work: if $x_i \neq y_j$ then $d(i,j)=min(d(i-1,j)+1,d(i,j-1)+1,d(i-1,j-1)+2)$ and if $x_i=y_j$ then $d(i,j)=min(d(i-1,j)+1,d(i,j-1)+1,d(i-1,j-1))$



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