Блог пользователя wil93

A graph problem
Автор wil93, 14 лет назад, По-английски
I'm solving a problem from Italian Olympiad in Informatics, the statament says:

There is a secret organization. If you want to enter the organization you must find two members of the organization who will guarantee for you. You got N guys, and M relationships (i,j) between them. A relationship means that guy[i] guaranted for guy[j] (or vice-versa).

A "triad" is a triple (i,j,k) of guys such the relationships (i,j) (j,k) (k,i) exist.

You want to count how many triads are in the input file, that is formed as follows:

First line, M (relationships) and N (guys)
From 2 to M+1 each line has 2 integers (i,j) representing a relationship between i and j (or viceversa)

Output: the number of triads.

  •  1 ≤ N ≤ 100000.
  • N-1 ≤ M ≤ 2N-3.
  • 1 ≤ I, J ≤ N.

    • Sample input:
    13 8
4 2
8 3
1 2
8 5 
6 8
4 8
7 2
6 7
2 8
7 4
8 1
5 6
3 2
    Output:
    5

    Note: the order in which you consider a triad is irrelevant. In the sample we have the triad 2,4,7 that is the same as saying 4,7,2 ...

    - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    • Проголосовать: нравится
    • +8
    • Проголосовать: не нравится

    14 лет назад, # |
      Проголосовать: нравится 0 Проголосовать: не нравится
    My first approach was to use a map < int, set<int> > to get the relationship between (x,y) as follows:

    if ( mymap[x].find(y) != mymap.end() ) // then (x,y) exist

    I'm still convinced that this method should be ok, for the logaritmic search of set.

    So, for each guy (A), i try all his adjacent guys (B), and for each adjacent guy of B (guy C) i check if (C,A) exist.

    May this check be simplified in some way?

    Anyway the condition will be true for 2,4,7 but also for 4,2,7. So i thought "I'll make a set of the SUMS of triads indexes" like: myset.insert(a+b+c); // will not be performed if (a+b+c) is already in the set

    But in this way some diffirent triads were recognized equal. So i changed as follows:
    myset.insert(a+b+c+a*b*c);

    This gross method got 5/5 test cases (but the last test ran in 2,2 seconds while the limit was 2)

    - - - - - - - - - - -

    Then i made an observation: if a triad (x,y,z) exists, then my algorithm will find it exactly 6 times (disposition of 3 by 2 without repetition).

    Then instead of inserting everytime in the set, I made a simple count++ and at the end i made printf("%d",count/6);

    I was surprised when i saw that the new algorithm had the same execution time of the old one :(

    - - - - - - - - - - -

    Then I tried with the good old adjacency matrix, and it worked! Last test in 0,15 sec!
    But when running with a big N gets about 2GB of ram on my pc -.-''

    - - - - - - - - - - -

    After all, i noticed that the condition N ≤ 100000 is not applied (in the biggest test, N < 2000) so my program fit in time & memory. But the question is: how the hell is possible to fit with a big N ?
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Oh, and i have a little question: can I prove that having 6 integers (a,b,c) and (d,e,f) will never be true the condition (a+b+c+a*b*c) == (d+e+f+d*e*f)? Obviously assuming (d,e,f) isn't a permutation of (a,b,c)
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        No, there are many test exist that incorect for your rule:
        {(1,1,5) , (1,2,3)}. 
        you can write code to see all the test, like this:
        for (int i=1;i<=100;i++)
        for (int j=i;j<=100;j++)
        for (int z=j;z<=100;z++){
        int tmp= i+j+z + (i*j*z);
        if (mark[tmp]){
        printf ("%d %d %d\n%d %d %d\n//////////////\n", i,j,z, x[tmp],y[tmp],k[tmp]);
        }
        else{
        mark[tmp]= true;
        x[tmp]=i, y[tmp]=j, k[tmp]=z;
        }
        }

        ------------------------------
        for your main question, i think greedy algorithm can solve this.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Oh that's true :)

          But in the main task we have

          (a≠b≠c) and (d≠e≠f)

          Couse nobody can guarantee for himself...

          Again, if this condition can fail (or cannot fail), would it be possible to find the mathematical proof of that?
          → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          I just found with your code {1,4,5} and {1,2,9} that fails my condition :(
          → Ответить
    14 лет назад, # |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Hi,

    I have this heuristic solution due to the sparse nature of the graph.

    Firstly, we compute the degrees of each vertex in the graph (in-degree + out-degree).

    If degree[x] <= 1, we know that we can reject x, as x will never form a triad.

    If degree[x] = 2, then we know that if x is in a triad, it can only be in one triad. So we can check whether x is in a triad and then delete it from the graph.

    If we do this simplification, we will eventually end in a situation where degree[x] >= 3 for all x. I think the worst case is if we do not delete any edges at all during this process (basically a complete graph followed by a lot of isolated vertices).

    Therefore, suppose the graph has K vertices left after we simplify the graph:

    2N - 3  = approximately K^2. That means we will have around sqrt(N) vertices left.

    If we use the K^3 algorithm now, the solution will be on the order of N*sqrt(N), which is about 32 million. I think this should run in time.

    If not, you can add in more heuristics. For example, you can run SCC and analyse each component separately. Maybe the transpose graph is even easier to analyse (This is assuming that (i,j) and (j,i) are both allowed. In that case, you are able to get a complete (or almost complete) undirected graph, so the transpose graph has very little edges). You can analyse the number of triads in the transpose graph. Suppose that is A. Then the answer is (K choose 3) - A.

    EDIT:

    Oops, I realised that it does not have to be a complete graph. All it needs to be is a 3-regular graph. That means there are still N/3 vertices left! :O.

    To solve this, I think we can keep removing vertices for degrees <= 10 for example, or until the remaining number of vertices is small enough. Then the preprocessing time will be around N * lg N * (10 choose 2) = 74 million, which should be small enough.

    In any case, this algorithm should work on randomly generated graphs, so this should give you a lot of marks :D. Maybe you will fail one or two testcases if you are unlucky.

    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Well, based on the way graph is created there always be vertex with degree <= 2 in each subgraph
      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      The idea of calculating degree is formidable :)
      I'm going to try that :)
      → Ответить
    14 лет назад, # |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Everyone seems to skip legend which is important this time ;)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Hi,

      May I know why you say that there will always be a vertex with degree <= 2 in each subgraph? Also, may I know what legend is skipped?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Because there are no more then 2 edges to the guys that becomes part of mafia before given guy
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Sorry, I dont understand what you mean :(. Are you saying that there are no more than 2 edges pointing to the people who form the earliest possible mafia group, before anyone else joins?
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Let say it other way. Let's direct edges from guy, who invites to guy, who invited. Then there are no more then 2 incoming edges
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Oh, so you are saying that we draw edge from i to j with guy i guarantees guy j. Then indegree of any person x <= 2?

              Are you referring to this statement? "If you want to enter the organization you must find two members of the organization who will guarantee for you. "

              However, is it not possible that there are more than 2 people who can guarantee you, and you can choose any two?

              Just checking, if indegree of any person <= 2, is your solution to process the vertices one by one? Since indegree <= 2, the triads each vertex is in can be processed in at most 2 * D[x] time, where D[x] is the outdegree of vertex x. I think you would need some set or map to check for the edges efficiently, so the overall runtime is N lg N?

              → Ответить