Please read the new rule regarding the restriction on the use of AI tools. ×

pikamonstruosa's blog

By pikamonstruosa, history, 22 months ago, In English

I recently started my journey here on codeforces and today I did my first contest ( of many to come, hopefully ). The idea for the problems I did (A and B) are really cool, so I want to share it with whoever wants to see them.

A - The observation needed for this problem is that, given an optimal subarray, we have two cases. Let's assume you want to expand it to the right ( it's the same case if it's for the left ), if the next number is already on the array, r-l-c(l,r) increases by one, since c(l,r) stays the same and r increases by 1, so overall, the value increases by 1. If the next value is not on the array, c(l,r) increases by one and so does r, so overall, the value stays the same. That is, if you expand an optimal subarray, the value we want to maximize either stays the same or increases by 1. Then, all you need to do for a given test is to print 1 n.

B - I am still not sure how to prove that this idea is correct, but what I thought on this problem is that the optimal answer has all the multiples of the gcd of everyone.

Those are the ideas I had on this contest! The ideas, although simple, were not trivial to be seen, and that is where I think the beauty of CP and math problems are. I would like to thank the developers of the contest, Cocoly1990, waaitg and Imakf for the good time I had trying to solve it!

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

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice solutions!!