APAIRS PROBLEM DISCUSSION

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.