10599 - Robots(II)

kmhasan · Post by **kmhasan** » Tue Jan 13, 2004 12:23 pm

Right. I admit that I should have stated the output limits. Sorry about that.

I modeled this problem to a LIS problem. You see, if you are in (r1,c1) and you can go to (r2,c2) then r2>=r1 AND c2>=c1. So if you pick up coords of the garbages then you can find the Longest Increasing Sequences to know the maximum number of garbages that you can collect. And to find the number of possible ways, you just need to count all possible LISs. That makes the problem a lot easier than it might look.

I hope this would help.

Dohan Kim · Post by **Dohan Kim** » Mon Jul 10, 2006 3:41 pm

I tried to solve this problem like this.. (Dynamic Programming)
And Sample Input is correct in my program.

But i got WA always.

What can I do to get AC?

Sorry for my English skill.

Code: Select all

#include <iostream>

#define SIZE 100

#define MAX(x, y) ((x > y)? (x): (y))

using namespace std;

void print(int x, int y, int via[SIZE+1][SIZE+1], int column, bool field[SIZE+1][SIZE+1])
{
	if (via[x][y] == -1) return;

	if (via[x][y] == 1) print(x-1, y, via, column, field);
	else print(x, y-1, via, column, field);

	if (field[x][y] == true) cout << (x-1) * column + (y-1) + 1 << ' ';
}

int main()
{
	int Case;

	for (Case = 1; ; Case++)
	{
		int row, column;
		bool field[SIZE+1][SIZE+1];
		int e[SIZE+1][SIZE+1];

		cin >> row >> column;

		if (row == -1 && column == -1) break;

		int i, j, k, l;

		for (i = 1; i <= row; i++)
		{
			for (j = 1; j <= column; j++) 
			{
				field[i][j] = false;
				e[i][j] = 0;
			}
		}

		bool fir = true;
		while(1)
		{
			int x, y;
			cin >> x >> y;

			if (x == 0 && y == 0) break;

			field[x][y] = true;

			if (fir == true)
			{
				e[x][y] = 1;
				fir = false;
			}
		}

		int d[SIZE+1][SIZE+1];
		int via[SIZE+1][SIZE+1];

		d[0][1] = d[1][0] = 0;
		via[0][1] = via[1][0] = -1;

		for (i = 1; i <= row; i++)
		{
			for (j = 1; j <= column; j++)
			{
				d[i][j] = MAX(d[i-1][j], d[i][j-1]) + (int)(field[i][j]);
				via[i][j] = ((MAX(d[i-1][j], d[i][j-1]) == d[i-1][j])? 1: 2);
			}
		}

		for (i = 1; i <= row; i++)
		{
			for (j = 1; j <= column; j++)
			{
				if (field[i][j] == true || (i == row && j == column))
				{
					for (k = 1; k <= i; k++)
					{
						for (l = 1; l <= j; l++)
						{
							if (field[k][l] == true)
							{
								if (field[i][j] == false && i == row && j == column && field[k][l] == true && d[k][l+1] == d[i][j]) e[i][j] += e[k][l];
								else if (d[k][l]+1 == d[i][j] && field[k][l] == true) e[i][j] += e[k][l];
							}
						}
					}
				}
			}
		}
		
		cout << "Case#" << Case << ": ";
		cout << d[row][column] << ' ' << e[row][column] << ' ';
		print(row, column, via, column, field);
		cout << endl;
	}

	return 0;
}

Solmon K. · Post by **Solmon K.** » Mon Jul 10, 2006 4:08 pm

Don't process finish point and garbage point together..

finish point processing must be in another loop

and, I think your location is too long

Dohan Kim · Post by **Dohan Kim** » Mon Jul 10, 2006 4:14 pm

Thx. Solomon K.

But you don't say to me why "finish point processing must be in another loop ".

I can't understand why because i'm a little foolish.

Please say to me why.

Solmon K. · Post by **Solmon K.** » Mon Jul 10, 2006 4:20 pm

hmm.

finish point and garbage point has little different condition.

I can't really understand your code,

so I can't assure my thinking is true..

pdwd · Post by **pdwd** » Wed Aug 25, 2010 2:36 am

Is it possible to solve this problem faster than O(n^2*m^2) ?

DJWS · Post by **DJWS** » Fri Nov 26, 2010 3:22 pm

Sure. It can be solved with O(n * n * m).

zslwyuan · Post by **zslwyuan** » Thu Jan 27, 2011 4:45 am

Can anyone find a case for me?
I have tried many case,and haven't found it get wrong.
But I WA?
why?
My Code:

Code: Select all

