All Questions
335 questions
4
votes
1
answer
76
views
Struggling with bottom up approach for This Kattis Problem: The mailbox manufacturers
Problem link : https://open.kattis.com/problems/mailbox
It feels like a variation of Egg dropping problem but i cant seem to wrap my head around how I am unable to do this. It is also tagged as an ...
- 57
1
vote
2
answers
78
views
Why does my A* algorithm expand nodes differently when using heapq vs. a set for the open set?
I'm implementing an A* search algorithm for a maze solver in Python. Initially, I maintained the open set as a plain set and selected the node with the lowest f-score using:
current = min(open_set, ...
- 21
3
votes
2
answers
112
views
How to optimize the performance of nested loops with dynamic data structure updates in Python?
How can I optimize this code for better performance while maintaining the correctness of dynamic updates?
Is there a way to restructure the nested loop or use a different approach to reduce the time ...
3
votes
4
answers
153
views
How to efficiently solve the Maximum Product Subarray problem in Python?
I’m trying to solve the Maximum Product Subarray problem, which is described as follows:
Given an array of integers (positive, negative, or zero), find the maximum product of any contiguous subarray.
...
- 41
3
votes
1
answer
84
views
Counting the number of positive integers that are lexicographically smaller than a specific number
Say I have a number num and I want to count the number of positive integers in the range [1, n] which are lexicographically smaller than num and n is some arbitrary large integer. A number x is ...
- 225
5
votes
1
answer
414
views
Longest complete subsequence of ordered vowels [duplicate]
Given a string made up of "a", "e", "i", "o", or "u", find the longest subsequence of vowels in order. For example, is the string is "aeiaeiou&...
- 71
3
votes
2
answers
144
views
A more efficient algorithm in finding the number of distinct decompositions a number has using only repdigits
This is a problem from a previous semester that I am trying to upsolve. I am trying to solve a problem involving the total number of ways of decomposing a number using only repdigits. A repdigit is a ...
- 51
1
vote
1
answer
326
views
Asteroid Mining - Dynamic Programming problem
I was given the following assignment:
There is n gram of mineral to be dug up on a certain asteroid. At the beginning there is only one robot at our disposal. Each robot can do one of two activities ...
- 51
3
votes
3
answers
314
views
Longest Repeating Subsequence: Edge Cases
Problem
While solving the Longest Repeating Subsequence problem using bottom-up dynamic programming, I started running into an edge case whenever a letter was repeated an odd number of times.
The goal ...
1
vote
1
answer
87
views
Finding the most optimal way for updating a dynamic-programming array
Imagine there are n people in a line, which every one of them has there unique value for themselves from 1 to n, we try to sort them like this:
repeat
swapped = false
for i from 1 to n do:
...
- 53
2
votes
3
answers
868
views
Maximum Sum Without Skipping Two Contiguous Elements
The task is to find the maximum sum of a subsequence of integers from a given list. The subsequence must follow two conditions:
It must be contiguous, meaning the selected elements are in consecutive ...
- 31
1
vote
0
answers
587
views
Dice Roll Simulation (Permutation Approach)
This is a question on leetcode. I'm aware it's efficiently a dynamic programming question, but I wanted to try a different approach to really exercise my understanding of data structures and ...
- 339
3
votes
4
answers
186
views
How to find min cost for element selection from a sequence of adjacent pairs
Given an array of integers (with at least two elements), I need to choose at least one element of each adjacent pair of elements in the array in a way that costs me the least. Then, return the cost ...
- 33
0
votes
1
answer
84
views
How is it possible to memoize longest divisible subset using only the length (and end position)?
The goal is to find the largest divisible subset. A divisible subset is a subset s.t. for every pair of elements i, j, either i is divisible by j or j is divisible by i. The general approach to solve ...
- 9,643
1
vote
1
answer
171
views
Optimization problem in Python. Dynamic programming
I have the following task.
There is a list of segments: list[int]. All these segments must be involved. We have the length of the rope and infinite number of ropes. when we make combinations, most ...
- 33