Can anybody give the approach to solve problem WEICOM of oct lunchtime
1 Like
We can reformulate the question in terms of directed graph. So now the score for each vertex is nothing but the outdegree of that vertex. So k is nothing but the sum of squares of outdegree.
Now the graph that will be formed will be a special kind of graph known as tournament graph.You can learn important properties about tournament graphs online. Specifically for this problem there is a important property for outdegree sequence for tournaments.
First you have to realize what is the maximum value of k that is possible. Actually it is summation of i^2 from i = 0 to n-1.Graph which corresponds to this is the one in which always higher index vertex wins.
Another important thing to realize is that given a degree sequence , how to change the degree sequence so as to decrease its sum of square value while maintaining sum of degree sequence (Sum of outdegree is number of edges which is nC2 which is constant). Take the min and max degree from the degree sequence and then increase degree for min by 1 and decrease degree for max by 1. One could observe that the decrease we get is 2 (max - min - 1). So in this way we can decrease the sum of square value. Infact you can choose any two degree from degree sequence and decrease it by 2* (b-a-1).
So what you could do it initialize the degree sequce for which sum of squares is max. Then decrease it in such a way that it is greater than or equals to k but less than current sum of squares. We can do this by first trying max and min. If the difference is so high that the new sum of square value is less than k then we will not perform this operation. If operation is not performed then we will try max with second min. And so on… If not able to perform operation with any degree discard the max degree. Discarding means we will have max degree for sure in final graph and store it somwhere else.
After that if we got the degree sequence from the discarded degrees as the desired one that is sum of squares is k then this is our answer. Else it is not possible.
At first step it is a valid tournament graph. And also after every step it will be a valid one. We can prove it by mathematical induction.
Here is my solution : https://www.codechef.com/viewsolution/16001454
Time Complexity
As you might have noticed that degree sequence corresponding to max sum of squares is (0 1 2 3 … n-1 ) And min sum of squares is ((n-1)/2 (n-1)/2 … (n-1)/2 ). So each vertex has degree changed by O (N). And as there are N vertices we will require O (N^2) operations. And another log (N) factor to find mins and maxs.
So O (N^2 logN).
You might say that what if max and min operation is not performed and some operations are wasted because of that. Now notice that if if we do not perform the operation that means difference between curr sum of squares and k is O (N) and then we can easily reduce to k in O (N^2) as in every sucessfull operation we will decrease by atleast 2. So in O (N) successfull operations we will be able to finish it. And in worst case consider O (N) unsucesful operation for each successful operation. So total operations is again O(N^2).
Proof of why every valid k will be reached by using above approach
Earlier I have written that “One important reasoning behind this approach is that if k is possible than we can reach it from any degree sequence which have sum of square higher than k by performing operations we mentioned”. When @sir_zaid02 asked to prove this, I tried a lot to prove it. But I was not able to prove it. Instead it turned out to be a wrong statement and I found a counter example for it also. Thanks to @sir_zaid02 for raising the question.
Now as this assumption was wrong, I started to doubt if my solution is correct. Though it gave me accepted but it may be the case that test cases are weak. So I started thinking for the proof of whether using my approach, I can reach all valid k. And by thinking for some time, I got a proof for proving that indeed my solution will be able to reach any valid k.
Let us observe the pattern what happens to the degree sequence if we only operate on max and min degree every time. For example let us take case of n=5. So the pattern goes as follows :
(0 1 2 3 4) -> (1 1 2 3 3) -> (1 2 2 2 3) -> (2 2 2 2 2)
Similar for n=6,pattern goes as follows :
(0 1 2 3 4 5) -> (1 1 2 3 4 4) -> (1 2 2 3 3 4) -> (2 2 2 3 3 3)
Do you observe any pattern here or observation here. From this pattern I observed that if we only operate on max and min then my degree sequence will always be continuous that is degree sequence will have all values in between a and b for some a and b. So based on this we can say that we can decrease the sum of squares by any amount from 2 to 2*(b-a-1). Of course decrease should be multiple of 2. Now what this means for us is that the moment we are unsuccessful in operation on max and min that is decrease = 2*(max-min-1) is way much higher than decrease we want then in one go we can operate on degree c and max degree such that 2*(max-c-1) = (currCost-k). And we will always be able to get such c because we know that 2*(max-min-1) > (currCost-k) that is 2*(max-min-1) > 2*(max-c-1) that is c>min which is always possible.
Optimization base on the above proof :
As the all the degree values are continuous, there is no need to use set or map to find min and max. Just store current min and max degree and count of each degree. And after each operation check if count[min]==0 then do min++ and if count[max]==0 max–. So this approach will have time complexity of just O(N^2) which is better than earlier one of O(N^2log(N)).
My new solution : https://www.codechef.com/viewsolution/16023920
**Algorithm for generating tournament from valid out degree sequence **
Assign a label to every vertex that is assign each outdegree in the outdegree sequence with some label. So lets label it from vertex 1 to vertex n. Now take vertex n and draw a directed edge from n to k vertices with highest outdegree where k is outdegree of vertex n.Also add a edge from remaning (n-1-k) vertices to vertex n. Also decrease outdegree of all such remaning (n-1-k) vertices by 1. Now remove vertex n and recurse on remaning (n-1) vertices. Remember to label only once and not change the labels during recursion. This algorithm is similar to Havel Hakimi algorithm that is used for constructing for generating undirected graphs from a valid degree sequence.You can learn about it on wikipedia or some other online resource
So that’s the approach. If any problem in understanding, please comment. I will try to improve my answer or reply to your comment.
6 Likes
@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?
I have updated regarding time complexity of my approach in my answer.
Great solution. Mate…
Can you share some reference, links to study tournament graphs. I don’t semm to be able to find any detailed one
@taran_1407 Actually I have first heard about the tournament graphs from graph theory course in our institute. In our course we have studied only some basic properties of tournaments. So the basic properties can be found here :
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_chap06.pdf . For this question I searched on google about the properties of score sequence of the tournament which can be found here : http://shodhganga.inflibnet.ac.in/bitstream/10603/18536/5/05_chapter%202.pdf
1 Like
Thanks mate.
Heard about tournament graphs for the first time. During the contest, I reformulated question as.
Divide N*(N-1)/2 into N parts (all smaller than N), such that sum of squares of parts is K with constraints on other parts.
Like, if one part is N-1, all other parts are smaller than N-1.
If one part is zero, all other parts >0.
In short, i wasted time trying to derive properties of outdegree of vertices of tournament graphs during contest. 
Your approach was best.
@anno This is the first problem I came across where I have used concepts of tournament graph. So i do not know any other problem which uses some of the properties of tournament graph. According to me I think there are lots and lots of different properties related to different types of special graphs. It is very hard to know all of them. So What I do is model the question in form of graph wherever applicable and and once I know the type of graph, I then google about the properties of the graph. I have seen many questions where reformulating question based on graph makes the problem easier.
1 Like
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!
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–Hakimi_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.
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!
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.