Purendra_'s blog

Problem C in Codeforces Round 916 (Div. 3) has a wrong tag of "greedy"
By Purendra_, history, 4 months ago, In English

https://codeforces.com/contest/1914/problem/C

Consider the following case,

3 10 4 8 4 2 9 10

Out of the choices to use the 3rd quest are either (4) or (9), greedy would ideally choose 9 but if you keep choosing 9 over 4 we end up with the answer as 84 rather than 86

4 > 8 > 9 > 9 > 9 > 9 > 9 > 9 > 9 > 9 = 84 4 > 8 > 4 > 10 > 10 > 10 > 10 > 10 > 10 > 10 = 86

How is it tagged as greedy?

  • Vote: I like it
  • -2
  • Vote: I do not like it

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

Greedy as in, for the points we get by repetition of a task, we will choose the quest which gives us maximum points (and has been chosen atleast once) greedily for as many times as we want. (The choice for elements in array $$$b$$$ is greedy)

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

Greedy means taking the most optimal choice at the current moment and at the end it will to lead the best answer. You have to choose b greedily here

→ Reply