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.net/gym/104669/problem/L↵
↵
<spoiler summary = "Editorial">↵
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 intervalof length $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↵
↵
Code: https://pastebin.com/RNj74CVN ↵
</spoiler>↵
↵
↵
Link: https://codeforces.net/gym/104669/problem/L↵
↵
<spoiler summary = "Editorial">↵
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
↵
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↵
↵
Code: https://pastebin.com/RNj74CVN ↵
</spoiler>↵
↵
