aopo's blog

By aopo, history, 4 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aopo (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I mean how having atmost 9 distinct prime factors allows us to directly say YES/NO even without brute forcing for larger N?

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Exactly Same Problem , but with smaller constraints on a[i]:(https://codeforces.com/problemset/problem/1043/F)

»
4 weeks ago, # |
Rev. 5   Vote: I like it +15 Vote: I do not like it

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$$$.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok, so i guess using this fact/understanding we can even find 1 such possible susbset.