It looks like this could be solved with a BFS-based solution, advancing each person 1 at a time. For the both the dog and cat, keep track, for each node, the earliest time he can get to the node. If the dog can reach the cat in the same turn (same meaning time+1 based on how the question words time) or earlier, then that node must be pruned from the cat's BFS search.
In the end, the answer is the max time for the dog among the nodes that the cat can reach (that haven't been pruned). Since the graph is a tree and not, say, a cycle, I can't imagine a situation where the dog can't ever catch the cat.
These are just my initial thoughts; I haven't given much time into a proof or anything, but this seems like it would work to me.
1st one was pretty simple a brute force
For 2nd one : (my solution got pass)
Consider n = 13
Here ‘1’ denotes there are one 4s at unit place
Consider n = 15
Here ‘1’ denotes there are one 4s at unit place + As ‘5’ i> 4 there i one more 4
Consider n = 51
Here ‘5’ denotes there will be 5 fours at unit place and as ‘5’>4 denotes that there will once an occurrence of 40-49
Consider n = 153
‘15’ denotes there will be 15 fours at unit place
‘1’ denotes there is range of 40-49 + ‘5’ >4 so one more range of 40-49
Code :
Prefix[0] = 0
For i in n : prefix[i] = prefix[i-1]*10 + (s[i]-’0’)
Cut = 0;
Mult = 1;
For i in [n-1 to 0]
Cut += prefix[i]mult + (s[i]>’4’)
Mult = mult9
Return prefix[n]-cut
For 3 question (it also passed):
Get dist_d []and dist_c[] as distance of each node using dfs call for each node C and
D.
Now for each i :
If our C can reach there before D (which means dist[d]>dist[c]+1)
then : ans = max(ans,2*dist[d]-1)
Return ans;
Reason :
If our node C can reach any node i then he can travel there and wait for D to come.
Consider this :
1*(D here at start) - 2 - 3 - 4 - 5 - 7
|
6 (C here at start)
Now our D at 1 sec goes to 2
Then C at 2 sec goes to 4
Then D at 3 sec goes to 3
Then C at 4 sec goes to 5
And so on
My Solution for Second Question:
Time: O(N) Space: O(N)
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
vector<int> prefix(s.length() + 1, 0);
int m = 1;
for(int i = 1; i <= s.length(); i++){
prefix[i] = prefix[i - 1] * 10 + m;
m *= 9;
}
int res = 0;
for(int i = 0; i < s.length(); i++){
res = res + prefix[s.length() - 1 - i] * (s[i] - '0') + (s[i] - '0' > 4 ? prefix[s.length() - 1 - i + 1] - prefix[s.length() - 1 - i] * 10: 0);
}
cout << stoi(s) - res << endl;
return 0;
}