## 301 - Transportation

Moderator: Board moderators

Jucovschi Constantin
New poster
Posts: 9
Joined: Sat Oct 26, 2002 6:30 pm

### How to solve 301 in time 0.00

How to solve 301 in time 0.00

I've tried some kind of opptimized backtracking and it run for 4.661 sec.

How to make this time 0.00 ?

Is there any other method ?

Cloud Song
New poster
Posts: 1
Joined: Fri Jun 20, 2003 2:14 pm
hi, if you use a simple pruning in the B&B, you can get 0.00

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
hi,excuse me
What is B&B?

srdjan
New poster
Posts: 1
Joined: Wed Oct 08, 2003 4:37 pm

### problem 301

What's a good algorithm for problem 301? I can't think of any dynamic programming solution. I'm using recursion but basically it's considering every possible set of orders (with distinct total number of passengers) between two stations and that's why I'm getting TLE.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Branch & Bound

[It could also mean Bed & Breakfast, but that's probably not what he meant =P]

Sanya
New poster
Posts: 5
Joined: Mon Oct 27, 2003 3:05 pm
Location: Ukraine
Hi, can somebody give me test data for this problem, please.
I don't know why my code produces WA. Thank you.
[pascal]
var
n,m,k,i,j,sum,bestsum:integer;
c:array[1..22] of integer;
r:array[0..6] of integer;
a,b,x:array[1..22] of byte;
begin
while True do
begin
if (n=0)and(m=0)and(k=0) then break;
for i:=1 to k do read(a,b,c);
for i:=0 to m-1 do r:=n;
i:=0; sum:=0; bestsum:=0;
while True do
begin
inc(i);
j:=a;
while(j<b)and(r[j]>=c) do inc(j);
if j=b then
begin
for j:=a to b-1 do dec(r[j],c[i]);
x[i]:=1; inc(sum,(b[i]-a[i])*c[i]);
end else
begin
x[i]:=0;
end;
if i=k then
begin
if sum>bestsum then bestsum:=sum;
while (i>0)and(x[i]=1) do
begin
dec(sum,(b[i]-a[i])*c[i]);
for j:=a[i] to b[i]-1 do inc(r[j],c[i]);
dec(i);
end;
while (i>0)and(x[i]=0) do dec(i);
if i=0 then break;
dec(sum,(b[i]-a[i])*c[i]);
for j:=a[i] to b[i]-1 do inc(r[j],c[i]);
x[i]:=0;
end;
end;
writeln(bestsum:1);
end;
end.
[/pascal]

Opexoc
New poster
Posts: 2
Joined: Tue Jul 06, 2004 4:57 pm
Location: Poland
Contact:

### 301

Who can help me with this problem ? J have sumbited my solution but my
program still use too much memory. I think about better solution but nothing come to my head!

Kire Sopov
New poster
Posts: 7
Joined: Wed Sep 15, 2004 2:01 am
Here's my code, if it can help...
[cpp]
/* @JUDGE_ID: xxxxxx 301 C++ "Backtracking" */
#include <stdio.h>

#define MAX_ORDERS 25
#define MAX_STATION 10

// Global templates
template <class _T>
inline void Swap(_T &x, _T &y)
{
_T z = x;
x = y;
y = z;
}

// Global class definitions and typedefs
struct TICKET_ORDER
{
inline TICKET_ORDER():m_nFrom(0), m_nTo(0), m_nTickets(0), m_nEarnings(0) {}

inline TICKET_ORDER(int nFrom, int nTo, int nTickets)
{
m_nFrom = nFrom;
m_nTo = nTo;
if (m_nFrom > m_nTo) Swap<int>(m_nFrom, m_nTo);
m_nTickets = nTickets;
m_nEarnings = nTickets * (m_nTo - m_nFrom);
}

inline void Set(int nFrom, int nTo, int nTickets)
{
m_nFrom = nFrom;
m_nTo = nTo;
if (m_nFrom > m_nTo) Swap<int>(m_nFrom, m_nTo);
m_nTickets = nTickets;
m_nEarnings = nTickets * (m_nTo - m_nFrom);
}

inline bool operator > (const TICKET_ORDER &rhs)
{
if (m_nFrom != rhs.m_nFrom)
return (m_nFrom > rhs.m_nFrom);
return (m_nTo > rhs.m_nTo);
}

int m_nFrom, m_nTo, m_nTickets;
int m_nEarnings;
};

typedef TICKET_ORDER *PTICKET_ORDER;

class ORDERS_STACK
{
public:
inline ORDERS_STACK():m_nTop(-1) {}

inline void Push(int i)
{
m_arr[++m_nTop] = i;
}

inline int Pop()
{
return m_arr[m_nTop--];
}

inline int GetTopVal()
{
return m_arr[m_nTop];
}

inline bool IsEmpty()
{
return (m_nTop < 0);
}

private:
int m_arr[MAX_ORDERS];
int m_nTop;
};

// Global function declarations
void GetOrders(PTICKET_ORDER pOrders, int &nMaxOrders, int nCapacity, int nB);
int ProcessOrders(PTICKET_ORDER pOrders, int nMaxOrders, int nCapacity);

// The main entry
int main()
{
int nCapacity, nCityB, nNumOrders;
TICKET_ORDER arrOrders[MAX_ORDERS];

while (1)
{
scanf("%d%d%d", &nCapacity, &nCityB, &nNumOrders);
if ((nCapacity == 0) && (nCityB == 0) && (nCityB == 0))
break;
if (nCityB > 7) nCityB = 7;
if (nNumOrders > 22) nNumOrders = 22;
GetOrders(arrOrders, nNumOrders, nCapacity, nCityB);
printf("%d\n", ProcessOrders(arrOrders, nNumOrders, nCapacity));
}

return 0;
}

void GetOrders(PTICKET_ORDER pOrders, int &nMaxOrders, int nCapacity, int nB)
{
int nFrom, nTo, nQuantity, i(0);
int nTmp = nMaxOrders;

while (nTmp--)
{
scanf("%d%d%d", &nFrom, &nTo, &nQuantity);
if (nFrom > nB) nFrom = nB;
if (nTo > nB) nTo = nB;
if ((nQuantity <= nCapacity) && (nFrom != nTo))
{
pOrders[i].Set(nFrom, nTo, nQuantity);
if (i)
for (int j = i - 1; j >= 0; --j)
if (pOrders[j] > pOrders[j + 1])
Swap<TICKET_ORDER>(pOrders[j], pOrders[j + 1]);
i++;
}
}

nMaxOrders = i;
}

int ProcessOrders(PTICKET_ORDER pOrders, int nMaxOrders, int nCapacity)
{
int nTotalEarnings(0), nCurOrder(0), nMaxEarnings(0);
int arrPeopleInside[MAX_STATION];
ORDERS_STACK stack;

if (nMaxOrders == 0)
return 0;
if (nMaxOrders == 1)
return pOrders[0].m_nEarnings;

for (int i = 0; i < MAX_STATION; ++i)
arrPeopleInside[i] = 0;

while (1)
{
while (nCurOrder == nMaxOrders)
{
if (stack.IsEmpty())
return nMaxEarnings;
nCurOrder = stack.Pop();
nTotalEarnings -= pOrders[nCurOrder].m_nEarnings;
for (int i = pOrders[nCurOrder].m_nFrom; i < pOrders[nCurOrder].m_nTo; ++i)
arrPeopleInside[i] -= pOrders[nCurOrder].m_nTickets;
nCurOrder++;
}

bool bCanDo = true;
for (int i = pOrders[nCurOrder].m_nFrom; i < pOrders[nCurOrder].m_nTo; ++i)
if (arrPeopleInside[i] + pOrders[nCurOrder].m_nTickets > nCapacity)
{
bCanDo = false;
break;
}

if (bCanDo)
{
nTotalEarnings += pOrders[nCurOrder].m_nEarnings;
for (int i = pOrders[nCurOrder].m_nFrom; i < pOrders[nCurOrder].m_nTo; ++i)
arrPeopleInside[i] += pOrders[nCurOrder].m_nTickets;
stack.Push(nCurOrder++);
if (nMaxEarnings < nTotalEarnings)
nMaxEarnings = nTotalEarnings;
}
else
nCurOrder++;
}

return nMaxEarnings;
}
/*"@END_OF_SOURCE_CODE*/[/cpp]

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 301 - Transportation

i don't know how to solve this problem.could somebody give me some idea?thank you very much!!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hi,

You can solve this problem by backtracking. Good luck~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China
thanx,i have solved this problem ,backtracking ,thank you!

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Hi, I'm trying to solve this problem, but got WA.
I want to know the information about the problem description.
Can anyone help me?

Code: Select all

``````10 4 8
0 1 1
0 2 2
0 3 3
1 2 3
1 3 4
1 4 5
2 4 6
3 4 7
0 0 0
``````
Can the train pass the station visited once?
For example, in above test case,
if the train can pass the station visited once, the biggest possible total earning is 40.
But, if the train can't pass the station visited once, the biggest possible total earning is 32.

And if you have any test case, show me for debugging.

Code: Select all

``````#include<stdio.h>
#include<stdlib.h>
#define MAX 7
#define NORAIL -1
#define ON  1
#define OFF 0
int capacity, dest, max;

void function(int now, int earn, char passed[MAX+1][MAX+1]) {
int i, j;
if(now==dest) {
if(earn > max) max = earn;
return;
}
for(i=0; i<=dest; i++) {
if(passed[now][i]==ON) continue;
passed[now][i] = passed[i][now] = ON;
passed[now][i] = passed[i][now] = OFF;
}
}

main() {
int ticket, a, b, np, i, j;
char passed[MAX+1][MAX+1];
while(scanf("%d %d %d\n", &capacity, &dest, &ticket)!=EOF && !(capacity==0 && dest==0 && ticket==0)) {
for(i=0; i<=dest; i++) {
for(j=0; j<=dest; j++) {
passed[i][j] = OFF;
}
}
for(i=0; i<ticket; i++) {
scanf("%d %d %d\n", &a, &b, &np);
if(np > capacity) np = capacity;
}
}
max = 0;
function(0, 0, passed);
printf("%d\n", max);
}
return 0;
}
``````
Thank you.

