The bruteforce is only correct way to solve this problem you are to write function that will generate all permutations of(0,1) length n(where n-number of stones in pile) than you have calculate weight of all stones that you took in concrete permutation and find minimal difference between 2 piles. that's all sorry for poor eng Brute force is the easiest to implement here but not the only way. You can also develop a DP scheme to solve this problem, especially if you were given not 20 but, say, 100 stones... Could you explain, what does the abbreviation «DP» mean here, please? As usual, DP == Dynamic Programming Thank you so much for the hint. I did try with brute force. Not sure why I am getting #WA 1. Could you please kindly help me with some test cases? Hi All, Thank you for all your support and help. Just got AC with brute force method. regards Anupam I found i really fast and simple solution for this one. Main idea is: 1.Get 2 arrays(first one to store weights and sec to store 0 or 1 as includes in sum or not) 2.Find what sum would be best case 3.Go trough array and add to the sum until you get more than best sum 4.Now you need to make sum optimal,you do that this way: 1.If current sum is greater than best you remove one element that is closest to current sum - best sum but only if by doing that you get better solution than the one you've got before 2.If current sum is lest that optimal than you need to add one element that was not in sum and also you do that only if by doing that you get better solution than the one you've got before 5.If there were no changes in last pass you print result as abs(main sum - 2*current sum) Hope you like it :) i've got AC (0,015s and 212kb memory) using this algorithm Edited by author 27.01.2012 20:35 I dont think brute force would be the best approach. Because when the input is 20, maximum number of elements to be considered is 10. So that would leave us with something like this (20!)/(20-10)! = 20*19*18*17*16*15*14*13*12*11 I am not quite sure whether we would be able to check the last permutation (worst case) within the two seconds time limit. Please correct me if I am wrong.. Every stone can be in group A or in group B. Just brute every variant of every stone. O(2^N * N). Oops... I was wrong. On a second thought, we should not find the permutations but the combinations. But still that crosses 1.5 millions... :( Accepted 0.015 120 KB start: for each stone put stone in the other pile if the difference is greater than before then put it back else let it stay in this pile end for if the difference is smaller than before the for loop then goto start (do another pass) make sure that you don't get an infinite loop. it happened and I got TLE at test 2 Edited by author 15.06.2012 18:22 Edited by author 15.06.2012 18:22 Hm...I developed another solution, but don't know why it is wrong. "Put" means add to the sum, like: left += element; 1. Sort stones in their weight from bigger to lower. 2. If there is only 1 stone - it is an answer. 3. If there are 2 stones - absolute of their difference is an answer. 4. Else: put first stone to left (or right) and second to ther right (or left). 5. Put next stone to the side which is lowerю 6. Repeat 5 until number of stones will be reached. 7. Print the absolute value of difference of the left and right. Where I'm wrong? Edited by author 30.06.2012 23:35 Edited by author 30.06.2012 23:41 For Novosad. I go in that way to, but what's wrong with this solution? The flaw Hypбол is that this algorithm (which I did first, too, by the way) *always* places the largest and 2nd largest stones in different piles. Inputs like 5 4 6 7 8 9 require the 9 and 8 to be together in one pile. I'm not aware of any algorithm smarter than "try all combinations and choose the smallest difference). Any heuristic solution that doesn't try all combinations will fail to input specially crafted to fit the "blind spot" of the heuristic, like in this case. This problem does NOT belong in the beginner's section IMO! > This problem does NOT belong in the beginner's section IMO! OK, I see the simple O(2^n) algorithm, but still, I wouldn't call this a beginner's problem, since this technique of partitioning via binary strings is definitely not obvious to beginners. It's absolutely a very important technique, but someone who just picked up coding would take some while to think this up. Edited by author 15.09.2012 18:46 Edited by author 15.09.2012 18:46 > This problem does NOT belong in the beginner's section IMO! OK, I see the simple O(2^n) algorithm, but still, I wouldn't call this a beginner's problem, since this technique of partitioning via binary strings is definitely not obvious to beginners. It's absolutely a very important technique, but someone who just picked up coding would take some while to think this up. Edited by author 15.09.2012 18:46 I think so. Anyway, I can just use brute force right now. :-$ Edited by author 09.11.2013 18:50 The easiest one is brute-force There are 2 cycles, one of them is generating (0, 1) sequence, (1 if we include the stone in 1-st set of stones and 0 if not), there are 2^n permutations. The second cycle checks, if we should include the stone in the 1-st set and adds its weight to the current set weight. We should find the best difference between 2 sets' weights, the weight of one set is current_weight, of the second, obviously, sum - current_weight (sum is weight of all the stones), and the difference is abs(current_weight - (sum - current_weight)) = abs(sum - 2 * current_weight). But this is bad algorithm since it's complicity is O(n * 2^n), which is over 20 million in this problem in worst case. The DP algo complicity is O(n * sum), which is better in most of problems except this one, because if there are 20 stones and weight of each is 100000, then n * sum = 40 million, which is 2 times worse. Edited by author 29.03.2013 14:57 Solve it with brute force, afaik this problem is of NP class. I have solved it with Dp in 0.015. Is there anyone fast(DP)? I'd be more interested in your memory strategy. I don't think DP alg will differ much for the same problem Maybe the test data are so simple, and DP is able to accept. But I don't think DP method is right. dp(bug task) and bruteforce (2^n) are both accepted for me it got accepted with brute force Time : 0.015 (I think its the minimal time) C++ using maps and vectors Used DP Want d code? gaston770@gmail.com Less than 15 lines of the algorithm My solution cost monstrously 0.187s using DP... Легко решается с динамическим програмированием. Делишь сумму камней на 2 части, потом запускаешь рюкзак до суммы камней/2, ответом будет являться abs(sum-2*maxx), где sum - сумма камней, а maxx - макс. вес, который мы можем поместить в наш "рюкзак" I got an error on #8 after rejudging the problem. First i got AC. This time I tried a brute force approach. first i generated al binary digits from 0 to 2^N. then i counted sum of the stones where the bit was 1. The difference total-2*sum had to be minimal. AC in 0.2 sec I tried this approach but got TLE for test 3. Question i keep asking myself is, "Must you check all the 2^N combinations. if "No" how should you set your break point? Try to write more effective code, don't use string and set at all! Try to write more effective code, don't use string and set at all! Thank You. Just nailed it. [code deleted] Edited by moderator 29.01.2022 19:44 The short explanation is that the greedy algorithm is wrong. A simple example: it always places the largest and 2nd largest stones in different piles. Understanding this, it's not hard to come up with input that fails, e.g.,: 5 4 6 6 7 9 (sum of the largest and next largest stones = sum of remaining smaller stones) Optimization problems like this generally require that all combinations be examined. Either in brute force generate and test, or smarter "try all" schemes like recursion with backtracking (and memo-ization) or dynamic programming, to reduce redundant work. Hello, Thanks a lot. I was searching for a test case which would fail the greedy algorithm. But still donot understand why the greedy algorithm fails. I am a begineer to algorithms. Could you just explain. with regards gogreen. Hi, I was using greedy algorithm and found out the flaw. Because there are 2 buckets, and you put one stone after another (this is the major flaw), regardless of its way to keep it minimum difference, there is still a possibility that the combination is not the optimal solution. For example, I believe that 1,1,1,3 would cause problem. The first step, 1 on bucket1, second step, 1 on bucket2. This equals to the difference to be 0. Third step, 1 on bucket1 or bucket2, fourth step, 3 on opposite of what you did in third step, However, as you can see the most optimal solution is 1,1,1 in bucket1, 3 in bucket2. Greedy would work if the number of stones on both buckets are equal or have difference of 1 (due to odd numbers). Edited by author 22.05.2013 07:30 The problem says "You have a number of stones with known weights W1, …, Wn. " This is unclear because you can suppose there are more stones than the n weights (you can imagine two different stones having the same weight). And worst, in the output description, the author's problem uses letter n with two different cases (upper N for the number of stones and lower n for the numbers of weights), this gave me trouble and lets me think the problem was more complicated than it really is. Please, use the same case for the two letters and, better, be more explicit by starting the statement problem in this way : You have a number n of stones with known weights W1, …, Wn
Edited by author 05.05.2013 19:55 There is a DP solution for this version of knapsack problem with O(n*max(wi)) time and O(max(n, max(wi))) space. It's a beat tricky, but still not so difficult in implementation. Just use your brains wisely ;) But an easy one is a brute-force, where we need to search between 2^n sets of piles. P.S. To admins, how about adding a new problem "Stone Pile 2" with N<=1000, 1<=Wi<=10000 and with writing the exact piles to output :) What parameters in the test number 9? I found such test: 36 25 12 10 8 7 1 the right answer 1, but I received the response 5 - really the program wrong, the unique decision - search of all possible options! PS: а не по английски тут можно писать? Edited by author 15.04.2013 15:15 * New tests have been added. * First test is now the sample from the problem statements. * Memory limit is changed from 16 MB to 64 MB. * Time limit is changed from 2 seconds to 1 second. Solutions have been rejudged. More than 1700 authors have lost AC. hello, I wrote the code for this problem in python. I sure my logic is right, but do not know why i get a wrong answer. I have pasted my code below. If someone could help me find where the bug is .. it would be of great use #timus 1005 import sys,math class Timus1005: def __init__(self): pass
def minimumDiffrence(self,weights): weights.sort() if (len(weights) == 1): return weights[0]
if (len(weights) == 2): return (weights[1] - weights[0])
weights.reverse()
pile1 = 0 pile2 = 0
for stone in weights: added = False if (pile1 < pile2) and added == False: pile1 = pile1 + stone added = True
if (pile1 > pile2) and added == False: pile2 = pile2 + stone added = True
if (pile1 == pile2) and added == False: pile1 = pile1 + stone added = True
return int(math.fabs(pile1 - pile2))
if __name__ == "__main__": w = [] for line in sys.stdin: for word in line.split(' '): w.append(int(word))
p = Timus1005() print p.minimumDiffrence(w[1:])
My solution of 1005 problem was accepted. Here it is: #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int n,t; vector<int> w; cin >> n; for(int i = 0; i < n; ++i) { cin >> t; w.push_back(t); } sort(w.begin(), w.end()); vector<int>::reverse_iterator it = w.rbegin(); vector<int>::reverse_iterator end = w.rend(); int s = 0; for(; it != end; ++it) s += *it; it = w.rbegin(); s = s/2 + (s%2); int l = 0, r = 0; for(; it != end; ++it) if(l + *it <= s) l += *it; else r += *it; cout << abs(l-r) << endl; return 0; } But there is a test, where this solution gives a wrong answer: 6 101 51 51 3 2 2 Yeah, right answer is 0, but your 2.. I hope that admins will add some new tests. Edited by author 11.08.2012 20:16 Just use Greedy algorithm =) > Just use Greedy algorithm =) Greedy is wrong for this problem. I have made two solutions.. 1st one was failing at test case#5 and second one was failing @test case#2. Then I combined both and took the minimum out of both and in this case its again failing @test case#2. If you analyse, 1st one was failing@ Test Case#5 so its answer was proper for Test case#2. Now I took the minimum of 1st and 2nd solution and its again failing @Test case#2. That means my 2nd solution is giving minimal output than 1st one. So I can say that the Test case#2 is wrong. may be your 2nd solution is wrong although it luckily passes test1? > So I can say that the Test case#2 is wrong. 99.99% of all posts saying "test X is wrong" are wrong :). Of course, if your WA2 code calculates a smaller value for test #2 than your WA5 code (which gets the correct answer for #2), then your combination algorithm will yield the wrong result for test #2. Please, someone tell me the input data for the test#2 #include <stdio.h> #include <stdlib.h> main() { int i,j,k,t; int sum; int max; int mark; int a[22]; int* x; x=(int*)malloc(1048578*sizeof(int)); scanf("%d",&a[0]); for(i=1,sum=0;scanf("%d",&t)!=EOF;i++) { for(j=1;j<=i-1 && t>a[j];j++); for(k=i-1;k>=j;k--){a[k+1]=a[k];} a[j]=t; sum+=t; } x[0]=1;x[1]=0; for(i=1;i<=a[0];i++) { for(j=1,mark=0,max=0;j<=x[0];j++) { x[j+x[0]]=x[j]+a[i]; if(x[j]+a[i]<=sum/2) max=max>x[j]+a[i]?max:x[j]+a[i]; } x[0]*=2; } printf("%d",sum-2*max); } I test it with a large data but can't find error... Can anyone explain the DP algorithm logic posted for this problem through examples?? If you want to get AC with DP, you can gain inspiration by reading about knapsack problem on wikipedia. P.S. I suggest that you solve this problem without DP first. It has simple solution, that is why it got "problem for beginners" tag. Hi Artem Khizha I have done some brute force code and i am able to get the answers but when i submit it i get WA #1 but i get the correct answer on my compiler. This is the code i have posted, //timus ru programming problems //stone pile #include<stdio.h> #include<conio.h> #include<math.h> #include<stdlib.h> //void even_diff(int [],int); //#define N 100000 int main(){ //clrscr(); int n; int i,j; int temp=0; int sum_l=0,sum_r=0; long cur_sum=0; long old_sum=0; long stones[100000];
//printf("\nenter n:"); scanf("%d",&n);
//printf("\nenter wts: ");
for(i=0;i<n;i++) scanf(" %ld",&stones[i]);
for(i=0;i<n;i++) cur_sum+=stones[i]; old_sum=cur_sum; cur_sum=cur_sum/2; if(n==1) printf("\n%ld",stones[0]); else if(n==2) printf("\n%ld",abs(stones[0]-stones[1])); else{
for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ if(stones[i]<stones[j]){ temp=stones[i]; stones[i]=stones[j]; stones[j]=temp; } } } sum_l=stones[0]; sum_r=stones[1];
for(i=2;i<n;i++){ if(sum_l<sum_r){ if(sum_l+stones[i]<=cur_sum){ sum_l+=stones[i]; } } else sum_r+=stones[i]; } if(old_sum%2==0) printf("\n%ld",abs(sum_l+sum_r-(2*cur_sum))); else printf("\n%ld",abs(sum_l-sum_r));
getch(); return 1;
} Edited by author 08.07.2012 19:03 Any help please?? Is it actually a Time Limit Exceeded error?? I dont understand!! Try this test: > 6 > 1 4 5 6 7 9 It will show you, why you get WA#1 first, and then you will see that your approach leads to WA#5. :-) And yes, it is not guaranteed that 1st test is the one from the statement. Try this test: > 6 > 1 4 5 6 7 9 It will show you, why you get WA#1 first, and then you will see that your approach leads to WA#5. :-) And yes, it is not guaranteed that 1st test is the one from the statement. Hi Artem I get 0 as the answer as (9+7)=16 and (1+4+5+6)=16 Is it not correct?? or does this correct answer lead to a wrong one for further tests? What is WA#5? So the first test need not be the sample given the problem, thanks for the info Oh, I forgot that I run your solution first on: > 4 > 1 3 9 27 Actually, I just do not understand the answer you print in cases of even N. :-) P.S. I cannot prove that sorting doesn't help here, but don't be surprised if it really doesn't. :-) Edited by author 08.07.2012 21:40 Hi Artem i get 0 for this which is wrong, This is because for even sum i print left+right-2*sum. I did this because for even sums i thought the answer would be 0 as most of the cases i tried were like that eg:3,1,1,1 total sum=6 here first half of the sum is 3 and next half is 1+1+1=3,so i add 3 and 1+1+1=3 and finally i subtract from 2*total sum/2. It is a wrong process as shown by the test case you have given. I have to think of another way now!! Hi Artem I have modified the code and now i am getting the proper answer for your test case: 27,9,1,3 the min diff is 14 this is the code #include<stdio.h> #include<conio.h> #include<math.h> #include<stdlib.h> //void even_diff(int [],int); //#define N 100000 #define TRUE 1 #define FALSE 0 int main(){ //clrscr(); int n; int i,j; int temp=0; long sum_l=0,sum_r=0; long cur_sum=0; long old_sum=0; long stones[100000]; int left_out=0; int isLeftOut;
//printf("\nenter n:"); scanf("%d",&n);
//printf("\nenter wts: ");
for(i=0;i<n;i++) scanf(" %ld",&stones[i]);
for(i=0;i<n;i++) cur_sum+=stones[i]; old_sum=cur_sum; cur_sum=cur_sum/2; //printf("\ncur_sum=%ld",cur_sum); if(n==1) printf("\n%ld",stones[0]); else if(n==2) printf("\n%ld",abs(stones[0]-stones[1])); else{
for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ if(stones[i]<stones[j]){ temp=stones[i]; stones[i]=stones[j]; stones[j]=temp; } } } sum_l=stones[0]; sum_r=stones[1];
isLeftOut=FALSE; for(i=2;i<n;i++){ if(sum_l+stones[i]<=cur_sum) sum_l+=stones[i]; else if(sum_r+stones[i]<=cur_sum) sum_r+=stones[i]; else{ left_out=stones[i]; isLeftOut=TRUE; } } /*if(old_sum%2==0) printf("\n%ld",abs(sum_l+sum_r-(2*cur_sum))); else*/ if(isLeftOut) printf("\n%ld",abs(sum_l-sum_r-left_out));
else printf("\n%ld",abs(sum_l-sum_r));
} //printf("\nsum_l=%ld sum_r = %ld",sum_l,sum_r);
getch(); return 1;
} I am getting WA#5. I dont know what more i should do as i feel i have taken a long long time to do this simple problem!!! All polynomial algorithms are wrong, don't even try to write them, WA will be yours. Well, as I said, I don't know how to prove that your solution is wrong. But I know that you can get AC in two different ways: with backtracking in O(2^N) (quite easily) and with DP in O(N*W) (a bit trickier). Thank you Artem for your help So it must be done either with backtracking or DP, gues ill have to start learning these two techniques for this problem Backtracking (with memo-ization) and DP are two techniques that make the 'try all possible combinations" more efficient, but they're still "try all combinations" solutions. For problem sizes like this one ( 1 <= N <= 20 ), explicitly enumerating and trying all possible partitions runs pretty quickly. Adding together 20 numbers a million times is nothing for a 3GHz processor. This is my code, it works good on the sample test, but I get WA1 #include <stdio.h> unsigned int w[20], s, i, n, max, h, j, k, r[20], l[20]; bool a[50001]={1}, u[50001][20]; int main (void){ scanf("%u", &n); for(i = 0; i < n; i++){ scanf("%u", &w[i]); h += w[i]; } for(i = 1; i <= h/2; i++) for(j = 0; j < n; j++){ if(u[i - w[j]][j] == 0 && a[i - w[j]] && i - w[j] >= 0){ a[i]++; for(k = 0; k < n; k++) u[i][k] = u[i-w[j]][k]; u[i][j]++; max = i; j = n; } } printf("%i", h - 2*max); return 0; } It's not clear what your algorithm is (all the single letter variables make for unreadable code), but to quote from another thread about this question, "all polynomial time algorithms are wrong." You must consider all possible combinations, because otherwise there will be an input somewhere that will cause your solution to fail. My AC solution gives wrong answer on this test: 5 100 30 50 30 90 Right answer: 0 # include <stdio.h> # include <conio.h> # include <math.h> # include <stdlib.h> # include <time.h> # include <limits.h> bubble( int a[] , int n ) { int i , j , t;
for( i = n - 1 ; i >= 1 ; i-- ) for( j = 1 ; j <= i ; j++ ) if( a[j - 1] > a[j] ){ t = a[j - 1]; a[j - 1] = a[j]; a[j] = t; } } int bul_( int *dizi , int optimum , int adet ) { static int min = INT_MAX; int i; min = min < optimum ? min : optimum ; if( dizi[0] > optimum ) return; if( adet == 0 && dizi[0] < optimum ) min = min < optimum - dizi[0] ? min : optimum - dizi[0] ; for( i = 0 ; i < adet ; ++i ) bul_( dizi + i + 1 , optimum - dizi[0] , adet - i - 1 );
return min; } int main() { int dizi[100] , adet , i , optimum , toplam = 0 , deger; scanf("%i",&adet); for( i = 0 ; i < adet ; ++i ){ scanf("%i",&dizi[i]); toplam += dizi[i]; } bubble( dizi , adet ); optimum = toplam / 2; deger = bul_( dizi , optimum , adet ); printf("%i",toplam % 2 == 0 ? deger * 2 : 2 * deger + 1 ); system("pause"); return 0; }
this code solve only four test case
|
|