Общий форум @ Timus Online Judge

Chmel_Tolstiy TimeLimit [8] // Задача 1610. Нынче в моде кактусы 1 апр 2008 15:17

$wordfish 100*100 not enough? [2] // Задача 1313. К вопросу о спорте 9 июл 2012 23:57

outsky what the fuck is test#4? // Задача 1654. Шифровка 16 сен 2012 15:13

ashwin Help to Understand DP algortihm [12] // Задача 1005. Куча камней 7 июл 2012 17:15

Can anyone explain the DP algorithm logic posted for this problem through examples??

Artem Khizha [DNU] Re: Help to Understand DP algortihm [11] // Задача 1005. Куча камней 8 июл 2012 00:40

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.

ashwin Re: Help to Understand DP algortihm [10] // Задача 1005. Куча камней 8 июл 2012 18:37

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

ashwin Re: Help to Understand DP algortihm [9] // Задача 1005. Куча камней 8 июл 2012 19:07

Any help please??
Is it actually a Time Limit Exceeded error?? I dont understand!!

Artem Khizha [DNU] Re: Help to Understand DP algortihm [8] // Задача 1005. Куча камней 8 июл 2012 19:27

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.

ashwin Re: Help to Understand DP algortihm [7] // Задача 1005. Куча камней 8 июл 2012 20:13

Artem Khizha [DNU] писал(a) 8 июля 2012 19:27

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

Artem Khizha [DNU] Re: Help to Understand DP algortihm [6] // Задача 1005. Куча камней 8 июл 2012 20:39

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

ashwin Re: Help to Understand DP algortihm [5] // Задача 1005. Куча камней 8 июл 2012 21:37

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!!

ashwin Re: Help to Understand DP algortihm [4] // Задача 1005. Куча камней 9 июл 2012 00:14

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!!!

Alexey Dergunov [Samara SAU] Re: Help to Understand DP algortihm // Задача 1005. Куча камней 9 июл 2012 00:22

All polynomial algorithms are wrong, don't even try to write them, WA will be yours.

Artem Khyzha Re: Help to Understand DP algortihm [2] // Задача 1005. Куча камней 9 июл 2012 01:26

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).

ashwin Re: Help to Understand DP algortihm [1] // Задача 1005. Куча камней 9 июл 2012 21:20

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

Bogatyr Re: Help to Understand DP algortihm // Задача 1005. Куча камней 15 сен 2012 19:06

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.

PrankMaN Why WA1 [1] // Задача 1005. Куча камней 13 апр 2012 04:06

Fyodor Menshikov Mistake in statement [1] // Задача 1197. Один в поле воин 15 сен 2012 09:47

Darwesh Pleaze Tell me what will the output for n=7 and k = 10??? if you have done it... [1] // Задача 1009. K-ичные числа 13 сен 2012 11:12

ONU_Dudnik test 8 [1] // Задача 1880. Собственные числа Psych Up 20 янв 2012 14:42

Vladislav Java [2] // Задача 1409. Два бандита 6 авг 2012 00:45

Ruzmamat Ruzmamat [2] // Задача 1409. Два бандита 21 мар 2012 02:05

bavykinE Задача А Набор за время менее t [10] // Задача 1885. Комфорт пассажиров 29 окт 2011 13:13

Ankit Mehta Wrong Answer Test #3 Please Help! [4] // Задача 1020. Ниточка 8 июн 2011 16:16

orcchg hint [1] // Задача 1313. К вопросу о спорте 22 авг 2011 21:31

Frankie Keep getting WAs [2] // Задача 1024. Перестановки 28 ноя 2011 19:34

kkk, i figured out about the LCMs pretty much myself, but i just keep getting WAs on tests like 4 or 3 and that's sooo embarassing
<code>
#include <stdio.h>
#include <cmath>
#include <set>

using namespace std;

long long gcd(long long a, long long b) {
    return !b ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return (a / gcd(a,b) * b);
}

