18DaysLeft's blog

why is this approach not working?
By 18DaysLeft, history, 15 hours ago, In English

for this problem 1237B - Balanced Tunnel , This is my approach 309018105

I am starting from behind in second array and if a Car has moved backwards that is its position in coming out array is greater that coming in array then make it a victim and then for all cars coming before it check if they have crossed it until we find new victim and update it too and check for them too.

My thinking is that any car that has been overtaken will go back unless it overtakes someone else. So there is always a victim and so it should work. But it doesn't is there a case i am missing because in 4th test case i am missing the answer by big difference.

I have solved the problem with brute force but it is ugly 309016497, so was wondering why this victim approach is not working.

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

»
14 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

Think about this test case:

4

1 2 3 4

1 3 2 4

the answer is 1 but your code gives 0. Why? ask yourself you will get your answer. :)

→ Reply
  • »
    »
    14 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ops! my bad this is not the test case. i was wrong. But wait i am trying to finding one

    → Reply
  • »
    »
    14 hours ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    well well i got the test case.

    1

    5

    1 2 3 4 5

    4 5 1 3 2

    Correct answer — 3

    Your code gives — 2

    Now try to understand your code with this test case step by step you will get your answer.

    → Reply
    • »
      »
      »
      9 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks but my code fails at your test case because later checks which fixed 309074936

      But now the instead of passing 122 i pass 179 of 224 cases

      → Reply
»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem is your current victim is not the worst victim.

→ Reply
»
13 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

your first code found an victim and count its first car that go earlier than it,and if right after that is another victim your code just jump to it,did not fully checking previous,then you must check fully it,because one victim can be overtaken by some cars , not only one

→ Reply
  • »
    »
    9 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks I got it. Nyemot mentioned the same thing. My victim isn't the worst in many cases.

    → Reply