carusel02/pa-algorithm-problems

Algorithm problems

Problem 1 - ferryboat

Solution:

• Employ a binary search to efficiently find the optimal cost for ferry transport.
• At the lowest cost end, assign the maximum weight for a car, ensuring the final cost is minimal.
• At the highest cost end, allocate the total sum of car weights.
• Use binary search to check if distributing the final cost evenly among ferries is optimal. Adjust costs accordingly.

Code:

• Utilize a binary search function to find the optimal cost for ferry transport.
• Read inputs, calculate total weight and maximum weight, then call the binary search function to find the optimal cost.

Problem 2 - nostory

Solution:

• For the first task, maximize score by pairing the largest numbers from both lists.
• For the second task, maximize score by swapping the smallest maximum with the largest minimum, given a number of moves.

Code:

• Read inputs and call the corresponding task function. Task 1: Sort and sum the largest numbers. Task 2: Find the minimum and maximum of all pairs and accumulate the positive differences up to a given number of moves.

Problem 3 - sushi

Solution:

• Adapt the knapsack problem with infinite volume for tasks 1 and 2. For task 3, expand the problem to accommodate adding N objects to the backpack.

Code:

• Read inputs and call each function accordingly. Task 1 & 2: Calculate average values for plates and their prices. Task 3: Adjust the problem to handle adding N objects to the backpack.

Problem 4 - signals

Solution:

• Solve using dynamic programming with recurrence relations between steps.
• For both tasks, relate the current number of bits with specific counts of 1s to the previous steps.

Code:

• Construct and initialize the DP matrix.
• Implement recurrence relations for both tasks, considering various combinations of 1s in binary strings.

Problem 5 - badgpt

Solution:

• Recognize the Fibonacci sequence in the results and compute the nth Fibonacci number for consecutive n letters of n or u.

Code part:

• Call the function to find the nth Fibonacci number for consecutive n letters of n or u.