I get wrong answer in Pro E for Error of accuracy, and my 1.5 hours run out. Maybe we should pay more attention to the calculation of plane geometry...
On voidmax → Editorial Tinkoff Internship Warmup Round 2018 and Codeforces Round #475 (Div. 1 + Div. 2) , 3 years ago
We'd like to combine the rectangles to a big one, and let's call a way to build the big rectangle A GOOD WAY. In a good way, we can move some small rectangles. For example:
It has four types of rectangles and shows a good way. We can also get the same big rectangle in this way:
It can be built by first constructing one part of them, then copy them several times. The Editorial states that every big rectangle contains the same part, like the picture above. More formally, we need to build one BASE PART, such that it contains all types of small rectangles, and the gcd of the numbers of all types in a part is 1. So we need to divide every ci with gcdi = 1 to nci (call it G), and check if base part can be built. If built, we will copy the base part G times to make a bigger rectangle, and the number of ways is the number of divisors of G (copy x times in one direction and y times another,x * y = G). Else, the answer is 0.
The last is how to check the base part. We divide the rectangles into different groups based on their a, and discover that if a way is good, each line's ratio of number of b is the same. For example, when a = 2, [b = 1]: [b = 2]: [b = 4] = 3: 5: 7, and when a = 3, [b = 1]: [b = 2]: [b = 4] must be 3: 5: 7. Based on this we just need to compare some ratios and check if they are the same.
However, I don't understand the last step's formula transformations very clearly, while I could only understand it with this: Dividing n people into k non-empty groups, means that we first choose j, 0 ≤ j ≤ n - 1, people to be members of person n's group, and then divide the remained persons into k - 1 groups.
Something about Problem G. I guess most of us get the formula below easily:
But the Editorial above claims:
So may anybody prove that: