Recently I wrote my very first problem (that was $$$>$$$ D2A and not just a standard application of an algorithm) that I both wrote and solved myself.
Link: https://codeforces.com/gym/104669/problem/L
Let $$$R$$$ be the sum of all the elements.
Denote the sum of the first set to be $$$s1$$$ and the sum of the second set to be $$$s2$$$. Notice that the gcd has to be a factor of $$$R$$$ because if $$$\text{gcd} | s1$$$ and $$$\text{gcd} | s2$$$ then $$$\text{gcd} | (s1 + s2)$$$. So we can check every factor of $$$R$$$, see if it possible achieve this factor as the $$$\text{gcd}$$$, and then take the max factor that works.
A factor $$$f$$$ works if there is a subset $$$s$$$, $$$|s| < b$$$ that adds up a multiple of $$$f$$$ because the sum of the numbers from $$$a$$$ to $$$a + b - 1$$$ not in $$$s$$$ will also be divisible by the $$$f$$$. We need to find some way to optimize knapsack dp using the fact that the numbers are consecutive.
Considering fixing the size of the subset to be $$$s$$$.
Claim: There exists a subset of $$$a, a + 1, ..., a + b - 1$$$ of size $$$s$$$ that adds up to every number from the sum of the first $$$s$$$ numbers to the last $$$s$$$ numbers of the subset.
Proof: We can prove this with induction. Our base case is the subset containing the first $$$s$$$ numbers. Notice for a given subset, we can increasing the subset sum by $$$1$$$ by increasing by $$$1$$$ the greatest element that can be increased. A number cannot be increased if it would become $$$> a + b - 1$$$ or if increasing it by $$$1$$$ would give you a number already in the subset. The only case where we can't increase the subset sum by $$$1$$$ is when we have the last $$$s$$$ numbers as our subset. Thus we can represent all subset sums we can hit as a series of $$$b - 1$$$ intervals (we don't consider interval where $$$s = b$$$ because if we choose this for one set, the other set would be empty).
We can check in $$$O(1)$$$ if a multiple of $$$f$$$ is in each interval by checking either if the interval is of length $$$\ge f$$$ or if the smallest subset sum mod $$$f$$$ is larger than the largest subset sum mod $$$f$$$. In both cases it is guaranteed there is some subset sum which is $$$0$$$ mod $$$f$$$. So this is a total of $$$O(m)$$$ for each factor.
The time complexity of the solution is: $$$O(R^{\frac{1}{2}} + R^{\frac{1}{3}}b) = O((ab + b^2)^{\frac{1}{2}} + (ab + b^2)^{\frac{1}{3}}b)$$$
We take $$$R$$$ to the power of $$$\frac{1}{3}$$$ because the number of factors of a number $$$n$$$ is bounded by $$$n^{\frac{1}{3}}$$$. You could also check this oeis sequence to confirm that the number of factors is small: https://oeis.org/A066150
Auto comment: topic has been updated by skye_ (previous revision, new revision, compare).
Auto comment: topic has been updated by skye_ (previous revision, new revision, compare).
Great d2E level problem. Anyone reading should try it out :)
"guys give me contribution"
giving you negative contribution
the poster had sent in a discord server this message and i thought it wads funny i am not asking for contribution
you could have posted the ss instead otherwise how could people know what you were indicating
yeah haha, i realize that now
orz
nou
I still don't understand how you solved for $$$O(a^{\frac{3}{4}} + \text{factorization}(R))$$$.
That sounds interesting, I only have $$$O(a + \sqrt{b})$$$ solution.
I think his idea was something along the lines of 'we probably don't have to check that many factors if we check from greatest to least and break once we find one that works' so instead of checking each of $$$b - 1$$$ intervals, he instead checked each factor $$$f$$$ in $$$O(\frac{R}{f})$$$ because if the factors are big, this will take less time and somehow found a bound on the number of factors we have to check but I didn't completely understand what he did.
Btw if you want to, could you share your solution/if you liked the problem?
My optimisation is based on the fact that if we look at values we can get by using $$$b/2$$$ elements, the length of this segment of values will be $$$\frac{b^2}{4}$$$ (roughly). So for any number less than that we surely have something divisible by it inside this segment. So we only need to check divisors that are greater than $$$\frac{b^2}{4}$$$. $$$R = \frac{b(2a+b-1)}{2} = O(b(a+b))$$$. Let's enumerate big divisors of $$$R$$$ by trying $$$\frac{R}{k}$$$ for small integer $$$k$$$. We can see that we only need to iterate over $$$\frac{4R}{b^2} = O(\frac{a}{b} + 1)$$$ values of $$$k$$$. Since checking each one of them takes $$$O(b)$$$ time, we can check all in $$$O(a+b)$$$.
The problem is nice.
We also don't need to check any divisors less than $$$a+\frac{b-1}{2}$$$: put $$$a$$$ and $$$a+b-1$$$ in the first set, and the rest in the second set, which immediately gives that as the GCD. (This is the best we can do, given that $$$R=b(a+\frac{b-1}{2})$$$ and we can force $$$b$$$ to be prime.)
Together with the idea from @above, it suffices to check divisors $$$\frac{R}{k}$$$ for $$$k$$$ up to $$$\frac{R}{\max(b^2/4, a+\frac{b-1}{2})} \approx \min(4a/b, b)$$$. Because $$$R \approx (4a/b)(b^2)$$$ this minimum is at most $$$R^{\frac{1}{3}}$$$.
Checking if a divisor $$$\frac{R}{k}$$$ works can also be optimized to $$$O(k)$$$: enumerating the $$$k$$$ multiples of $$$\frac{R}{k}$$$ less than $$$R$$$, it suffices to calculate the largest $$$x$$$ such that $$$a + (a+1) + \cdots + (a+x) = \frac{x(x+1)}{2} + (x+1)a \leq C$$$ with quadratic formula, and check if $$$C \leq (a+b-x-1) + \cdots + (a+b-1)$$$. Each multiple can be done in $$$O(1)$$$.
Combining both of these optimizations, the complexity is essentially $$$O(\text{sum of factors of R below }R^{\frac{1}{3}})$$$. Admittedly I don't have an asymptotic bound for this, but empirical data using highly composite numbers suggests it should be at most $$$R^{\frac{1}{2}}$$$ for reasonable $$$R$$$.
Then fixing $$$a$$$ and varying $$$b$$$, the upper bound is maximized when $$$b \approx \sqrt{a} \implies R \approx a^{3/2}$$$, which gives the bound $$$a^{3/4}$$$, plus finding the largest divisor at most $$$\frac{b^2}{4}$$$ if required.
Auto comment: topic has been updated by skye_ (previous revision, new revision, compare).
TankU