On the list of things that are never gonna happen, recontest is never gonna happen the most.
2 Likes
yeah hopefully it will pass.
btw, what was this question worth in terms of points 50 or 75?
75
right. Isn’t it really easy for some people because if there exists 99 or the string length is 1, there’s an answer. I couldn’t figure it out, but many could have, easily.
Man, I hate this no pretest setting. Just found an edge case for 50 point problem where my code fails. 
I am so stupid, its not even an edge case, its simple normal case for which I should have tested and code should have failed in pretests. 
1 Like
Same dread and regret here bro.
I am just hoping that testcases aren’t that strong.
bro
do they hire for system specialist engineer i.e top 3000 this year
thanks in advance
@aditya_dalal @h_sh
Here’s the solution for the problem Number of City
On a very high level,
First, parse the input to form a tree.
Then, for every node, find the minimum number of days for a vendor to reach that node. This can be done using two DFSes. Output the maximum days among all.
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
#define MAX 1002
vector<int> tree[MAX*MAX];
int n, m, A, B, i, j, k, days[MAX*MAX]={0}, depth[MAX*MAX]={0}, parent[MAX*MAX]={0};
bool vendors[MAX*MAX]={0};
string city[MAX+2];
int treeIndex(int i, int j){
return (i-1)*m + (j+1)/2;
}
/* Parses the input to form a standard tree */
void setTree(int i, int j){
int in = treeIndex(i, j);
if(city[i-1][j] == ' ' && tree[treeIndex(i-1, j)].empty() ){
parent[ treeIndex(i-1, j) ] = in;
tree[in].push_back(treeIndex(i-1, j));
setTree(i-1, j);
}
if(city[i][j+1] == ' ' && tree[treeIndex(i, j+2)].empty()){
parent[ treeIndex(i, j+2) ] = in;
tree[in].push_back(treeIndex(i, j+2));
setTree(i, j+2);
}
if(city[i][j-1] == ' ' && tree[treeIndex(i, j-2)].empty()){
parent[ treeIndex(i, j-2) ] = in;
tree[in].push_back(treeIndex(i, j-2));
setTree(i, j-2);
}
if(city[i][j] == ' ' && tree[treeIndex(i+1, j)].empty()){
parent[ treeIndex(i+1, j) ] = in;
tree[in].push_back(treeIndex(i+1, j));
setTree(i+1, j);
}
//cout<<"Sat "<<in<<endl;
}
void calcDays(int N){
if(vendors[N]){
days[N]=0;
//cout<<N<<"="<<days[N]<<" "<<depth[N]<<"\t";
return;
}
vector<int> :: iterator it;
int cmp, maxx=0;
days[N] = MAX*MAX;
for(it=tree[N].begin(); it!=tree[N].end(); it++){
calcDays(*it);
days[N] = min(days[N], 1+days[*it]);
if(days[*it]>=MAX*MAX)
cmp = 1 + depth[*it];
else
cmp = 0;
maxx = max( maxx, cmp );
}
if(days[N] >=MAX*MAX)
depth[N] = maxx;
//cout<<N<<"="<<days[N]<<" "<<depth[N]<<"\t";
}
int maxAns=0;
int newDays[MAX*MAX]={0};
void getAns(int N){
int profit = 0;
newDays[N] = days[N];
if(parent[N]!=0) // If N is not root then check if the actual value is lesser
newDays[N] = min( days[N], newDays[parent[N]]+1 );
if(vendors[N]){ // If this node is a vender, just return
return;
}
vector<int> :: iterator it;
for(it=tree[N].begin(); it!=tree[N].end(); it++ ){
if(days[*it] >= MAX*MAX){
profit = max(profit, depth[*it]+1);
}
else{
getAns(*it);
}
}
maxAns =max (maxAns, newDays[N]+profit);
//cout<<"at "<<N<<" = "<<maxAns<<endl;
}
int main()
{
int a, b, in;
cin>>n>>m>>A>>B;
getchar();
//cout<<"Caught char\n";
for(i=0; i<=n; i++){
//gets(&city[i]);
getline (cin, city[i]);
}
cin>>k;
for(i=0; i<k; i++){
cin>>a>>b;
in = (a-1)*m + b;
//cout<<"Vendor at "<<in<<endl;
vendors[in] = 1;
}
/* Parse the input to form a tree with parent and children pointers */
setTree(A, B*2-1);
/* Set root to be the initial location of us */
int root = (A-1)*m + B;
/**
* Calculates the depth of each node, and
* Minimum number of days for a vendor to reach every node
* It only gets the rihgt days for the root since we started the dfs from root
* It doens't take into account the cases where it may be possible to get lesser days
for a particular node from a path which includes the root
* Just try to think about what this function is doing and you may understand the problem.
* */
calcDays(root);
/**
* newDays is going to hold the correct number of days for each node for a vender
to reach that node.
**/
newDays[root] = days[root];
/* Do the second DFS to get the correct days and keep track of the maximum among all*/
getAns(root);
cout<<maxAns<<endl;
return 0;
}
2 Likes
This code is hard to write at time of contest
1 Like
Galat hai ye ; pta nhi kyu ; par galat hai
I think you are talking about the amusement park question. Same happened with me too. It was very weird and I kind went into a no return zone coz I was unable to think why is this the answer to my input. I read question 4-5 times and then realised it was a glitch.
According to the question description and explanation of sample test case, shouldn’t the expected output of the two testcases in the screenshot be the same??? If not can anyone explain?
So i guess many experienced this random behavior in compile and test section.
It was just a glitch though 
What they wanted? Every type of train must be boarded once (by type i mean N) or the different start times that were given for ith type of train be considered as another train.
As the multiple running times of ith type of train overlapped so…were there t[i] trains? or am i wrong?
lol, then time to forget about this test!
1 Like
happened with me for a question.
the compiler is not running the custom tc. only default Tc is running.
Yeah, same felling we have no idea how much test cases is right!!!
Hi do u got the same qn with the same name “Number Of City” or “Number Of Cities”