Why my problem going time limit exceeded even I am implementing binary search my solution

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

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

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

1 | 1-gon | 198 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | awoo | 186 |

4 | SecondThread | 186 |

6 | Um_nik | 182 |

7 | vovuh | 178 |

8 | Ashishgup | 176 |

9 | antontrygubO_o | 174 |

10 | -is-this-fft- | 173 |

Why my problem going time limit exceeded even I am implementing binary search my solution

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/05/2021 06:49:18 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Your solution uses

`Array.LastIndexOf`

. This Java function iterates over the complete array, so the complexity will again beO(n). Look with the binary search for the smallest elementa[i] that is greater thanx, then the answer isi.I am sorting then using binary Search but it is still giving TLE. Can you check this one and let me know why?

63616723

Your binary search implementation is wrong. The idea behind binary search is, that the search range gets halved each time. In your implementation you decrease the search range only by one (via

`left++`

and`right--`

), so the complexity is as bad as just doing a linear search.For a binary search you need something like

`left = mid + 1`

instead of`left++`

and`right = mid-1`

instead of`right--`

. But no guarantee, that this is the only mistake. I only glanced over your code for a second.Btw, that's also a very long way of writing the binary search.

I would write it like that:

The idea behind my though process is: I sustain two invariants the complete program.

`l`

is the largest shop that I know of in which I can buy the candy. At the beginning I don't even know if I can buy it at the first shop, so I initialize it with`l = -1`

.`r`

is the smallest shop where I know that I can't buy the candy, so at the beginning it is`list.size()`

, since I don't know if I can buy from the last one or not.I want to know, how we could have done this problem if prices at some shops would be same?

Exactly the same way.

But we also have to keep track of the frequency of prices ?

No, that doesn't matter.

I wrote that in my code I find the largest shop that I know of in which I can buy the candy. This is maybe a little imprecise. Correctly it should be: I find the largest index such that I can buy from the shop corresponding to the index.

And that handles duplicates per default. E.g. if the prices are $$$2, 3, 5, 5, 6$$$ and I have $$$5$$$ coins. Then I find the index 3.

Thanks for the explanation ,I understood it

Actually I woke up today realizing i wrote that wrong lmao. Sorry, my bad. Thanks for checking it out!

The following is a simple C++17 implementation using upper_bound function.

37844068

In your binary search implementation, if x equals to arr[mid] then you are using LastIndexOf (which has O(n) complexity) that's why you are getting TLE I recently solved this problem and I faced the same problem you need to replace LastIndexOf with binary search which finds the last occurrence of any element like this one.

Please don't copy the code try to understand it. Here is my solution for further reference Solution

come on man, its a 3 year old post.

Oh shit