#include<cstdio>
#include<cstring>
using namespace std;
int map[102][102],dp[102][102],prh[10001],n,m,hmn;
long long tp[10001][3],tpf[10001],check[10001],dhm[102],dsm[102],ans;
void prhelp(int now,int x,int y)
{    
    if (!x||!y)return;
    if (map[x][y]){prh[now]=(x-1)*m+y;now--;}if (!now)return ;
    if (dp[x-1][y]>dp[x][y-1]){prhelp(now,x-1,y);}
    else prhelp(now,x,y-1);
}
long long search(int x)
{
     if (check[x]!=-1)return check[x];
     if (tp[x][2]==dp[n][m]){return check[x]=1;}
     int i;long long ans=0;
     for (i=x+1;i<=hmn;i++)
     if (tp[i][0]>=tp[x][0]&&tp[i][1]>=tp[x][1]&&tp[i][2]==tp[x][2]+1&&tp[i][2]+tpf[i]-1==dp[n][m])ans+=search(i);
     return check[x]=ans;
}

int main()
{
/*    freopen("1.txt","r",stdin);
    freopen("2.txt","w",stdout);*/
    int i,j,k,l,t=0;   
    while(scanf("%d %d\n",&n,&m)==2)
    { 
        ans=0;
        if (n==-1&&m==-1)break;
        memset(map,0,sizeof(map));memset(dp,0,sizeof(map));
        while (scanf("%d %d\n",&k,&l)&&k&&l)map[k][l]=1;
        for (i=1;i<=n;i++){dp[i][1]=map[i][1]+dp[i-1][1];}
        for (i=1;i<=m;i++){dp[1][i]=map[1][i]+dp[1][i-1];}
        for (i=2;i<=n;i++)
            for (j=2;j<=m;j++)
                if (dp[i-1][j]>dp[i][j-1])   dp[i][j]=dp[i-1][j]+map[i][j];
                else   dp[i][j]=dp[i][j-1]+map[i][j];
        hmn=0;
        memset(tp,0,sizeof(tp));
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++)
                if (map[i][j]){hmn++;tp[hmn][0]=i;tp[hmn][1]=j;}
        memset(dsm,0,sizeof(dsm));memset(dhm,0,sizeof(dsm));
        memset(tpf,0,sizeof(tpf));
        long long max=-1;
        for (i=1;i<=hmn;i++)
        {
            for (j=0;j<=i-1&&(tp[i][2]<=max||max==-1);j++)
                if (tp[j][2]+1>tp[i][2]&&tp[j][0]<=tp[i][0]&&tp[j][1]<=tp[i][1])
                   tp[i][2]=tp[j][2]+1;
            if (tp[i][2]>max)max=tp[i][2];
        }
        memset(dsm,0,sizeof(dsm));memset(dhm,0,sizeof(dsm));
        tp[hmn+1][0]=100000;tp[hmn+1][1]=100000;tp[hmn+1][2]=0;
        max=-1;
        for (i=hmn;i>=1;i--)
        {
            for (j=i+1;j<=hmn+1&&(tpf[i]<=max||max==-1);j++)
                if (tpf[j]+1>tpf[i]&&tp[j][0]>=tp[i][0]&&tp[j][1]>=tp[i][1])
                   tpf[i]=tpf[j]+1;
             if (tpf[i]>max)max=tpf[i];
        }
        memset(check,-1,sizeof(check));
        t++;
        for (i=1;i<=hmn;i++)
        if (tp[i][2]==1&&tp[i][2]+tpf[i]-1==dp[n][m])
        ans+=search(i);
        prhelp(dp[n][m],n,m);
        printf("CASE#%d: %d",t,dp[n][m]);
        printf(" %lld ",ans);
        for (i=1;i<=dp[n][m];i++)printf("%d%c",prh[i],i==dp[n][m]?'\n':' ');        
    }
    return 0;
}

Jing1228 · Post by **Jing1228** » Wed Jul 06, 2011 7:55 pm

Can anybody tell why sample input one should output 4 as number of ways???
Shouldn't that be 11 ????

why is the following not one of the answer

0 1 2 3 4 5 6 7
1 O O O O - - -
2 - - - O O O O
3 - - - - - - - O
4 - - - - - - - O
5 - - - - - - - O
6 - - - - - - - O

where garbages are located at (1,2) (1,4) (2,4) (2,6) (4,4) (4,7) (6,6 ) respectively , just as the sample figure show.

why...?? isn't that also a valid way to go? and also collect 5 garbages??

Do I misunderstand this problem ?

thx for the reply... Orz

lighted · Post by **lighted** » Sat Jun 28, 2014 11:07 am

I used DP to find maximal number of garbage that we can collect.
To find in how many ways we can collect garbages i used BFS in directed graph.
Here nodes are garbages and direction of edges is directed to Southeast.
If there is an edge from ith garbage to jth i add number of ways i can collect garbages until ith node to jth result.

Code: Select all

removed, after acc..

lighted · Post by **lighted** » Tue Jul 08, 2014 2:28 pm

Please somebody tell me if my algorithm is correct.
I can't understand where is my bug.
Is it wrong algo or wrong implementation

brianfry713 · Post by **brianfry713** » Tue Jul 08, 2014 10:42 pm

Input:

Code: Select all

AC output:

Code: Select all

