# Tag Info

Accepted

### Arrays. Find row with most 1's, in O(n)

Below is an algorithm which runs in $\mathcal{O}(1)$ memory and $\mathcal{O}(n)$ time. It accepts a $n \times n$ matrix $A$ which is $1$-indexed, follows the constraint described in the problem, and ...
• 391

### Arrays. Find row with most 1's, in O(n)

Hint: If the first row has k 1s, and the second row has k’ 1s, then there is no need to determine k’ at all if k’ <= k. How do you find in O(1) that k’ <= k? And if k’ > k, which you checked ...
• 30.7k
Accepted

### Approximation algorithm for binary (linear) programs

As pointed out here (Are there practical methods for solving ILP?), there are some usefullness to form your problem as an ILP and directly give that to a solver. There are multiple ways to tackle an ...
• 1,467
Accepted

• 391

### What does "computer steps" mean in this runtime definition?

“Computer steps” has intentionally no precise definition. This is usually about execution time, and we assume that every computer has a constant time T, which is different for every computer, and each ...
• 30.7k

### How is the prefix function (for KMP) time complexity O(N)?

I figured it out. j never goes negative and it increases by at most n times. Thus the while loop (which always decreases j) will run a lifetime total of not more than n times.
• 324
1 vote

### Mapping spherical coordinates onto faces of an icosahedron

I have done quite a bit in this area - and will share the repo when I am finished. But for the specific question above, I think a good approach is to use a KDTree. Here is the set of face-centres of ...
• 33
1 vote
Accepted

### MSOL for a vertex-cover enlargement problem

You can use CMSOL which allows cardinality predicates. See 5.2.6 in this report. This is authored by Courcelle himself. You can refer the original paper by Courcelle too, but it is a bit more terse. ...
• 402

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