# MAIL_DELIVER - Editorial

Author: sho358
Tester & Editorialist: iceknight1093

2268

# PREREQUISITES:

Multisource dijkstra

# PROBLEM:

You’re given an undirected graph on N vertices with M edges.
K mail carriers are present on it: the i-th of them starts at vertex X_i and has a range of D_i; meaning he can deliver mail to any vertex that’s at most distance D_i away from X_i.

Can every vertex receive its mail?

# EXPLANATION:

If K = 1, we could run a BFS from the starting point and till distance D_i; and check if all vertices are covered in \mathcal{O}(N + M).

This of course generalizes to a (slow) solution for K \gt 1: run a separate BFS for each mailman and check if all vertices are visited in the end.
Of course, the complexity here is \mathcal{O}(K\cdot (N+M)), which is too slow.

A natural optimization to try now would be to attempt a multisource BFS, however it doesn’t quite work directly because of the D_i values; so a previously visited vertex can’t simply be skipped.

Example Suppose we have mail carriers at 1 and 5, with D_1 = 5 and D_5 = 4.

If we BFS from 1 first, we’ll end up marking vertices 4 and 6, but not 7.
BFS-ing from 5 will then stop before marking 7, since vertices on its path are already marked.

This case also shows that trying to BFS from vertices with larger D_i first isn’t necessarily correct either.
What really matters is how many moves we have left from each vertex.

In particular, we need to know the maximum number of remaining steps from each vertex.
To do this, we can instead transform our algorithm to a multisource dijkstra!

Let \text{rem}[u] be the maximum number of remaining steps from vertex u.
First, for each mail carrier i, set \text{rem}[K_i] \gets \max(\text{rem}[K_i], D_i).

Then, for a vertex u and an adjacent vertex v, \text{rem}[v] can be updated with \text{rem}[u]-1.
Notice that this is similar to the usual dijkstra with distances, where we update \text{dist}[v] with \text{dist}[u]+wt.

So, simply running dijkstra’s algorithm on this will give us the correct values of \text{rem}[u] for all u.
Note that here, we want to keep the maximum value and not the minimum; make sure to implement that correctly.

Finally, if \text{rem}[u] \leq 0 for any vertex the answer is No; otherwise the answer is Yes.

# TIME COMPLEXITY

\mathcal{O}((N+M)\log N) for each testcase.

# CODE:

