UWCOI20E - Escape - Editorial

PROBLEM LINK:

Practice
Practice

Author: Bumjun Kim
Tester: Jatin Yadav
Editorialist: Bumjun Kim

DIFFICULTY:

Medium

PREREQUISITES:

Dijkstra, Bitmask

PROBLEM:

You are given a graph with N vertices and E edges with some vertices containing keys that lock other vertices. Find the shortest path from vertex 1 to vertex N.

Subtask 1 [30 points]: N \leq 20000, E \leq 100000, K = 0

Subtask 2 [30 points]: N \leq 10000, E \leq 20000, K \leq 6

Subtask 3 [40 points]: N \leq 100000, E \leq 200000, K \leq 12

EXPLANATION:

Subtask 1:

In this subtask, there are 0 keys which means that standard Dijkstra passes the subtask. This solution runs in O(ELogE).

Subtask 2:

For this subtask, there are up to 6 keys. It is possible to have a 2D array with dimensions 2^6 and 10000 which stores the subsets of the keys taken and the vertex. Dijkstra can be performed on the new set of vertices which passes the subtask. This algorithm runs in O(2^6*ELog(E*2^6))

Subtask 3:

For this subtask, there are up to 12 keys. It is possible to see that the only nodes with importance are the starting and ending nodes and nodes with either keys or nodes that are locked. Dijkstra can be run from these nodes in order to create a compressed version of the graph. The solution used in subtask 2 can now be used on the compressed graph which passes the subtask. This solution runs in O(24*ELogE).

SOLUTIONS:

Setter's Solution
#include "bits/stdc++.h"
using namespace std;

int main() {
  
  long long n, e, k;
  cin >> n >> e >> k;
  
  bool impcheck[n+1];
  memset(impcheck, 0, sizeof impcheck);
  
  vector<pair<long long, long long> > adj[n+1];
  
  vector<long long> imp;
  imp.push_back(1);
  imp.push_back(n);
  impcheck[1] = true;
  impcheck[n] = true;
  
  for (long long i=0; i<e; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    adj[a].push_back(make_pair(b, c));
    adj[b].push_back(make_pair(a, c));
  }
  
  vector<pair<long long, long long> > lpairs;
  
  long long addmask[n+1];
  memset(addmask, 0, sizeof addmask);
  long long needmask[n+1];
  memset(needmask, 0, sizeof needmask);
  
  for (long long i=0; i<k; i++) {
    long long a, b;
    cin >> a >> b;
    lpairs.push_back(make_pair(a, b));
    imp.push_back(a);
    imp.push_back(b);
    addmask[a] |= (1<<i);
    needmask[b] |= (1<<i);
    impcheck[a] = true;
    impcheck[b] = true;
  }
  
  long long su = imp.size();
  
  vector<pair<long long, long long> > comp[su+1];
  
  long long addmaskc[su];
  long long needmaskc[su];
  memset(addmaskc, 0, sizeof addmaskc);
  memset(needmaskc, 0, sizeof needmaskc);
  
  for (long long RT=0; RT<imp.size(); RT++) {
    long long sr = imp[RT];
    long long distance[n+1];
    for (long long i=0; i<n+1; i++) distance[i] = LLONG_MAX;
    priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > > proc;
    proc.push(make_pair(0, sr));
    
    addmaskc[RT] = addmask[imp[RT]];
    needmaskc[RT] = needmask[imp[RT]];
    
    while (!proc.empty()) {
      pair<long long, long long> r = proc.top(); proc.pop();
      long long no = r.second, di = r.first;
      if (distance[no] < di) continue;
      distance[no] = di;
      if (impcheck[no] && no != sr) continue;
      for (long long i=0; i<adj[no].size(); i++) {
        long long ot = adj[no][i].first;
        long long od = di + adj[no][i].second;
        if (distance[ot] > od) {
          distance[ot] = od;
          proc.push(make_pair(od, ot));
        }
      }
    }
    
    
    for (long long i=0; i<imp.size(); i++) {
      if (i != RT) {
        long long to = imp[i];
        if (distance[to] == LLONG_MAX) continue;
        comp[RT].push_back(make_pair(i, distance[to]));
      }
    }
  }
  
  long long dist[su+1][(1<<k)];
  for (long long i=0; i<su+1; i++) for (long long j=0; j<(1<<k); j++) dist[i][j] = LLONG_MAX;
  
  priority_queue<pair<long long, pair<long long, long long> > > proc; // dist, mask, node
  proc.push(make_pair(0, make_pair(0, 0)));
  
  long long mn = LLONG_MAX;
  
  while (!proc.empty()) {
    pair<long long, pair<long long, long long> > fi = proc.top(); proc.pop();
    long long di = fi.first;
    long long no = fi.second.second;
    long long ma = fi.second.first | addmaskc[no];
    if (dist[no][ma] < di) continue;
    dist[no][ma] = di;
    if (no == 1) {
      mn = min(mn, di);
    }
    for (long long i=0; i<comp[no].size(); i++) {
      long long ot = comp[no][i].first;
      long long dis = di + comp[no][i].second;
      if ((ma | needmaskc[ot]) == ma) {
        if (dist[ot][ma] > dis) {
          dist[ot][ma] = dis;
          proc.push(make_pair(dis, make_pair(ma, ot)));
        }
      }
    }
  }
  
  if (mn == LLONG_MAX) cout << -1 << endl;
  else cout << mn << endl;
  
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
  os<<"("<<p.first<<", "<<p.second<<")";
  return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
  os<<"{";
  for(int i = 0;i < (int)v.size(); i++){
    if(i)os<<", ";
    os<<v[i];
  }
  os<<"}";
  return os;
}

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const ll INF = 1e16 + 61;
const int N = 100005;
const int K = 30;
ll D[K][K];
int ulta[N];

