You are not logged in. Please login at www.codechef.com to post your questions!

×

TACTQUER- editorial

2
1

PROBLEM LINK:

Practice
Contest

Author: Tuấn Anh Trần Đặng
Tester: Kamil Dębowski
Editorialist: Tuấn Anh Trần Đặng

DIFFICULTY:

Hard

PREREQUISITES:

Graph, Dynamic Programming

Problem

Given a weighted vertex-catus of N vertices answer Q queries about the shortest path between a pair of arbitrary vertices u and v.

Assumptions

We will mainly work on the DFS tree of the catus eg. performing DFS from 1 and only take the edges that connect a vertex to the unvisited vertex during the process.

Sub-problem 1

Calculate the shortest path from 1 to every vertex u.

Solution

Let’s call this d[u]. We can get d by doing a dynamic programming in the DFS process. When we visit u there are two situations:

  1. u is not belong to any cycle: d[u] = d[parent[u]] + length of the edge from parent[u] to u.
  2. u is in a cycle C. In this case let top[C] is the vertex closest to the root in C. d[u] = d[top[C]] + shortest path from top[C] to u.

Note that there are exactly two ways to go between two vertices in the same cycle C so the shortest path from top[C] to u is just either the distance L from top[C] to u in the DFS tree or length of cycle C - L. top[C] should be pre calculated.

Sub-problem 2

Calculate the distance disTopDown(u, v) between u and one of it descendants v (in the DFS tree).

Solution

  • If u is not belongs to any cycle then disTopDown(u, v) = d[v] - d[u]. This is correct since when we go from 1 to v we must go to u first.
  • If u is belong to the cycle C. When go from 1 to v we may not go to u since we have two ways to pass through the cycle C. However we will have to go to the vertex b that is the vertex closest to v in C. We have that disTopDown(u, v) = d[v] - d[b] + shortest distance from b to u. Again since b and u are in the same cycle the distance between them can be easily calculated.

So it seems like our solution is quite obvious now: distance between two vertices u and v is disTopDown(lca(u, v), u) + disTopDown(lac(u, v), v) where lca(u, v) is the lowest common ancester of u and v in the DFS tree. But we still missing one more piece: how to find b. Let get to the final sub-problem.

Sub-problem 3

We will make the problem a bit more genernal. Given the cycle C and the vertex v find the first vertex of C in the path from v to the root of the DFS tree.

solution

Hint: we can use the similar technique that we used in finding LCA.

Order the cycle in the way that if cycle A lies on the path from root to cycle B then cycle A will get the larger order. One way is to use the order of the DFS completion of the top vertex eg. if the DFS process at top[B] finished later then B got larger order. Now you may already guessed the solution. We trying to go from v toward the top as far as possible making sure that we never enter the cycle C. Let order[C] is the order of cycle C we have to make sure that the maximum order of cycles that has a vertex in the path from v toward the root does not larger or equal to order[C].

Recall the problem of finding LCA, we have to prepare f[u][i] is the 2^i th parent of u. The formular is quite simple:

  • f[u][0] = parent[u]
  • f[u][i] = f[f[u][i - 1]][i - 1]

Apply the same technique let maxOrder[u][i] is the maximum label from u to its 2^ith parent:

  • maxOrder[u][0] = max(order[u], order[parent[u]]) where order[u] is the order of the cycle contain u or -1 if is does not belong to any cycle.
  • maxOrder[u][i] = max(maxOrder[u][i - 1], maxOrder[f[u][i - 1]][i - 1]);

With maxOrder calculated we try to jump from v toward the root and makesure that we never go a vertex with a order larger than or equal to order[C]. If b exist it will be the parent of the vertex we ended up at since we tried to go as close to C as possible but never enter it.

Summary

The solutions contains three part:

  1. Initial DFS to prepare infomation of the cycles eg. top vertex, label …
  2. Second DFS to calculate d[] and maxLabel[][].
  3. Answer the queries: (distance from u to v) = disTopDown(lca(u, v), u) + disTopDown(lca(u, v), v);

Complexity: O((N + M)logN)

Author's/Tester's Solutions:

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 18 Sep '16, 21:32

tuananh93's gravatar image

5★tuananh93
116613
accept rate: 0%

edited 19 Sep '16, 00:24

admin's gravatar image

0★admin ♦♦
19.5k348496535

