You are not logged in. Please login at www.codechef.com to post your questions!

×

Techgig coding contest semifinal approach needed

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.

asked 24 May '18, 18:51

beginner_1111's gravatar image

4★beginner_1111
241110
accept rate: 13%

@abdullah768 can u answer?

(24 May '18, 18:51) beginner_11114★

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.

link

answered 24 May '18, 19:09

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

edited 24 May '18, 19:10

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

(24 May '18, 19:34) beginner_11114★

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

(24 May '18, 21:28) sdssudhu6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×148

question asked: 24 May '18, 18:51

question was seen: 262 times

last updated: 24 May '18, 21:28