711 - Dividing up

serur · Post by **serur** » Wed Apr 26, 2006 4:19 pm

Well, I think this piece of code is correct (in fact, it cannot be otherwise than correct, for I copied your code somewhere here

)

Code: Select all

while(n[1]>2)
	{
		n[1]-=2;
		n[2]++;
	}
	while(n[2]>2)
	{
		n[2]-=2;
		n[4]++;
	}
	while(n[3]>2)
	{
		n[3]-=2;
		n[6]++;
	}

In my previous postings I meant this. The last loop is indeed (n3=3, n6=0) -> (n3=1, n6=1), is it not?

About reduction of n[6] - to be able to make restitutions to Marsha and Bill (if any is needed)
we must have roughly (and that's enough) 5*n[5]+4*n[4]+...+n[1] points in addition, or am I talking nonsense(:))?

stcheung · Post by **stcheung** » Sun Aug 10, 2008 3:03 am

Some of the previous posts only made things more confusing, so let me try to summarize all the hints so far:
(1) You are likely to get TLE with a straightforward Dynamic Programming solution. You need to reduce the number of balls intelligently.
(2) The strategy for reducing 1,2,3 balls is very simple. Basically reduce {1,1} to {2} whenever you have at least three 1-balls. Similarly for the 2-balls and 3-balls.
(3) The strategy for reducing 4,5 balls are pretty much the same. You want to reduce both 4-balls and 5-balls to 6-balls. When you reduce 4-balls, you need to make sure the number of 4-balls you reduce and the number of 6-balls you reducing to are both even. For instance, reducing {4,4,4} to {6,6} would be wrong. You also need to figure out at least how many 4-balls you will need before you can reduce them.
(4) Finally, you also need to reduce the number of 6-balls. You know if both sides have at least one 6-ball, then you could have safely removed both 6-balls at the beginning. So the only time you can't reduce 6-balls is when all the 6-balls are used to "balance" the sum of the rest of the balls. So you need to figure out the C in the equation 6*C >= 5*n[5] + 4*n[4] + 3*n[3] + 2*n[2] + n[1]

chiu1234 · Post by **chiu1234** » Sun Aug 24, 2008 8:40 am

Code: Select all

#include <stdio.h>
       
int main(){
  int input[7], small[7], big[7], count = 0, sum = 0, small_sum = 0, big_sum = 0,transfer;
  bool flag, divided, transfered;  
   
  while(true){
    count++;
    sum = 0, small_sum = 0, big_sum = 0;
    flag = true;
    for (int i = 1; i<=6; i++){
      scanf("%d", &input[i]);
      if (input[i]) flag = false;
      sum += input[i] * i;  
      small[i] = 0;
      big[i] = 0;
    }
    if(flag) break;
    
    if (sum % 2 == 1){
      printf("Collection #%d:\n", count);
      printf("Can't be divided.\n\n");
      continue;
    }      
    
    for (int j = 1; j<=6; j++){
      small[j] = big[j] = input[j]/2;
      small_sum += small[j] * j;
      big_sum += big[j] * j;
      if((input[j] % 2) == 1){
        small[j]++;
        small_sum += j;
      }      
    }
    
    divided = true;
    while(small_sum > big_sum){
      transfer = (small_sum - big_sum)/2;
      if (transfer > 6) transfer = 6; 
      transfered = false;
      for (int i = transfer; i >= 1; i--){
        if (transfered) break; 
        for (int j = 6; j >= i; j--){
          if (small[j] > 0){
            if ((j - i) == 0){
              small[j]--;
              small_sum -= j;
              big[j]++;
              big_sum += j;
              transfered = true;
              break;
            }
            else if(big[j - i] > 0){
              small[j]--;
              small[j - i]++;
              small_sum -= i;
              big[j]++;
              big[j - i]--;
              big_sum += i;
              transfered = true;
              break;              
            }
          } 
        } 
      }
      if (!transfered){
        divided = false;
        break;
      }
    }            
     
    printf("Collection #%d:\n", count);
    if(divided){
      printf("Can be divided.\n\n");
    }
    else{
      printf("Can't be divided.\n\n");
    }    
  }
}

I dont know why got a WA, I tested so many testcase but can't find an error, my method is first divided the marble into 2 part, e.g. {11 11 10 10 11 11} will divided to small:{6 6 5 5 6 6}
and big{ 5 5 5 5 5 5}. Then exchange marbles between 'small' and 'big' until 2 part got equal sum(sum of small part always >= sum of big part) or can't exchange.
I think this method is logically ok but don't why always got WA, can anyone who got find some test case to show my program is wrong pls? I dont know what wrong, I try this question about 2 days but still can't figure it out

lnr · Post by **lnr** » Sun Dec 07, 2008 10:06 am

To little joey

The problem asks wether it is possible to divide the balls in two sets

with equal amounts of points. We can characterise every possible

collection of balls according to this divisibility by saying it is

'divisible' or 'non-divisible'. Now in reducing the number of balls in a

particular set by replacing some low valued balls by a smaller number of

higher valued balls, we have to make sure that the 'divisibility' of the

set doesn't change.

When replacing 3 1-balls by 1 1-ball and 1 2-ball: (n1=3, n2=0) -> (n1=1,

n2=1), the divisiblity of the set doesn't change (the divisibility of

both sub-sets is 'non-divisible').

