301 - Transportation

All about problems in Volume 3. 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
Jucovschi Constantin
New poster
Posts: 9
Joined: Sat Oct 26, 2002 6:30 pm

How to solve 301 in time 0.00

Post by Jucovschi Constantin » Sun Nov 03, 2002 6:36 pm

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

Post by Cloud Song » Fri Jun 20, 2003 2:16 pm

hi, if you use a simple pruning in the B&B, you can get 0.00

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Fri Jul 04, 2003 4:02 pm

hi,excuse me
What is B&B?

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

problem 301

Post by srdjan » Wed Oct 08, 2003 4:43 pm

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.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Nov 14, 2003 12:04 am

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

Post by Sanya » Sun Dec 14, 2003 11:41 pm

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
read(n,m,k);
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

Post by Opexoc » Thu Jul 29, 2004 11:05 pm

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!
Any answer will be appreciated!

Kire Sopov
New poster
Posts: 7
Joined: Wed Sep 15, 2004 2:01 am

Post by Kire Sopov » Wed Sep 15, 2004 2:05 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

Post by oulongbin » Mon Feb 21, 2005 10:06 am

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

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

Post by Observer » Mon Feb 21, 2005 2:00 pm

Hi,

You can solve this problem by backtracking. Good luck~ :wink:
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

Post by oulongbin » Fri Feb 25, 2005 7:36 am

thanx,i have solved this problem ,backtracking ,thank you! :D

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Sat Oct 07, 2006 11:23 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 adj[MAX+1][MAX+1];
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(adj[now][i]==NORAIL) continue;
    if(passed[now][i]==ON) continue;
    passed[now][i] = passed[i][now] = ON;
    function(i, earn+abs((now-i)*adj[now][i]), passed);
    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++) {
        adj[i][j] = NORAIL;
        passed[i][j] = OFF;
      }
    }
    for(i=0; i<ticket; i++) {
      scanf("%d %d %d\n", &a, &b, &np);
      if(np > capacity) np = capacity;
      if(adj[a][b] < np) {
        adj[a][b] = adj[b][a] = np;
      }
    }
    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

Post by Yousef_Hanafi » Sat Apr 18, 2015 7:00 am

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 ?
thanks in advance

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.
Reason: Added code blocks

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

Re: 301 - Transportation

Post by anacharsis » Fri Jul 10, 2015 8:31 pm

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;
	}

}


Post Reply

Return to “Volume 3 (300-399)”