CareerCup

I think this code will fail when you stuck in an infinite cycle.
Let the path 1-> 2-> 3-> 4-> 1
Then, you will be stuck in your first while loop.

i may suggest a code in python:

def find_meet(edges_list, a,b,n):
visited = [0]*n
d = {}
visited[a] = 1
if visited[b] == 1:
return a
visited[b] = 1
t = edges_list[a]
while t!= -1 and visited[t] == 0:
visited[t] = 1
t = edges_list[t]
t = edges_list[b]
# print(visited)
while t!= -1 and visited[t] == 0:
visited[t] = 1
t = edges_list[t]
# print(visited)
if t == -1:
return -1
return t


t = int(input())
for _ in range(t):
n = int(input())
edges_list = list(map(int,input().split()))
a,b = map(int,input().split())
# print([i for i in range(n)])
# print(edges_list)
print(find_meet(edges_list, a, b, n))

################# SIddhesh dosi #######################

I am not sure how can we do it in O(Log(n)), but with O(n) it should be easy.

1) Keep a map where you store the cells which can be reached by C1.
2) Traverse through the path of C1, keep on storing the path in the map. {c1: 1, c1->exit: i, c1->exit->exit: 1 ....}
3) Do the same traversal for c2, at any time if you find the exit path exist in the above map then that is the meeting point of 2 cells.

In Javascript:

var path               = {},
      meetingPoint = null;
while(c1.exit) {
	var cell = c1.exit;
	path[cell] = 1;
}
while(c2.exit) {
	if (path[c2.exit] === 1) {
		meetingPoint = c2.exit;
	}
}

return meetingPoint;

Can u tell me the sol of this in c

Python code irukkah thala?

?

var path = {},
meetingPoint = null;
while(c1.exit) {
var cell = c1.exit;
path[cell] = 1;
}
while(c2.exit) {
if (path[c2.exit] === 1) {
meetingPoint = c2.exit;
}
}

return meetingPoint;

1
23

madarchod ke baccho answer toh sahi bata do

static int solution(int[] array) {
int n = array.length;
int count[] = new int[n];
Arrays.fill(count, 0);
for(int i = 0; i < n; i++) {
if(array[i] != -1)
count[array[i]] += i;
}
int maxWeight = 0;
int nodeNumber = 0;
for(int i = 0; i < n; i++) {
if(count[i] > maxWeight) {
maxWeight = count[i];
nodeNumber = i;
}
}
return nodeNumber;
}

You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves).

The cells are named with an integer value from 0 to N-1.

You have to find:

The sum of the largest sum cycle in the maze. Return -1 if there are no cycles.

1. Sum of a cycle is the sum of the node number of all nodes in that cycle.

INPUT FORMAT:

1. The first line has the number of cells N.

2. The second line has a list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell 'i' in one step. edge[i] is -1 if the 'i'th cell doesn't have an exit.

OUTPUT FORMAT:

The first line denotes the sum of the largest sum cycle.

Sample Input and Output

Input:

1

23

441413888 0 8 14 9

15 11-1 10 15 22

22 22 22

22 21

Output:

45

You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves).

The cells are named with an integer value from 0 to N-1.

You have to find:

The sum of the largest sum cycle in the maze. Return -1 if there are no cycles.

1. Sum of a cycle is the sum of the node number of all nodes in that cycle.

INPUT FORMAT:

1. The first line has the number of cells N.

2. The second line has a list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell 'i' in one step. edge[i] is -1 if the 'i'th cell doesn't have an exit.

OUTPUT FORMAT:

The first line denotes the sum of the largest sum cycle.

Sample Input and Output

Input:

1

23

441413888 0 8 14 9

15 11-1 10 15 22

22 22 22

22 21

Output:

45

var path = {},
meetingPoint = null;
while(c1.exit) {
var cell = c1.exit;
path[cell] = 1;
}
while(c2.exit) {
if (path[c2.exit] === 1) {
meetingPoint = c2.exit;
}
}

return meetingPoint;

# Anwer to this question in Python:

def meet(edges,c):
        
    startCell = c[0]
    c1_cells=[]
    cell = startCell
    while cell > -1 and cell not in c1_cells:
        c1_cells.append(cell)
        cell = edges[cell]
            
    startCell = c[1]
    c2_cells=[]
    cell = startCell
    while cell > -1 and cell not in c2_cells:
        c2_cells.append(cell)
        cell = edges[cell]
        
    min_dist = 99999
    ans = -1
     
    for j in c1_cells:
        if j in c2_cells:
            dist = max(c1_cells.index(j) , c2_cells.index(j))
            if dist < min_dist:
                min_dist = dist
                ans = j
    return ans

size = int(input())
edges = list(map(int,input().strip().split()))
c = list(map(int,(input().split())))

print(meet(edges,c))

Address bta ghar ka madarchod

Address bta madarchod