I'm stuck in this problem: https://quera.org/problemset/34090?tab=description
you can use google translation for the statement
For n ≤ 22, I used brute force. For n ≥ 40, I randomly selected two disjoint subsets of size 18, and it worked fine. However, I'm failing the cases where 22 < n < 40.
Here is a code snippet: https://pastecode.io/s/h6rdjqzf
the cases I'm failing have 24 < n < 40 Previously, I tried selecting 18 random elements for set1, then chose elements not in set1 for set2, and filled the rest randomly without repetition.
This also failed — the cases where 24 < n < 40 are particularly tough. It's as if there's only one unique solution, and the problem expects you to find it through randomness.
I think the following should work:
Firstly, note that if $$$n \geq 30$$$, a solution will exist. This is because among all $$$2^{30}$$$ subsets, by pigeonhole, there will exist two of them whose sum modulo $$$m$$$ is the same. And we can construct an answer by discarding the elements common to both subsets.
Therefore, we can perform a brute force on at most $$$30$$$ elements. The rest of the problem is just a standard meet-in-the-middle: we can partition the elements into two sets $$$A$$$ and $$$B$$$, and brute force at most $$$3^{15}$$$ possibilities for each set. The $$$3$$$ represents the decision to "put element in the first group", "put element in the second group", or "put element in neither group". For each of these possibilities, we can store the value of (sum of first group) — (sum of second group) modulo $$$m$$$, and look for a pair of values with sum $$$0$$$ or $$$m$$$. We just need to be a bit careful to deal with the "all elements get put into neither group" case.
Pretty nice problem imo! I didn't expect an elegant solution upon reading it.
nice idea especially the (sum of first group) — (sum of second group)
however the time limit is 1 second
I just did a loop from 1 to 3^15*(convert_to_base3) and it took 20 second
is there a way implement this faster ?
Hey i tried the google translate but still cannot understand it properly .... can u pls write the problem statement in english please
i just used google translate I don't know this language
if your one was better pls share .... otherwise just explain the problem shortly
Image-link
You have n<=1e6 numbers, and a integer m<1e9. You want to find two disjoint sets of the numbers that have the same sum modulo m.
my main question is what to output if it is possible ... can't understand in the above statement
You output the sets, or more specifically the ternary mask that constructs the sets. You output n digits. If the i'th is 0 it means that the i'th number is in neither of the sets, if it's 1 then the i'th number is in the first set and if it's 2 then the i'th number is in the second set
What is a ternary mask? Do I need to learn them as a beginner
Here's my implementation which passes: https://pastecode.io/s/4cw5jpkc (I originally tried saving possibilities inside of a map<int,int>, but I guess that was way too slow, so I changed it to sorting + 2 pointers.)
I think it's quite borderline though, since it TLE'd without the vector reserve calls.
Although I feel like the judge itself is surprisingly slow? On custom invocation on CF, some random $$$n = 30$$$ input took about 300ms, so I suspect they're not compiling with O2 or something (although I'm too lazy to see if this is true).
thank you , I was just trying exactly as just you said in your first comment and carefully optimized my code to the last point just like your code but instead of DFS I was doing for loop and it was giving TLE at some cases.
I copy pasted your DFS and it worked finally
DFS works exactly in around (3^15)
while my for loop was (3^15*15)
Np! I see, maybe taking mod 3 is slow or something. Anyways, I feel like the TL is kind of bad lol
Need a slight help! Thanx in advance ... Can the bound for n be lower ? Like n = 15 since, (2^15 = 32768) > (sqrt(m) = 31623) where I took max value of m which is 1e9 ... This is from the fact of birthday paradox. Is this possible to check only for 15 elements askd ?
I mean can you explain a bit why have you taken 30? only and why checking for only 30 elements (that too randomly) works ?
$$$30$$$ is the smallest number for which the pigeonhole thing I said works (because $$$2^{30} \gt 10^9$$$). You could maybe get AC with an even smaller number, depends on how much effort was spent constructing the test cases, but I don't think it'd be provable (birthday paradox is just a heuristic argument).
Ok ... It might work if i random shuffle it and take the first 15 or maybe 20 values