10594 - Data Flow

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

Moderator: Board moderators

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

10594 - Data Flow

Post by erfan » Sat Dec 27, 2003 8:04 am

I verify again and again but may be sample I/O for one is wrong:
input:
4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 100
output:
140
I think it should be
input:
4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 10
output:
140
Am i correct or incorrect?
Any one please check it:

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Sat Dec 27, 2003 2:14 pm

i think the sample i/o is ok.
see

1st we find the shortest path (according to time). the shortest path time is 7 (per unit data) and the path is(1->2->4 or 1->3->4).

here the link capacity is 100. so, we can send the whole data at the same time.

so total time for 20 unit data is = 7*20=140
so it is ok.

i solved this problem by bfs. i run bfs again and again untill D amount data is not transferred.

best of luck
Rakeb

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Sat Dec 27, 2003 3:13 pm

Yah,
i was wrong.I can realize my misunderstanding. :evil:
Now i got it AC.
Actually it is a great problem :lol: :lol:
Thanks for help.

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm

10594 - Bad judge data or problem statement

Post by Lars Hellsten » Tue Dec 30, 2003 6:02 am

After wasting a fair bit of time trying to solve this using network flow, I discovered that a much simpler approach of repeatedly picking the shortest path, then deleting that path, gets AC. This is incorrect though, according to the problem description. Consider the following test case:

8 11
1 2 0
1 3 0
1 4 0
5 8 0
6 8 0
7 8 0
2 6 1
3 7 1
2 5 2
3 6 2
4 7 2
3 1

Clearly it is possible to transmit 3 units of data through this network. My incorrect (but accepted) solution attempts to push data through the edges with cost 1 initially. However, once those two paths are used and removed, there is no way to push the third data packet through the network, so it outputs "Impossible." This is totally wrong, according to the problem statement.

I guess this is why the success rate on the problem is so low.

kzaman010
Problemsetter
Posts: 18
Joined: Wed Jan 16, 2002 2:00 am
Location: Bangladesh
Contact:

Post by kzaman010 » Tue Dec 30, 2003 6:11 am

You are right. And that's why I posted a message
not to submit it two days ago. I have already sent the updated data and
then removed the post " Not to submit".

It will be rejudged soon. Sorry for the inconvenience.

Marcin Kwiatkowski
New poster
Posts: 5
Joined: Thu Jan 01, 2004 10:43 pm
Location: Gdynia, Poland

Post by Marcin Kwiatkowski » Wed Jan 07, 2004 10:27 pm

Code: Select all

4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 1

Why answer for this test is Impossible? Could anybody explain me that?
And one more thing...why the answer for this test case:

Code: Select all

4 5
1 4 1
1 3 3
3 4 4
1 2 2
2 4 5
20 10
is 80?
"Imagination is more important than knowledge" Albert Einstein

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Tue Jan 13, 2004 9:47 am

rakeb wrote: best of luck
Hello, rakeb
I get WA on the problem all the time
Would you give me some input/output ?
Thx :D

User avatar
filipek
New poster
Posts: 9
Joined: Sat Jun 22, 2002 12:16 pm
Location: Poland
Contact:

Post by filipek » Tue Jan 13, 2004 4:40 pm

Marcin Kwiatkowski wrote:

Code: Select all

4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 1
You cannot send 20 packets through this network, if edge capacity is 1 - you'll send 1 packet through 1-3-4 and one through 1-2-4, but no more.
Marcin Kwiatkowski wrote:

Code: Select all

4 5
1 4 1
1 3 3
3 4 4
1 2 2
2 4 5
20 10
is 80?
Sending ten packets through 1-4, which takes 10 * 1 = 10 time, and 10 through 1-3-4 or 1-2-4 (whichever you want), which takes 10 * 7 = 70 time, 10 + 70 = 80.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Fri Jan 16, 2004 7:38 am

Previously this problem had a very simple solution which was infact not correct but later it was corrected by the problemsetter. And now it is not as easy as it was before. On your first thought you might think of doing something like calculating the SSSP and removing the edges and then calculate SSSP again and keep on doing so until you reach the needed amount. But the problem arises when you are provided with an input where if you remove the SSSP you can never reach the needed amount so you need to find the shortest combination making sure that you reach the target amount if it is possible.

I'd solved this problem right on the very first or second day it was added to OJ but later I got WA on correct rejudgement. Hope to solve it soon but right now I'm little busy with other things.

I hope I could make you understand what exactly is asked for in this problem. If you think your solution does that correctly and still you are getting WA then let me know, may be I'll give you some test I/O cases.
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

Post by tat tvam asi » Fri Jun 04, 2004 12:49 am

Helo

In the first case of the sample input why it is not
possible to send the data as follows:
10 packet 1->4 (10 time unit)
10 packet 1->2->1->4 (50 time unit) ?

Peace,
Csaba Noszaly

User avatar
filipek
New poster
Posts: 9
Joined: Sat Jun 22, 2002 12:16 pm
Location: Poland
Contact:

Post by filipek » Fri Jun 04, 2004 12:59 am