Author's code (C++)
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=1000000007;
ld const PI=3.14159265359;
ll const MAX_N=3e5+5;
ld const EPS=0.00000001;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(a) (int)a.size()
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll t,n,m,k,x,d,viz;
vector<ll>g;
void testcase(){
cin>>n>>m>>k;
for(ll i=1;i<=n;i++)
{
viz[i]=0;
}
for(ll i=1;i<=k;i++)
{
cin>>x[i];
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q;
for(ll i=1;i<=k;i++)
{
cin>>d[i];
viz[x[i]]=min(-d[i],viz[x[i]]);
q.push(mp(-d[i],x[i]));
}
for(ll i=1;i<=m;i++)
{
ll x,y;
cin>>x>>y;
g[x].pb(y);
g[y].pb(x);
}
while(!q.empty()){
ll x,y;
x=q.top().s;
y=q.top().f;
q.pop();
if(viz[x]!=y){
continue;
}
for(auto it : g[x]){
if(viz[x]+1<viz[it]){
viz[it]=viz[x]+1;
q.push(mp(viz[it],it));
}
}
}
int ans=1;
for(ll i=1;i<=n;i++)
{
if(viz[i]==0){
ans=0;
}
}
if(ans){
cout<<"YES"<<endl;
}else cout<<"NO"<<endl;
for(ll i=1;i<=n;i++)
{
viz[i]=0;
g[i].clear();
}
}
int32_t main(){
CODE_START;
cin>>t;
while(t--){
testcase();
}
}

Editorialist's code (Python)
from heapq import heappop, heappush
for _ in range(int(input())):
n, m, k = map(int, input().split())
pos = list(map(int, input().split()))
dis = list(map(int, input().split()))
adj = [ [] for _ in range(n)]
for i in range(m):
u, v = map(int, input().split())

dist = [-1] * n
queue = []
for i in range(k):
x, d = pos[i] - 1, dis[i] - 1
dist[x] = max(dist[x], d)
heappush(queue, (-d, x))
while queue:
rem, v = heappop(queue)
rem *= -1
if rem != dist[v] or rem == 0: continue
if dist[x] < rem - 1:
dist[x] = rem - 1
heappush(queue, (1 - rem, x))

print('Yes' if min(dist) >= 0 else 'No')

1 Like

I made a multiple source bfs to compute dis{node) for each node the smallest distance to a mail carrier and I maintain in each connected component the maximum distance that a carrier can reach and then I check if dis[node] is less or equal than this this maximum distance (I made with dsu) but I’m getting Wa on only two subtasks .Can anyone help me ?

1 Like

It seems that the array X can have duplicate values of nodes, and we need to pick the maximum value of d_i for each node.

Now, consider these two statements:

• Mail from node x can travel atmost da distance.
• Mail from node x can travel atmost db distance.

If we consider the max(da, db) then one of the above statements would be wrong!

1 Like

I agree that test case is a very malicious, but if you read closely to the problem, it only ever talks about it from the perspective of mailmen on the node, and not the node itself. A matter of semantics rather than DSA, but nonetheless it should be max.

1 Like

I see, so there can be multiple mailmen present on a single node and we consider max of their distances, man I am dumb!

2 Likes

Nice Problem, but the test cases are poorly generated, I saw the contest submissions there are many solutions that assume the range of a node [i.e. the maximum distance that we can go starting from node i, such that both i and j, dist(i,j) = max dist we can go from i, are under the same mail carrier node x] will be updated at most 5 to 6 times for node i. Here are a few solutions that take advantage of this and got AC.

Sample Input :
1
19 18 10
10 11 12 13 14 15 16 17 18 19
1 3 5 7 9 11 13 15 17 19
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19

Sample Output :
YES

Explanation :
Node 19 has d = 19 so it is quite obvious that node 19 would be able to reach node 1. and the graph is basically a straight line.

There are many more as well.

@iceknight1093 Is test case generation intentionally random ? If so, does this not transform the problem into sort of a randomization problem ?

NOTE : There are also accepted solutions that will get TLE if the inputs are given in a certain pattern.

1 Like

So in Question Thank U, Next (MAIL_DELI) most of the code that are getting accepted are failing on following tescases:

Testcase 1 :

1
14 13 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
9 10
10 11
11 12
12 13
13 14

Testcase 2:

1
15 14 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 9
2 9
3 9
4 9
5 9
6 9
7 9
8 9
9 10
10 11
11 12
12 13
13 14
14 15

And many more…

On these testcase answer should be YES but many accepted codes are giving No

and there and many many more testcases which can be made to fail on following solutions:

https://www.codechef.com/viewsolution/97874231

https://www.codechef.com/viewsolution/97874272

https://www.codechef.com/viewsolution/97874509

https://www.codechef.com/viewsolution/97874514

https://www.codechef.com/viewsolution/97874590

https://www.codechef.com/viewsolution/97885334

https://www.codechef.com/viewsolution/97876075

https://www.codechef.com/viewsolution/97875297

And many more…

There are many more solution on same pattern

So please rejudge all solution or make the contest unrated as it is currently unfair for many participants.

1 Like

All these codes contains

       if (visited[node] == 5)
continue;


Why they write visited[node]==5 ? It’s just a arbitrary number or there is any logic behind this?

They actually assumed that a particular node can only be updated at most 5 times, this approach would have been valid if it was written that the inputs are generated randomly. @aakash_172 it’s just an arbitrary number they assumed.

1 Like

Ok,got it.But they all assumed 5 as arbitrary which looks like copied code from same source.

2 Likes

No, generation wasn’t random.
In fact, there are specific tests to kill whatever wrong/slow solutions the author and I could come up with when testing (multisource bfs, multisource bfs that greedily chooses the largest D_i each time, a few more heuristics I don’t recall right now).

Unfortunately, the specific heuristic you mentioned isn’t something we thought of, and the tests didn’t catch it.
As an aside, yes, it’s very interesting that so many submissions chose 5 (which is an arbitrary small number) as the constant…

1 Like

I don’t understand one thing. Why are we taking the remaining distance as max(da, db) at every node. As we are using dijkstra’s , we can be sure that a node is reached with maximum possible remaining distance right? Or am I missing something? Can someone explain it?

@lachu49, It just depends on the implementation, if you are inputting something like d[x[i]] then you may loose the max value. But if you input each d_i separately in the priority queue then no need to consider the max.

But still my code fails in some tests. Anyways, I got your point. Thanks!

can someone give me some problems on multisource Dijkstra?

Why dfs is giving TLE?