Techgig coding contest semifinal approach needed

general
1

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.

2

@abdullah768 can u answer?

3

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.

4

@sdssudhu can u explain more about the first question approach ?

5

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 :slight_smile: ).