Puff... getting wrong answer ?!!?

[Maggi Iggam]

Here's the question :-

Problem 2: List of Books, (K Narayan Kumar / R Shreevatsa, CMI)
This is another problem about Indraneel's library. His library has one long shelf. His books are numbered and he identifies the books by their number. Each book has a distinct number.
He has lost many books, since many of his friends borrow his books and never bother to return them. He does not want to lose any more books and has decided to keep a record of all books that he lends to his friends. To make the task of borrowing a book a little difficult, he has given the following instructions to his friends: when they borrow a book, they must record in a register its position from the left among the books currently on the shelf.
Suppose there are 5 books in the library and they are arranged as follows:
26 1 42 15 3
If someone walks in and borrows the book 42, then he will record 3 in the register because this book is the third from the left on the shelf. Now the shelf looks like this:
26 1 15 3
If the next person borrow the book 3, he writes down 4 in the register since this is currently the fourth book from the left on the shelf, and so on.
Indraneel knows the initial arrangement of the books in his library at the time that he introduced the register system. After a while he examines his register and would like to know which books have been borrowed. Your task is to write a program to help Indraneel solve this problem.
Input format
The first line of the input contains a single integer M indicating the number of books in Indraneel's library. The next line contains M distinct positive integers describing the sequence in which the books are arranged on the library shelf. The third line of input contains a single integer N indicating the number of entries in the register. This, in turn, is followed by N lines (lines 4 to N+3), each containing one positive integer. The integer on line 3+i indicates the position from left of the book ith book borrowed. (You may assume that the number on line 3+i is at most M-i+1.)
Output format
N lines with one positive integer on each line. The number on line i is the book borrowed by the ith borrower.
Test Data:
You may assume that 1 ≤ M ≤ 1000000 and 1 ≤ N ≤ 4000.
Example:
Here is the sample input and output corresponding to the example discussed above.
Sample Input
5
26 1 42 15 3
2
3
4
Sample Output
42
3
CPU Timelimit: 3 seconds
Memory limit: 64M
Grading style:

Here's my solution :-

#include <iostream>
using namespace std;
int main(){
    int i,j,n,m,li[1000001],judge[4001],jc=0,tmp,tc=0;
    cin>>m;
    for (i=1;i<=m;i++) cin>>li[i];
    cin>>n;
    for (i=1;i<=n;i++) {
        cin>>tmp;
        tc++;
        for (j=0;j<jc;j++) {
            if (tmp>=judge[j]) tc++;
        }
        cout<<li[(tmp+tc-1)]<<endl;
        judge[jc]=li[(tmp+tc-1)];
        jc++;
        tc=0;
    }
}

It is working correctly in the given example , but gives me message "Wrong Answer" when i submit it .
Can anybody help me ?
Thnx for help in advance .

[coder777]

I'd suggest using variables that are more descriptive. Well I really don't know what this 'judge' means.

So this is the corrected code:

#include <iostream>
using namespace std;
int main(){
  int i,j,n,m,*li = new int[1000001] /*new because it crashes the stack otherwise*/,judge[4001],jc=0,tmp,tc=0;
  cin >> m;
  for(i = 0; i < m; ++i)
  {
    cin >> li[i];
  }
  cin >> n;
  for(i = 0; i < n; ++i) {
    cin >> tmp;
    judge[i] = li[tmp - 1];
    for(j = tmp; j < m; ++j) { // Note this!
      li[j - 1] = li[j];
    }
  }
  for(i = 0; i < n; ++i) {
    cout << judge[i] << endl;
  }
  return 0;
}

are you able to figure what's going on? Note that the program will crash if the user input is wrong

[ne555]

@coder777: Time Limit Exceeded.
¿Are you sure that you need new[] ?

@Maggi Iggam: Good idea, but

5
1 2 3 4 5
5
1 1 1 1 1

Your output:
1
2
2
2
2

[Maggi Iggam]

hmmmm... yes ne555 , i think you pointed out correctly .
coder777 , yeah your code is definatly neat and working , but it is fetching only 60% marks , just same as my one of codes i made previously ! :( can you improve it , as value of m can be very large indeed , thus it is exceeding time limit !
So can anybody tell me a better algorithm ??

[ne555]

Try to correct what you've got.
Explain what you tried to do, we might figure out the mistake.

[coder777]

ne555 wrote:

¿Are you sure that you need new[] ?

Code::Blocks/Windows -> Yes



Ok, interesting. That's the best I can think of now:

#include <iostream>
using namespace std;
int main(){
  int i,j,n,m,*li = new int[1000001] /*new because it crashes the stack otherwise*/,judge[4001],jc=0,tmp,tc=0;
  cin >> m;
  for(i = 0; i < m; ++i)
  {
    cin >> li[i];
  }
  cin >> n;
  for(i = 0; i < n; ++i) {
    cin >> tmp;
    judge[i] = tmp - 1;
    for(j = 0; j < i; ++j) { // Note this!
      if(judge[j] < judge[i])
        ++(judge[i]);
    }
  }
  for(i = 0; i < n; ++i) {
    cout << li[judge[i]] << endl;
  }
  return 0;
}

You may improve it with sorting?

[Maggi Iggam]

Hey thanks a lot coder777 , as i read this program i felt that it was perfect , but i don't know why it is giving 0 points and telling "Wrong Answer" !!!!

Even i am in delemma ?!?

Thanks a lot coder777 for extending a helping hand !

And yes the program runs within time limit !!!!

[coder777]

Yes it has a flaw. On line 15 it compares changed with unchanged values.

This can be mended when you use an array say judge2[4001] where you put the unchanged values:

#include <iostream>
using namespace std;
int main(){
  int i,j,n,m,*li = new int[1000001] /*new because it crashes the stack otherwise*/,judge[4001],judge2[4001],jc=0,tmp,tc=0;
  cin >> m;
  for(i = 0; i < m; ++i)
  {
    cin >> li[i];
  }
  cin >> n;
  for(i = 0; i < n; ++i) {
    cin >> tmp;
    judge2[i] = judge[i] = tmp - 1;
    for(j = 0; j < i; ++j) { // Note this!
      if(judge2[j] < judge[i])
        ++(judge[i]);
    }
  }
  for(i = 0; i < n; ++i) {
    cout << li[judge[i]] << endl;
  }
  return 0;
}

[Maggi Iggam]

Still , its giving "worng answer" messsage , though within time limit coder777 !!!
Thnx still.

[coder777]

Well

#include <iostream>
using namespace std;
int main(){
  int i,j,n,m,*li = new int[1000001] /*new because it crashes the stack otherwise*/,judge[4001],judge2[4001],jc=0,tmp,tc=0;
  cin >> m;
  for(i = 0; i < m; ++i)
  {
    cin >> li[i];
  }
  cin >> n;
  for(i = 0; i < n; ++i) {
    cin >> tmp;
    judge2[i] = judge[i] = tmp - 1;
    for(j = 0; j < i; ++j) {
      if(judge2[j] <= judge[i]) // Note
        ++(judge[i]);
    }
  }
  for(i = 0; i < n; ++i) {
    cout << li[judge[i]] << endl;
  }
  return 0;
}

A little bit of debugging on your side wouldn't do harm...

[Maggi Iggam]

Actually coder777 , i really couldn't understand what are you actually doing , so i couldn't debug it :) , instead i was trying and here's the code what i have brought to :-

