This problem was asked in a contest conducted today called 'GitHub Code Geek Fest' (I think it is only for partner colleges in India).
Problem Statement:
Given a grid with N rows (numbered from 1 to N) and M columns (numbered from 1 to M) consisting of upper case English characters.
You are initially in the cell (1,1) and you want to go to cell (N,M) such that the path you follow is Palindromic.
During each move, you either move to the next cell in the current row, or in the current column, i.e, if the current cell is (x,y), then after the move it can be either (x+1,y) or (x,y+1). (Basically, you can either move to the right or down).
A path is called Palindromic if the letter in the first cell is equal to the letter in the last cell, the letter in the second cell is equal to the letter in the second-to last cell, and so on.
Also, you can increment or decrement a letter at some position (i,j) with the cost of 1 unit. Incrementing a letter changes it to the next letter in the alphabet (e.g., 'A' to 'B', 'L' to 'M', and 'Y' to 'Z'). Decrementing a letter changes it to the previous letter in the alphabet (e.g., 'B' to 'A', 'M' to 'L', and 'Z' to 'Y').
The letter 'A' cannot be decremented and the letter 'Z' cannot be incremented. Multiple operations may be applied to the same index.
Find the minimum cost incurred for a path from (1,1) to (N,M) such that the path is Palindromic.
Constraints:
- 1 ≤ N,M ≤ 100
- The values in the grid only consist of uppercase English letters
Test Cases:
(The problem setters didn't provide any test cases, I came up with these)
Input:
4 4
A X Y Z
C D X Y
P Z E S
Q R B A
Output: 2 (If we follow the path A->C->D->Z->E->B->A, we can change C to B (cost : 1) and D to E (cost : 1) to make the path palindrome)
Input:
4 3
H E Y
H H L
C H H
Z Y H
Output: 0 (We follow the path H->H->H->H->H->H, It is already a palindrome, we don't have to perform any operation)
I initially thought of a DP approach, but couldn't figure out the transitions properly. Any help would be appreciated.
I'm not sure if $$$O(n^2m^2)$$$ would pass. But here is an idea:
Consider a graph where nodes are like this- $$$((i,j),(i',j'))$$$. We will add an edge from $$$((i_1,j_1),(i'_1,j'_1))$$$ to $$$((i_2,j_2),(i'_2,j'_2))$$$ only if $$$(i_1,j_1)$$$ is adjacent to $$$(i_2,j_2)$$$ and $$$(i'_1,j'_1)$$$ to $$$(i'_2,j'_2)$$$ in the original graph. The edge would be weighted, with a cost required to change letters at $$$(i_1,j_1),(i'_1,j'_1)$$$ to letters at $$$((i_2,j_2),(i'_2,j'_2))$$$ respectively.
Now, the answer would be the minimum cost of path from source $$$((1,1),(n,m))$$$ to any of the goal states, which would be { $$$((i,j),(i,j)) | \forall i,j$$$ } or { $$$((i,j),(i',j'))$$$ | which are adjacent }
It would also have a log factor, due to the minimum cost path. Maybe if someone could suggest an optimization to this?
You're solution in facts works in $$$O(min(n,m)^2max(n,m))$$$.
First, $$$min(m,n)$$$ is the maximum size of a diagonal in the grid, $$$max(m,n)$$$ is the number os diagonals.
The points in a given diagonal $$$d1$$$ just pairs with another specific diagonal $$$d2$$$, which is the diagonal that respects the restriction $$$d1 + d2 = n+1$$$( the first one pairs with the last one, the second with the $$$n-1$$$ diagonal, and so on).
pair the points of $$$d1$$$ with $$$d2$$$ give us $$$O(min(n,m)^2)$$$, which is the size of the two diagonals, since we have $$$O(max(m,n))$$$ diagonals, the number of nodes in the graph is $$$O(min(n,m)^2max(n,m))$$$
Each node will have at most 4 edges ( one point can go up or left, and the other can go right or down), then the number of edges is $$$O(min(n,m)^2max(n,m))$$$ too.
Another detail is that the resulting graph is a DAG, so you can compute minimum cost without the log factor.