My experience on my first contest. (And my solutions to the problems I did)

Revision en3, by pikamonstruosa, 2022-11-26 19:52:19

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English pikamonstruosa 2022-11-26 19:52:19 13 Tiny change: 'and [user:lmakf] for ' -> 'and [user:Imakf] for '
en2 English pikamonstruosa 2022-11-26 19:51:11 2 Tiny change: 'ee them.\n**A**\n-' -> 'ee them.\n\n**A**\n-'
en1 English pikamonstruosa 2022-11-26 19:50:00 1483 Initial revision (published)