Help needed for Spoj problem: Hypertubes, UCBINTH

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
2	maomao90	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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