Skip to main content

Questions tagged [fastest-algorithm]

Fastest-algorithm competitions are won by the answer with the smallest asymptotic time complexity. For challenges based on actual runtime, use [fastest-code] instead.

Filter by
Sorted by
Tagged with
3 votes
7 answers
287 views

Find the most isolated point

Given two non-empty sets of points \$P,T = \{(x,y)\ |\ x,y \in \mathbb{Z} \}\$, find the point \$p \in P\$ such that it is the "most isolated" from all points in \$T\$. The "most ...
bigyihsuan's user avatar
  • 9,706
5 votes
1 answer
289 views

Dishonest dungeon staff

This is a joint post with https://puzzling.stackexchange.com/questions/126255/dishonest-dungeon-staff You are faced with the difficult task to set up a dungeon for adventurers. However you made a deal ...
Fluorine's user avatar
  • 151
1 vote
4 answers
639 views

How to optimize rectilinear borders

Given an \$n \times n\$ matrix of integers, The task is to find the optimal dividing line that maximizes the sum of the integers on the same side as the top left corner. The dividing line should be ...
Simd's user avatar
  • 2,936
1 vote
1 answer
546 views

Where to put a circle?

Consider an \$n \times n\$ grid of integers which is part of an infinite grid. The top left coordinate of the \$n \times n\$ grid of integers is \$(0, 0)\$. The task is to find a circle which when ...
Simd's user avatar
  • 2,936
4 votes
2 answers
355 views

Optimizing polygon

For this problem you are given an \$n \times n\$ matrix of integers. The task is to find a pentagon in the matrix with maximum sum. The pentagon must include part (or all) of the x and y axes as two ...
Simd's user avatar
  • 2,936
0 votes
2 answers
221 views

Smashing Dominoes [closed]

Challenge This challenge is based on the domino effect: Initially, each domino is located on one straight line and is in a vertical state. It can be dropped either to the left along the same straight ...
Michael's user avatar
  • 11
4 votes
1 answer
596 views

Which line is best?

Consider an \$n \times n\$ grid of integers. The task is to draw a straight line across the grid so that the part that includes the top left corner sums to the largest number possible. Here is a ...
Simd's user avatar
  • 2,936
6 votes
4 answers
610 views

Sum of the sum of all possible subsets raised to power k

You are given an array A of non-negative integers. You can pick any non-empty subset, S from the array A. The score of a subset S is the sum of the elements in S raised to the power of K, i.e. for a ...
chere 01's user avatar
1 vote
2 answers
557 views

Compute how many are no larger than each item in an array

Input: an array of length \$n\$ containing integers in the range \$0\$ to \$2n\$. For each integer \$x\$ in the array, compute the number of integers that occur before \$x\$ that are no larger than \$...
Simd's user avatar
  • 2,936
6 votes
3 answers
521 views

Pick a random string at a fixed edit distance

I have string \$s\$ of length \$n\$ and some constant integer \$k\$ which is at most \$n\$. Give the fastest algorithm to sample a random string with Levenshtein distance \$k\$ from \$s\$ uniformly. ...
Simd's user avatar
  • 2,936
11 votes
11 answers
1k views

(Robbers) Fast and Golfiest Season 1: The Lord of the Strings