Please move the problem to practice, the given link doesn't work.

(22 Sep '16, 01:21) nibnalin6★

I was very disappointed solving that problem, it is very sad that in Codechef you are giving such well-known and messy problem. For example, "BZOJ 2125" is the exactly the same problem. I had also seen a lot of variations of such problem. I'd love to see much more fresh problems here.

link

answered 19 Sep '16, 02:22

notimesea's gravatar image

6★notimesea
1304
accept rate: 0%

my solution using dijkstra : output is ok.. but why it shows sigsev.. please tell ,, :)

include<bits stdc++.h="">

using namespace std;

define max 20001

define INF 100100

vector<int>G[max]; vector<int>cost[max]; int d[max];

struct data {

int city,dist;
data(int a,int b)
{
    city = a;
    dist = b;

}
bool operator < (const data& p) const
{

    return dist>p.dist;
}

};

void Dijkstra(int start,int node) { int i,j,u,v;

for(j=0; j<=node; j++)
    d[j] = INF;

priority_queue<data>Q;

Q.push(data(start,0));

d[start] =0;

while(!Q.empty())
{
    data top = Q.top();
    Q.pop();

    u = top.city;

    for(i=0; i<G[u].size(); i++)
    {
        v = G[u][i];

        if(d[u]+cost[u][i]<d[v])
        {
            d[v] = d[u]+cost[u][i];

            Q.push(data(v,d[v]));
        }
    }
}

}

int main() { int node,edge,i,j,k,l,m,x,y,z,start,end,cas;

scanf("%d",&cas);

for(k=1; k<=cas; k++)
{

    scanf("%d%d%d%d",&node,&edge,&start,&end);

    for(i=0; i<edge; i++)
    {
        cin>>x>>y>>z;

        G[x].push_back(y);
        G[y].push_back(x);

        cost[x].push_back(z);
        cost[y].push_back(z);
    }


   // Dijkstra(start,node);



     if(d[end]==INF)
        printf("Case #%d: unreachable\n",k);

    else
        printf("Case #%d: %d\n",k,d[end]);


    memset(d,0,sizeof(d));

    for(l =0; l<max; l++)
    {
        G[l].clear();
    }

    for(m =0; m<max; m++)
    {
        cost[m].clear();
    }
}

return 0;

}

link
This answer is marked "community wiki".

answered 20 Sep '16, 20:16

suvro_datta's gravatar image

2★suvro_datta
1
accept rate: 0%

my solution using dijkstra .. output is ok.. but why it shows sigsev .. please anyne tell :)

include<bits stdc++.h="">

using namespace std;

define max 200009

define INF 300100

vector<int>G[max]; vector<int>cost[max]; int d[max];

struct data {

int city,dist;
data(int a,int b)
{
    city = a;
    dist = b;

}
bool operator < (const data& p) const
{

    return dist>p.dist;
}

};

int Dijkstra(int start,int node,int end) { int i,j,u,v;

for(j=0; j<=node; j++)
    d[j] = INF;

priority_queue<data>Q;

Q.push(data(start,0));

d[start] =0;

while(!Q.empty())
{
    data top = Q.top();
    Q.pop();

    u = top.city;

    if( u == end ) return ( d[end] );

    for(i=0; i<G[u].size(); i++)
    {
        v = G[u][i];

        if(d[u]+cost[u][i]<d[v])
        {
            d[v] = d[u]+cost[u][i];

            Q.push(data(v,d[v]));
        }
    }
}

}

int main() { int node,edge,i,j,k,l,m,x,y,z,start,end,cas;

    scanf("%d%d",&node,&edge);

    for(i=0; i<edge; i++)
    {
        cin>>x>>y>>z;

        G[x].push_back(y);
        G[y].push_back(x);

        cost[x].push_back(z);
        cost[y].push_back(z);
    }



    scanf("%d",&cas);
    while( cas-- )
    {

    scanf("%d%d",&start,&end);
    printf( "%d\n",Dijkstra(start,node,end) );




    memset(d,0,sizeof(d));



    }


return 0;

}

link

answered 20 Sep '16, 20:20

suvro_datta's gravatar image

2★suvro_datta
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,029
×1,902
×1,281
×1,161
×42
×5

question asked: 18 Sep '16, 21:32

question was seen: 3,344 times

last updated: 22 Sep '16, 01:21