Submission : (https://mirror.codeforces.com/contest/1692/submission/275124032)

Problem : (https://mirror.codeforces.com/contest/1692/problem/E)

Why this approach fails, can anyone give some counter test case?

# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3773 |

3 | Radewoosh | 3646 |

4 | ecnerwala | 3624 |

5 | jqdai0815 | 3620 |

5 | Benq | 3620 |

7 | orzdevinwang | 3612 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | cry | 161 |

2 | awoo | 160 |

2 | maomao90 | 160 |

4 | atcoder_official | 157 |

5 | -is-this-fft- | 156 |

6 | nor | 155 |

7 | adamant | 153 |

8 | maroonrk | 152 |

8 | Um_nik | 152 |

10 | djm03178 | 146 |

Submission : (https://mirror.codeforces.com/contest/1692/submission/275124032)

Problem : (https://mirror.codeforces.com/contest/1692/problem/E)

Why this approach fails, can anyone give some counter test case?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/07/2024 23:48:59 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Consider array

`0 1 1 0 1 1 0`

, target sum is 1. Clearly it can't be done in less than 5 operations, because you must remove at least two 0s to be able to remove at least three 1s. But your approach would remove both outer zeros and set`zero`

to 1, then remove 3 more 1s, leading to a total cost of 4. It doesn't take into account thatbothouter 0s had to be removed.Thank you, i haven't noticed it.

The correct answer is 4 your algorithm returns 3.

The reason it fails in this case is that it performs the correct steps but only counts removing zeros from both ends as 1 operation. (the last else statement in your loop)

If you correct it your approach will still be incorrect as in the case:

After the fix your algorithm will return 8, instead of the correct 5 (it remove the first 5 numbers)

As far as I know there is no greedy solution to the problem.

This problem is equivalent to finding a subarray of maximum size with a sum equal to K (the numbers you leave). This can be solved with a sliding window.

Thank you.

Yeah, i later tried sliding window and it worked, i was just curious whether it can be done with two pointers alone but it doesn't seem to work. thank you once again.