10099 - The Tourist Guide

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

wireshark
New poster
Posts: 1
Joined: Sun Jun 22, 2014 12:43 pm

Re: 10099 - The Tourist Guide

Post by wireshark » Sun Jun 22, 2014 12:45 pm

A little modification to the problem. I want print the path along which the guide has to travel. How to do that?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10099 - The Tourist Guide

Post by brianfry713 » Tue Jun 24, 2014 12:04 am

Check input and AC output for thousands of problems on uDebug!

goktan
New poster
Posts: 2
Joined: Tue Jul 15, 2014 9:51 pm

Re: 10099 - The Tourist Guide

Post by goktan » Tue Jul 15, 2014 9:55 pm

Hi,
Same problem with many others that although my code goes through with all of the test cases I could find and generate, I keep getting WA from the judge. Maybe you can see the problem here and help me.
One comment would be, this code is my playground so I intentionally used dijkstra's shortest path and BFS approach with sticking to STL.

Code: Select all

#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <iomanip>
#include <algorithm>
#include <stdint.h>
#include <exception>
#include <set>
#include <queue>
using namespace std;

struct Pred {
    Pred(int i): val(i) {}
    bool operator() (std::pair<const std::pair<int, int>, long int> &p) {
        return p.first.first == val;
    }
private:
    int val;
};

