Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

CandidFlakes's blog

Just need hint for Problem C
By CandidFlakes, history, 4 months ago, In English

This is the problem. This is my WA attempt.

What I have observed is that a maximum of (n/2-1) maxima is possible for an array of size n, where n is even. So initially I created another array q such that the final array a = p+q , has all elements equal. Then I greedily tried to create (n/2-1) maximas by swapping the elements of array q( In the code it's ans array). I am willing to explain more if clarification is needed. Please just give me the hint, I want to solve it myself.

I will be thankful for any help!

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

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

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

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

look at the tests

and I think you can look at the hints in the editorial

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Quick hint/intuition: Indices of all local maximas in an optimal arrangement should have the same parity.

→ Reply