×

# approach for Weird Competition

 1 Can anybody give the approach to solve problem WEICOM of oct lunchtime asked 29 Oct '17, 11:11 1★ayushi09 32●5 accept rate: 0%

 0 @aayushkapadia I had this approach of doing bfs and pruning during the contest but couldn't prove the complexity? How do you establish a upper bound on this? answered 29 Oct '17, 14:55 4★ps_1234 59●3 accept rate: 0% I have updated regarding time complexity of my approach in my answer. (29 Oct '17, 15:23)
 0 Very nice explanation. But after finding the degree sequence we needed which is equal to k, how did you assign the degrees to different players? Small explanation about it will help me solve the problem completely. Thank You! answered 31 Oct '17, 16:20 2★ramini 61●5 accept rate: 8% There is a algorithm called Havel-Hakimi algorithm which generates the undirected graph from the degree sequence and also reports if it is not possible. You can look it up here : https://en.wikipedia.org/wiki/Havel%E2%80%93Hakimi_algorithm . For our purpose that is building tournament graph from out degree sequence, we have to use similiar approach and you can see that in my code (I have written a function called getTournament(outDegreeSequence)) : https://www.codechef.com/viewsolution/16023920 . But first read and understand Havel-Hakimi algorithm before reading my code. (01 Nov '17, 12:37)
 0 I read about Havel-Hakimi algorithm but I'm unable to understand getTournament() function. Since both in-degree and out-degree are involved I'm unable to get using which of them is the graph constructed, why are you reducing it's size in every iteration, why did you take node numbers and many more. Please explain it like you explained above on how to approach the problem. If possible please explain that function completely. Thank You! answered 02 Nov '17, 02:37 2★ramini 61●5 accept rate: 8% I have updated and explained in my main answer. I am only dealing with outdegree of vertices. Node numbers has to be there because we must keep track of each vertex. So labelling has to be done so that it do not get lost while sorting. (02 Nov '17, 14:36)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×550
×140

question asked: 29 Oct '17, 11:11

question was seen: 780 times

last updated: 02 Nov '17, 14:41