Pull to refresh
144.15

Algorithms *

Everything about algorithms

Show first
Rating limit
Level of difficulty

Why x^0 = 1 visually

Reading time3 min
Views1.1K

The traditional definition for the operation of exponentiation to a natural power (or a positive integer) had introduced approximately as follows:

Exponentiation is an arithmetic operation originally defined as the result of multiple multiplications a number by itself.

But the more precise formulation is still different:

Raising a number X to an integer power N is an arithmetic operation defined as the result of multiple [N by mod times] multiplications or divisions one by number X.

Let's figure it out under the cut! >>
Total votes 5: ↑5 and ↓0+5
Comments0

LeetCode, Hard++ (Acceptance 24%, Latest): 2867. Count Valid Paths in a Tree. DFS. O(n). Swift

Level of difficultyHard
Reading time2 min
Views1.6K

The intuition is to employ a depth-first search (DFS) approach through the tree.

During each step in the traversal, we perform the following key calculations:

1. Determine the path that ends at the current node.

2. Compute two different subtree paths that traverse the current node.

3. Maintain an array that keeps track of the cases where paths contain either 0 or 1 prime number.

This method allows us to efficiently count the valid paths in the tree while considering the presence of prime numbers.

Read more
Total votes 7: ↑2 and ↓5-1
Comments1

LeetCode, Hard: 2818. Apply Operations to Maximize Score. Swift

Level of difficultyHard
Reading time4 min
Views1.2K

Time complexityO(max(nums) * log(max(nums)) + n * log(n)). Accounting for computing prime scores, using the stack to compute next greater elements, and sorting the tuples.

Space complexityO(max(nums) + n). Considering the space required for arrays and the stack used for computation.

Read more
Total votes 2: ↑1 and ↓10
Comments1

LeetCode, Hard, last two problems: 2809. Min Time to Make Array Sum At Most x & 2813. Max Elegance of a K-Length Subseq

Level of difficultyHard
Reading time3 min
Views827

2809. Min Time to Make Array Sum: Efficient Swift solution, using dynamic programming, for minimizing time to reach a sum in arrays A and B. Time: O(n²), Space: O(n).

2813. Max Elegance of K-Length Subseq: Swift code for elegantly selecting unique k-length subsequences with profit and categories. Solution uses sorting and iteration. Time: O(nlogn), Space: O(n).

Github: https://github.com/sergeyleschev/leetcode-swift

Read more
Total votes 1: ↑1 and ↓0+1
Comments2

LeetCode 2532 (Hard++, Extra Category, Amazon). Time to Cross a Bridge. Swift solution

Level of difficultyHard
Reading time5 min
Views1.1K

Hard++, Extra Category.

Amazon.

Overflow checks have been taken into consideration. The maximum time to move a box is at most 4 * 1000 (four steps to move the box, each taking 1000 time). With at most 1e4 boxes, the total time is at most 4e7, ensuring the solution is safe.

Read more
Rating0
Comments0

LeetCode 2801 (Hard, Acceptance 14.5%). Count Stepping Numbers in Range. DP. Handles large inputs (10^9 + 7)

Level of difficultyMedium
Reading time3 min
Views701

Given two positive integers low and high represented as strings, find the count of stepping numbers in the inclusive range [low, high].

A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.

Return an integer denoting the count of stepping numbers in the inclusive range [low, high].

Since the answer may be very large, return it modulo 10^9 + 7.

Hard, Acceptance Level 14.5%.
Dynamic Programming (DP).
Efficiently handles large inputs (10^9 + 7).

Latest and Most Hardest Problem.

Read more
Rating0
Comments0

LeetCode 2790 (Hard). Maximum Number of Groups With Increasing Length. Solution of the day. O(N logN). Math

Level of difficultyMedium
Reading time3 min
Views1.2K

Simple Swift Math Solution.

Time complexity: O(N logN).

