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
0 votes
3 answers
595 views

Find the best staircase to maximize the sum

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,770
1 vote
1 answer
506 views

Find the optimum circle in an infinite grid

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,770
4 votes
2 answers
310 views

Maximum pentagon sum

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,770
0 votes
2 answers
218 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
560 views

Finding the optimal straight line boundary

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,770
6 votes
4 answers
600 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
552 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,770
6 votes
3 answers
506 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,770
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
17 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
229 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
386 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
338 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
592 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
  • 97.7k
2 votes
0 answers
359 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
  • 97.7k
7 votes
2 answers
476 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
337 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
198 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
657 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
377 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
569 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
152 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
419 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
232 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
462 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
558 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
295 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
292 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
318 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
339 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
462 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
  • 235
2 votes
1 answer
651 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
201 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
704 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
  • 22.3k
-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
516 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,821
13 votes
3 answers
580 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
955 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
140 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
13 votes
2 answers
781 views

Total Derangement (Difficulty Level: Hard)

The problem: Write a function which, given a cycle length n and a number of cycles m, where 'm' is within ...
Alecto Irene Perez's user avatar
5 votes
0 answers
293 views

Solve a Single Player Tron Game [closed]

Solve a Tron Game Tron is a great game, and if you haven't played it the internet has MANY online versions available. A fun challenge is to try to write an AI that plays Tron, which is normally much ...
ATaco's user avatar
  • 10.8k