Getting wrong answer !

[Maggi Iggam]

Here's the question :-

Problem 1: Book Sorting, (K Narayan Kumar, CMI)
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

CPU Timelimit: 3 seconds
Memory limit: 64M
Grading style: ioi

And here's my solution :-

#include <iostream>
using namespace std;
int main ()
{
    int i,j,n,bl[200000],pn,tmp,co=0;
    cin>>n;                             //Input number of books
    for (i=1;i<=n;i++) cin>>bl[i];      //Store books in the given order
    for (i=1;i<=n;i++) {
        if (bl[i]!=i) {                 //Check wether book this book should be here or not 
           pn=bl[i];                    //Now from here we will change order of listing as per question
           bl[i]=i;
           for (j=i+1;j<=n;j++) {
               tmp=bl[j];
               bl[j]=pn;
               pn=tmp;
               if (pn==i) break;
           }
           co++;
        }
    }
    cout<<co;
    system("PAUSE");
}

It works correctly for sample input but when i submit this code , it gives "wrong answer" message to me for all 10 test cases !
Can anybody please help me out ?
Thanks in advanced .

[ne555]

Input:
5
5 1 2 3 4
Output:
1
Your output:
4

Array index goes from 0 to n-1. It will be out of bounds.
¿And who told you to put a system("PAUSE"); ?

[Maggi Iggam]

But i believe that output should be 4 only , as given in example .
First we will put 1 in place of 5 , then put 2 in place of 5,then 3 in place of 5 & then 4 in place of 5.

& ne555 i put system("PAUSE"); so that if anyone who reads and try to help me , should not get exit before he is able to read the output , after typing input in his compiler. :)
Thanks ne555 for stretching out helping hand .

[Berzeger]

First, C++'s array index goes from 0, as ne555 pointed out. So you should have for (i = 0; i < n; i ++), otherwise you'll get out of bonds.
Second thing is, pick better names for your variables. How should someone reading your code figure out at first sight what b1, pn, co and so on mean. :)

[ciphermagi]

http://www.cplusplus.com/forum/beginner/1988/#msg7275

[vin]

But i believe that output should be 4 only , as given in example .

Indraneel will rearrange this in ascending order by first moving book 1 5 to the beginning end of the shelf to get 1 2 3 4 5

First, C++'s array index goes from 0, as ne555 pointed out. So you should have for (i = 0; i < n; i ++), otherwise you'll get out of bonds.

Just make the array bl[200001] and never use bl[0].

[Maggi Iggam]

Ok , now i have made array bl[200001] and not using bl[0] at all , neither using system("PAUSE"); . Here's Final code , but it is still saying "Wrong Answer" ?!?

#include <iostream>
using namespace std;
int main ()
{
    int i,j,n,bl[200001],pn,tmp,co=0;
    cin>>n;                             //Input number of books
    for (i=1;i<=n;i++) cin>>bl[i];      //Store books in the given order
    for (i=1;i<=n;i++) {
        if (bl[i]!=i) {                 //Check wether book this book should be here or not 
           pn=bl[i];                    //Now from here we will change order of listing as per question
           bl[i]=i;
           for (j=i+1;j<=n;j++) {
               tmp=bl[j];
               bl[j]=pn;
               pn=tmp;
               if (pn==i) break;
           }
           co++;
        }
    }
    cout<<co;
}

[viliml]

try this:

#include <iostream>
using namespace std;
int main ()
{
    int i,j,n,bl[200001],pn,tmp,co=0;
    cin>>n;                             //Input number of books
    for (i=0;i<n;i++) cin>>bl[i];      //Store books in the given order
    for (i=0;i<n;i++) {
        if (bl[i]!=i) {                 //Check wether book this book should be here or not 
           pn=bl[i];                    //Now from here we will change order of listing as per question
           bl[i]=i;
           for (j=i+1;j<n;j++) {
               tmp=bl[j];
               bl[j]=pn;
               pn=tmp;
               if (pn==i) break;
           }
           co++;
        }
    }
    cout<<co;
}

[Maggi Iggam]

@viliml thnks , i tried your code , but it is still giving "Wrong Answer" !!!

[ne555]

Your task is to write a program to help Indraneel determine the minimum number of moves that are necessary to sort his book shelf.

5
5 1 2 3 4

If you 'move' the 5 to the end then the sequence gets sorted.
1 movement.
Your code says 4.

[Maggi Iggam]

I do not agree with this ne555 . Previous code did the same think as this but it manually did as it was said in problem (see example) and i got 6 test case correct but rest 4 were stuck with time-limit . In above solution of mine i am just trying to do theoritically what i did previously . Here is the previous solution :-

#include <iostream>
using namespace std;
int main(){
    int m,n,el[4000],i,o;
    cin>>m;
    int *bl=new int[m];
    for (i=1;i<=m;i++) cin>>bl[i];
    cin>>n;
    for (i=1;i<=n;i++) {
        cin>>el[i];
        cout<<bl[el[i]]<<endl;
        for (o=el[i];o<m;o++) {
            bl[o]=bl[(o+1)];
        }
    }
}

Now i am just trying to avoid rotating my booklist array & instead keep its record theoritically .

[hanst99]

If you 'move' the 5 to the end then the sequence gets sorted.
1 movement.
Your code says 4.

In-place, it takes 4 movements.

0: 5 1 2 3 4
1: 1 5 2 3 4
2: 1 2 5 3 4
3: 1 2 3 5 4
4: 1 2 3 4 5

You can't get lower than that unless you're either dealing with a list that supports removing from the beginning and inserting from the end or a similar data structure.

[ne555]

In each move he can pick up any book from the shelf and insert it at a different place in the shelf.

That's the definition of a movement.

the example wrote:

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

Moving the 3 counts as one movement.
Now ¿where does it say that you can't move a book to the right? ¿or to any end?

but rest 4 were stuck with time-limit

There is difference between wrong answer and time limit exceed.
When getting TLE your program takes too much time, so its output it is not compared. So you don't know if the answer was correct.

You may assume that 1 ≤ N ≤ 200000

Your algorithm is O(n^2), that means C * 4e10. Try to limit around 5e6.
So you need to change the complexity to something like O(n lg n). You only need to count the ones that are 'out of place'

About your last code: ¿what's the array 'el' for?
And again, array index goes from 0 to n-1

    int *bl=new int[m];
    for (i=1;i<=m;i++) cin>>bl[i];

is out of bounds

[Maggi Iggam]

Thanks a lot ne555 , maybe you are correct but then why is it so that my last code i gave you gave 6 correct answers and my previous code posted earlier here gave me all wrong answers ??
And yes i have corrected out of bound problem , you caught me right there .