How will I solve the following problems?Urgent!

[Nikhar]

Hey guys, I have got a C++ competition tomorrow and it is very important for me. Following are few of the questions from past years. Please, please, pleeeasse read them and guide me on how do I solve them so that I get some preparation for tomorrow

http://pastebin.com/m226a46ab

http://pastebin.com/m79b943db

http://pastebin.com/m370be9ea

http://pastebin.com/m1c2ede0c

PS:- OH man, I am so desperate!!

Please please help me.

[ChaseVoid]

Who is going to read through all those links? If you want answer to specific problem, quote it and give proper explanation to what exactly you need help with.

[poet]

Do you have specific questions concerning these tasks or need complete solution? In the latter case I cannot help. But we can discuss ideas and problems. E.g. under the first link there is a task to compute the maximum size of the audience in the hall given an input data of the following form

N
e1 l1
e2 l2
...
eN lN

where N - nb of noted person, ek and lk - (e)nter and (l)eaving time of k-th noted person to the hall. Task: find the maximum number of persons being in the hall at the same time.

The simplest solution woud be to have a vector (array) of ints, where i-th element corresponds to the i-th minut. Then looping through the input table, on each step, say k-th, we increment elements in the vector with indicies i: ek<=i<=lk. When all the entries are looked up we simply search the maximum in the built vector.

for(k=0;k<N;++k) {
	// read ek, lk
	for(i=ek;i<=lk;++nbPersonsAt[i++]);
}
int max=0;
for(i=0;i<nbPersonsAt.size();++i)
	if(nbPersonsAt[i]>max)
		max=nbPersonsAt[i];

value of max is the answer.

[Nikhar]

@chasevoid
I didn't quote the problems because they won't fit in as this forum has restriction on the max length.

@poet

Thanks for the reply.
I am not looking for complete answers. I just want to someone to help me as to how should I go about solving the problems.

I thought of the code you provided. But there's a little problem. As far as my calculation goes, this program will require exponential run time. The inputs can go as long as a few thousands. Just imagine the time it would take.

[poet]

Where do you see an exponential complexity? It's linear under the given assumption on entry and exit time to be in [0, 107], which means that we have at most 108*N+108 evaluation.

[Nikhar]

Oh sorry. I must have miscalculated.

[Nikhar]

Regarding the second problem, someone said its a variation of Bin Packing. Is that true?

[blackcoder41]

how things are going bro or sis? here's a solution, it's not a good algorithm but i'll post it anyway.. this uses brute force..

#include <iostream>
#include <conio.h>
using namespace std;

int n, m;
int found=0; //if a combination if possible
int * price; //book prices
int select[3]; //the three books

int safe(int v) {
    for(int x=0; x<3; x++) {
      if(select[x]==v) return 0;
    }
    return 1;
}

int sum() {
    int tmp = 0;
    for(int x=0; x<3; x++)
      tmp += price[select[x]];
    return tmp;
}

void print() {
    cout << "============\n";
    for(int x=0; x<3; x++)
      cout << price[select[x]] << '\n';
    cout << "============\n";
}

void find(int i) {
    if(found) //we've found one!
      return; //go back now..
    if(i==3) { //we've picked 3 books already..
      if(sum()==m) { //check if is matches target
        found = 1; //yehey..
        print(); //print the combination
      }
    }else
    for(int x=0; x<n; x++) {
      if(safe(x)) { //check no duplicate book
        int tmp = select[i]; //remember our last book
        select[i] = x; //grab the book
        find(i+1); //choose another book
        select[i] = tmp; //get the last book again..
      }
    }
}

int main() {
    cout << "Number of books: ";
    cin >> n;
    cout << "Coupon amount: ";
    cin >> m;
    price = new int[n];
    cout << "Book Price:\n";
    for(int x=0; x<n; x++)
        cin >> price[x];
    for(int x=0; x<3; x++)
        select[x] = -1;
    find(0);
    if(!found)
        cout << "Sorry no combination possible..\n";
    cout << "Searching over..\n";
    return 0;
}

[Nikhar]

Thanks a lot blackcoder41. I am finding it a bit difficult to understand the algorithm you have used.
Can you explain it to me?

Meanwhile, I'll try to understand it too. :)

[blackcoder41]

hey what happen in your C++ competition? anyway what part didn't you understand in my code?

[Nikhar]

Hey Blackcoded41...the competition went OK. Out of the two questions given, I was able to solve one of them.

[blackcoder41]

good for you.. so you win? anyway can you post the problem they gave in the competition?

[Nikhar]

The results will be announced in a week.

Actually, we werent allowed to take the question paper back with us. So, sorry...can't post the questions.

[blackcoder41]

good luck then.. anyway in first problem you post why is the answer 4?

Serial No Enters at Leaves at
1 1 7
2 2 4
3 6 9
4 3 8
5 5 10
In this example, the maximum size of the audience during the programme was 4. This
was achieved between time 6 and 7.

[Nikhar]

Thanks. :)

[poet]

@blackcoder41:

anyway in first problem you post why is the answer 4?

because there is no time when all 5 persons were together in the hall (e.g., 2nd and 3rd guys never met) but during 6th and 7th minutes four persons were in the hall:


#: 1 2 3 4 5 6 7 8 9 10 <-- minutes
1: + + + + + + + - - -
2: - + + + - - - - - -
3: - - - - - + + + + -
4: - - + + + + + + - -
5: - - - - + + + + + +
----------------------
+: 1 2 3 3 3 4 4 3 2 1 <-- nb of people in the hall