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