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.
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. :)
Ops! my bad this is not the test case. i was wrong. But wait i am trying to finding one
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.
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
Problem is your current victim is not the worst victim.
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
Thanks I got it. Nyemot mentioned the same thing. My victim isn't the worst in many cases.