Wrong Answer ???

[Maggi Iggam]

Here's the question :-

Indraneel has to sort the books in his library. His library has one long shelf. His books are numbered 1 through N and he wants to rearrange the books so that they appear in the sequece 1,2, ..., N.
He intends to do this by a sequence of moves. In each move he can pick up any book from the shelf and insert it at a different place in the shelf. Suppose Indraneel has 5 books and they are initially arranged in the order
2 1 4 5 3
Indraneel will rearrange this in ascending order by first moving book 1 to the beginning of the shelf to get
1 2 4 5 3
Then, moving book 3 to position 3, he gets
1 2 3 4 5
Your task is to write a program to help Indraneel determine the minimum number of moves that are necessary to sort his book shelf.
Input format
The first line of the input will contain a single integer N indicating the number of books in Indraneel's library. This is followed by a line containing a permutation of 1, 2, ..., N indicating the intial state of Indraneel's book-shelf.
Output format
A single integer indicating the minimum number of moves necessary to sort Indraneel's book-shelf.
Test Data:
You may assume that 1 ≤ N ≤ 200000. You may also assume that in 50% of the inputs, 1 ≤ N ≤ 5000.
Example:
Here is the sample input and output corresponding to the example discussed above.
Sample Input
5
2 1 4 5 3
Sample Output
2

Here's my solution :-

#include <iostream>
using namespace std;
int main ()
{
    int i,j,books[1000],n,tp,tmp,co=0;
    bool flag=false;
    cin>>n;
    for (i=1;i<=n;i++) cin>>books[i]; //take all inputs
    for (i=1;i<=n;i++) {
        if (books[i]!=i) {  //if true then book at ith position is not at its place
           co++;
           for (j=n;j>i;j--) {  //start searching for book i from end
               if (books[j]==i) flag=true;  //if book found flag it true
               if (flag==true) {  //if we have found the book , start shifting all books such that required book comes to at its actual place
                  tmp=books[j];
                  books[j]=books[j-1];
                  books[j-1]=tmp;
               }
           }
           flag=false;
        }
    }
    cout<<co;
}

But when i submit this program , it gives msg "Wrong Answer" for all 10 test cases ? This program is running correctly for example though , can anybody correct the program or tell me where i am going wrong ?

[coder777]

Where do those exercises come from? They are by far more interesting than the other.

For this exercise it'd be better if you understood the previous one. And it'd be better with more debug output.

The specific problem is the condition on line 12. It should be j>=i
But you will have a time problem

[Maggi Iggam]

well , these problems come from Indian online judge named iarcs ( http://opc.iarcs.org.in/index.php/problems/ ) .

yeah , i corrected the condition at line 12 , and i don't think i would have time problem for this algorithm - it ran in very very less time though gave wrong answer .

Can you please give more hint/correction ? I can't get it .

[coder777]

these problems come from Indian

I thought something like this. The normal exercises are way more boring.

minimum number of moves

This is the essence of this exercise.

take an easier origin: 5 1 2 3 4 6 7 8 9

if you wouldn't persistently refuse to place output (after the second loop) you'd see that your algorithm does this:

1 5 2 3 4 6 7 8 9
1 2 5 3 4 6 7 8 9
1 2 3 5 4 6 7 8 9
1 2 3 4 5 6 7 8 9

That means Indraneel needs 4 moves. Not exactly the minimum

On line 10 you have the right place for the misplaced book, but you don't care. You should.
The first step to the solution is:

Use the index of the misplaced book.
Move all books right of the that book one to the left (no need to swap or going backward) until the index in question. Output: 1 2 3 4 4 6 7 8 9
Correct the index in question. Output: 1 2 3 4 5 6 7 8 9
EDIT: Or you may swap (like you do now, but from left to right) and you don't need that correction. There're always more than one way...
That's it: one move for one misplaced book

Be aware that it's not the final solution. Just implement it. it's a good basis.
The next steps are: Finding the flaws and incorporate the solutions.