I am not objecting, but I am slightly puzzled. The question specifies a time limit of 2 seconds, yet my submission CodeChef: Practical coding for everyone passed with a time of 3.31 seconds. How come? Are time limits scaled for different languages (I am using Python 3, using the PyPy3 compiler)?
@aberent
Here in CodeChef, we have different time multiplers for different compilers.
You can learn more about it here.
1 Like
@avijit_agarwal could you help me know why this o(n*m) solution is TLE. Thanks CodeChef: Practical coding for everyone 10
hi @swapnil159
https://www.codechef.com/viewsolution/35703437
can you explain why i am getting tle in this??
Can someone look at My solution
i simply used DP algo for finding a path from [1,1] to [n,m] with ‘#’ as blocks
I don’t know on which test case it failed.
@avijit_agarwal @aman_robotics
Fails for
1
1 1
b
Edit: It gives RE on codechef IDE
And it should give wrong anser then why tle??
@avijit_agarwal @swapnil159
Can you tell me what test cases my code is failing? I have been stuck for hours.
My soluton
Can anybody Please help me, I used the given approach but gettind WA. I tested for myself but not able to find the error.
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
vector<string> strs(n);
for(int i=0;i<n;i++) cin>>strs[i];
//each string has size m
set<pair<char,pair<int,int> > > set_of_truth;
set_of_truth.insert({strs[0][0],{0,0}});
string res="";
while(set_of_truth.size())
{
char smallest=set_of_truth.begin()->first;
res+=smallest;
vector<pair<int,int>> potential_candidates;
while(set_of_truth.size() && set_of_truth.begin()->first==smallest)
{
potential_candidates.push_back({set_of_truth.begin()->second.first,set_of_truth.begin()->second.second});
set_of_truth.erase(set_of_truth.begin());
}
set_of_truth.clear();
for(int i=0;i<potential_candidates.size();i++)
{
int r=potential_candidates[i].first;
int c=potential_candidates[i].second;
if(r+1<n && strs[r+1][c]!='#') set_of_truth.insert({strs[r+1][c],{r+1,c}});
if(c+1<m && strs[r][c+1]!='#') set_of_truth.insert({strs[r][c+1],{r,c+1}});
}
}
cout<<res<<endl;
}
}
@avijit_agarwal I tried dfs approach
Can you tell me whats wrong in the code
https://www.codechef.com/viewsolution/35708838
@garyhost
It seems yesterday was your unlucky day. But we always guarantee the participants to learn something new. It seems you did an inefficeient string concatenation in your program at line 220.
ans=ans+ minch;
Instead you should have done,
ans+=minch;
You may look at this post for explanation
Hope it helps 
1 Like
Wow…thank you so much for the help. Really came across this issue for the first time. Indeed this was the problem. Yesterday was unlucky but now I know the mistake and will make sure to be careful about this.
1 Like
@priyanshu219
Read the question carefully. You are required to print the lexicographically smallest string.
I had to a nap to understand this editorial …xD
@avijit_agarwal @swapnil159 @galencolin
Please help me in finding what test cases my code is failing. I have spent hours on this.
My solution
@summerbrander
Your solution is failing for this testcase-
1
6 3
rqq
qsq
qss
rsq
pss
sqq
correct output: rqqqsqsq
1 Like
@avijit_agarwal @aman_robotics
pls help i can’t find why i am getting WA …any help will be appreciated
#include<bits/stdc++.h>#define ll long long
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t,n,m;
cin>>t;
while(t–)
{
cin>>n>>m;
string st[n];
bool path[n][m]={0},path1[n][m]={0};
for(int i=0;i<n;i++)
{
cin>>st[i];
}
for(int i=n-1;i>=0;i–)
{
for(int j=m-1;j>=0;j–)
{
if(i==n-1&&j==m-1)
{
path[i][j]=1;
continue;
}
if(st[i][j]==’#’)
path[i][j]=0;
else
if(i==n-1)
path[i][j]=path[i][j+1];
else if(j==m-1)
path[i][j]=path[i+1][j];
else path[i][j]=path[i][j+1]||path[i+1][j];
}
}
string ans="";
ans+=st[0][0];
path1[0][0]=1;
for(int k=1;k<n+m-1;k++)
{
char c=‘z’;
for(int i=max(0,k-m+1);i<=k&&i<n;i++)
{
int j=k-i;
if(i>0&&path[i][j]&&path1[i-1][j]&&c>st[i][j])
c=st[i][j];
if(j>0&&path[i][j]&&path1[i][j-1]&&c>st[i][j])
c=st[i][j];
}
ans+=c;
for(int i=max(0,k-m+1);i<=k&&i<n;i++)
{
int j=k-i;
if(i>0&&path[i][j]&&path1[i-1][j]&&c==st[i][j])
path1[i][j]=1;
if(j>0&&path[i][j]&&path1[i][j-1]&&c==st[i][j])
path1[i][j]=1;
}
}
cout<<ans<<’\n’;
}
}
i focused on how your path was building up and i found an garbage value at the begining of path1 creation
1
3 3
azz
a#z
a#z
path path 1
1 1 1 1 1 20 <- garbage value.
0 0 1 0 0 0
0 0 1 0 0 0
1 1 1 1 1 1
0 0 1 0 0 0
0 0 1 0 0 0
1 1 1 1 1 1
0 0 1 0 0 1
0 0 1 0 0 0
1 1 1 1 1 1
0 0 1 0 0 1
0 0 1 0 0 1
update : i changed this line of the code :
bool path[n][m]={0},path1[n][m]={0};
to
bool path[n][m],path1[n][m];
for (int i = 0; i < n ; i++) for (int j = 0; j < m; j++) path[i][j] = path1[i][j] = false;
and got AC.
why does this happen ? @akshitm16 @galencolin
1 Like