Fast and Golfiest Robbers Thread Welcome to the first season of Fast and Golfiest, a cops-and-robbers challenge! I designed this challenge to encourage competitive coding for efficiency (fastest ...
Shiran Yuan's user avatar
18 votes
15 answers
1k views

(Cops) Fast and Golfiest Season 1: The Lord of the Strings

Fast and Golfiest Cops Thread Welcome to the first season of Fast and Golfiest, a cops-and-robbers challenge! I designed this challenge to encourage competitive coding for efficiency (fastest ...
Shiran Yuan's user avatar
0 votes
0 answers
233 views

How to efficiently count all powers of 2 in a given set of numbers in vb.net?

Every integer can be expressed in powers of 2. You know this as the binary system Assume you are given a set of k numbers (...
aludebe's user avatar
  • 17
7 votes
6 answers
387 views

Bumping Series Implementation

I have a follow-up question here from my previous question on Math SE. I am lazy enough to explain the content again, so I have used a paraphraser to explain it below: I was considering arbitrary ...
Aitzaz Imtiaz's user avatar
5 votes
3 answers
357 views

Minimum Cut finder

Write a program that takes an undirected graph and finds the minimum cut, i.e., the set of edges that, if removed, would disconnect the graph into two or more connected components. The program should ...
user avatar
9 votes
4 answers
597 views

RADD decomposition of an integer

Introduction The \$RADD(n)\$ operation is defined as the sum of \$n + [\$ the number whose decimal representation are the decimal digits of \$n\$ in reverse order \$]\$, see A004086. After reversal, ...
Hugo Pfoertner's user avatar
16 votes
1 answer
374 views

Best partitioning set

Given an array of \$n\$ positive integers we will say its self-sum order is the number of ways to add elements from it to make \$n\$. We will count ways as distinct up to associativity. So \$1+(2+3)\$...
Wheat Wizard's user avatar
  • 98.8k
2 votes
0 answers
372 views

Decompose number N into the sum of three triangular numbers [closed]

It is known that any natural number can be decomposed into the sum of three triangular numbers (assuming 0 is triangular), according to Fermat's Polygonal Number Theorem. Your task is to come up with ...
Study's user avatar
  • 45
7 votes
1 answer
238 views

Find run ascending lists faster

In this question I asked you to determine if a run ascending list could be made. It was code-golf so naturally most the answers are very slow. But what if we want it to be fast. In this challenge I ...
Wheat Wizard's user avatar
  • 98.8k
7 votes
2 answers
480 views

NxM List Combination Closest to Target

Given a list of N lists, each containing M positive integers, and a separate list of M positive integers (target values), return a list of N scalars (integers with a value of 0 or more) that ...
drmosley's user avatar
  • 757
10 votes
1 answer
340 views

Counting overlapping objects

Consider a NxN pixel grid with up to M objects drawn on it, either squares or diamonds: square    diamond The objects may overlap, so recognition is hard. The task is to give the minimal possible ...
Hans-Peter Stricker's user avatar
-2 votes
1 answer
201 views

Print all digits of an integer [duplicate]

Challenge Given a positive integer, find the fastest way to iterate over its digits. Bytecode size doesn't matter as much as speed of execution. Examples For 6875, the program would output ...
Paul Razvan Berg's user avatar
9 votes
5 answers
664 views

Edit distance where a substitution only costs the first time

This challenge is about the following variant of edit distance. Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter ...
user avatar
12 votes
1 answer
378 views

Leon's shooting range problem

Leon's story Leon is a professional sling shooter and he comes to a shooting range everyday to practice. A casual target is not a challenge for him anymore so before shooting he first covers the ...
Elgirhath's user avatar
  • 740
13 votes
3 answers
571 views

How much weight can you lift?

With all the gyms closed down with the COVID-19 situation, we have to exercise with the weight we have lying around at home. The problem is, we have a small selection of plates at varying weights, and ...
Josue Espinosa's user avatar
1 vote
0 answers
156 views

Minimum Hop Count in Directed Graph based on Conditional Statement [closed]

A directed graph G is given with Vertices V and Edges E, representing train stations and unidirectional train routes respectively. Trains of different train numbers move in between pairs of Vertices ...
Viswa's user avatar
  • 173
13 votes
1 answer
420 views

Gossipping ladies

Problem description Vertices \$V\$ of directed graph \$G=(V,E)\$ represent gossipping ladies; edge \$(u,v) \in E\$ signifies that lady \$u\$ knows of lady \$v\$ (which does not imply that lady \$v\$ ...
kyrill's user avatar
  • 615
4 votes
2 answers
235 views

How many ways can given subsequence occur in given sequence?

Let me know if this task has already been posed. I haven't found it when I looked. Input master sequence \$\ X = x_1\dots x_n\$: sequence of characters, eg. \$\rm international\$ subsequence \$\ Y = ...
kyrill's user avatar
  • 615
3 votes
1 answer
478 views

Gaussian integer division reminder [closed]

Gaussian integer is a complex number in the form \$x+yi\$, where \$x,y\$ are integer and \$i^2=-1\$. The task is to perform such operation for Gaussian integers \$a,b\$, that \$a=q \cdot b+r\$ and \$|...
Alexey Burdin's user avatar
5 votes
2 answers
560 views

Highest cardinality grouping of contiguous integers with minimum-sum threshold

Challenge Given an array of positive integers and a threshold, the algorithm should output a set of consecutive-element-groupings (subarrays) such that each group/subarray has a sum greater than the ...
Mike Ponemariko's user avatar
11 votes
1 answer
299 views

Compute my Sacred Geometry [closed]

In the tabletop RPG named Pathfinder, there is a feat that characters can take called Sacred Geometry, which allows a character who has it to buff their spells in exchange for doing some math: to use ...
nick012000's user avatar
2 votes
0 answers
108 views

Total time to deteriorate all shielded cells [closed]

Problem: We have a two dimensional matrix of positive integer cells. On each turn any non-zero cell with a neighbor (top/bottom/left/right) of zero decreases by 1. We want count to the number of non-...
LFA's user avatar
  • 21
-7 votes
4 answers
294 views

Is this number a palindrome? [closed]

Input A single integer in your language's preferred format, e.g int or an array of digits are all acceptable. Output A truthy or falsely value, depending on ...
Geza Kerecsenyi's user avatar
23 votes
23 answers
4k views

Upside-Down Pyramid Addition...REVERSED! [closed]

Upside-Down Pyramid Addition is the process of taking a list of numbers and consecutively adding them together until you reach one number. When given the numbers ...
Whimpers's user avatar
  • 355
6 votes
0 answers
319 views

Minimum cost of solving the Eni-Puzzle

You're tasked with writing an algorithm to efficiently estimate cost of solving an Eni-Puzzle from a scrambled state as follows: You're given m lists of containing n elements each(representing the ...
Conor James Thomas Warford Hen's user avatar
6 votes
2 answers
340 views

Buy the most appropriate items

A store is having a big sale. If your price reaches $199 or more, you can reduce it by $100. You can buy each product only once. Here's an example list of products: (in order to simplify, the names of ...
Saber's user avatar
  • 173
3 votes
0 answers
112 views

determine if the circle is boxed in [closed]

Pretty simple challenge here. Who can make the fastest algorithm (lowest time complexity) to determine whether or not the circle is "boxed in" given the following setup? Input: Your program receives ...
sam-pyt's user avatar
  • 131
4 votes
1 answer
463 views

Meeting splitter

Introduction Large meetings waste working time. Our aim is to split a large meeting into a number of smaller meetings, so the average number topics that a person discusses is minimized but every ...
Konrad Höffner's user avatar
-3 votes
2 answers
1k views

Fastest way to perform the equivalent of an if-statement in x86 assembly

The task is simple: Create an if-statement from scratch in x86 assembly that runs in as few clock-cycles as possible. Must be x86 assembly. Can't use any of the conditional jump/branch instructions (...
Lance's user avatar
  • 245
2 votes
1 answer
657 views

Two Dimensional Waterflow problem [closed]

The one dimensional twitter waterflow problem is this: You are given an array that represents a hill in the sense that the ith entry is the height of the ith location of the hill. When it rains, ...
Agnishom Chattopadhyay's user avatar
1 vote
0 answers
202 views

3-inverter with two NOT gates [closed]

Introduction I recently came across an oral exam where the candidates were asked to find a logical circuit than can negate 3 inputs A,B,C using only two NOT gates. ...
John Do's user avatar
  • 111
5 votes
1 answer
367 views

Find elements in an array computing a given function value

Problem Description Given: a function \$f(a, b, c, d, e) = \frac{a \times b}c + \frac de\$ an array \$x = [x_1, x_2, x_3, x_4, ..., x_n]\$ of non-distinct integers a target value \$k\$ What is the ...
versatile parsley's user avatar
3 votes
3 answers
705 views

Which number is bigger?

Define f(a,b) := a if b=1; a^f(a,b-1) if b>1 (Tetration, where ^ means power) for positive integers ...
l4m2's user avatar
  • 24.5k
-2 votes
1 answer
231 views

Find the longest uninterrupted arc in N dimensions

See similar question for 2D case: Find the longest uninterrupted arc The challenge here is to find the longest uninterruped great circle arc around a unit hypersphere in N dimensions, with a random ...
F Chopin's user avatar
  • 269
11 votes
5 answers
519 views

Find the longest uninterrupted arc

The challenge here is to find the longest uninterruped arc around a unit circle with a random amount of points distributed in random positions around it. Here is a diagram to assist my explanation: ...
F Chopin's user avatar
  • 269
-2 votes
3 answers
334 views

Fastest to find the joint

The input is an array (or space-separated string, as you wish), zero-indexed, consisting of one strictly increasing array and one strictly decreasing array (in this order, not other vice versa), each ...
nicael's user avatar
  • 4,811
13 votes
3 answers
583 views

Remove entries from array to sort it and maximize sum of elements

This challenge is from an admission test to a closed number cyber security course. Anyway it doesn't have to do with cyber security, it's just to test the students logical and coding skills. Task ...
Marco's user avatar
  • 251
9 votes
3 answers
958 views

Approximate floating point number with n-digit precision

We have a floating point number r between 0 and 1, and an integer p. Find the fraction of integers with the smallest ...
peterh's user avatar
  • 357
3 votes
1 answer
1k views

remove duplicates from array [closed]

You have given an array from which we need to remove duplicates. Rules: First or immediate duplicates gets removed first. Array contains natural numbers ...
Satish Patel's user avatar
6 votes
2 answers
141 views

Find the rectangle [closed]

Overview Given a 2 dimensional array of values with a filled in rectangle, find the position and size of the rectangle. Do it in the fewest array accesses as possible. Requirements The ...
Daffy's user avatar
  • 1,065