Contest Experience: Leetcode Weekly Contest 397

About the contest:

• This contest was conducted by Leetcode on May 12, 2024.
• In this contest, there are a total of 4 problems, and 90min are given to solve the problems.

Link of the Contest: LeetCode Weekly Contest 397

Perks/Prizes/Offers:

My Experience:

I was able to solve 3 out of 4 problems during these contests.

OVERVIEW OF ALL CONTEST PROBLEM:

LET’S DISCUSS THE PROBLEM:

Question 1 : Permutation Difference between Two Strings

The problem requires calculating the permutation difference between two strings, s and t, where t is a permutation of s and each character appears at most once. The permutation difference is the sum of the absolute differences between the indices of each character in s and their corresponding indices in t. For example, with s = “abc” and t = “bac”, the difference is |0-1| + |1-0| + |2-2| = 2. To solve this, we use a hash map to store the index of each character in s. Then, we iterate through t, summing the absolute differences between the current index in t and the stored index from s. This sum represents the permutation difference.

Question 2 : Taking Maximum Energy From the Mystic Dungeon

To solve the problem, we use a dynamic programming approach by creating a dp array of size k to store the maximum energy accumulated starting from positions with the same modulo k value. By iterating backwards through the energy array, we update the dp array to include the current magician’s energy, ensuring we account for all possible jump sequences. This method tracks the optimal energy gain for each starting position, and the maximum value in the dp array after processing all magicians gives the maximum possible energy gain.

Question 3 : Maximum Difference Score in a Grid

To find the maximum total score, iterate through the matrix while keeping track of the minimum value encountered from the cells that can be moved to the current cell (either from above or from the left). For each cell, calculate the score as the difference between the current cell value and this minimum value. Update the maximum score obtained so far, and adjust the current cell’s value to maintain the minimum value for future comparisons. By updating the matrix in-place, we ensure that the minimum values needed for future score calculations are readily available. The highest score from all possible valid moves gives the result. This dynamic programming approach ensures efficient computation of the maximum score by leveraging previously computed minimum values for each cell’s potential moves.

Conclusion:

At the end I was able to solve 3 problem out of 4 problem. last question was difficult to me. I waste lot of time to solve last question but I was not able to solve it. All the best for upcoming contest.

Thank you !!!