Problem Link - Magic Rankings
Problem Statement:
Everybody loves magic, especially magicians who compete for glory in the Byteland Magic Tournament. Magician Cyael faces challenges in her performances and must perform for judges whose fixed scores she knows in advance, represented in an N×N square matrix. The task is to calculate the maximum score Cyael can achieve based on the judges’ scores.
Approach:
The key idea of this solution is to use dynamic programming to find the maximum score Cyael can achieve while traversing the matrix from the top-left to the bottom-right corner. We maintain a DP array where each cell DP[i][j] represents the maximum score obtainable at that position by considering the maximum scores from the top and left cells, effectively allowing us to find the best path through the judges’ scores. If the final score is negative, it indicates “Bad Judges”; otherwise, we calculate the average score based on the total movements made.
Time Complexity:
- O(n^2) for filling the
DParray as we iterate through each cell in the n×n matrix.
Space Complexity:
- O(n^2) for the
DParray used to store the maximum scores.