MAXTOPO - Editorial

mine too nice problem :slight_smile:

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.

1 Like

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

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.

1 Like

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

6 Likes

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

2 Likes

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

1 Like

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

2 Likes

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

1 Like

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

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.

2 Likes

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.

5 Likes

@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 ??

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

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

1 Like

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.

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

Testcase
1
35 21
1 2
1 3
3 4
4 5
5 6
4 7
7 8
8 9
9 10
10 11
11 12
12 13
7 14
14 15
14 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
16 24
24 25
25 26
26 27
25 28
28 29
29 30
30 31
31 32
32 33
33 34
29 35

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)

2 Likes

@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

|node_no-> 1 |modded_ans 417702580
|node_no-> 2 |modded_ans 12285370
|node_no-> 3 |modded_ans 892092528
|node_no-> 4 |modded_ans 515653569
|node_no-> 5 |modded_ans 122160823
|node_no-> 6 |modded_ans 797710618
|node_no-> 7 |modded_ans 992325573
|node_no-> 8 |modded_ans 515653569
|node_no-> 9 |modded_ans 585942265
|node_no-> 10 |modded_ans 269153842
|node_no-> 11 |modded_ans 212733174
|node_no-> 12 |modded_ans 740165652
|node_no-> 13 |modded_ans 21769578
|node_no-> 14 |modded_ans 602397116
|node_no-> 15 |modded_ans 429482271
|node_no-> 16 |modded_ans 469862819
|node_no-> 17 |modded_ans 867465710
|node_no-> 18 |modded_ans 213958423
|node_no-> 19 |modded_ans 202326405
|node_no-> 20 |modded_ans 639009863
|node_no-> 21 |modded_ans 966157181
|node_no-> 22 |modded_ans 725221652
|node_no-> 23 |modded_ans 550741817
|node_no-> 24 |modded_ans 592971908
|node_no-> 25 |modded_ans 438445459
|node_no-> 26 |modded_ans 905360337
|node_no-> 27 |modded_ans 761922368
|node_no-> 28 |modded_ans 426206064
|node_no-> 29 |modded_ans 106551516
|node_no-> 30 |modded_ans 17758586
|node_no-> 31 |modded_ans 808743049
|node_no-> 32 |modded_ans 669569665
|node_no-> 33 |modded_ans 646640590
|node_no-> 34 |modded_ans 313136490
|node_no-> 35 |modded_ans 709016226
Ratios
|node_no-> 34 |ratio: 0.00012218953939322934671
|node_no-> 23 |ratio: 0.0003568011158143985469
|node_no-> 13 |ratio: 0.00063251106894370651484
|node_no-> 33 |ratio: 0.0041544443393697977883
|node_no-> 22 |ratio: 0.012131237937689550595
|node_no-> 12 |ratio: 0.021505376344086021505
|node_no-> 2 |ratio: 0.029411764705882352941
|node_no-> 32 |ratio: 0.068548331599601663505
|node_no-> 21 |ratio: 0.20016542597187758481
|node_no-> 6 |ratio: 0.31372549019607843138
|node_no-> 11 |ratio: 0.35483870967741935483
|node_no-> 31 |ratio: 0.7311822037290844107
|node_no-> 27 |ratio: 0.81818115577706370561
|node_no-> 35 |ratio: 0.99999919039418897344
|node_no-> 1 |ratio: 1
|node_no-> 20 |ratio: 2.1350978770333609046
|node_no-> 10 |ratio: 3.7849462365591397849
|node_no-> 30 |ratio: 5.666662078900404183
|node_no-> 5 |ratio: 10.666666666666666667
|node_no-> 3 |ratio: 16.5
|node_no-> 19 |ratio: 16.547008547008547012
|node_no-> 26 |ratio: 27.81815929642016599
|node_no-> 9 |ratio: 29.333333333333333334
|node_no-> 29 |ratio: 33.999972473402425097
|node_no-> 15 |ratio: 42.34087481146304676
|node_no-> 18 |ratio: 99.282051282051282062
|node_no-> 28 |ratio: 135.99988989360970039
|node_no-> 4 |ratio: 176
|node_no-> 8 |ratio: 176
|node_no-> 25 |ratio: 458.99962839093273881
|node_no-> 17 |ratio: 479.86324786324786329
|node_no-> 7 |ratio: 850.66666666666666669
|node_no-> 24 |ratio: 1001.4537346711259755
|node_no-> 14 |ratio: 1439.5897435897435899
|node_no-> 16 |ratio: 1919.4529914529914532
Ans
1 417702580

1 Like

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

2 Likes

thanks for the link it really helped

1 Like