#include<iostream>
using namespace std;
int main() {
    int i,j,n,booklist[100],m,borrowed[4000],tc;
    cin>>m;
    for (i=1;i<=m;i++) cin>>booklist[i];
    cin>>n;
    for (i=1;i<=n;i++) {
        cin>>borrowed[i];
        tc=0;
        for (j=1;j<i;j++) {
            if (borrowed[j]<=borrowed[i]) tc++;
        }
        cout<<booklist[(borrowed[i]+tc)];
    }
}

Though this is giving wrong answer still , i am trying to do it !
And realy thankyou for your efforts :)

[coder777]

The problem is that the output should appear after the input is done. Therefore 'tc' has to be an array with the same size like 'borrowed' and you need a second loop after the borrowed loop.

The idea is: Since I can't move the books I move the index to the books. So whenever the user borrows a book the index must be incremented as long as a book left of the current book is borrowed.

Imagine that the user enters 1 three times. The first time he enters 1 he means the first book.
The second time he enteres 1 he means the second book and so forth.
The second time the amount of books are already borrowed left of the current book is 1 and so add 1 to the entered index.
If he enters 1 the third time 2 books are already borrowed left of the current. That means to get the index where the book really is you need to add 2 to the entered index.

You need to hold those corrected index in an array to show the borrowed books. And you need to hold the index entered in an array to find the index left of the currently entered index.

Hope that makes it a bit clearer.

I can show you some code, but it's up to you to make it running

[Maggi Iggam]

Yes , it made me clear .
First of all 'tc' need not be needed , we can can print the book taken any time , as the compiler checks our program by taking all given output in a file and comparing with result file , thus we can print out book taken as we take input !!! (u can take this fact for granted , i have tried on previous problems !) .
And yes , the idea you explained me , is exactly the same as mine from the starting !!!
And once again thanks coder777 !!!

[coder777]

I don't see any problem with your code except that you need to write

cout<<booklist[(borrowed[i]+tc)] << endl; // Note: endl

on line 14 otherwise it's not printed on a new line

[Maggi Iggam]

Yeah , you correctly pointed me that , it was really a silly mistake !
And also that at the time of declaration , i need to increase array size , but still even after correcting these mistakes , don't know how it is saying "Wrong Answer" and i have really lost hope for getting correct answer !
I have started believing that the checking program is wrong !!! for i have tried writing the code , testing it many many many times , but still getting same message .

And thankyou coder777 a lot !

[coder777]

Ok, I considered the thing again. It doesn't suffice to consider just the left books. You need to consider the right books as well:

5
26 1 42 15 3
3
3
42
1
26
2
42

This is the output with your latest (slightly modified) code. Can you imagine why? Hint: You need that second array to mend this.

To get this right you really need to try out any combination possible

[Maggi Iggam]

Okay , you are saying true !
Its really giving wrong answers in such cases .
let me see how can i correct it , thnq coder777 .

[coder777]

Disregard the idea with the second array. It's not that mind boggling if you test the combinations. I can show you the solution if you want

[Maggi Iggam]

definatly u can show me the solution , one can learn a lot from it and i tried your second array but dont know its still wont work .

[coder777]

Ok, here is the solution:

#include<iostream>
using namespace std;
int main() {
    int i,j,n,booklist[100],m,borrowed[4000],tc;
    cin>>m;
    for (i=1;i<=m;i++) cin>>booklist[i];
    cin>>n;
    for (i=1;i<=n;i++) {
        cin>>borrowed[i];
        tc=0;
        for (j=1;j<i;j++) {
            if (borrowed[j]<=borrowed[i]) tc++; // the left books
            if (borrowed[j]>borrowed[i]) borrowed[j]--; // the right books
        }
        cout<<booklist[(borrowed[i]+tc)] << endl;
    }
}

So test it with as many books as possible. Combinations are: single/multiple books. Book(s) for right/middle/left right/left right/middle ...

please tell me if that finally works, since I want to see it finished