MAXTOPO - Editorial

kittu2539 · March 15, 2021, 11:11am

mine too nice problem

bennyjoseph · March 15, 2021, 11:25am

Hey, could you please once check lines 67, 76, 77, and 110? maybe you’ll get an idea of what I did. I assumed the root performance as 1 then I multiplied by the fraction by which it is changing and sorted by that long double array.

kittu2539 · March 15, 2021, 11:32am

how it got ac tho?
could you explain how did u calculated that pref array?
like how it works?

bennyjoseph · March 15, 2021, 11:43am

yeah, let us assume the “number of orderings” of the root is some k. Then the performance array will store the fraction by which some other node of the tree differs with k.
let’s say \{1,1\},\{2,0.5\},\{3,1.38\} then we can say that 1 is root and 2 has about 50% of the “number of orderings” as 1 and 3 has 1.38 times. so the maximum is 3.
This performance array is calculated when moving down the child (re-rooting the tree) and the values are propagated.

vyast · March 15, 2021, 11:58am

[Insight] Number of Topological Orderings of a Directed Tree - Codeforces.
this blog is also helpful. this help me during the contest

abhisek_12345 · March 15, 2021, 12:57pm

i did the same bro for all 1<=k<=n, really nice trick to maintain ratios and sort according to ratios and map the modded answer to print the required answer. You people can see my submission

abhisek_12345 · March 15, 2021, 12:59pm

it helped me too, rigorous searching for dynamic rooting and topological sorting in tree led me there

abhisek_12345 · March 15, 2021, 1:03pm

bro, surprisingly i did almost same step, maintained ratios during rerooting dfs.
my submissionmy submission

abhisek_12345 · March 15, 2021, 1:04pm

Solving this MAXTOPO problem made me very happy. Thanks for this problem

mahimarrhahe · March 15, 2021, 1:45pm

link to partial solution can anybody tell where I got wrong for 10 points,cuz what I did was just brute forced the solution and still got no ac

infinite_king · March 15, 2021, 2:14pm

It helped me too. I derived the formula to calculate the Toplogical sorting (TS) when we fix a node , but it includes the number of TS of it’s childs and we can’t even store the answer for large values ( in order to compare with other node TS ) so i thought this is not the right way , and moved on to other problems , at last i wanted to give it another try , googled if there was another way to calculate the TS , and stumbled upon this blog , and finally realized that , i missed to recognize that the formula can be simplified.

peresz · March 16, 2021, 12:17am

I used the idea in this blog post to solve it for K \in {1,2,3, \ldots, N}. The idea is that the number of topological orderings, if the root is v, can be simply expressed as \frac{N!}{\prod_{u=1}^N s^{(v)}_u}, where s^{(v)}_u is the size of the subtree rooted at u. To find the root with the maximum number of orderings, you just have to find the minimum of the product, i.e., \min_v \prod_{u=1}^N s^{(v)}_u. This product can be large but you can take the logarithm. See this solution. The sorting in line 56 is an overkill for K \in {1,2}, but then in the next line we can choose any K.

kkumarr1250 · March 16, 2021, 7:35am

@peresz can you please tell why you have used log and why it is helpful in this question.
And yes it was very awesome to come with that formula. Can you please tell, how you get the expression of number of topological orderings . observation or any theoretical ??

yosay55777 · March 16, 2021, 12:17pm

Good editorial. Nice Explanation.
Coincidentally, my approach is 80% similiar to editorial approach

peresz · March 16, 2021, 8:40pm

The formula comes from the above mentioned blog post, which unfortunately I can’t access at the moment. You can get it by expanding the recursive formula (the first formula in the EXPLANATION section above). The blog post also has a very nice intuitive reason why the formula is true.

Once you got the formula, you just have to keep track of the subtree sizes when you change the root of the whole tree. If you change the root to one of its neighbors then only the corresponding two subtree sizes will change. This was explained in the above editorial too. So you can calculate these for all possible roots. (This is the \mathtt{sizes} array in the code.) Now you could calculate the product of the subtree sizes for each possible root but the resulting number would be too big to handle. However, you don’t need the exact values of these products, you just need to find the minimum. (Or the second smallest.) Since log is a strictly monotonously increasing function, the order does not change if you apply the log and then find the smallest. What you get from the log is that the number won’t grow large since multiplications will turn into additions. (The log of a big number is a small number. )

spaanse · March 17, 2021, 6:09pm

I also had that idea but didn’t implement it because of the risk with double precision.
So for low K it will indeed work, for higher K two elements might get swapped because the precision of the double isn’t good enough to distinguish them. I am convinced test cases exist that would defeat your algorithm for general K, but it’s quite hard to find them. I am currently trying to proof that those test cases exist.

spaanse · March 19, 2021, 1:35pm

I found a testcase for the more general problem that would fail if @peresz approach was used with 32-bit float.

Testcase

The right anwer is

1 417702580

But when you modify peresz’ code to use 32-bit floats it gives

35 709016226

However using 64-bit floats (default) still gives the right answer.
I do believe there are testcases that would also break the 64-bit float version but I can’t find an efficient way to find them as then N must be a lot larger and my current search algorithm is O(N choose N/2)

abhisek_12345 · March 20, 2021, 10:46am

@spaanse Brother you are right but
since cp questions or in general programming problems have an upper limit or constraint according to which solution is provided , it was right to provide that solution with double data type,
I also gave by maintaining ratios in MAXTOPO.
Even modern computer have a limit due to architecture upto which they can directly multiply two number but we can extend that by creating larger array for storing answers.

In a similar way, sufficiently long data type can be used according to constraint,

So it is not right to say that there exist test cases for which solution will fail because there also exists long enough data types(or can be made user defined) to satisfy the constraint of problem.

Like my solution gave this output

My Output

peresz · March 22, 2021, 10:47pm

As @abhisek_12345 has already said, you have to solve any problem within the constraints of the problem provided. Sure, you can always take N to be too large for any fixed precision arithmetic. However, the problem statement says that N \leq 5 \cdot 10^5.

Let’s do some calculations! The largest number I store in the \mathtt{products} array is at most \ln(N!) \approx 6 \cdot 10^6, for N = 5 \cdot 10^5. You can get this using Stirling’s approximation. The smallest difference between any of these numbers is at least \ln(N) - \ln(N - 1) \approx 2 \cdot 10^{-6}, again for N = 5 \cdot 10^5. See line 43 in my code. The ratio of the two is around 3 \cdot 10^{12} < 2^{42}. This means that I need around 42 bits of precision for the code to work. Python floats are IEEE-754 double precision numbers which contain 53 bits of precision.

So all in all, I do not think you will be able to find a testcase that defeats my algorithm in the constraints given by the problem. Of course, I can be wrong in which case I would be curious to see such a testcase.

bhpra · April 2, 2021, 9:11am

thanks for the link it really helped