Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Страница 10 | WA #9 | YuriG | 1005. Куча камней | 15 апр 2013 15:10 | 2 | WA #9 YuriG 14 апр 2013 20:48 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 | Test 5 Wrong Answer | Dmitriy | 1005. Куча камней | 3 окт 2015 08:24 | 5 | Could someone write input data for test 5? My program works properly for the input below: 6 1 4 5 6 7 9 Edited by author 08.04.2013 17:51 I've already found bug in my alghoritm. It gets wrong answer on the following input: 5 11 10 8 7 6 May be this test helps someone. Thanks for the information! | Brute Force after rejudge | TinyJanssen | 1005. Куча камней | 11 июн 2013 19:57 | 4 | 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. | Problem 1005 Stone Pile has been rejudged | Vladimir Yakovlev (USU) | 1005. Куча камней | 29 мар 2013 01:04 | 1 | * 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. | 1005 - stone pile | gogreen | 1005. Куча камней | 25 мар 2013 14:58 | 1 | 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:])
| Hint | TakeOver | 1005. Куча камней | 11 дек 2012 22:10 | 4 | Hint TakeOver 7 дек 2012 22:45 Just use Greedy algorithm =) Re: Hint Andrew Sboev [USU] 7 дек 2012 23:51 > Just use Greedy algorithm =) Greedy is wrong for this problem. | Test#2 | codersapiens | 1005. Куча камней | 27 окт 2012 01:38 | 1 | Test#2 codersapiens 27 окт 2012 01:38 Please, someone tell me the input data for the test#2 | help me find a test data for the error. | HaiyangZheng | 1005. Куча камней | 3 окт 2012 18:42 | 1 | #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... | hints | 6ahodir | 1005. Куча камней | 23 июл 2015 11:42 | 8 | hints 6ahodir 24 сен 2012 12:12 A very good resource, but it still very hard for me to understand though...:( very thanks, I understood! Thanks for the hints: using dynamic programming. Re: hints Ealham Al Musabbir 23 июл 2015 11:42 | TEST Case #2 is wrong | Prasanna Kantal | 1005. Куча камней | 12 ноя 2012 15:38 | 3 | 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. | WA( I not underdstand why) | ZiDo | 1005. Куча камней | 22 май 2013 07:29 | 4 | [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 | To admins: weak tests. | Lerie[ONPU-12] | 1005. Куча камней | 11 сен 2012 23:31 | 1 | My AC solution gives wrong answer on this test: 5 100 30 50 30 90 Right answer: 0 | what is the problem? | Ahmet Faruk Ozkan | 1005. Куча камней | 23 авг 2012 20:10 | 1 | # 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
| New test | Cadovvl | 1005. Куча камней | 14 дек 2012 20:13 | 3 | 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 | Why WA#1 | Mad_Sanek | 1005. Куча камней | 8 авг 2012 00:54 | 1 | type list = array[1..21] of longint; var n,i,w1,w2,d:integer; w:list; begin read(n); d:=0; For i:=1 to n do read(w[i]); If n=1 then begin write(w[1]); halt; end; For i:=1 to n div 2 do begin If w1>w2 then w2:=w2+abs(w[i+d]-w[i+d+1]) else w1:=w1+abs(w[i+d]-w[i+d+1]); d:=d+1; end; If n mod 2=0 then write(abs(w1-w2)) else write(w[n]-abs(w1-w2)); end. 1 1 is correct(1). 5 1 8 13 27 14 is correct(3). Test #5 is correct. Where is the mistake? Edited by author 08.08.2012 01:02 | Help to Understand DP algortihm | ashwin | 1005. Куча камней | 15 сен 2012 19:06 | 13 | 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. | Why WA1 | PrankMaN | 1005. Куча камней | 15 сен 2012 18:55 | 2 | 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. | Check error. wrong Accept | LostInSpace | 1005. Куча камней | 5 апр 2012 18:02 | 1 | Some incorrect algorythm has a wrong "Accept" test: 6 9 8 6 5 4 1 | Dont work test №5 | Sega_As | 1005. Куча камней | 7 июл 2012 18:36 | 4 | program kamni; var n, i, k, min, v,a,b: integer; m: array[1..1000] of int64; begin readln(n); for i := 1 to n do begin read (m[i]); end; for i := 1 to n - 1 do begin min := i; for k := i + 1 to n do if m[min] < m[k] then min := k; v := m[min]; m[min] := m[i]; m[i] := v; end; a:=0; b:=0; for i:=1 to n do if a-b<=0 then a:=a+m[i] else b:=b+m[i]; begin writeln(a-b); end; end. 6 1 4 5 6 7 9 why 2? 9+7=16 и 1+4+5+6=16 o, senk you!) Edited by author 02.03.2012 01:01 | 1005. Куча камней | akron | 1005. Куча камней | 18 фев 2012 20:39 | 1 | using System; using System.Collections.Generic; using System.Linq; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { Program a = new Program(); a.run(); } void run() { // System.IO.StreamReader file = new System.IO.StreamReader(@"input.txt"); byte n = Convert.ToByte(Console.ReadLine()); string[] str = Console.ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries); List<int> l = new List<int>(); for (byte i = 0; i < n; i++) l.Add(Convert.ToInt32(str[i])); int k1=0, k2=0; for (byte i = 0; i < n; i++) { if (k1 >= k2) { k2 += l.Max(); l.Remove(l.Max()); } else { k1 += l.Max(); l.Remove(l.Max()); } } Console.WriteLine(Math.Abs(k1-k2).ToString()); Console.ReadKey(); } } } пишет что Crash, на компе компилится... в чём может быть проблема? |
|
|