I think my solution for the problem “Minimum-path” is correct, can anybody give a counter-test-case where it fails ?
Link:- CodeChef: Practical coding for everyone
(Earlier I bymistakely put @_nishant403’s solution link.)
Edit:-Got my mistake, need to take special-care when checking with m1,m2.
My AC submission :CodeChef: Practical coding for everyone
very weak test cases in this question @admin you should include t=10 n=1000 and grid values= 1 and char values = a,it will tle for many code,and how could some one overlook it,it is basic test cases. some people solution are passing,look after it.
#include
#include
using namespace std;
int main() {
char S[100000],str[100000],pos;
long int Q,N,L,R,count,T;
cin>>str;
cin>>Q;
while(Q–)
{
cin>>N;
if(N==1)
{
cin>>L>>pos;
if(L>=1 && L<=strlen(str))
{
str[L-1]=pos;
}
}
if(N==2)
{
T=0;
cin>>L>>R;
if(L<=R && L>=1 && R<=strlen(str))
{
copy(str,str+R,S);
for(long int i=L-1;i<=R-1;i++)
{
count=0;
if(S[i]!='-' && i<=R-2)
{
for(long int j=i+1;j<=R-1;j++)
{
if(S[i]==S[j])
{
S[j]='-';
count++;
}
}
if(count>0)
{
T++;
}
}
}
cout<<T<<endl;
}
}
}
return 0;
}
is the code correct for FFC320D?
So what is the optimal approach ? @nvdrag_123 Mainly when
dp[i-1][j]=dp[i][j-1] , how to check which of the both strings is lexicographically better in an optimal manner ?
First I will find which positions can be in optimal path without considering characters.
Then I traverse all the nodes diagonally (bfs order). First I marked (0,0) as valid, Then i mark all the next nodes reachable from it.
Consider all nodes in the same diagonal which are in optimal path and have its upper or left side node marked valid, Then mark all nodes from this diagonal which has the least character.
So anybody thinking,how to find all the nodes which might be on the shortest path from (1,1) to (n,m) , here’s what we do, for each node situated at (i,j), if minimum cost to travel from (1,1) to (i,j) + minimum cost to travel from (i,j) to (n,m) - a(i,j)= x , then that node lies on one of the shortest paths from (1,1) to (N,M),where x=shortest path from (1,1) to (N,M)
Now, make a special graph G (unweighted) of all these nodes.
Now, from node (1,1) to node (n,m) all paths of this special graph G have equal length , so you can without any tension, do a special kind of bfs on this graph. And for each level from (1 to k=n+m),find the minimum character node.
If for level-1,minimum character node=‘a’, for level-2, its ‘b’,for level ‘3’,its ‘c’. Then the final answer will be “abc”
Meaning of my special BFS:–>“You are at the root, see all connected guys to it, all guys which have minimum value, only they should be pushed in the queue, keep doing this till you reach node (n,m) .”
Thanks for the valuable inputs! @nishant403 
got it thanks…
how to solve Gump Loves Palindromes.
we have only one “_” in the string , so we place every character (a-z), and then try to compute the difference of odd length palindromes and even length palindromes,
for calculating odd and even length palindromes, DP solution of O(N*N) will give TLE, there is an optimized way to do the same using Manacher’s Algorithm
see this Manacher's Algorithm - Finding all sub-palindromes in O(N) - Algorithms for Competitive Programming
hey, I tried the same approach but it is giving WA, and i tried several test cases, it is giving correct answer (compared with the accepted solutions)
code :- CodeChef: Practical coding for everyone
help me, in finding the counter-test-case
At line number 110:- bool visited[(n*m)+5] ; where n*m===>1000000 , you cannot declare array of size [10^6] locally . Declare it globally.
Its still wrong because of all the matrices and (other arrays) you declared inside int-main() have size of [10^6] which is not allowed, and Codechef throws WA instead of RE, when we declare array of size [10^6]…its just my experience… In-short, either only use vectors, but if you are using array-1-D-2-D- in any form, then declare everything globally and clean the containers after each test-case.
You can declare it in main as well using new operator like this
int n = 1000000;
int *a = new int[n];
For bigger sizes, this declaration won’t work properly
int n = 1000000;
int a[n];
not the memory issue,
the problem is in the BFS part when i am sorting i am taking only the first character, and if the first and second character is same, may be second character can lead to smaller string (lexicographically)
corner case :-
1
5 5
1 2 3 4 9
2 9 4 5 9
3 9 9 4 3
4 5 4 9 2
9 9 3 2 1
aabff
afpqr
bjklp
bbbpp
zzbbb
answer :-
25
aabbbbbbb
but by this algo it is giving different string,
I can only think of a solution to do the DFS and at last compare all the strings,
If anyone know the efficient solution for this, please provide it
I knew that issue but I did not comment as I was busy with other things, if memory is not the issue, then do this in bfs :-
1)You are at the root, see all connected guys to it, all guys which have minimum value, only they should be pushed in the queue, keep doing this till you reach node (n,m) .
2)I’ll write its AC code in free time
You were sorting, it was bound to go wrong 
What I changed is, push all the nodes in the new queue for next iteration,
which has the same least character as q[0].f
@aarls
Hello,
The algorithm I and @nishant403 mentioned above does work.
See,my AC submission : - CodeChef: Practical coding for everyone
All you need to take care while doing the bfs is push only those nodes in the queue which have minimum character value and completely ignore other nodes of the graph as they won’t ever give better string we want!! This way your string will always be lexi-cographically smallest.