CASE#1: 73 3006720 1 2 60 117 174 231 288 289 290 291 348 349 351 352 353 354 355 356 358 359 416 417 418 532 533 590 591 648 649 707 764 821 822 823 825 882 884 941 942 999 1056 1057 1058 1115 1172 1173 1174 1231 1288 1289 1346 1403 1404 1405 1407 1409 1410 1411 1412 1414 1415 1416 1417 1418 1419 1420 1421 1423 1424 1481 1538 1539 1596
CASE#2: 40 1020 3 4 127 168 169 171 173 174 175 216 217 218 219 220 221 222 223 224 225 266 267 308 309 350 351 352 355 357 359 361 362 363 364 365 366 367 368 409 450 451
CASE#3: 78 4304832 2 3 5 6 7 9 10 68 126 128 129 130 131 189 190 191 249 251 252 254 255 257 258 259 318 319 377 435 436 437 495 553 611 612 613 614 672 673 674 732 733 734 735 736 737 795 853 854 912 970 1028 1086 1087 1145 1146 1147 1148 1149 1150 1151 1152 1210 1211 1212 1270 1328 1387 1388 1504 1562 1620 1621 1795 1796 1854 1912 2028 2029
CASE#4: 68 72 16 46 76 91 106 121 136 166 181 211 226 241 256 271 287 302 332 347 377 392 393 423 453 468 483 528 543 558 573 574 589 634 649 664 694 709 724 739 740 741 756 786 801 802 817 818 833 834 849 850 865 880 910 925 940 955 970 971 972 973 988 1003 1018 1048 1093 1108 1123 1155
CASE#5: 125 209018880 98 99 196 293 294 295 296 298 299 300 494 495 592 593 595 692 789 790 791 792 793 891 892 893 894 895 1089 1186 1187 1284 1381 1478 1479 1480 1481 1482 1483 1581 1582 1583 1584 1681 1682 1779 1781 1782 1784 1785 1786 1884 1885 1982 1984 1985 2082 2083 2085 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2098 2195 2292 2293 2390 2391 2393 2490 2491 2588 2685 2687 2688 2689 2690 2691 2788 2789 2790 2984 2985 2986 3083 3277 3278 3375 3472 3569 3666 3667 3668 3765 3766 3767 3768 3769 3770 3867 3964 4061 4062 4063 4064 4065 4162 4259 4260 4261 4262 4263 4264 4265 4266 4363 4460 4655 4752 4946
CASE#6: 22 10 1 3 14 25 36 47 59 60 71 82 93 104 105 116 127 128 130 131 132 143 154 165
CASE#7: 73 15697800 2 53 103 104 105 106 107 109 111 161 162 163 164 214 314 364 414 415 416 417 418 420 421 422 472 473 523 524 525 526 527 528 578 579 629 630 680 730 731 732 782 882 932 982 983 1033 1083 1133 1184 1185 1235 1236 1237 1287 1289 1290 1291 1341 1391 1392 1443 1493 1543 1544 1594 1644 1645 1695 1696 1746 1796 1798 1799
CASE#8: 86 35264 1 28 55 82 109 163 164 191 192 193 220 248 249 276 303 304 305 332 333 360 361 388 415 442 469 496 523 577 604 605 606 634 661 662 663 690 744 745 772 799 800 827 855 882 883 910 937 964 965 966 967 994 1021 1102 1129 1156 1157 1184 1211 1238 1265 1292 1293 1294 1321 1348 1349 1376 1403 1404 1431 1458 1485 1539 1593 1620 1674 1728 1782 1809 1863 1944 1971 2025 2052 2079
CASE#9: 69 33000 2 35 68 101 102 104 137 203 204 237 303 369 402 435 468 501 534 568 601 634 667 700 733 766 767 768 801 834 867 934 935 936 937 938 971 1004 1037 1038 1039 1072 1073 1074 1075 1076 1077 1110 1111 1112 1146 1179 1212 1213 1215 1248 1281 1282 1283 1316 1317 1350 1416 1417 1483 1516 1517 1518 1551 1584 1617
CASE#10: 61 3087 25 37 49 50 62 63 75 76 100 112 136 149 150 162 174 186 187 211 223 247 259 271 283 307 319 343 355 367 368 404 416 440 452 464 465 477 489 501 525 537 549 573 585 597 609 621 645 657 669 681 693 717 729 730 742 766 779 803 827 828 840

lighted · Post by **lighted** » Fri Jul 11, 2014 10:59 am

Thanks brianfry713!

I found my bug.

If there is an edge from (j, i) garbage to (x, y) garbage
we must add number of ways of (j, i) to (x, y) if only if f(j, i) + 1 == f(y, x).
Here f(j, i) is maximal number of garbages we can collect from (0, 0) to (j, i).

It became very different implementation of BFS.

OJ Board

10599 - Robots(II)

10599 WA

....

...

Re: 10599 - Robots (II)

Re: 10599 - Robots (II)

Can anyone find a case for me?

Re: 10599 - Robots (II)

10599. WA

Re: 10599 - Robots (II)

Re: 10599 - Robots (II)

Re: 10599 - Robots (II)