The official editorial of the Half Sequence says
This
Reason they give
But, what is the proof behind it? I mean what is the intution behind saying this? Can someone give a formal proof for it.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
The official editorial of the Half Sequence says
For N > 18 (practically, even 16), remove all odd numbers from the input. If we have atleast (N+1)/2 elements remaining and if their GCD is 1 then we have a solution.
Observe that any single number (<=10^9) can be made up of atmost 9 distinct prime numbers. This means that if GCD([B_0, B_1,..., B_N]) = 1, then there must exist atleast one subset of length at most 9 whose elements have GCD=1.
But, what is the proof behind it? I mean what is the intution behind saying this? Can someone give a formal proof for it.
Name |
---|
Auto comment: topic has been updated by aopo (previous revision, new revision, compare).
I mean how having atmost 9 distinct prime factors allows us to directly say YES/NO even without brute forcing for larger N?
Pick any number A. If (N+1)/2 >= 10 then for every prime p that divides A you can just pick one number that is not divisible by p. These <=10 numbers already have GCD=1 and you can pick any other numbers to make it (N+1)/2 total.
If you have a subset $$$S$$$ of size less than $$$ceil((N+1)/2)$$$ with $$$\gcd(S)=1$$$, you can insert to it any $$$ceil((N+1)/2)-|S|$$$ elements and it'll still satisfy the gcd condition. So your goal is to find any subset of size $$$\le ceil((N+1)/2)$$$ with $$$\gcd = 1$$$.
Fix any element $$$x$$$ in $$$B$$$ which must be included in $$$S$$$. $$$x$$$ can have at most 9 distinct prime factors. Let them be $$$p_1, \cdots, p_k, k \le 9$$$. Since $$$\gcd(B)=1$$$, for each $$$p_i$$$, $$$B$$$ must have an element $$$b_i$$$ which is not divisible by $$$p_i$$$ ($$$b_i$$$s can be equal). Then just set $$$S=\lbrace x, b_1, \cdots, b_k \rbrace$$$, and we must have $$$\gcd(S)=1$$$ since $$$\gcd(S)$$$ divides $$$x$$$ and none of the $$$p_i$$$ divides it. This set is enough to determine that the answer is YES if $$$|S| \le k+1 \le ceil((N+1)/2)$$$. Since $$$k \le 9$$$, this inequality always hold if $$$N \ge 18$$$.
Ok, so i guess using this fact/understanding we can even find 1 such possible susbset.