Easy

# PREREQUISITES:

Graphs, Shortest paths, Greedy

# PROBLEM:

Given a weighted undirected graph and a sequence of nodes B, find the minimum length of a subsequence of B and let that subsequence be A (or report no such A exists). A should satisfy the condition that when we visit the cities in A in order and use some shortest path between adjacent cities in A, the sequence of cities we visit is exactly B.

# QUICK EXPLANATION

Greedily build A by making sure that adjacent cities in A have the greatest possible distance.

# EXPLANATION:

First, in order to check if a sequence of cities from u to v is a shortest path from u to v, we should compute the shortest path for each pair (u, v). This is known as all-pairs shortest paths. All-pairs shortest paths can be solved simply by applying Dijkstra for each node u as the starting node. There is a lesser-known solution using Floyd-Warshall that has a very short implementation (which you can find in my code).

Let’s try to find A. A_0 has to be equal to B_0, so the next thing we could do is to find A_1, which will be equal to B_{i_1} for some i_1. It makes sense to try to make i_1 as big as possible (while still making sure that the sequence B[0, i_1] is a shortest path from B_0 to B_{i_1}), because if we do, there will be fewer cities left in B to cover, so the sequence A will probably be shorter.

After we find i_1, we will find i_2, and the same intuition of making i_2 as big as possible still applies. After we find i_2, we do the same thing again to find i_3, and so on, until we reach L-1 (the end of B). The pseudocode is shown below:

• ans = 1, last = 0
• Perform the following process while last < L-1:
• next = last
• While next+1 < L, we’ll try to extend next:
• Let d be the sum of distances between adjacent cities from B_{last} to B_{next+1}.
• If d is the same as the shortest distance from B_{last} to B_{next+1}, we can’t extend anymore, so we stop.
• next=next+1
• If next = last:
• We can’t extend so return no solution.
• last = next
• ans=ans+1

Note that if we know that B_{last} to B_{next+1} does not form a shortest path, then all B_{next+x} where x>0 will not form a shortest path from B_{last}, so we will not check those.

It remains to prove that this greedy solution is correct. Let G be the sequence generated by the greedy solution and let O be an optimal solution with the longest common prefix with G. If that longest common prefix is the entire sequence, then the greedy solution is an optimal solution. Otherwise, let k be the length of the common prefix, so G_i=O_i for 0\le i < k and G_k \ne O_k.

Note that G_k > O_k, because the greedy solution always extends as much as possible. If G_k \ge O_{k+1}, then we can remove O_k from O and still have a valid sequence, which contradicts the fact that O is an optimal solution.

Why the new sequence is valid

We know that G_{k-1} to G_k is a shortest path, and since O_{k-1}=G_{k-1} and O_{k+1}\le G_k, O_{k-1} to O_{k+1} is a shortest path.

Otherwise, G_k < O_{k+1}. We can change O_k to G_k and still obtain a valid optimal sequence. However, the new O will have a longer common prefix, which contradicts the fact that O had the longest common prefix out of all optimal sequences.

Why the new sequence is valid

We know that O_{k-1} to the new O_k must be a shortest path (because the greedy solution chose G_k=O_k). The new O_k to O_{k+1} is still a shortest path because the old O_k (which forms a shortest path to O_{k+1}) was increased to become G_k.

# SOLUTIONS:

Setter's Solution
``````#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
if(!(l<=x && x<=r)){
cerr<<l<<" "<<r<<" "<<x<<endl;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

int T;
int n,m,l;
int arr;
int dist;
int edge;
int dp;
int main(){
//freopen("03.txt","r",stdin);
//freopen("03o.txt","w",stdout);
while(T--){
for(int i=1;i<=l;i++){
if(i==l){
} else{
}
if(i>1){
if(arr[i] == arr[i-1]){
cerr<<arr[i]<<endl;
}
assert(arr[i]!=arr[i-1]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
edge[i][j] = -1;
dist[i][j] = 1e9 + 5;
}
dist[i][i] = 0;
}
for(int i=0;i<m;i++){
int u,v,w;
assert(u!=v);
assert(edge[u][v] == -1);
edge[u][v] = edge[v][u] = w;
dist[u][v] = dist[v][u] = w;
}

for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
}
}
}
bool ok=true;
for(int i=1;i<=l-1;i++){
assert(edge[arr[i]][arr[i+1]] != -1);
if(edge[arr[i]][arr[i+1]] != dist[arr[i]][arr[i+1]]){
ok=false;
}
}
if(!ok){
cout<<-1<<endl;
continue;
}
dp= 1;
for(int i=2;i<=l;i++){
int sm = 0;
dp[i]= 1<<30;
for(int j=i-1;j>=1;j--){
sm += edge[arr[j]][arr[j+1]];
if(sm != dist[arr[j]][arr[i]]){
break;
}
dp[i] = min(dp[i],dp[j] + 1);
}
}
cout<<dp[l]<<endl;
}
assert(getchar()==-1);
}
``````
Tester's Solution
``````#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

#define int ll