On the other hand, if we have a subset of 5 4-balls, the divisibility is

clearly 'non-divisible', the divisibility of a subset of 2 4-balls and 2

6-balls, however, is 'divisible', so the reduction (n4=5, n6=0) -> (n4=2,

n6=2) is invalid.

About your last question:
The reduction (n3=2, n6=0) -> (n3=0, n6=1) is invalid, but the reduction

(n3=3, n6=0) -> (n3=1, n6=1) is valid.

Hope it helps.

And

No, that is not correct.
The case of 10 4-balls: the only thing you can be sure of, is that one

hand contains at least 5 4-balls, but you don't know how the remaining 5

balls are divided between the hands. You could replace 5 4-balls by 4 5-

balls: (n4=10, n5=0) -> (n4=5, n5=4), but then you would violate the

divisibility constraint.

The case of the 10 5-balls is also incorrect.

About the last reduction in the previous posting:

the reduction (n3=2, n6=0) -> (n3=0, n6=1) is invalid for two reasons:
1. it violates the divisibility constraint, as stated above;
2. you can't be shure both 3-balls are in the same hand (either Marsha's

or Bill's).

the reduction (n3=3, n6=0) -> (n3=1, n6=1) however is valid for two

reasons:
1. both states are 'non-divisible';
2. because there are 3 balls, you can be sure one hand has at least 2

balls.

(I took what you called 'Dirichlet's Principle' for granted in my

previous posting).

Still confused about divisibility and the term 3 1-balls by 1 1-ball and 1 2-ball or 10 4-balls you mentioned.
And "by replacing some low valued balls by a smaller number of higher valued balls".

Would you please explain with the sample input data in detail?
pls...

AKJ88 · Post by **AKJ88** » Tue Mar 12, 2013 9:20 am

Can anyone tell me what is wrong with my code please?
Thanks in advance.

Code: Select all

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;

const int marbValues[] = {1, 2, 3, 4, 5, 6, 10, 100, 200, 1000};
const int MC = 10;