The time complexity of this solution is dominated by the sorting step, making it O(N logN), where N is the length of the input array usageLimits. The rest of the operations involve simple arithmetic and comparisons, which take linear time. Therefore, the overall time complexity of the function is O(NlogN).

Only 10 lines of code.

Read more
Rating0
Comments0

LeetCode 2612 (Hard). Minimum Reverse Operations. Swift. BFS. O(n+k). O(n)

Level of difficultyHard
Reading time3 min
Views1.5K

LeetCode 2612 (Hard). Minimum Reverse Operations.

The algorithm follows a breadth-first search (BFS) approach to determine the minimum number of reverse operations needed to bring the 1 to each position in the array.

To speed up the algorithm, we mark banned positions with -2 instead of using set lookups. This optimization reduces the constant coefficient and improves the speed of the algorithm, but it may still result in a time limit exceeded (TLE) error.

For each visited position, there are potentially O(k) target positions that can be reached through reverse operations. To avoid the multiplicative cost of iterating over all these potential positions, we update the nextNode2s array. This array initially points forward by 2, but we update it dynamically to point beyond all the target positions considered for each visited position. This optimization helps improve the efficiency of the algorithm and avoids unnecessary computations.

Read more
Total votes 2: ↑2 and ↓0+2
Comments0

LeetCode 956 (Hard). Solution of the day. Tallest Billboard. Swift. DP

Level of difficultyHard
Reading time2 min
Views2.3K

Solution of the day.
LeetCode 956 (Hard). Tallest Billboard.

The code uses dynamic programming to solve the problem. It maintains a dictionary dp, where the keys represent the possible height differences between the two billboards, and the values represent the maximum sum of heights achieved for each height difference.

Read more
Total votes 3: ↑2 and ↓1+2
Comments0

Hashing and its C++ applications

Level of difficultyMedium
Reading time6 min
Views4.8K

Hash, salt, SHA-1, SHA-2, std::hash.. To a non-programming person that may come up as some kind of a recipe that just does not seem to add up. In a sense, this is indeed supposed to be a gibberish to any third party and a strong, helpful mechanism for us, programmers. 

At the start of writing this article, I had one clear idea to get across the table: to finally unveil this mystery of hashing in C++ for beginners. I, a beginner myself, also wanted to solidify my knowledge in this area; so let’s get started.

Read more
Total votes 2: ↑2 and ↓0+2
Comments0

Affordable as a Bus, Comfortable as a Taxi: A Promising Type of Public Transport for Large and Medium-Sized Cities.Part3

Level of difficultyMedium
Reading time32 min
Views1.4K


Translation provided by ChatGPT, link to the original article in Russian

Link to Part 1: «Preliminary Analysis» (ру / eng )
Link to Part 2: «Experiments on a Torus» (ру / eng )
Link to Part 3: «Practically Significant Solutions» (ру / eng )
Link to «Summary» (ру / eng )

1 Playing Diplomacy


1.1 What this work is about


You're reading the third and final article in a series dedicated to minibus route schemes that would allow you to travel reasonably quickly, inexpensively, and most importantly, without any transfers, from any intersection to any other within a large city. You'll see many graphs, formulas, and figures below, but before we get to the technical part, I'd like to discuss the challenge of implementing this idea and invite you to participate in solving it.

1.2 A puzzle for the talented and brave (Eccentrics are welcome: ?)


I propose an adventure,
I propose a game,
I propose that you become part of a positive change in the lifestyle of almost a billion people around the planet,
I can't do this alone.
To start, I need your help with the following:
Read more →
Total votes 3: ↑2 and ↓1+2
Comments4

Affordable as a Bus, Comfortable as a Taxi: A Promising Type of Public Transport for Large and Medium-Sized Cities.Part2

Level of difficultyMedium
Reading time56 min
Views1.1K

(Jean-Claude Mézières)

Translation provided by ChatGPT, link to the original article in Russian