Yousef_Hanafi
New poster
Posts: 1
Joined: Sat Apr 18, 2015 6:42 am

### Re: 301 - Transportation

Hi, I'm trying to solve this problem, but got WA..
I tried hundreds of cases and all were correct ..
and this is my code
can anyone help or give me some tricky cases ?

Code: Select all

``````#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n , b ,o, Max = 0;
struct order
{
int s ,d,c;
};

vector<order> v;
bool valid (order s , int n)
{
int x = 0;
if ( s.d > b || s.s > b)
return false;
if ( v.empty())
if ( s.c <= n )
return true;
for(int i = 0; i<v.size(); i++)
{
if (v[i].d >s.s)
x+= v[i].c;
}
if ( x + s.c <= n)
return true;

return false;
}
int FindMaxVal(order * mat , int ord  , int sum ,int count)
{
for(int i = ord; i< o; i++)
{
if(valid(mat[i],n))
{
sum += mat[i].c * (mat[i].d - mat[i].s);
count += mat[i].c;
v.push_back(mat[i]);
FindMaxVal(mat,i+1,sum,count);
if ( sum > Max)
Max = sum;
sum -= mat[i].c * (mat[i].d - mat[i].s);
count -=mat[i].c;
if( !v.empty())
v.erase(v.begin()+v.size()-1);
}
}
return Max;
}

