Canadian Computing Competition Problem

[IntermediateBeginner]

I'm trying to do a junior problem from the CCC from the U of Waterloo to judge my C++ skills and see what I still have to learn (which is a lot).
So lalalala, I'm successfully destroyed all of the problems until, BAM!
Question J5 from the 2007 test completely pulverized me.
My question is, how do I do this?
Thanks you guys so much!
The question is a bit long... *embarrassed*

Question:
A truck driver is planning to drive along the Trans-Canada highway from Vancouver to St. John’s, a distance of 7000 km, stopping each night at a motel. The driver has been provided with a list of locations of eligible motels, with the respective distance of each motel, measured in km, from the starting point in Vancouver. Some of the motel locations are:
0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000
but more motel locations may be added just before the trip begins.

Determine if it is possible to complete the journey if:

1. the trucking company insists that the driver travels a minimum distance of A km per day,
2. the law sets a maximum distance of B km per day, and
3. each night, the driver must stay at an eligible motel (from the above list or the additional locations described below).

The driver is interested in different options when making the trip, and you are to write the program to calculate how many different options there are. For example, if no new motel locations are added, A=1and B=50, then it is impossible to make the trip, i.e., the number of options is 0. If A=970and B=1030then there is one way to make the trip, but if A=970and B=1040then there are four ways to make the trip. There are two ways to make the trip if A=970, B=1030, and we add one stop at 4960.

Input Specification
The first two lines of the input are the minimum distance A and the maximum distance (1 <= A <= B <= 7000 ), both of which are integers. The third line of the input is an integer N(0 <= N <= 20), followed by N lines, each giving the location mof an additional eligible motel (0<m<70). You should note that no two motels are located at the same distance from Vancouver.

Output Specification
Output the number of different ways the driver can choose the motels to make the trip, under the given constraints.

Sample Inputs and Outputs
Sample Input|Sample Output
1 |0
500
0

970 |1
1030
0

970 | 4
1040
0

970 |2
1030
1
4960

[SirSmilesaLot]

i understood the problem, but one thing is not clear from your problem statement, assume A=10 b=1500 , the driver has two options 990 and 1010 on day one, what should we assume on day 2 is he is starting from 990 or 1010?? the next days available choices depend on that

[IntermediateBeginner]

Well, you are trying to find out how many ways there are to get to the end, so it doesn't really matter. There. I also made fixed the question a bit (i copy and pasted it from the website so there were a bit of problems)

[cire]

Here's one way:

#include <algorithm>
#include <iostream>
#include <vector>

template <typename T>
void orderedInsert(T & v, typename T::value_type addMe)
{
    v.insert(std::lower_bound(std::begin(v), std::end(v), addMe), addMe);
}

typedef std::vector<unsigned> vec;

unsigned waysToTravel(vec::iterator beg, vec::iterator end, unsigned min, unsigned max)
{
    vec::iterator lb = std::lower_bound(beg, end, *beg + min);  // *lb is the first motel in range for the day.

    if (lb == end)                                              // We've reached the end of the journey
        return 1;

    vec::iterator ub = std::upper_bound(beg, end, *beg + max);  // *ub is the first motel that isn't in range for the day.

    unsigned count = 0;
    while (lb != ub)                                            // for each motel in range, count the ways to travel.
        count += waysToTravel(lb++, end, min, max);

    return count;
}


int main()
{
    vec motels = { 0, 990, 1010, 1970, 2030, 2940, 3060, 3930, 4060, 4970, 5030, 5990, 6010, 7000 };

    unsigned minDist;
    unsigned maxDist;
    unsigned numAdditionalMotels;
    std::cin >> minDist >> maxDist >> numAdditionalMotels ;
    
    for (unsigned i = 0; i < numAdditionalMotels; ++i)
    {
        unsigned motel;
        std::cin >> motel;
        orderedInsert(motels, motel);
    }

    std::cout << waysToTravel(std::begin(motels), std::end(motels), minDist, maxDist) << '\n';
}

http://ideone.com/NgkhMS

[ne555]

^ Time Limit Exceeded

[Script Coder]

I quickly put down this pseudo code, have not done much checking, but basically should be a type of DFS/BFS:

//Assumes 0 and 7000 are always motel stops
int A,B = input();
int[] distances={input};	//assumes converted input
queue current={0};	//holds positions in the distances array
int number_of_routes=0;

while !current.empty() {
	t=current.next();
	for(int i=1, sum=distances[t+i]; sum<=B; ++i, sum+=distances[t+i]) {
		if(sum>=A) {
			if(t+i==distances.lenght()-1) {	//we are at the end so it is a valid path
				++number_of_routes;
			} else {	//we have another possibility
			current.add(t+i);
			}
		}
	}
}

/*
Input: 0 40 90 110 700
Converted Input: 0 40 50 20 590
*/
/* Also, if A is the minumum drive allowed per day, does that mean that in an input like (Assume 90 as final):
	A=50		 here 
				  |
				  v
	Input: ..... 50 90
	the driver would not be able to complete his journey?
*/

[elohssa]

This is some old example code I have that can be easily modified to solve this problem. Not sure if it is most efficient approach though.

#include <vector>
#include <set>
using namespace std;

struct Node
{
	set<Node*> directChildren, indirectChildren;
	vector<Node*> indirectChildrenWithDuplicates;
#ifdef _DEBUG
		char name/*for easy to read debugging*/;
		Node(char pname): name(pname) { }
#endif
};

void FindIndirectChildren(Node& node, set<Node*>& parents)
{

	for(set<Node*>::iterator i=parents.begin();i!=parents.end();++i)
	{
		
		if(*i!=&node && (*i)->directChildren.find(&node) == (*i)->directChildren.end() )
		{
			(*i)->indirectChildren.insert(&node); 
			(*i)->indirectChildrenWithDuplicates.push_back(&node);
		}
	}

	for(set<Node*>::iterator i=node.directChildren.begin(); i != node.directChildren.end();++i)
	{
		parents.insert(*i);
		FindIndirectChildren(**i, parents);
	}
}


int main()
{
	Node a('a'),b('b'),c('c'),d('d'),e('e'),f('f'),g('g'),h('h'),i('i');
	
	a.directChildren.insert(&b);
	b.directChildren.insert(&f);
	e.directChildren.insert(&h);
	e.directChildren.insert(&c);
	f.directChildren.insert(&e);
	h.directChildren.insert(&i);
	i.directChildren.insert(&g);
	b.directChildren.insert(&i);
	f.directChildren.insert(&i);

	set<Node*> parents;
	parents.insert(&a);

	FindIndirectChildren(a, parents);

}

Basically count the number of times the (pointer) address of the hotel at the furthest distance appears in firstNode.indirectChildrenWithDuplicates after all the other stuff is done.

[Smac89]

I don't know if this solves all correctly, but test and see.
http://ideone.com/DBecvM

Problem source: http://www.cemc.uwaterloo.ca/contests/computing/2007/stage1/juniorEn.pdf

E: Yep this solution works. Found the test data
http://www.cemc.uwaterloo.ca/contests/computing/2007/index.html

[IntermediateBeginner]

Guys...
Uh...
I looked at you guys epic solutions and... *very embarrassed*
I sorta... don't understand much of it?
And I also never used algorithyn.h or vector.h
Can someone explain what the heck elohssa and Script Coder wrote?
Still, thank you guys very much!

[Smac89]

The one I wrote is in python. Script Coder wrote sort of an outline of what the solution looks like. elohssa's solution can solve the problem but it needs to be rewritten to use the input involved with the problem