The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
233 views

a)(d,c)

b)(d,b)

c)(e,b)

d)(e,f)

asked in DS by Veteran (70k points) | 233 views

3 Answers

+1 vote

Answer would be b) (d,b)

You can find meaning of cross edge (for BFS on undirected graph)  here. Usually cross edges are used in context of Depth First Search Forest.

Since edge (d,b) is present in the breadth first search tree, it can't be cross edge (according to the meaning in the given link).

Following is the breadth first tree:

answered by Loyal (4k points)
reshown by
@pratyush..BFS undirected graph doess not have back and forward edges??

@Akriti: I know for a fact that BFS of an undirected graph does not have back and forward edges. I have checked it on few simple graphs, but don't have an elaborate proof. However one of the answers in the this  post may clear it little bit. If you still want a credible source then you can check CLRS 3rd ed. problem 22-1 (a). This problem asks reader to prove the same.

THANKS @PRATYUSH
bfs tree in ans given ll b undirected ?
Yes. But even if they are directed it doesn't matter. Trees have an implicit direction from ancestor towards descendants. Actually I tried to draw it undirected but since I used an online tool, which had only directed lines to draw, the tree is directed here.
+1 vote

algorithm to detect cross edge and tree edge : 

Algorithm BFS(Vertex s
// iterative algorithm

initialize container L0, level, to contain vertex s 
i = 0 
while Li is not empty do {
create container Li+1 to initially be empty      // next level 
for each vertex v in Li do      // vertices in previous level
for each edge e incident on v do
if edge e is unexplored then
let w be the other end of e 
if vertex w is unexplored then 
    label e a discovery edge and  insert w into Li+1 
else 
    label e as a cross edge
i = i + 1
} //
So we can say that in case of bfs  with undirected  graph , the edge which are not including in the tree are cross edge.
So B will be the answer  , because bfs  tree contains : { (a-c) , ( a-d) , (a-e) ,  (c - f) ,  ( d - b ) }  all this mentioned edges would be tree edges.
answered by Loyal (2.9k points)

 @vipsharmavip solved all three in fb hck ?

yep, but got wa answer on third due to some silly mistake in my code.
I did the recurrence but multiplied by the probability term at last. Overflows may times.
That problem will be solved either by coefficient in binomial expansion ( polynomial multiplication )
i used the above , and also can be solvable with dynamic programming.

This is my correct code for third one :
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
vector<double>  multiply(vector< double > A , vector< double > B){
  int m = A.size();
  int n = B.size();
   vector< double > res(m + n - 1);
   for(int i = 0 ; i < m + n - 1 ; ++i ) res[i] = 0;
   for(int i = 0 ; i < m ; ++i )
     for(int j = 0 ; j < n ; ++j )
     res[i + j] += (A[i] * B[j]);
     return res;
}
double coeficient(int X , int Y , int S){
    vector< double > res;
    vector< double > A;
    res.push_back(1);
    A.push_back(0);
    for(int i = 1 ; i <= Y ; ++i )
    A.push_back(1.0/Y);
    while(X){
      if(X & 1)
      res = multiply(res , A);
      X = X >> 1;
      A = multiply(A , A);
    }
     double ans = 0;
     S = max(0 , S);
     for(int i = S  ; i < res.size() ; ++i )
        ans += res[i];
 return ans;
}
int main(){
                cin.sync_with_stdio(false);
                freopen("a.txt","r",stdin);
                freopen("b.txt","w",stdout);
                   int T , tt = 1;
                   cin >> T;
                   while(T--){
                                 int N , S ;
                                 cin >> S >> N;
                                 double ans = 0.0;
                                 for(int i = 1 ; i <= N ; ++i ){
                                  string x;
                                  cin >> x;
                                  int X = 0;
                                  if(x[1] == 'd')
                                  X = (x[0] - '0') ; else
                                  X = (x[0] - '0') * 10  + (x[1] - '0');
                                  int idx = -1;
                                  if(x[1] == 'd')
                                  idx = 2; else
                                  idx = 3;
                                  int Y = 0;
                                  if(idx + 1 == x.size())
                                   Y = x[idx] - '0'; else {
                                   if(x[idx + 1] >= '0' && x[idx + 1] <= '9')
                                   Y = (x[idx] - '0') * 10 + (x[idx + 1] - '0'); else
                                   Y = x[idx] - '0';
                                   }
                                      int  Z = 0;
                                       for(int j = 0 ; j < x.size() ; ++j ){
                                         if(x[j] == '+'  || x[j] == '-'){
                                           for(int k = j + 1 ; k < x.size() ; ++k )
                                             Z = Z * 10 + (x[k] - '0');
                                             if(x[j] == '-')
                                             Z = -Z;
                                             break;
                                         }
                                    }
                                   int s  = S - Z;
                                   double res = coeficient(X , Y , s );
                                   ans = max(ans , res);
                               }
                               printf("Case #%d: %.7lf\n",tt++, ans);
                   }
 return 0;
}

 

yes ..generating function concept.  $\Sigma$ the coefficients of x^k where k > (H-z).

Yes will solve it in your method later :)