int dist,dp;
int b;
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,m,l;
int i,j,k;
cin>>n>>m>>l;
rep(i,l){
cin>>b[i];
b[i]--;
}
rep(i,n){
rep(j,n){
dist[i][j]=inf;
dp[i][j]=inf;
}
dist[i][i]=0;
dp[i][i]=0;
}
int u,v,w;
rep(i,m){
cin>>u>>v>>w;
u--;
v--;
dist[u][v]=w;
dist[v][u]=w;
dp[u][v]=w;
dp[v][u]=w;
}
rep(i,n){
rep(j,n){
rep(k,n){
dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);
}
}
}
i=0;
j=1;
ll sofar=0;
int ans=2;
while(j<l){
if(dp[b[i]][b[j]]==sofar+dist[b[j-1]][b[j]]){
sofar+=dist[b[j-1]][b[j]];
j++;
}
else{
if(i+1==j){
ans=-1;
break;
}
ans++;
sofar=0;
i=j-1;
}
}
cout<<ans<<endl;
}
return 0;
}
``````
Editorialist's Solution
``````#include <bits/stdc++.h>
using namespace std;

const int mxN=200, mxL=1e4;
int n, m, l, b[mxL], d1[mxN][mxN], d2[mxN][mxN];

void solve() {
//input
cin >> n >> m >> l;
for(int i=0; i<l; ++i)
cin >> b[i], --b[i];
memset(d1, 0x3f, sizeof(d1));
for(int u, v, w; m--; ) {
cin >> u >> v >> w, --u, --v;
d1[u][v]=d1[v][u]=w;
}

//all pairs shortest path with floyd warshall
memcpy(d2, d1, sizeof(d1));
for(int i=0; i<n; ++i)
d2[i][i]=0;
for(int k=0; k<n; ++k)
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
d2[i][j]=min(d2[i][k]+d2[k][j], d2[i][j]);

//build a
int ans=1;
for(int i=0, j=0; i<l-1; i=j, ++ans) {
//make sure path from b[i] to b[j] is shortest while trying to extend j
while(j+1<l) {
//find length of paths between cities in b[i] and b[j+1]
int e=0;
for(int k=i; k+1<=j+1; ++k)
e+=d1[b[k]][b[k+1]];
if(e>d2[b[i]][b[j+1]]) {
//not shortest path
break;
}
++j;
}
if(i==j) {
//we can't extend
cout << "-1\n";
return;
}
}
cout << ans << "\n";
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

int t;
cin >> t;
while(t--)
solve();
}
``````

Please give me suggestions if anything is unclear so that I can improve. Thanks 8 Likes

Hey, in the setters solution the last part

for(int i=2;i<=l;i++){
int sm = 0;
dp[i]= 1<<30;
for(int j=i-1;j>=1;j–){
sm += edge[arr[j]][arr[j+1]];
if(sm != dist[arr[j]][arr[i]]){
break;
}
dp[i] = min(dp[i],dp[j] + 1);
}
}

This takes L^2 time complexity(worst case) and L is 10^4 thus L^2 will be 10^8 and if have to do this for 10 test cases. Will it not give TL

2 Likes

If you think about it, it’s O(ln) and not O(l^2).

Explanation

The shortest path cannot consist of more than n nodes (otherwise some node would repeat and it would not be the shortest). The inner loop breaks once the path is not the shortest, so it runs at most n times.

3 Likes

oh yes , my bad …thanks dude 1 Like

I used that observation to get AC. Btw it was a very nice problem for people who want to try dp + floyd warshall.

1 Like

Excuse me,

If d is the same as the shortest distance from B_{last} to B_{next+1}, we can’t extend anymore, so we stop.

it should be

If d is not the same as the shortest distance from B_{last} to B_{next+1}, we can’t extend anymore, so we stop.

right?

``````using namespace std;

typedef long long int ll;
typedef unsigned long long ull;
typedef double db;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;

#define fi first
#define sc second
#define w(n) while(n--)
#define f(i,n) for(ll i=1;i<=n;i++)
#define fr(i,n) for(ll i=0;i<n;i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
w(t)
{
ll n,m,l;
cin>>n>>m>>l;
ll b[l+1];
ll shortest_path[n+1][n+1];
ll pathchk[n+1][n+1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
{shortest_path[i][j]=0;  pathchk[i][j]=0;}
else{ shortest_path[i][j]=INT_MAX;pathchk[i][j]=INT_MAX;}
}
}
ll ans=1;
for(int i=1;i<=l;i++)
{
cin>>b[i];
}
f(i,n)
{
ll u,v,w;
cin>>u>>v>>w;
u--;v--;
shortest_path[u][v]=w;
shortest_path[v][u]=w;
pathchk[u][v]=w;
pathchk[v][u]=w;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(j==i)
continue;
for(int k=1;k<=n;k++)
{
if(k==i)
continue;
shortest_path[j][k]=min(shortest_path[j][k],shortest_path[j][i]+shortest_path[i][k]);
}
}
}
/* for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<shortest_path[i][j]<<" ";
}
cout<<"\n";
}*/
if(l==2)
cout<<2<<"\n";
else
{
ll k=0,q=1;ll fg=1;ll pichla=0;
for( q=1;q<=l-1;q=q+fg-1)
{
k=0;
for(int j=q+1;j<=l;j++)
{
k=k+pathchk[b[j-1]][b[j]];
ll d=shortest_path[b[q]][b[j]];
if(k!=d)
{
ans++;
fg=j-1-pichla;
pichla=fg;
//cout<<fg<<"\n";
k=0;
break;
}
}
}
cout<<ans<<"\n";
}
}
}

why my code is giving runtime error can anybody please explain``````

Can you please explain me that if we get no solution for the minimum subsequence…but for another subsequence we got one possibility then how are we handling this case?