handsome_gay's blog

A way to solve 1547F(#731F) by implementation
By handsome_gay, history, 3 years ago, In English

As we know, if $$$x\neq 1$$$ and $$$x\neq y$$$, then either $$$gcd(x,y)=x$$$ or $$$gcd(x,y)<=\frac{x}{2}$$$. That means for each element $$$a_i$$$ in the array, it will change at most $$$log(a_i)$$$ times before it becomes $$$1$$$.

So we can implement the process, but for every round we only consider the element that will change, then we just do $$$O(N*log(a_i))$$$ times change.

How to find the elements that will change in the next round? We can see that elements will change in the next round, are only in the elements change in this round and their left element, so we just check them. The number of elements we check is $$$O(N*log(a_i))$$$ too.

solution
  • Vote: I like it
  • +45
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice solution :)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you/someone please help to elaborate this? I'm quite fascinated by this solution. I tried doing Brute Force for this problem submission:121999001 which got TLE. I did not find any way to optimize it which is mentioned in this post. It would be really nice if I could get any additional help in understanding the solution.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You check all elements in every round of BruteForce. There can be $$$N$$$ rounds , so it has a $$$O(N^2)$$$ complexity, may lead to TLE.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can see that elements will change in the next round, are only in the elements change in this round and their left element, so we just check them.

Can you explain this sentence again?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    For example, if $$$N=10$$$, and $$$a_3,a_7$$$ change in this round, then we can assert that only $$$a_2,a_3,a_6,a_7$$$ may change in the next round. We can only check whether $$$a_2,a_3,a_6,a_7$$$ will change in the next round. Other elements certainly won't change in the next round so we don't check them.

    That's because: $$$a_i$$$ will change if $$$gcd(a_i, a_{i+1})\neq a_i$$$, so if both $$$a_i$$$ and $$$a_{i+1}$$$ does not change in this round, then $$$a_i$$$ won't change in the next round.

    → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

With the $$$\LaTeX$$$ markup, this looks like you're talking about factorials on first glance. You may want to consider instead writing this as: $$$x \neq y$$$. (Code is x \neq y).

→ Reply