S.P.A.R.K's blog

Silly to ask, but reallly irritating
By S.P.A.R.K, history, 3 years ago, In English

My solution to the problem 1665C - Tree Infection : 153109990 gives WA on test6 and i am unable to find the corner case . If possible, please help correcting my solution

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

Comments Comments (2)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

In general, your solution fails whenever there are multiple highest elements where element-bs-1==0 inside the priority queue. while that particular top element is finished, the other top elements are not and still have a value of 1. (eg. multiple 2s, bs=1) Here's a counterexample demonstrating this:

10

1 1 1 1 2 2 2 2 2

(Answer should be 5)

If you remove the line that handles this, your solution should work.

→ Reply