Page 1 of 1

How to solve 301 in time 0.00

Posted: Sun Nov 03, 2002 6:36 pm
by Jucovschi Constantin
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 ?

Posted: Fri Jun 20, 2003 2:16 pm
by Cloud Song
hi, if you use a simple pruning in the B&B, you can get 0.00

Posted: Fri Jul 04, 2003 4:02 pm
by hank
hi,excuse me
What is B&B?

problem 301

Posted: Wed Oct 08, 2003 4:43 pm
by srdjan
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.

Posted: Fri Nov 14, 2003 12:04 am
by UFP2161
Branch & Bound

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

Posted: Sun Dec 14, 2003 11:41 pm
by Sanya
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]

301

Posted: Thu Jul 29, 2004 11:05 pm
by Opexoc
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!

Posted: Wed Sep 15, 2004 2:05 am
by Kire Sopov
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]

301 - Transportation

Posted: Mon Feb 21, 2005 10:06 am
by oulongbin
i don't know how to solve this problem.could somebody give me some idea?thank you very much!! :D

Posted: Mon Feb 21, 2005 2:00 pm
by Observer
Hi,

You can solve this problem by backtracking. Good luck~ :wink:

Posted: Fri Feb 25, 2005 7:36 am
by oulongbin
thanx,i have solved this problem ,backtracking ,thank you! :D

Posted: Sat Oct 07, 2006 11:23 am
by tan_Yui
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.

Re: 301 - Transportation

Posted: Sat Apr 18, 2015 7:00 am
by Yousef_Hanafi
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();
	}
}

Re: 301 - Transportation

Posted: Fri Jul 10, 2015 8:31 pm
by anacharsis
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;
	}

}