int main()
{
while ( cin >> n >> b >> o && n && b && o )
{
order * mat = new order[o];
for(int i = 0; i<o; i++)
{
cin >> mat[i].s >> mat[i].d >> mat[i].c;
}
int sum = 0 , count = 0 ;
Max = 0;
cout <<FindMaxVal(mat,0,sum,count)<<endl;
v.clear();
}
}``````
Last edited by brianfry713 on Fri Jun 19, 2015 6:28 am, edited 1 time in total.

anacharsis
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

### Re: 301 - Transportation

Some I/O

In:

Code: Select all

``````266 6 10
2 5 38
2 5 81
2 3 6
2 5 30
2 3 170
2 3 36
2 3 45
0 3 93
1 4 150
0 5 17
78 5 14
1 2 135
0 4 161
0 2 140
1 4 150
1 3 75
1 2 180
0 3 15
1 2 105
0 4 16
1 2 56
0 2 49
1 3 47
1 4 9
0 4 22
106 6 12
1 5 20
0 4 118
1 4 31
2 5 126
1 4 144
2 3 113
1 4 192
0 3 108
1 5 108
0 5 63
0 3 14
0 4 55
177 5 13
1 3 26
1 4 128
0 3 140
1 2 39
1 4 162
0 3 126
1 2 55
0 4 70
1 3 91
1 3 17
0 3 154
1 3 157
0 2 88
56 6 13
0 5 159
2 3 129
0 5 134
0 5 25
1 3 176
0 5 187
0 3 199
0 5 117
0 3 145
0 4 125
1 3 79
0 3 9
1 3 46
283 6 11
2 5 75
1 4 153
2 3 186
0 4 17
1 4 12
0 4 25
1 3 109
2 5 131
0 3 60
0 4 68
2 4 157
112 6 10
2 3 146
2 4 50
1 5 37
0 4 162
0 4 97
2 3 55
0 5 12
1 3 159
0 3 77
2 4 30
170 4 17
0 3 113
1 3 72
1 2 92
0 3 167
0 2 94
0 2 159
0 3 46
1 3 99
1 3 53
0 3 36
1 3 42
0 2 93
1 3 72
0 3 102
1 3 47
1 2 129
1 3 89
215 4 5
0 2 106
0 2 123
1 2 87
1 3 121
1 3 86
234 4 6
1 3 8
0 3 32
1 2 19
0 3 19
0 3 121
1 2 135
194 6 7
0 5 13
0 4 164
2 5 33
1 3 164
1 5 52
2 4 42
0 4 36
162 5 18
0 2 99
1 3 52
1 3 182
0 2 110
0 4 167
1 2 174
1 3 73
0 3 132
0 2 25
0 3 141
1 3 5
1 3 192
1 4 152
1 2 46
0 4 149
0 3 25
1 4 96
1 3 183
194 4 15
1 3 107
1 3 152
0 2 35
0 3 160
0 3 13
0 3 144
1 2 155
1 3 157
0 2 39
0 3 111
0 3 155
1 2 146
0 2 103
1 3 198
0 2 137
163 4 13
1 2 60
0 3 53
0 3 146
1 3 169
0 2 156
0 3 67
0 3 125
1 2 154
0 2 192
1 2 91
0 2 9
0 3 24
1 3 23
274 5 6
0 4 167
1 4 86
0 3 82
0 3 164
1 2 90
1 2 77
205 5 11
0 3 11
0 4 186
0 2 57
0 2 71
0 4 135
1 2 173
1 3 20
1 2 95
1 2 81
1 4 185
1 2 143
80 4 14
0 2 112
0 2 11
0 3 157
0 2 29
0 2 29
1 3 60
0 2 147
1 3 139
1 2 38
1 2 30
1 3 133
1 2 20
1 2 164
0 3 43
238 5 20
0 3 46
1 4 112
0 3 43
0 4 39
1 4 117
0 3 86
1 3 150
1 3 107
0 2 32
0 4 180
1 4 168
0 4 164
1 2 198
1 2 191
0 4 175
1 2 28
1 3 130
0 3 133
1 2 180
0 4 32
299 4 21
1 3 157
0 2 103
1 2 144
1 2 176
1 2 150
0 2 73
0 2 133
1 3 52
0 2 166
1 2 87
0 2 171
0 3 78
0 2 145
1 2 159
1 3 187
0 3 29
1 2 43
0 2 182
0 3 22
1 3 54
1 3 41
103 4 11
1 2 66
0 3 173
0 2 119
1 3 63
0 3 50
0 2 119
0 2 185
1 2 183
1 3 152
0 2 68
1 3 85
0 0 0
``````
AC out:

Code: Select all

``````820
224
437
496
152
935
448
501
418
551
721
606
543
465
926
777
187
940
723
170
``````
If that's not enough, here's an I/O generator to play with:

Code: Select all

``````import java.util.Random;

public class InGen {

public static void main( String[] args ) {
Random randy = new Random( System.currentTimeMillis() );

for ( int i = 0; i < 20; ++i ) {
int n = randomInRange( 50, 300, randy );
int maxS = randomInRange( 4, 7, randy );
int orders = randomInRange( 5, 22, randy );
System.out.println( String.format( "%d %d %d", n, maxS, orders ) );
int midS = maxS / 2;

for ( int j = 0; j < orders; ++j ) {
int start = randomInRange( 0, midS, randy );
int end = randomInRange( midS, maxS, randy );

if ( start == end ) {
--j;
continue;
}

int pass = randomInRange( 5, 200, randy );
System.out.println( String.format( "%d %d %d", start, end, pass ) );
}
}

System.out.println( "0 0 0" );
}

private static int randomInRange( int start, int end, Random randy ) {
return randy.nextInt( end - start ) + start;
}

}

``````