But I must say ...I used the almost same code for input processing .. But when I downloaded other's code they used stringstream.. hardly $4$ to $5$ lines

yep stringstream is also another way , i used it with getline , many times...
any good link to know clearly about forward,back ad cross edges?

@vipsharmavip 

I am assuming you have gone through some problems (QS) and solved using generating function multiplication as above. Could you refer $2$/$3$ problems on this type (solvable using above method) from any OJ ?

@vipsharmavip  Congrats :)

Debashish Deka

https://a2oj.com/Category.jsp?ID=42  :  all this problem are based on fast fourier transform( fft ) 

otherwise you can google it.

As in my code for the third problem i used 0(n^2) method to multiply two polynimals , 

FFT polynomial multiplication , are easy and helps to multiply two polyonomials in O(nlogn) complexity,

Mostly problems which are based on FFT solution are not so easy  but after deducing the solution to general form they will becom easy to solve.

http://e-maxx.ru/algo/fft_multiply  :  this is the link where you can find the fft polynomial multiplication

 ( Translate to english ) 

@  srestha

why congrats ?

 

I am aware of the max.ru page on fft. But I could not get easily from there, so I tried from this ..again in russian :) . Thanks for the problem set link. So, if the dice values are very big, then fft should be used right ?

The above problem is also solvable with dynamic programming
f( roll , face , sum )  with three states or  with 2 states too
where f( i , j ,  k ) =  number of ways to make k sum ending with jth value in ith roll of dice.

Complexity will be  : O( roll * face * sum )    or let say O( N ^ 3 )        with dp
with  coefficient   we have to calclaulate ( 0  +  x + x^2 +  x^3 ....  X^face ) ^ roll     
then  again it will be  : O(N ^ 3 )  , if we are multiplying two polyinomials in O(N^2) and if we use fft polynomial divide and conq.   then it will be O(N^2logN)   which is very fast as compared to above.
So if we increase some constraint on the third problem or number of test cases.  Then go for fast multiplication ( FFT )
U have done all three questions.
I have done last year also, not a big deal ! anyways thanks
regarding above comments.

I know how to find complexity. Thanks for explaining, though. Hope in upcoming days will discuss more on these problems.

like to see you in further rounds! (y)
+1 vote

Answer

 

answered by Boss (6.1k points)
@Arnab Bhadra Does any other cross edge exists in above tree.

Related questions

0 votes
1 answer
1
asked in Programming by rahul sharma 5 Veteran (17.4k points) | 101 views
0 votes
1 answer
2
asked in DS by Parshu gate Loyal (3.6k points) | 33 views
0 votes
0 answers
3


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,982 questions
36,818 answers
91,198 comments
34,706 users