int main() {
    
    int N, R;
    
    queue<int> qu;
    
    map<int, bool> visited_cities;
    map<int, bool> queued_cities;
    map<int, long int> carry_count;
    map<int, long int> carry_count_min;
    int count = 0;
    while(count++, true) {
        visited_cities.clear(); queued_cities.clear(); carry_count_min.clear(); carry_count.clear();
        cin >> N >> R;
        if(N==0 && R==0) break;
        for(int i=1; i<=N; ++i) {
            visited_cities[i] = false;
            queued_cities[i] = false;
            carry_count[i] = numeric_limits<int>::max();
            carry_count_min[i] = numeric_limits<int>::max();
        }
        
        map<pair<int, int>, long int> ways;
        int c1, c2, p;
        while (R--) {
            cin >> c1 >> c2 >> p;
            ways[{c2, c1}] = p;
            ways[{c1, c2}] = p;
        }
        int start, end, passengers;
        cin >> start >> end >> passengers;
        
        qu.push(start);
        queued_cities[start] = true;
        carry_count[start] = 0;
        while(!qu.empty()) {
            int working = qu.front(); qu.pop();
            if(working == end) continue;
            visited_cities[working] = true;
            map<pair<int, int>, long int>::iterator it = ways.begin();
            while((it = find_if(it, ways.end(), Pred(working)))!= ways.end()) {
                if(visited_cities[it->first.second]) {
                    it++;
                    continue; // if I visited here previously
                }
                if(!queued_cities[it->first.second]) { //enqueue city unless it has been previously, not necessarily needed though. already we are mimicking this by visited flag
                    qu.push(it->first.second);
                    queued_cities[it->first.second] = true;
                }
                double rounds = 1+((passengers-1) / (it->second-1)); //find rounds to make on this road minus 1 is from algorithm, plus 1 is the guide taking this seat
                if(rounds > 0 && carry_count[working]+(int)rounds < carry_count[it->first.second]) { //if my working cells carry count plus the roads carry count is smaller than previous carry counts
                    carry_count[it->first.second] = carry_count[working]+(int)rounds;
                    carry_count_min[it->first.second] = min(it->second, carry_count_min[working]);
                }
                it++;
            }
        }
        //cout << carry_count[end] << endl;
        cout << "Scenario #" << count << endl;
        double rounds;
        if(passengers==0) rounds = 0;
        else rounds = 1+((passengers-1) / (carry_count_min[end]-1));
        cout << "Minimum Number of Trips = " << static_cast<long long int>(rounds) << endl << endl;
        
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10099 - The Tourist Guide

Post by brianfry713 » Wed Jul 16, 2014 8:04 pm

Try solving it without using floating point.
To take the integer ceiling of a divided by b, you could use:
(a + b - 1) / b
Check input and AC output for thousands of problems on uDebug!

goktan
New poster
Posts: 2
Joined: Tue Jul 15, 2014 9:51 pm

Re: 10099 - The Tourist Guide

Post by goktan » Thu Jul 17, 2014 1:19 pm

Try solving it without using floating point.
To take the integer ceiling of a divided by b, you could use:
(a + b - 1) / b
I was doing this in different way on the next line but nevertheless I did take your advice and changed the code to the following. Unfortunately again my test cases are fine but it is still a WA according to judge.

Code: Select all

#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <iomanip>
#include <algorithm>
#include <stdint.h>
#include <exception>
#include <set>
#include <queue>
using namespace std;

struct Pred {
	Pred(int i) : val(i) {}
	bool operator() (std::pair<const std::pair<int, int>, long int> &p) {
		return p.first.first == val;
	}
private:
	int val;
};

int main() {

	int N, R;

	queue<int> qu;

	map<int, bool> visited_cities;
	map<int, bool> queued_cities;
	map<int, long int> carry_count;
	map<int, long int> carry_count_min;
	int count = 0;
	while (count++, true) {
		visited_cities.clear(); queued_cities.clear(); carry_count_min.clear(); carry_count.clear();
		cin >> N >> R;
		if (N == 0 && R == 0) break;
		for (int i = 1; i <= N; ++i) {
			visited_cities[i] = false;
			queued_cities[i] = false;
			carry_count[i] = numeric_limits<int>::max();
			carry_count_min[i] = numeric_limits<int>::max();
		}

		map<pair<int, int>, long int> ways;
		int c1, c2, p;
		while (R--) {
			cin >> c1 >> c2 >> p;
			ways[{c2, c1}] = p;
			ways[{c1, c2}] = p;
		}
		int start, end, passengers;
		cin >> start >> end >> passengers;

		qu.push(start);
		queued_cities[start] = true;
		carry_count[start] = 0;
		while (!qu.empty()) {
			int working = qu.front(); qu.pop();
			if (working == end) continue;
			visited_cities[working] = true;
			map<pair<int, int>, long int>::iterator it = ways.begin();
			while ((it = find_if(it, ways.end(), Pred(working))) != ways.end()) {
				if (visited_cities[it->first.second]) {
					it++;
					continue; // if I visited here previously
				}
				if (!queued_cities[it->first.second]) { //enqueue city unless it has been previously, not necessarily needed though. already we are mimicking this by visited flag
					qu.push(it->first.second);
					queued_cities[it->first.second] = true;
				}
				//int rounds = 1 + ((passengers - 1) / (it->second - 1)); //find rounds to make on this road minus 1 is from algorithm, plus 1 is the guide taking this seat
				//(a + b - 1) / b
				int rounds = (passengers + it->second - 1 - 1) / (it->second-1);
				if (rounds > 0 && carry_count[working] + rounds < carry_count[it->first.second]) { //if my working cells carry count plus the roads carry count is smaller than previous carry counts
					carry_count[it->first.second] = carry_count[working] + (int)rounds;
					carry_count_min[it->first.second] = min(it->second, carry_count_min[working]);
				}
				it++;
			}
		}
		//cout << carry_count[end] << endl;
		cout << "Scenario #" << count << endl;
		int rounds;
		if (passengers == 0) rounds = 0;
		//else rounds = 1 + ((passengers - 1) / (carry_count_min[end] - 1));
		else rounds = (passengers + carry_count_min[end] - 1 - 1) / (carry_count_min[end] - 1);
		cout << "Minimum Number of Trips = " << rounds << endl << endl;

	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10099 - The Tourist Guide

Post by brianfry713 » Thu Jul 17, 2014 9:46 pm

BFS won't work. Try using the minimax version of Floyd-Warshall's algorithm or a modified Dijkstra's algorithm.
Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

Re: 10099 - The Tourist Guide

Post by LazyTym » Mon Sep 22, 2014 5:08 pm

how it is solved in 0.000 sec? can anyone explain???????? My AC code solve in 0.022 sec and i use dijkstra's algo and do not use any stl..........

thanks in Advance.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10099 - The Tourist Guide

Post by lighted » Tue Sep 23, 2014 12:24 pm

Maybe it's possible to implement heap to optimize dijkstra's algo from O(N * N) to O(N * logN).
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

Re: 10099 - The Tourist Guide

Post by sreka11 » Tue Sep 23, 2014 2:38 pm

Can someone help me by showing my mistake ? I am getting a Runtime Error !

Code: Select all


Acc

Last edited by sreka11 on Wed Sep 24, 2014 11:26 am, edited 2 times in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10099 - The Tourist Guide

Post by lighted » Tue Sep 23, 2014 7:22 pm

Try this
turcse143 wrote:check this input:

Code: Select all

input:
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 1 99
0 0
output:
Scenario #1
Minimum Number of Trips = 0
hope it helps.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

Re: 10099 - The Tourist Guide

Post by sreka11 » Tue Sep 23, 2014 9:56 pm

TO: lighted Your test works for my code, it outputs 0. But I am getting a Runtime Error which is really strange.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10099 - The Tourist Guide

Post by lighted » Tue Sep 23, 2014 11:34 pm

Input

Code: Select all

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 1 99

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 1 99
0 0
I joined sample test above and it shows RE here. http://ideone.com/RKyqfb
I am not sure if it is main reason of RE, but when you seperate input tests by a blank line it gives RE.
Last edited by lighted on Wed Sep 24, 2014 1:26 am, edited 1 time in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

Re: 10099 - The Tourist Guide

Post by sreka11 » Wed Sep 24, 2014 12:44 am

But do the real tests have blanks inbetween or not ?

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10099 - The Tourist Guide

Post by lighted » Wed Sep 24, 2014 2:42 am

I checked accepted solution for 10099 to read by line into cstring and then sscanf from that cstring and got WA. So it becomes that there can be blank lines or some input values that should be on same line can be on different lines. Try to use Scanner with nextInt(). :)
Also i sent you PM.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sreka11
New poster
Posts: 15
Joined: Fri Aug 15, 2014 8:06 pm

Re: 10099 - The Tourist Guide

Post by sreka11 » Wed Sep 24, 2014 8:34 am

Thanks a lot, I got Acc with Scanner.

Post Reply

Return to “Volume 100 (10000-10099)”