note:g18wa7y2

This is a list of problems recently discussed on ##algorithms which (probably) allow better solutions. The stated complexity usually comes with no guarantee.

𝟏.
Assume you are given a sequence of $N$ prizes of positive values $A,\ldots A[N]$; additionally, every prize is designated as either type A'' or type B''. You are to choose at most $M$ prizes of maximal total value subject to the following condition: every chosen prize of type A precedes (has smaller index in $A$ than) every chosen prize of type B. ($M$ may be parametrically smaller than $N$.)
𝘊𝘶𝘳𝘳𝘦𝘯𝘵 𝘳𝘦𝘴𝘶𝘭𝘵: $O(N \log M)$.

𝟐.
For a set $\{S_1,\ldots S_N\}$ of $N$ subsets of $\{1,2,\ldots N\}$ determine if it contains two disjoint subsets $S_i\cap S_j= \emptyset$.
𝘊𝘶𝘳𝘳𝘦𝘯𝘵 𝘳𝘦𝘴𝘶𝘭𝘵: $O(N^{2.373})$.

𝟑.
Let $A$ be an integer array of length $N$ and $K$ a given integer. What is the maximal length of a contiguous subarray $X=A[p:q]$ such that every element of $X$ occurs in $X$ at least $K$ times?
𝘊𝘶𝘳𝘳𝘦𝘯𝘵 𝘳𝘦𝘴𝘶𝘭𝘵: $O(N \log N)$, 𝘣𝘶𝘵 𝘴𝘪𝘮𝘱𝘭𝘦𝘳 𝘢𝘭𝘨𝘰𝘳𝘪𝘵𝘩𝘮𝘴 𝘰𝘧 𝘵𝘩𝘦 𝘴𝘢𝘮𝘦 𝘤𝘰𝘮𝘱𝘭𝘦𝘹𝘪𝘵𝘺 𝘸𝘦𝘭𝘤𝘰𝘮𝘦.

𝟒.
Let $G=(V,E)$ be a sparse directed acyclic graph with $V=N$ vertices, $E=O(N)$. Find a topological ordering of $G$ (if $(u,v)\in E$, then $u$ comes before $v$) such that $\max_{v\in V} f(v,i(v))$ is minimized, where $i(v)$ is the index of $v$ in the ordering, and $f(v,t)$ is a given function (cost to process $v$ at time $t$), monotonically increasing in $t$.
𝘊𝘶𝘳𝘳𝘦𝘯𝘵 𝘳𝘦𝘴𝘶𝘭𝘵: $O(N \log^2N)$.

𝟓.
You are given a set of $N$ strings of length $M$ each from a given alphabet $A$ of $|A|=K$ symbols. Output a minimal cardinality set of strings with characters from $A\cup{*}$ such that expanding every $*$ as a single-character wildcard (say, $0{*}2{*}$ for $A=\{0,1,2\}$ turns into 9 words) you obtain the initial set.
𝘊𝘶𝘳𝘳𝘦𝘯𝘵 𝘳𝘦𝘴𝘶𝘭𝘵: $O(NM^2)$ 𝘸𝘰𝘳𝘴𝘵 𝘤𝘢𝘴𝘦, $O(NM)$ 𝘦𝘹𝘱𝘦𝘤𝘵𝘦𝘥.

𝟔.
Let $A$ be a permutation of $\{1,2,\ldots N\}$, and $B$ an array of $N$ non-negative integers. Is there a polynomial algorithm that constructs a braid where $k$-th thread ends in position $A[k]$ and participates in $B[k]$ intersections on the way (or outputs impossible'' if no such braid exists)?
The picture at
$\qquad\qquad$http://bit.ly/2cIldiC
is a solution for $A=(2,1,3,4)$ and $B=(3,1,2,4)$.
𝘊𝘶𝘳𝘳𝘦𝘯𝘵 𝘳𝘦𝘴𝘶𝘭𝘵: ?

𝟕.
Let $S$ be a multiset of $N$ integers with zero sum. Define $k(S)$ to be the maximal possible number of subsets in a partition of $S$ into subsets with zero sum each. What is the best $A$ such that we can find $k(S)$ in time $O^*(A^N)$?
𝘊𝘶𝘳𝘳𝘦𝘯𝘵 𝘳𝘦𝘴𝘶𝘭𝘵: $A=2$.

𝟖.
Let $A$ be an integer array of length $N$ sorted in non-decreasing order, and $g>0$ a given integer value. What is the minimal number of elements of $A$ that need to be changed so that $A$ remains non-decreasing but all pairs of neighboring elements have difference at least $g$?
𝘊𝘶𝘳𝘳𝘦𝘯𝘵 𝘳𝘦𝘴𝘶𝘭𝘵: $O(N^2)$.