void changeMarbleCount(int marblesCount[]){
	marblesCount[1] += 2*(marblesCount[0]/4); //constructing 2 based on 1
	marblesCount[0] %= 4;

	marblesCount[3] += 2*(marblesCount[1]/4); //constructing 4 based on 2
	marblesCount[1] %= 4;

	marblesCount[5] += 2*(marblesCount[2]/4); //constructing 6 based on 3
	marblesCount[2] %= 4;

	marblesCount[5] += 10*(marblesCount[4]/12); //constructing 6 based on 5
	marblesCount[4] %= 12;

	marblesCount[5] += 4*(marblesCount[3]/6); //constructing 6 based on 4
	marblesCount[3] %= 6;

	marblesCount[6] = 12*(marblesCount[5]/20); //constructing 10 based on 6
	marblesCount[5] %= 20;

	marblesCount[7] = 2*(marblesCount[6]/20); //constructing 100 based on 10
	marblesCount[6] %= 20;

	marblesCount[8] = 2*(marblesCount[7]/4); //constructing 200 based on 100
	marblesCount[7] %= 4;

	marblesCount[9] = 2*(marblesCount[8]/10); //constructing 1000 based on 200
	marblesCount[8] %= 10;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("C:\\acm_inp\\divup.in", "r", stdin);
#endif
	int marblesCount[MC], I, J, K, sum, nextVal, caseNum=1;
	int gotValue[420000];

	while(true){
		sum = 0;
		for(I=0; I<6; I++){
			scanf("%d", &marblesCount[I]);
			sum += marblesCount[I];
		}
		if(sum == 0)
			break;

		changeMarbleCount(marblesCount);
		sum = 0;
		for(I=0; I<MC; I++)
			sum += marbValues[I]*marblesCount[I];
		sum /=2 ;
		memset(gotValue, 0, sizeof(gotValue));
		for(I=0; I<MC; I++){
			J = marblesCount[I];
			while(J>0){
				for(K = sum; K>=1; K--)
					if(K >= marbValues[I])
						gotValue[K] = max(gotValue[K], marbValues[I]+gotValue[K-marbValues[I]]);
				J --;
			}
		}

		if(gotValue[sum] == sum)
			printf("Collection #%d:\nCan be divided.\n\n", caseNum++);
		else
			printf("Collection #%d:\nCan't be divided.\n\n", caseNum++);
	}


	return 0;
}

brianfry713 · Post by **brianfry713** » Tue Mar 12, 2013 10:47 pm

Input:

Code: Select all

710 745 731 702 701 736
929 953 943 1000 987 921
280 258 285 266 272 255
911 902 884 972 899 900
1180 1223 1215 1243 1199 1128
438 510 465 437 451 471
2825 2926 2840 2788 2923 2897
1039 1058 1111 1046 1013 1024
430 410 399 396 350 394
2305 2282 2323 2418 2361 2366
1300 1247 1288 1277 1208 1294
1845 1858 1891 1948 1876 1795
2829 2941 2871 2832 2837 2782
2822 2802 2803 2766 2744 2645
2453 2347 2383 2486 2331 2416
2386 2437 2338 2375 2371 2467
1176 1118 1097 1121 1071 1191
781 788 754 723 760 680
3113 3118 3114 3140 3229 3149
727 719 736 770 727 776
225 234 241 187 217 171
3120 3049 3077 3066 3072 3094
3225 2954 3072 3054 3049 3169
268 272 254 280 273 238
1786 1741 1767 1764 1803 1839
82 55 70 73 64 87
758 750 786 780 769 785
2121 2162 2180 2138 2221 2259
1451 1391 1426 1437 1471 1450
1440 1383 1377 1450 1479 1501
1071 1029 1069 1009 975 990
488 513 512 484 517 534
2890 2881 2928 2938 2984 2950
771 730 702 768 760 721
1817 1821 1887 1919 1922 1815
254 244 254 246 243 260
1103 1113 1063 1075 1045 1049
3055 3056 2967 3025 2995 2986
2949 3019 2990 2891 2894 2961
2774 2798 2816 2741 2718 2697
2809 2796 2638 2656 2752 2870
3023 3147 3109 3127 3178 3066
2309 2332 2333 2372 2261 2224
2165 2143 2058 2200 2188 2209
598 555 583 590 584 627
2346 2267 2348 2377 2342 2208
206 201 206 186 203 202
1516 1504 1484 1488 1490 1495
2918 2830 2811 2928 2901 2824
486 536 486 503 542 513
743 771 683 711 753 729
1400 1434 1461 1356 1374 1333
1697 1792 1747 1783 1687 1697
2435 2500 2465 2434 2551 2417
2100 2171 2167 2103 2131 2109
335 353 316 349 347 318
2724 2898 2850 2791 2840 2812
295 286 241 304 265 272
1320 1318 1297 1381 1314 1284
3310 3149 3321 3329 3193 3174
2766 2714 2767 2735 2768 2695
2344 2311 2350 2361 2359 2363
1282 1286 1186 1301 1231 1270
928 995 917 936 962 929
2291 2277 2326 2266 2189 2325
3301 3182 3161 3294 3310 3399
958 935 949 953 934 911
1719 1749 1677 1706 1693 1792
1836 1841 1786 1795 1844 1779
1778 1859 1768 1852 1758 1784
2659 2590 2610 2625 2681 2636
2342 2427 2334 2517 2354 2425
1063 1143 1031 1066 1065 1021
639 676 646 693 674 672
3345 3286 3336 3277 3221 3331
2046 2163 2104 2112 2047 2230
1629 1606 1599 1572 1627 1646
1680 1728 1677 1690 1741 1740
2369 2485 2493 2507 2448 2450
1090 1159 1017 1049 1082 1111
397 332 360 358 364 384
3113 3210 3179 3079 3161 3138
234 257 258 253 260 235
3264 3299 3225 3258 3339 3156
2712 2656 2647 2718 2716 2679
295 309 276 298 270 269
1808 1888 1818 1821 1868 1856
2143 2311 2138 2059 2071 2135
784 785 851 763 835 782
2764 2784 2780 2752 2738 2746
112 115 116 110 108 121
1176 1196 1216 1215 1152 1233
2862 2856 2927 2850 2724 2825
1489 1397 1436 1473 1398 1380
339 345 376 330 361 370
997 988 991 969 1013 1052
1467 1372 1415 1439 1434 1345
335 303 317 309 324 324
492 510 491 493 498 509
2836 2824 2888 2971 2862 2821
0 0 0 0 0 0

