Have anyone participated in techgig code gladiators 2018 semifinal. If so can u share your approaches for the two questions asked in semifinal round.

PS:Cannot post the question as it is locked and now we cannot see the questions any more.

Have anyone participated in techgig code gladiators 2018 semifinal. If so can u share your approaches for the two questions asked in semifinal round.

PS:Cannot post the question as it is locked and now we cannot see the questions any more.

1 Like

The first one was simple just simulate the possibilities considering only when the fish enters.

The second one was max-flow. Consider a universal source U. Now add edges U to i with weight as the number of monkeys on tree i(ti).

Let sum of all ti = S.

Now next create nodes 0β,1β,2β,β¦ which have exactly 1 incoming edge from 0,1,2,β¦ with some infinite weight . The position of 0 and 0β are same , 1 and 1β are same and so onβ¦,

Now from 0β add edges to all original nodes(0,1,2,β¦) that are reachable from it.

Now perform maxflow from U to 0 , U to 1 ,β¦ and for nodes whose maxflow is S increment the answer.

Yeah Ok If I remember it correctly it was catching fishes twice right.Notice that the number of fishes you are catching changes only when a fish enters or exits. You can consider only when the fish enters. Now for each entry point try all other entry points (this can be optimized but it passed so I didnβt care ).