Link to Part 1: «Preliminary Analysis» (ру / eng )
Link to Part 2: «Experiments on a Torus» (ру / eng )
Link to Part 3: «Practically Significant Solutions» (ру / eng )
Link to «Summary» (ру / eng )

Experiments on the Torus


This is the second part of a study dedicated to exploring new public transportation movement schemes. In the first part, we examined the simplest non-stop scheme and a single-transfer scheme based on it, which can be implemented in a grid city on a plane. In this part, our city model will be a grid city on a «flat» torus. Unlike a rectangle, a torus has no edge, and the positions of all points on it are absolutely equivalent. Due to the absence of an edge and (transitive) symmetry, calculations for a toroidal city are simpler, and numerical results are nearly identical to those for a rectangular city on a plane. These two conditions make a toroidal grid city an ideal testing ground for new passenger transportation movement schemes. In this article, we will explore two such schemes on the torus, and in the next one, we will return to the plane and adapt the results obtained here for use under the realistic conditions of a rectangular city.

The content of this study is not standalone and presupposes familiarity with the first part of the article. To understand Chapter 2, you will need a level of mathematics that corresponds roughly to the first two years of university; for everything else, high school level should suffice. It can be helpful to have a pencil and a piece of paper at hand while reading. If your browser displays formulas incorrectly, try refreshing the page a few times.
Read more →
Total votes 3: ↑3 and ↓0+3
Comments0

Affordable as a Bus, Comfortable as a Taxi: A Promising Type of Public Transport for Large and Medium-Sized Cities.Part1

Level of difficultyMedium
Reading time40 min
Views1.9K

(Jean-Claude Mézières)

Translation provided by ChatGPT, link to the original article in Russian

Link to Part 1: «Preliminary Analysis» (ру / eng )
Link to Part 2: «Experiments on a Torus» (ру / eng )
Link to Part 3: «Practically Significant Solutions» (ру / eng )
Link to «Summary» (ру / eng )

1. About this series of articles


1.1 Central result


If I haven't made a critical mistake, I have discovered an astonishing passenger transportation scheme with unique characteristics. Imagine this scenario: you are in a big city and need to get from point A to point B. All you need to do is walk to the nearest intersection and indicate the destination on your smartphone or a special terminal installed there. In a few minutes, a small but spacious bus will arrive for you. The bus is designed for easy entry without bending, and you can bring a stroller, bicycle, or even a cello inside. It provides comfortable seating where you can stretch your legs. This bus will take you to the nearest intersection to point B, and you will reach your destination without any transfers. The entire journey, including waiting at the stop, will take only 25-50% more time than if you were traveling by private car. Based on my estimation, in modern metropolises, this type of transportation will be widely adopted, and the cost of a trip on such buses will be similar to the fare of a regular city bus.

Surprisingly, the reasoning behind these findings is based on relatively simple mathematics, and perhaps even a talented high school student, under fortunate circumstances, could have guessed them on their own. The practical significance of the topic and the modest level of mathematical requirements prompted me to make an effort to write the article in such a way that the reader could follow the path of discoveries, learn some research techniques, and gain a successful example to explain to their children the purpose of mathematics and how it can be applied in everyday life.
Read more →
Total votes 6: ↑4 and ↓2+5
Comments6

«Promising Public Transportation for Large and Medium-Sized Cities» — the main idea in a brief summary

Level of difficultyEasy
Reading time9 min
Views1.5K

(source)

Translation provided by ChatGPT, link to the original article.

I recently published a series of articles titled 'As Cheap as a Bus, as Convenient as a Taxi...':

Link to Part 1: «Preliminary Analysis» (ру / eng )
Link to Part 2: «Experiments on a Torus» (ру / eng )
Link to Part 3: «Practically Significant Solutions» (ру / eng )

dedicated to making public transportation in large cities completely seamless, without the need for transfers. In the last article of the series, I extensively described a microbus movement scheme that allows them to operate almost like taxis while accommodating 5-10 passengers at once. Such a transportation system would enable city residents to travel from any intersection to another without any transfers, comparable in time to a personal car journey, and at a cost similar to a regular city bus ticket. However, the feedback from readers indicated that I chose an extremely ineffective way to convey the information, resulting in a failure to effectively communicate the essence of the matter.