Correct output:

Code: Select all

Collection #1:
Can be divided.

Collection #2:
Can't be divided.

Collection #3:
Can't be divided.

Collection #4:
Can be divided.

Collection #5:
Can be divided.

Collection #6:
Can be divided.

Collection #7:
Can be divided.

Collection #8:
Can't be divided.

Collection #9:
Can't be divided.

Collection #10:
Can't be divided.

Collection #11:
Can be divided.

Collection #12:
Can be divided.

Collection #13:
Can't be divided.

Collection #14:
Can't be divided.

Collection #15:
Can't be divided.

Collection #16:
Can't be divided.

Collection #17:
Can be divided.

Collection #18:
Can't be divided.

Collection #19:
Can be divided.

Collection #20:
Can be divided.

Collection #21:
Can't be divided.

Collection #22:
Can't be divided.

Collection #23:
Can be divided.

Collection #24:
Can't be divided.

Collection #25:
Can be divided.

Collection #26:
Can be divided.

Collection #27:
Can't be divided.

Collection #28:
Can be divided.

Collection #29:
Can be divided.

Collection #30:
Can be divided.

Collection #31:
Can't be divided.

Collection #32:
Can't be divided.

Collection #33:
Can be divided.

Collection #34:
Can't be divided.

Collection #35:
Can be divided.

Collection #36:
Can't be divided.

Collection #37:
Can't be divided.

Collection #38:
Can't be divided.

Collection #39:
Can't be divided.

Collection #40:
Can be divided.

Collection #41:
Can't be divided.

Collection #42:
Can be divided.

Collection #43:
Can't be divided.

Collection #44:
Can't be divided.

Collection #45:
Can't be divided.

Collection #46:
Can be divided.

Collection #47:
Can't be divided.

Collection #48:
Can be divided.

Collection #49:
Can be divided.

Collection #50:
Can be divided.

Collection #51:
Can't be divided.

Collection #52:
Can't be divided.

Collection #53:
Can't be divided.

Collection #54:
Can't be divided.

Collection #55:
Can be divided.

Collection #56:
Can be divided.

Collection #57:
Can be divided.

Collection #58:
Can't be divided.

Collection #59:
Can't be divided.

Collection #60:
Can be divided.

Collection #61:
Can't be divided.

Collection #62:
Can't be divided.

Collection #63:
Can't be divided.

Collection #64:
Can't be divided.

Collection #65:
Can be divided.

Collection #66:
Can be divided.

Collection #67:
Can't be divided.

Collection #68:
Can't be divided.

Collection #69:
Can be divided.

Collection #70:
Can be divided.

Collection #71:
Can be divided.

Collection #72:
Can be divided.

