Can anyone suggest the efficient approach to solve the APAIRS problem of Div1 , as i only made it to brute force solution of the problem.
2 Likes
Firstly realize that padding each number with 0s so they all have 19 digits does not change their score.
Call cnt(i, j) as the number of numbers between L…R that have the ith sorted digit as j. Set L = 1 and later erase by cnt array with R = L - 1. So now we only have an upper bound R.
Fix a prefix of R with length i so that the first i - 1 digits match exactly with R’s first i - 1, and the ith digit being strictly smaller than R’s ith one. Therefore every digit after this can be freely chosen.
So now our job is to count sequences A with these properties:
- a(i) = j
- a is sorted in a non - decreasing order
- For each number i we have a cnt(i) that is the least amount of times it should appear in a.
In addition, a can be permuted except for the first i numbers.
Define pre(i, j, k) as the number of ways to fill the first i numbers so that a(i) <= j, and j appeared k times already. Calculation of this can be easily done.
In addition, define a suf(i, j, k) too. Now, to calculate cnt(i, j), simply merge the pre and suf array together.
2 Likes
The ideal time complexity for the problem?
I planned to optimize this one, just checking for correctness but it got AC anyways. Ideal time complexity would be O(18 ^ 3 * 10 ^ 2 * T). Mine had an extra 18 but it passed anyways. (most likely due to that 18 not being fully 18, but 18 / 4)
1 Like
Bruh you legit solved the 2 hardest questions in the contest and 1 div2 question to be “part” of the contest. Aren’t you just trolling at this point xD
You remind me of Saitama 
Nice explanation ! Thanks.