I must admit that the previous three articles were written in a way that allowed readers to apply the acquired knowledge in practice or continue the research I started on their own. Unfortunately, my desire to 'teach' resulted in nearly 100 pages of complex mathematical text, which is clearly excessive for readers who simply wanted to familiarize themselves with the idea. Here, I will attempt to rectify this mistake and briefly, yet simply, explain the bus taxi technology.
Read more →
Total votes 6: ↑6 and ↓0+6
Comments0

Langton's ant: a mystery cellular automaton

Reading time4 min
Views2.6K

The life of Langton's Ant seems sad and lonely, but, as we'll soon discover, he is not ready to put up with such an outrageous situation and is trying his best to escape. American scientist Christopher Langton invented his ant back in 1986. Since then, no one has been able to explain the strange behavior of this mysterious model...

Read more
Total votes 8: ↑8 and ↓0+8
Comments3

Will transport planners lose their jobs as AI becomes smarter?

Level of difficultyMedium
Reading time13 min
Views1K

As a Product Manager who has worked on the development of delivery route optimisation software for 10+ years, I see that modern technologies can significantly improve the optimisation process and deliver better solutions. AI, machine learning, and other modern technologies have the potential to revolutionise the way delivery routes are optimised in the future.

With the increasing availability of data and the advancement of AI and machine learning algorithms, it is becoming possible to develop more sophisticated prediction models that can be integrated into optimisation algorithms to make more accurate and informed decisions about route planning and scheduling. Machine learning algorithms can be trained to predict customer demand based on historical sales data and other market trends, allowing businesses to optimise their delivery schedules and routes accordingly. AI can also be used to optimise delivery schedules based on customer preferences and other relevant factors.

Blockchain technology could be used to create a secure, decentralised database of information about deliveries, including information about the products being shipped, the route they are taking, and the status of the delivery. This could help increase transparency and accountability in the delivery process as well as reduce the risk of fraud and theft.

Internet of Things (IoT) devices, such as sensors and GPS trackers, may collect real-time data about delivery vehicles and their surroundings. This data could be analysed and used to optimise delivery routes in real time, as well as to track the location of deliveries and monitor the condition of the products being shipped.

Read more
Total votes 1: ↑1 and ↓0+1
Comments13

Collective meaning recognition

Reading time37 min
Views1.4K

The published material is in the Appendix of my book [1]

Modern civilization finds itself at a crossroads in which to choose the meaning of life. Because of the development of technology, the majority of the world's population may be "superfluous" - not in demand in the production of values. There is another option, where each person is a supreme value, an absolute individual and can be indispensably useful in the technology of the collective mind.

In the eighties of the last century, the task of creating a scientific field of "collective intelligence" was set. Collective intelligence is defined as the ability of the collective to find solutions to problems more effectively than each participant individually. The right collective mind must be...

Read more
Total votes 2: ↑2 and ↓0+2
Comments0

Riddles of the fast Fourier transform

Reading time10 min
Views1.6K

• The method of phase-magnitude interpolation (PMI)

• Accurate measure of frequency, magnitude and phase of signal harmonics

• Detection of resonances

The Fast Fourier Transform (FFT) algorithm is an important tool for analyzing and processing signals of various nature.

It allows to reconstruct magnitude and phase spectrum of a signal into the frequency domain by magnitude sample into the time domain, while the method is computationally optimized with modest memory consumption.

Although there is not losing of any information about the signal during the conversion process (calculations are reversible up to rounding), the algorithm has some peculiarities, which hinder high-precision analysis and fine processing of results further.

The article presents an effective way to overcome such "inconvenient" features of the algorithm.

Read in Russian

Read in English
Rating0
Comments0

Authors' contribution