4e494b's blog

[SOLVED] Help needed — 234C

By 4e494b, history, 5 years ago, In English

Hello codeforces community.

I was trying to solve question 234C from codeforces round #145 and I could not come up with a scheme/way to solve it. So I tried looking for the editorials for this round but could not find it. Also, I looked at successful submission but could not understand the intended solution for this problem.

It would help me if you could share your approach on how you would solve this problem.

Thank You.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Consider the idea of prefix count (like prefix sums), where pre[i] counts the number of non-positive elements from index 1 to index i (inclusive). Similarly, from right to left, let suf[i] counts the number of non-negative elements from index n to index i (inclusive). Then, to find the minimum number of temperatures that need to be changed, you simply loop over all the possible values of the index k from 1 to n — 1 and minimize over pre[i] and suf[i + 1] which is exactly the number of changes to satisfy the condition given in the problem statement.

Here is my submission 56948236.

→ Reply