10850 - The Gossipy Gossipers Gossip Gossips

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

Moderator: Board moderators

Post Reply
oldbam
New poster
Posts: 17
Joined: Tue Sep 14, 2004 9:30 am

10850 - The Gossipy Gossipers Gossip Gossips

Post by oldbam » Sat May 21, 2005 1:23 pm

Hi! Give me please critical input for this problem.
Life is beautifull !!!

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sat May 21, 2005 4:23 pm

Make sure you've sorted the times. That was my problem during contest time.

Regards
Sanny

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat May 21, 2005 6:44 pm

Say that:

- 1 meets 4 at time 0
- 2 meets 3 at time 1
- 3 meets 4 at time 1

1 is the right answer, but some straightforward implementations might turn out to return 101.

oldbam
New poster
Posts: 17
Joined: Tue Sep 14, 2004 9:30 am

Post by oldbam » Wed May 25, 2005 11:28 am

Still WA. I receive right answer on
4 1 1
0
2 4 1
1
3 4 1
1

I use BFS search. Why here can be a problem. All the times i keep in the array c[][][], where c[j][0]-number of times when person i meets person j.
I post my code. Maybe someone will see some mistakes, as i'm already tired of thinking about this problem.

Code: Select all

const int MAX = 21;
int c[MAX][MAX][1000];
int d[MAX];
int tmp[1000];

void main()
{
	int rez,times,q,f,t,i,j,tests,people,k,NO,aa,pp,ttt;
	int *z;
	deque<int> Q;
	scanf("%d\n", &tests);
	while(tests--) 
	{
		memset(c,0,sizeof(c));
		Q.clear();
		scanf("%d %d", &people, &j);
		for (i=1; i<=j; i++) {
			scanf("%d %d %d", &f, &t, &times);
			if (f==t) { for(k=1; k<=times; k++) scanf("%d", &ttt); continue; }
			for (k=1; k<=times; k++)  {
				scanf("%d", &aa);
				c[f][t][c[f][t][0]+k] = aa;
				c[t][f][c[f][t][0]+k] = aa;
			}
			c[f][t][0]+=times;
			c[t][f][0]+=times;
		}
		memset(d,-1,sizeof(d));
		Q.push_back(1);
		d[1]=0;
		while (!Q.empty()) {
			q = Q[0];
			Q.pop_front();
			for (i=1; i<=people; i++) {
				if (i==q) continue;
				if (c[q][i][0]) {
					for (j=1; j<=c[q][i][0]; j++) {
						// fill tmp array
						memset(tmp,127,sizeof(tmp));
						NO = tmp[0];
						if (d[q]>c[q][i][j]) tmp[j]=(d[q]/100+1)*100+c[q][i][j];
						else tmp[j]=c[q][i][j];
					}
					z = min_element(tmp, tmp+MAX);
					if (*z!=NO) {
						if (d[i]==-1 || d[i]>*z) {
							d[i]=*z;
							Q.push_back(i);
						}
					}
				}
			}
		}
		rez = 0;
		for(i=2; i<=people; i++) {
			if (d[i]==-1) rez = -1;
			else if (d[i]>rez) rez = d[i];
		}
		printf("%d\n", rez);
	}
}
Life is beautifull !!!

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Wed May 25, 2005 11:47 am

oldbam wrote:Still WA.
How do you know it's still WA? I can't see that this problem has been added to volume 108 yet.

oldbam
New poster
Posts: 17
Joined: Tue Sep 14, 2004 9:30 am

Post by oldbam » Wed May 25, 2005 12:56 pm

I tested it at my home PC with the input and receive right answer
Life is beautifull !!!

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi » Wed May 25, 2005 9:07 pm

Hi! After several WAs im bagging for help ;)

My algorithm is as follows:
I sort the times and doing simulation until there wasnt a meeting with changing news in the last 100 ticks.

I got right answers on every test case posted here and that i could think of. Maybe i missed something :/

Here comes the code:

Code: Select all



Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi » Wed May 25, 2005 10:57 pm

Got the bug ...

I forgot not to start simulating when there aint no meeting ...

finally AC

thank u ;)

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

10850 - The Gossipy Gossipers Gossip Gossips - WA

Post by wanderley2k » Thu Jun 02, 2005 3:00 am

Hi guys,

I try to solve the 10850 and receive many WA. I think that this problem is shortest-path.

I create this output:

Code: Select all

6
2 1
2 2 1
3

5 5
1 2 1
10
1 3 1
5
3 4 1
6
2 4 1
7
2 5 1
8

4 3
1 2 1
60
2 3 1
40
4 3 1
30

3 2
1 2 1
42
2 3 1
42

5 5
1 3 2
60 70
1 4 3
20 22 24
4 5 1
10
3 5 2
12 80
3 2 2
55 78

8 0
And my answer is
-1
8
230
42
80
-1

Thanks!

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Thu Jun 02, 2005 5:13 am

Your output is correct.

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

Post by wanderley2k » Thu Jun 02, 2005 2:12 pm

Then what is wrong?

Do you have critical input?

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sun Jul 30, 2006 1:49 am

Hi,

I don't know about shortest paths but this can be solved as a simulation problem. Just remember to increment the day only if you have visited everyone possible upto that day.

Post Reply

Return to “Volume 108 (10800-10899)”