1571 - Bus System

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
User avatar
ReynaldoGil
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified

1571 - Bus System

Post by ReynaldoGil » 7 years ago

http://coj.uci.cu/24h/problem.xhtml?abb=1571

I've seen many wrong answers to this problem, many of them in the test case 9, so it seems there's something weird here, so I ask for the admins to give at least an insight of what's wrong with that test case, or are the data tests wrong? I guess this problem wasn't taken from any other Olympiad, so it can't be found in Internet, please enlight us :D



User avatar
ReynaldoGil
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified

Re: 1571 - Bus System

Post by ReynaldoGil » 7 years ago

Anybody???
BTW who is dovier and what's the point on posting a link to every problem????

User avatar
dovier
Posts: 1143
Joined: 8 years ago
Location: Havana, Cuba
Gender: Male
Cuba

Re: 1571 - Bus System

Post by dovier » 7 years ago

Hello ReynaldoGil,
BTW who is dovier (...)
1- I'm the current 'ACM-ICPC Caribbean Director' since 2009.
2- I'm a professor in the UCI since 2008.
3- I'm co-founder of the COJ and current member of the COJ Development Team (CDEVT).
(...) what's the point on posting a link to every problem????
1- Avoiding mess at the subforum 'Problem set' (several threads discussing the same problem).
2- Establishing a stronger link between the problem description and its corresponding discussion thread at the forum.
3- Among other issues ...

If you have more questions or suggestions about the system (COJ+Forum), please post it in the appropiate subforum.

Best regards,
Dovier.

User avatar
ReynaldoGil
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified

Re: 1571 - Bus System

Post by ReynaldoGil » 7 years ago

Oh, sorry, itś just I had a feeling of another spammer in the forum, then itś alright. The problem is that it was annoying to see a recent topic in the 24th page, so that nobody would be able to read it again... You should put all those posts pointing each problem to the back of the forum.
BTW can the administrators post the 9th test-case of the so called Bus System problem??
thank you, keep your great job :D

User avatar
dovier
Posts: 1143
Joined: 8 years ago
Location: Havana, Cuba
Gender: Male
Cuba

Re: 1571 - Bus System

Post by dovier » 7 years ago

Hello ReynaldoGil,
The problem is that it was annoying to see a recent topic in the 24th page, so that nobody would be able to read it again...
You must use the option 'Mark forums read', so that hereinafter the freshest posts go up.
You should put all those posts pointing each problem to the back of the forum.
Believe me, I tried it ... but I didn't see any option to do that ... I recommend to use the search form or the sorting options listed at the end of the page.
thank you, keep your great job :D
You're welcome ... thank you to you for using our system!

Regards, Dovier.

User avatar
xshaka
Posts: 10
Joined: 7 years ago
Gender: None specified

Re: 1571 - Bus System

Post by xshaka » 7 years ago

Hi ReynaldoGil:

I'm the creator of the Bus System problem, and even when the problem test data has been checked for some other judges before being posted, we may be wrong. Can you please comment your approach here?

Best regards.

User avatar
ReynaldoGil
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified

Re: 1571 - Bus System

Post by ReynaldoGil » 7 years ago

Well, sorry for answering so late, my approach is just to simulate it, bus by bus, using some STL structures to make it faster, it's a bit error prone, but I've checked it more than once. Any clue on where my mistake could be?

User avatar
ReynaldoGil
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified

Re: 1571 - Bus System

Post by ReynaldoGil » 7 years ago

Does anybody else have something to say, as far I imagine, there are no dark points in my approach, I can guess that the "public" approach is the same, so what's the explanation of the WA? I would post my code here, but I know it's forbiden :)

User avatar
xshaka
Posts: 10
Joined: 7 years ago
Gender: None specified

Re: 1571 - Bus System

Post by xshaka » 7 years ago

Hi, my approach is similar I guess: I simulate the travel performed for every bus, but I think the key difference is I do need a more specific data structure for picking which group will get the bus at each stop. Could you please post your code? (it is allowed as long the code is not an AC code).

User avatar
ReynaldoGil
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified

Re: 1571 - Bus System

Post by ReynaldoGil » 7 years ago

ok, thank you, here you have it...

Code: Select all

#include <cstdio>
#include <list>
#include <set>
using namespace std;
const int MAX=100001;
struct group{
	int arrival, dest, size;
};
bool operator<(const group& a, const group& b)
{
	if(a.arrival!=b.arrival)return a.arrival<b.arrival;
	return a.size<b.size;
}
multiset<group> G[MAX];
list<group> stop[MAX];
int next[MAX]={0};
int T, N, M, Q;
int cap[MAX];
int time[MAX];
struct on{
	int num, dest;
};
bool operator<(const on& a, const on& b){
	return a.dest<b.dest;
}
int main() {
	int tem, totper=0;
	scanf("%d%d%d", &N, &T, &M);
	for(int i=1; i<=N; i++)scanf("%d", &cap[i]);
	time[1]=0;
	for(int i=1; i<M; i++)	{
		scanf("%d", &tem);
		time[i+1]=time[i]+tem;
	}
	scanf("%d", &Q);
	int A, B, C, D;
	for(int i=0; i<Q; i++)	{
		scanf("%d%d%d%d", &A, &B, &C, &D);
		G[C].insert((group){B, D, A});
		totper+=A;
	}
	int cur=0;
	for(int i=1; i<=M; i++)
		if(G[i].size()>0){
			stop[i].assign(G[i].begin(), G[i].end());
			next[cur]=i;
			cur=i;
		}

	cur=0;
	long long tottime=0;
	set<on>::iterator ss;
	list<group>::iterator it, ne;
	for(int i=1; i<=N && next[0]!=0; i++){
		multiset<on> bb;
		int p=0;
		int left=cap[i];
		while(next[p]!=0){
			cur=next[p];
			ss=bb.begin();
			while(ss!=bb.end()&& ss->dest <= cur)	{
				left+=ss->num;
				ss++;
			}
			bb.erase(bb.begin(), ss);
			it=stop[cur].begin();
			while(it!=stop[cur].end()){
				int curtime=(i-1)*T+time[cur];
				if(left>=it->size&&it->arrival<=curtime){
					tottime+=(long long)it->size*((i-1)*T+time[it->dest]-it->arrival);
					bb.insert((on){it->size, it->dest});
					left-=it->size;
					ne=it++;
					stop[cur].erase(ne);
				}
				else it++;
			}
			if(stop[cur].size()==0) next[p]=next[cur];
			else p=next[p];
		}
	}
	printf("%.3lf\n", (double)tottime/totper);
}

The struct on represent the people "on" the bus at every moment...

Post Reply

Return to “Problem set”