Help needed for Spoj problem: Hypertubes, UCBINTH

#	User	Rating
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	171
2	awoo	165
3	adamant	163
4	TheScrasse	159
5	maroonrk	155
6	nor	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

I tried to solve the Hypertubes problem on Spoj but I am getting TLE.

I tried to store the graph in the adjacency list(using set) and then iterated over 0 to n and for every entry in its adjacency element, updated its distance. It gives WA on the 25th test case which I understand why it is giving WA. Also, I think its complexity is m*k*k*log(min(n,k*k)). log factor is coming from insertion in the set.

NOTE: Graph storing part is not giving TLE.

For reference here is my WA code

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
double pi=acos(-1);
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
const ll mod=1e9;
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace std;
void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int N=100000;
vector<set<int>> graph(N);
void solve(){
  int n,k,m;
  cin>>n>>k>>m;
  rep(i,0,m){
    vector<int> v1(k);
    rep(j,0,k)  cin>>v1[j];

    rep(j,0,k){
      rep(l,j+1,k){
        graph[v1[j]-1].insert(v1[l]-1);
        graph[v1[l]-1].insert(v1[j]-1);
      }
    }
  }
  vector<ll> dis(n,1e18);
  dis[0]=1;
  rep(i,0,n){
    for(auto j:graph[i]){
      if(j!=i) dis[j]=min(dis[j],dis[i]+1);
    }
  }
  if(dis[n-1]==1e18) cout<<-1<<endl;
  else cout<<dis[n-1]<<endl;
}
int main(){
    optimizeIO();
    {solve();}
}

I had to store the graph as same as above(it will not give me TLE). I tried to use Disjoint set union for answering -1 if (n-1) index is not reachable from 0. If it is reachable then I tried to use priority_queue(Dijkstra) for finding the minimum distance from 0 to n-1 but it is giving me TLE on the 25th test case. I think that this approach has to be worked fine but it is throwing TLE. I also tried only Dijkstra without Disjoint set union but it still gives me TLE.

Here is my code which is getting TLE

TLE Code

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
double pi=acos(-1);
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
const ll mod=1e9;
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)
using namespace std;
void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int N=100000;
vector<set<int>> graph(N);
struct dsu{
  vector<ll> par,rank;
  dsu(ll n):rank(n,1),par(n,1){
    rep(i,0,n) par[i]=i;
  }
  ll root(ll a){
    if(a==par[a]) return a;
    return par[a]=root(par[a]);
  }
  void merge(ll a, ll b){
    a=root(a);
    b=root(b);
    if(a==b) return;
    if(rank[a]<rank[b]) swap(a,b);
    par[b]=a;
    rank[a]+= rank[b];
  }
};
void solve(){
  int n,k,m;
  cin>>n>>k>>m;
  rep(i,0,m){
    vector<int> v1(k);
    rep(j,0,k)  cin>>v1[j];
    rep(j,0,k) rep(l,0,k) if(j!=l) graph[v1[j]-1].insert(v1[l]-1);
  }

  dsu d(n);
  rep(i,0,n) for(auto j:graph[i]) d.merge(i,j);
  if(d.root(n-1)!=d.root(0)){
    cout<<-1<<endl;
    return;
  }

  vector<ll> dis(n,1e18);
  vector<ll> vis(n,0);
  dis[0]=1;
  priority_queue<pii,vector<pii>,greater<pii>> pq;
  pq.push({1,0});

  while(!pq.empty()){
    pii x=pq.top();
    pq.pop();
    if(x.s==n-1){
      cout<<dis[n-1]<<endl;
      return;
    }
    if(vis[x.s]==1) continue;
    vis[x.s]=1;
    for(auto j:graph[x.s])
      if(dis[j]> 1+x.f){
        dis[j]=1+x.f;
        pq.push({dis[j],j});
      }
  }
}
int main(){
    optimizeIO();
    solve();
}

My Questions are:

Can I get rid of this TLE?
Also, can someone mention what is expected complexity of this problem?
Is there any other methods to solve this question?

Edit 1: Here is proof that WA coming on 25th.

Comments (10)

Write comment?

rohit_1402

4 years ago, # |

I think you are getting TLE bcz you are using O(M.K^2.log(something)) for the storing the graph part as if M is 1000 and K is 1000 then definitely it is TLE. And for your WA code it is getting WA before the Test Case 25 so it is not running for further cases and giving the verdict WA not the TLE

→ Reply

vineetjai

4 years ago, # ^ |

← Rev. 3 →

It is giving WA after saying running 25th. So I think it means WA on 25th.

I have also submitted your code and it is showing running on 24th and then giving WA :(

you have to keep refreshing the page frequently only then you can see WA on 25th because 24 and 25 are very close.

Edit: Here is proof: URL

Ohh.. Yes it is giving WA on 25th. But why using priority_queue or even simple queue it is giving TLE?, the question remains the same <..>

Yes, why TLE with priority_queue?

merlin_

u might want to take a look at this

Did you use the same approach to solve the problem? If it is different then please share yours.

feodorv

COCI 2012/2013, task HIPERCIJEVI, the excerpt from "Round 5 solutions".

The graph described in the problem statement is a hypergraph. When solving the shortest path problem on a hypergraph, we can convert it to a “normal” undirected graph by simply connecting all pairs of nodes (stations) on the same hyperedge (hypertube) with undirected edges. This results in a graph with a total of $$$N$$$ nodes and $$$MK(K-1)/2$$$ edges. A simple breadthfirst search applied to this graph is then a solution, ignoring time and memory constraints. However, the constraints prevent such a solution from obtaining all points.

The most elegant way to speed up the solution is adding a new node for each hypertube, connecting it with undirected edges to all stations connected to the corresponding hypertube. Such a graph has $$$N+M$$$ nodes and $$$MK$$$ edges. A breadth-first search applied to this graph yields the solution $$$2X-1$$$, where $$$X$$$ is the number of stations on the shortest path from station $$$1$$$ to station $$$N$$$.

Necessary skills: breadth-first search

Thanks for the solution reference.

vineetjai's blog