akashm's blog

By akashm, 11 years ago, In English

Hi everyone
I am trying to solve the following problem
http://www.spoj.com/problems/AMR11F/
The editorials to this problem has a hint that it can be solved by floyd warshall algorithm but it doesnt provide the solution.
My question is how would i represent such kind of a graph using adjacency list or matrix. It would be appreciated if the code will be in c/c++/java/c#/python

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Vertices of a graph are:
1) All first floors of all towers
2) All floors connected by some bridge.
So there will be at most N + 2 * M vertices (<=300). For each tower calc distance (in O(1)) between pairs of adjacent vertices.
Run Floyd Warshall algorithm
To answer a query you need to find for each of given froors two nearest vertices and try all possible combinations (at most 4).

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanx for the help...just one more question i know its a silly one
    What is the logic behind 2*M...is it bcoz a bridge connects 2 floors of different towers??

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      Yes. For example we have N = 100, M = 100, and the edge i connects 5-th floor of tower i with 10-th floor of tower (i+1). there will be 300 vertices. In form (tower, floor): (1, 1) (1, 5) (1, 10) (2, 1) (2, 5) (2, 10) ... etc. Let cost of each edge is 42. Let d[U][V] = inf, d[(i, 1)][(i+1, 1)] = 1, d[(i, 1)][(i, 5)] = 5-1, d[(i, 5)][(i, 10)] = 10-5, d[(i,5)][(i+1,10)] = 42, and don't forget — graph is bidirectional i.e. d[U][V] == d[V][U].

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    will you more explore the query part of problem(last statement of your post) ?, as total vertices are N+(2*M) and vertices present in query might not be in those N+(2*M) vertices.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Ок, for example have 100 towers. in tower 5 there is bridges on floors 13 and 25, in tower 42 there is bridges on floors 73, 99, 200. for this two towers there will be 7 vertices of our graph (towerId, floor): (1, 1) (1, 13) (1, 25) (42, 1) (42, 73) (42, 99) (42, 200). the is an query (1, 19) (42, 87) for first point there is two nearest vertices: (1, 13) (1, 25). for the second (42, 73) (42, 99) chek all possible ways (1, 13) -> (42, 73), (1, 25) -> (42, 73), (1, 13) -> (42, 99), (1, 25) -> (42, 99)

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        @Alias what to do after finding these paths ?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no of vertices will be at most 2*(N+M)

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How come? From what i understand we represent the first floor of each tower by a vertice. Since there are n towers so we have n vertices at the moment. Now for each, bridge if the vertice is not already present, we add the vertices. Since there are m possible bridges. The no of distinct vertices to be added can be 2*m, since each query can have two new vertices.

      So the total number of vertices can be at max n+2*m