SECRETMI - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

DIFFICULTY:

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 readString(int l,int r,char endd){
	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){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
int T;
int n,m,l;
int arr[100100];
int dist[202][202];
int edge[202][202];
int dp[10101];
int main(){
	//freopen("03.txt","r",stdin);
	//freopen("03o.txt","w",stdout);
	T=readIntLn(1,10);
	while(T--){
		n=readIntSp(2,200);
		m=readIntSp(1,n*(n-1)/2);
		l=readIntLn(2,10000);
		for(int i=1;i<=l;i++){
			if(i==l){
				arr[i]=readIntLn(1,n);
			} else{
				arr[i]=readIntSp(1,n);
			}
			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;
			u=readIntSp(1,n);
			v=readIntSp(1,n);
			w=readIntLn(1,1000000);
			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]= 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
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// 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[213][213],dp[213][213];
int b[123456];
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 :slight_smile:

8 Likes
2

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
3

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
4

oh yes , my bad …thanks dude :smile:

1 Like
5

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
6

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?

7 
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;
        }
        // applying floyad warshell algorithm 
        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
8

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?