Question : CodeChef: Practical coding for everyone
my solution : CodeChef: Practical coding for everyone
While running on codechef ide, sometimes it gives TLE and sometimes successfully executed but while submitting, it gives wrong answer.
But when I checked it with manual input, it gives correct result. Plz help to identify, where is the problem?
I don’t know what your code is doing, but you can’t count inversions in linear time
There’s a trivial O(n^2) algorithm though, so you can write a bash and stress-test to find a countercase for your solution
I implemented stack using vector, when input is greater than or equal to top, then I pushed, and when input is less than top then I popped the element untill the top element is less or equal to input OR untill stack is empty. During this I also kept track of no. of pop using ‘pre’ and ‘pop’ variable & variable ‘total’ is used to keep track of what the problem is asking ao far. It seems my program is O(n).
I am unable to see where is O(n2) .
Can you explain how your logic will actually count the number of inversions (since you currently have WA)?
Also, what I meant was, you could write the O(n^2) algorithm and check your own program against it.
Yes, I can explain what I thought -
continue to Getting wrong answer in EURON problem - #3 by shubbuu
Let we have, 5 4 3 2 1 and
pre = 0, total = 0
input = 5;
pop = 0
here, stack is empty, push 5
total = pre + pop + total = 0
pre = pre + pop = 0
again, input = 4
pop = 0; // I initialized pop with 0 every time, when I have new input
top of stack is greater than input, thus pop from stack
so, pop = 1
now, stack is empty, push
total = pre + pop + total = 0 + 1 + 0 = 1
pre = pre + pop = 0 + 1 = 1
input = 3;
pop = 0
again, top of stack is greater than input, thus pop from stack
pop = 1;
now, stack is empty, push
total = pre + pop + total = 1 + 1 + 1 = 3
pre = pre + pop = 2
input = 2;
pop = 0;
agaib, top of stack is greater than input, thus pop from stack
pop = 1;
now, stack is empty, push
total = pre + pop + total = 2 + 1 + 3 = 6
pre = pre + pop = 2 + 1 = 3
input = 1;
pop = 0;
again, top of stack is greater than input, thus pop from stack
pop = 1;
now, stack is empty, push
total = pre + pop + total = 3 + 1 + 6 = 10