Collection #73:
Can't be divided.

Collection #74:
Can't be divided.

Collection #75:
Can be divided.

Collection #76:
Can't be divided.

Collection #77:
Can't be divided.

Collection #78:
Can be divided.

Collection #79:
Can be divided.

Collection #80:
Can't be divided.

Collection #81:
Can't be divided.

Collection #82:
Can't be divided.

Collection #83:
Can be divided.

Collection #84:
Can be divided.

Collection #85:
Can't be divided.

Collection #86:
Can't be divided.

Collection #87:
Can be divided.

Collection #88:
Can be divided.

Collection #89:
Can be divided.

Collection #90:
Can be divided.

Collection #91:
Can be divided.

Collection #92:
Can be divided.

Collection #93:
Can't be divided.

Collection #94:
Can't be divided.

Collection #95:
Can be divided.

Collection #96:
Can't be divided.

Collection #97:
Can be divided.

Collection #98:
Can be divided.

Collection #99:
Can't be divided.

Collection #100:
Can be divided.

AKJ88 · Post by **AKJ88** » Wed Mar 13, 2013 11:48 am

Thanks brianfry, I changed my code and now it produces the correct output but no luck in getting AC.
Here's my code with your input: http://ideone.com/xfOr9v
Thanks.

brianfry713 · Post by **brianfry713** » Wed Mar 13, 2013 10:08 pm

Input:

Code: Select all

2077 2124 1989 2074 2040 2087
0 0 0 0 0 0

AC output:

Code: Select all

Collection #1:
Can be divided.

AKJ88 · Post by **AKJ88** » Thu Mar 14, 2013 1:19 am

Thanks brianfry, I need to work on it.

shuvokr · Post by **shuvokr** » Tue Sep 24, 2013 1:15 am

Why got wa, my code give the right answer for all forum input, anyone help
My code

Code: Select all

#include <stdio.h>
#include <string.h>
using namespace std;

int istrue(int p, int half, int take);

int tot, in[ 7 ], dp[ 7 ][ 60003 ];
bool ck;

int main()
{
    //freopen("in.txt", "w", stdout);
    int i, a, b, c, d, e, f, kag = 0;
    while(~scanf("%d %d %d %d %d %d", &in[1], &in[2], &in[3], &in[4], &in[5], &in[6]))
    {
        tot = in[ 1 ] +  (in[ 2 ] * 2) +  (in[ 3 ] * 3) +  (in[ 4 ] * 4) +  (in[ 5 ] * 5) +  (in[ 6 ] * 6);
        if(!tot) break;
        memset(dp, -1, sizeof(dp));
        if((tot % 2))
        {
            printf("Collection #%d:\n", ++kag);
            puts("Can't be divided.");
            puts("");
            continue;
        }
        tot /= 2;
        ck = false;
        istrue(1, 0, 0);
        printf("Collection #%d:\n", ++kag);
        if(ck) puts("Can be divided.");
        else puts("Can't be divided.");
        puts("");
    }
    return 0;
}
int istrue(int p, int half, int take)
{
    if(half == tot)
    {
        ck = true;
        return 0;
    }
    if(p - 1 == 6) return 0;
    if(dp[ p ][ half ] != -1) return dp[ p ][ half ];
    int tmp = 0, tm = 0;
    if(take < in[ p ])
    {
        dp[ p ][ half ] = istrue(p, half + p, take + 1);
        dp[ p ][ half ] = istrue(p + 1, half + p, 0);
    }
    else dp[ p ][ half ] = istrue(p + 1, half, 0);
}

brianfry713 · Post by **brianfry713** » Fri Oct 11, 2013 2:49 am

Input:

Code: Select all

0 1 1 1 1 1
0 0 0 0 0 0

AC output:

Code: Select all

Collection #1:
Can be divided.

OJ Board

711 - Dividing up

Re: 711 - Dividing up

Re: 711 - Dividing up

Re: 711 - Dividing up

Re: 711 - Dividing up

Re: 711 - Dividing up

Re: 711 - Dividing up

Re: 711 - Dividing up

Re: 711 - Dividing up

Re: 711 - Dividing up

Re: 711 - Dividing up