int main()
{

    int n;

    scanf("%d", &n);

    set<int> ds; // a usual stl set which stores the distaces of all elements
    int tmp;
    for(int i=1;i<n+1;i++) {
        scanf("%d", &tmp);
        ds.insert(abs(i-tmp));
    }

    long long res;
    if(ds.size() == 1 && ds.count(0)) res = 1;
    else {
        if(ds.count(0)) ds.erase(ds.find(0));
        res = 1;
        for (set<int>::iterator it = ds.begin(); it != ds.end(); ++it) {
            res = lcm(res,*it);
        }
    }

    printf("%lld", res);

}
</code>
And the worst thing is I just can't think of a straightforward test for which that gives a wrong answer.
5 4 1 5 2 3 => 6
1 1 => 1
5 1 2 3 4 5 => 1
6 6 5 3 4 2 1 => 15
didn't check for ns like 100 and i don't think that's the problem. also i don't think the problem is about malformed longlong operation, cause if i replace that with ints the WAs are all the same.
would really like if someone helped me 'bout that ((

Edited by author 28.11.2011 19:38

Frankie Re: Keep getting WAs [1] // Задача 1024. Перестановки 29 ноя 2011 11:28

"Every problem has a simple, fast and wrong solution."
- that one is soooo right :D

i mean, i came up with the distances of the items, but those actually should be the lengths of cycles ))
it was like 4 1 5 2 3 => 3 2 1 2 2
but should be like 4 1 5 2 3 => 3 3 2 3 2
- and it's really straightforward to figure out how it works :D
the worst thing about my initial solution is that it worked in some trivial cases :)

now i made something like that:
[code deleted]
and finally got AC after 23 WAs :) so happy 'bout that

Edited by moderator 04.12.2019 20:47

Bogatyr Re: Keep getting WAs // Задача 1024. Перестановки 13 сен 2012 23:49

Look out for left over debug prints! I was tearing my hair out over WAs after I figured out doing the LCM of all the unique cycle counts and was convinced the approach was correct, and I was right! But one left over debug print messed me up until I finally saw it.

Mikael Arakelyan(ERIICTA) test for all [6] // Задача 1014. Произведение цифр 23 ноя 2010 21:56

Here is my own testing program ...
Now tell me please what is wrong here???
N ==0 Q == 10
N ==1 Q == 1
N ==2 Q == 2
N ==3 Q == 3
N ==4 Q == 4
N ==5 Q == 5
N ==6 Q == 6
N ==7 Q == 7
N ==8 Q == 8
N ==9 Q == 9
N ==10 Q == 25
N == 11 -1
N ==12 Q == 26
N == 13 -1
N ==14 Q == 27
N ==15 Q == 35
N ==16 Q == 28
N == 17 -1
N ==18 Q == 29
N == 19 -1
N ==20 Q == 45
N ==21 Q == 37
N == 22 -1
N == 23 -1
N ==24 Q == 38
N ==25 Q == 55
N == 26 -1
N ==27 Q == 39
N ==28 Q == 47
N == 29 -1
N ==30 Q == 56
N == 31 -1
N ==32 Q == 48
N == 33 -1
N == 34 -1
N ==35 Q == 57
N ==36 Q == 49
N == 37 -1
N == 38 -1
N == 39 -1
N ==40 Q == 58
N == 41 -1
N ==42 Q == 67
N == 43 -1
N == 44 -1
N ==45 Q == 59
N == 46 -1
N == 47 -1
N ==48 Q == 68
N ==49 Q == 77
N ==50 Q == 255
N == 51 -1
N == 52 -1
N == 53 -1
N ==54 Q == 69
N == 55 -1
N ==56 Q == 78
N == 57 -1
N == 58 -1
N == 59 -1
N ==60 Q == 256
N == 61 -1
N == 62 -1
N ==63 Q == 79
N ==64 Q == 88
N == 65 -1
N == 66 -1
N == 67 -1
N == 68 -1
N == 69 -1
N ==70 Q == 257
N == 71 -1
N ==72 Q == 89
N == 73 -1
N == 74 -1
N ==75 Q == 355
N == 76 -1
N == 77 -1
N == 78 -1
N == 79 -1
N ==80 Q == 258
N ==81 Q == 99
N == 82 -1
N == 83 -1
N ==84 Q == 267
N == 85 -1
N == 86 -1
N == 87 -1
N == 88 -1
N == 89 -1
N ==90 Q == 259
N == 91 -1
N == 92 -1
N == 93 -1
N == 94 -1
N == 95 -1
N ==96 Q == 268
N == 97 -1
N ==98 Q == 277
N == 99 -1
N ==100 Q == 455
N == 101 -1
N == 102 -1
N == 103 -1
N == 104 -1
N ==105 Q == 357
N == 106 -1
N == 107 -1
N ==108 Q == 269