struct graph{
  int n;
  vector<vector<pair<int, ll>>> con;
  void add_edge(int u, int v, ll c, bool bidirectional = true){
    con[u].push_back({v, c});
    if(bidirectional) con[v].push_back({u, c});
  }
  graph(int n) : n(n), con(n + 1){};
  vector<ll> dijkstra(int s, bool allow_locked = 0){
    priority_queue<pair<ll, int>,vector<pair<ll, int>>, greater<pair<ll, int>> > Q; 
    vector<ll> dist(n + 1, INF);
    dist[s] = 0;
    Q.push(pair<ll, int>(0LL,s));
    while(!Q.empty()) {
      pair<ll, int> top = Q.top();
      Q.pop();
      int v = top.second;
      ll d = top.first;
      if(d <= dist[v]) {
        for(auto it : con[v]){
          int v2 = it.first;
          ll cost = it.second;
          if(dist[v2] > dist[v] + cost) {
            dist[v2] = dist[v] + cost;
            if(!allow_locked && ulta[v2]) continue;
            Q.push(pair<ll, int>(dist[v2], v2));
          }
        }
      }
    }
    return dist;
  }
};
int locked[K];
// O(k^2 * 2^k + k * |E|)
int main(){
  int n, m, k; sd(n); sd(m); sd(k);
  graph g(n);
  for(int i = 1; i <= m; i++){
    int u, v, c;
    sd(u); sd(v); sd(c);
    g.add_edge(u, v, c);
  }

  locked[0] = 1;
  locked[2 * k + 1] = n;

  for(int i = 1; i <= k; i++){
    int p, q; sd(p); sd(q);
    assert(p != q);
    locked[i] = q;
    locked[i + k] = p;
    ulta[q] = i;
  }

  for(int i = 0; i <= 2 * k + 1; i++){
    vector<ll> d = g.dijkstra(locked[i]);
    for(int j = 0; j <= 2 * k + 1; j++){
      D[i][j] = d[locked[j]];
    }
  }

  graph g2((2 * k + 2) << k);

  for(int i = 0; i <= 2 * k + 1; i++){
    for(int mask = 0; mask < (1 << k); mask++){
      int node = (i << k) + mask;
      for(int j = 0; j <= 2 * k + 1; j++) if(j != i){
        if(ulta[locked[j]] && !(mask >> (ulta[locked[j]] - 1) & 1)) continue;
        int node2 = (j << k) + (mask | ( (j > k && j <= 2 * k) ? (1 << (j - k - 1)) : 0));
        g2.add_edge(node, node2, D[i][j], 0);
      }
    }
  }
  vector<ll> d = g2.dijkstra(0, 1);
  ll ret = INF;
  for(int mask = 0; mask < (1 << k); mask++) ret = min(ret, d[((2 * k + 1) << k) + mask]);
  printf("%lld\n", ret >= INF ? -1 : ret);
}
3 Likes

This is really a nice problem

Why am I not getting even 1st subtask pass. I took the code from geeks for geeks and every testcase is getting passed except the 1st testcase from each subtask. Here is my solution: https://www.codechef.com/viewsolution/29899994

Problem on codechef is that it doesnt have memory limit. So some faster solns managed to get 100pts with soln of 2nd subtask. Going by memory used I can see 3 AC solns with ~3GB memory seems subtask 2 gave AC on subtask 3 as well.
E.g. - My soln https://www.codechef.com/viewsolution/29897863

2 Likes

@jha try initializing the distance vector by LLONG_MAX or an equivalent value.

I previously held an account on an email id that i deactivated and made another account on the same email id . I just realized that the change is not reflected in my discuss username . Anything i can do to change it ? @admin ?
This is my current account : the___reaper

thanks bro, worked for 1st subtask

is there another way to compress the graph?

during solving this problem i find bfs fail in shortest distance weighted graph. is it correct or not? please suggest.

@ajaygupta007
yes it is a well known fact …bfs will find shortest path only if weight of all the edges are same