tat tvam asi wrote: 10 packet 1->4 (10 time unit)
10 packet 1->2->1->4 (50 time unit) ?
Aren't you using then edges 1-2 and 1-4 two times?

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

Post by tat tvam asi » Fri Jun 04, 2004 1:28 am

Thanks Filipek!
So I can not use edges more than once. (collision???)
I did not get it from the problem's description.
Peace,
Csaba Noszaly

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Mon Jun 21, 2004 9:19 am

Dreamer#1 wrote:I'd solved this problem right on the very first or second day it was added to OJ but later I got WA on correct rejudgement. Hope to solve it soon but right now I'm little busy with other things.

I hope I could make you understand what exactly is asked for in this problem. If you think your solution does that correctly and still you are getting WA then let me know, may be I'll give you some test I/O cases.
Hello Dreamer,
I got WA on this problem, could you give me some test cases?
Thanks in advance.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Sep 10, 2004 8:47 pm

Still no one to paste some test case??
I tried to use Successive Shortest Path algorithm to solve this problem,
but gets WA. Could anyone give me the output:

Code: Select all

10 16
1 9 8
6 9 7
7 9 83
10 9 6
8 9 64
3 9 62
4 9 59
2 4 29
4 8 29
8 5 64
3 5 40
6 5 2
10 5 76
5 7 70
4 7 7
7 1 21
805 22349
10 18
2 1 13
10 1 54
8 1 28
3 1 88
5 1 8
7 1 86
6 1 32
4 1 75
9 1 60
4 5 8
9 5 17
6 5 55
5 3 52
2 3 50
4 3 41
3 9 66
6 9 44
10 9 35
20235 21705
10 40
4 9 13
7 9 90
9 2 76
3 2 63
2 5 83
6 5 27
5 4 21
7 4 25
1 4 74
9 1 58
7 1 64
10 1 53
5 1 80
3 1 66
6 1 5
10 4 51
6 4 86
2 4 55
8 4 40
8 1 19
2 1 92
8 10 37
5 8 26
2 8 76
6 8 23
8 3 11
4 3 12
6 3 43
7 3 10
9 3 75
5 3 33
7 6 53
10 5 59
5 7 100
7 10 52
9 10 96
3 10 44
2 10 46
5 9 73
6 9 87
9750 13344
10 38
4 9 83
5 9 52
9 7 63
1 7 30
6 7 6
2 7 48
8 7 85
10 7 4
4 7 56
3 7 21
6 1 68
2 1 98
9 1 3
3 1 12
10 1 88
4 1 31
5 1 82
8 1 15
9 2 27
8 2 67
3 2 46
4 2 95
6 2 81
5 2 14
10 2 3
3 4 39
6 4 18
10 4 89
8 4 86
5 4 67
5 3 64
8 3 7
9 3 29
5 7 50
5 8 65
10 8 20
10 3 87
6 3 54
24639 8190
10 11
6 3 53
9 3 4
5 3 44
3 4 55
8 4 71
6 4 43
1 4 86
2 4 89
9 4 8
5 4 89
10 4 96
4972 23026
10 0
26969 1206
10 39
9 4 13
10 4 98
1 4 68
5 4 95
8 4 92
2 1 3
9 1 47
8 1 7
6 1 72
7 1 10
1 10 48
5 10 90
3 5 78
8 5 54
7 5 8
9 5 72
2 5 12
1 5 78
6 5 87
2 3 95
10 2 60
8 2 16
2 6 25
7 6 45
6 10 36
7 10 8
3 1 39
4 2 1
9 2 61
7 2 49
6 8 42
10 8 13
3 7 70
9 10 81
3 10 23
3 8 27
7 8 18
9 8 78
3 9 40
32702 15084
10 9
9 5 49
2 5 1
5 6 75
2 6 5
10 6 6
9 6 23
7 6 25
1 6 45
3 6 40
4124 28230
10 37
2 6 44
6 7 4
5 7 12
3 7 36
10 7 47
8 7 61
2 7 43
5 6 72
3 6 27
6 10 61
5 10 9
4 10 75
10 8 56
6 8 83
4 8 13
5 8 93
2 8 82
3 8 26
1 3 57
4 3 96
9 3 66
5 3 57
2 3 93
10 3 19
9 7 69
1 7 8
4 7 64
9 5 66
5 2 49
1 2 12
4 2 1
9 2 48
2 10 24
9 10 7
6 9 57
1 9 13
8 9 50
22137 19596
10 11
4 9 66
2 9 36
3 9 97
7 9 41
5 9 88
1 9 49
6 9 94
8 9 14
10 9 80
5 4 78
7 5 7
19920 24127
My output:

Code: Select all

11270
1092690
516750
841452
904904
Impossible.
694824
210324
465609
2569680
Thanks in advance
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Sep 10, 2004 9:43 pm

Did you consider the test case posted here:
http://online-judge.uva.es/board/viewtopic.php?t=4757 ?
It should break a solution that greedily removes shortest paths.

Post Reply

Return to “Volume 105 (10500-10599)”