I was trying to solve this problem from codeforces.
I understood upto the part where binary search was used to calculate the minimum value of branching coefficient but i am not able to build the tree from s, n and binary coefficient.
can someone explain the idea. It’s not clear in the editorial.
link to editorial : https://codeforces.com/blog/entry/64331
I did not understand this part
We know that the tree can be rebuilt so that the sum is any between maximum and minimum, so there are two conditions, which are satisfied (we want to put value 𝑥x to position 𝑖i).
- 𝑥x must be big enough, so if we fill suffix with numbers 𝑥x, 𝑥⋅𝑘x⋅k, 𝑥⋅𝑘2x⋅k2, … (the last non-zero number can be smaller, sum of numbers is 𝑛n) sum of sizes of subtrees will be not greater to 𝑠s.
- 𝑥x must be small enough, so if we fill suffix with 11, sum of sizes of subtrees will be not less than 𝑠s