Mikael Arakelyan(ERIICTA) Re: test for all // Задача 1014. Произведение цифр 23 ноя 2010 21:57

this program fails (WA) at test 8

Mikael Arakelyan(ERIICTA) Re: test for all [3] // Задача 1014. Произведение цифр 23 ноя 2010 22:38

this program shouldn't fail...

Edited by author 23.11.2010 22:39
#include<iostream>

int main()
{

    int a, b;
    bool t = true;
    std::cin >> a;
        if(a < 0 || a > 109){
            std::cin >> a;
        }
            int k = 6, j = 9, i = 9, test = 4;
            while(test >= 1){
                k = 5;
                 while(k >= 1){
                     i = 9;
                     while(i >= 2){
                         j = 9;
                          while(j >= 2){
                              if(test != 1){
                                  if(test * j * i * k == a){
                                      b = (test*1000) + (k*100) + (i * 10) + (j);
                                      t = false;
                                  }
                             }else if(k != 1 && test == 1){
                                  if(j * i * k == a){
                                      b = (k*100) + (i * 10) + (j);
                                      t = false;
                                  }
                              }else if(k == 1 && test == 1){
                                  if(j * i == a){
                                      b = (i*10) + j;
                                      //std::cout <<"i == "<<(i)<< " + j == " << j << '\n';
                                      t = false;
                                  }
                              }
                              j--;
                          }
                         i--;
                     }
                     k--;
                }test--;
            }
            if(a < 10){
                if(a==0){
                    b = 10;
                    t = false;
                }else if(a>=1){
                        b = a;
                        t = false;
                }
            }

        if(t == false){
            std::cout << b << '\n';
        }else{
            std::cout << -1 << '\n';
        }
    return 0;
}

Edited by author 23.11.2010 23:07

amirani Re: test for all // Задача 1014. Произведение цифр 22 авг 2011 22:43

In fact i don't really know C but i had the same problem on test 8 and the reason was that i needed bigger in (in pascal int64).
Thanks.

daftcoder [Yaroslavl SU] Re: test for all [1] // Задача 1014. Произведение цифр 23 авг 2011 11:42

try test 244140625

Ahmet Faruk Ozkan Re: test for all // Задача 1014. Произведение цифр 24 авг 2012 00:35

its answer is 555555555555

Darwesh Re: test for all // Задача 1014. Произведение цифр 13 сен 2012 19:51

I think the limit is 0<= N <= (10^9) not 109

Zachary wa 28 [1] // Задача 1793. Тарелки 2 13 мар 2012 15:17

sapiens_sch Сколько вершин в третьем тесте? [4] // Задача 1020. Ниточка 3 мар 2012 18:48

ManYang Java Time limit exceeded // Задача 1001. Обратный корень 12 сен 2012 08:55

Lerie[ONPU-12] To admins: weak tests. // Задача 1005. Куча камней 11 сен 2012 23:31

andy777 WA #7 [1] // Задача 1820. Уральские бифштексы 25 янв 2012 01:46