# MAXTOPO - Editorial

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

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.

2 Likes

thanks for the link it really helped

1 Like