10520 - Determine it

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

10520 - Determine it

Post by Alexander Kozlov » Thu Jul 03, 2003 4:33 pm

Dear friends!
I have just got AC for this problem.
I consider j >= 1. That is 1 <= i,j <= n and

.......................| max(aik + ank),...j > 1
aij = ........ + <...................................i >= j
.......................| 0, .......................j = 1

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Jul 03, 2003 5:25 pm

Can you post some examples?

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm

Post by Lars Hellsten » Fri Jul 04, 2003 1:34 am

Maybe he means that the j = 0 (j > 0) condition in the problem statement should actually be j = 1 (j > 1). You'll never actually consider j = 0 because k always starts at 1. If you implement this in the obvious way, your loop condition will probably do this check implicitly though.

Anyway, this problem is straightforward, aside from the not-quite-obvious-without-testing fact answers can be larger than 2^32.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Jul 04, 2003 9:28 am

I used long long and got WA, is this enough or do I need bigint?

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

Some tests

Post by Alexander Kozlov » Fri Jul 04, 2003 9:42 am

Input:

5 10
4 1
6 13
10 36
11 243
14 67
15 198
16 325
17 423
19 499

Output:

1140
42
3770
313416
4728294
13721734
87589260
308839050
859374414
4578345958

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Jul 04, 2003 7:12 pm

Thanks. Stupid mistake, I changed my stuff from int to long long and didn't remember to change one of the intermediate variables..

shihabbd81
New poster
Posts: 7
Joined: Sun Apr 13, 2003 8:39 am
Location: Buet, Bangladesh
Contact:

Sorry

Post by shihabbd81 » Sun Aug 03, 2003 6:30 am

the coditions should be j>1 and j=1 not j>0 and j=0
it was my mistake.
sorry.

Shihab Uddin
problemsetter of 10520

Examiner
New poster
Posts: 27
Joined: Thu Feb 19, 2004 1:19 pm

Post by Examiner » Sat Jun 05, 2004 12:09 pm

Then the formula implies a[n, 1] is always 0; this contradicts the input, unless the second number is also 0.
What's in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.
Alan J. Perlis

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

10520...check my I/O

Post by asif_rahman0 » Thu Aug 03, 2006 5:21 pm

can someone check my following Input/output.
my code gives the following answer:

Code: Select all

Input:
1 2
1 1
1 9
1 15
15 1
9 1
2 1
10 10
13 6
15 105
15 350
15 450
19 450
17 319
17 400
11 411
17 411
19 19

Output:
2
1
9
15
442370
3842
4
87060
565260
46448850
154829500
199066500
4128768900
648086142
812647200
7997238
834994998
174325798
Output is now corrected.

rabbi
Last edited by asif_rahman0 on Sun Aug 06, 2006 12:09 pm, edited 2 times in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Aug 03, 2006 5:28 pm

I get a different output only for 19 450 -- 4128768900.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Thu Aug 03, 2006 5:54 pm

thnx mf. :)
Got accepted.
It should be 64 bit data type.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Aug 05, 2006 3:32 am

asif_rahman0 wrote:thnx mf. :)
Got accepted.
It should be 64 bit data type.
Please, fix the output to the 19 450 case in your very first post in this thread, so people won't get confused by the incorrect output.

mhayter1
New poster
Posts: 15
Joined: Wed Jul 26, 2006 10:00 am

Post by mhayter1 » Sun Oct 21, 2007 6:29 am

Hi, I've past all test cases on the forum, and I use a 64 bit data type without success. Could anyone help?

Code: Select all

#include<iostream>
#include<algorithm>
using namespace std;

const unsigned long long SIZE=500;
unsigned long long memo[SIZE][SIZE];
bool found[SIZE][SIZE];
unsigned long long n;

inline void update(unsigned long long i,unsigned long long j,unsigned long long v)
{
    memo[i][j]=v;
    found[i][j]=true;
}
inline unsigned long long  mx(unsigned long long &a,unsigned long long &b)
{
    if(a>=b)return a;
    else return b;
}

unsigned long long zzz;

unsigned long long a(unsigned long long i,unsigned long long j)
{
    if(found[i][j]) return memo[i][j];
    if(i>=j)
    {
        unsigned long long s1=0;
        unsigned long long s2=0;
        if(i<n)
        {
            for(unsigned long long k=i+1;k<=n;k++)
            {
                unsigned long long ak1=a(k,1);
                update(k,1,ak1);
                
                unsigned long long akj=a(k,j);
                update(k,j,akj);
                
                unsigned long long sum=ak1+akj;
                s1=mx(s1,sum);
            }
        }
        else if(i==n)
        {
            s1=0;
        }
        if(j>1)
        {
            for(unsigned long long k=1;k<j;k++)
            {
                unsigned long long aik=a(i,k);
                update(i,k,aik);
                
                unsigned long long ank=a(n,k);
                update(n,k,ank);
                
                unsigned long long sum=aik+ank;
                s2=mx(s2,sum);
            }
        }
        else if(j==1)
        {
            s2=0;
        }
        unsigned long long aij=s1+s2;
        update(i,j,aij);
        return memo[i][j];
    }
    else
    {
        unsigned long long s1=0;
        for(unsigned long long k=i;k<j;k++)
        {
            unsigned long long aik=a(i,k);
            update(i,k,aik);
            
            unsigned long long akonej=a(k+1,j);
            update(k+1,j,akonej);
            
            unsigned long long sum=aik+akonej;
            s1=mx(s1,sum);
        }
        update(i,j,s1);
        return memo[i][j];
    }
}
        
int main()
{
    while(cin>>n>>memo[n][1])
    {
        memset(found,0,sizeof(found));
        found[n][1]=true;
        cout<<(unsigned long long)a(1,n)<<endl;
    }
    unsigned long long z;
    cin>>z;
    return 0;
}
    

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Re: 10520 - Determine It

Post by smilitude » Thu Jun 26, 2008 1:21 pm

i checked your program in my pc with all possible inputs. and after comparing with my ac program's output, my judge program printed

Code: Select all

Total Case 9481; passed 9481; failed 0

which astonished me! i am not sure why its not working in judge.
i used devcpp, and it works fine in my pc.
fahim
#include <smile.h>

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 10520 - Determine It

Post by andmej » Mon Jul 21, 2008 10:26 pm

I solved this using top-down dynamic programming (memoization). I was wondering, is it possible to solve this in a bottom-up approach? Thanks.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Post Reply

Return to “Volume 105 (10500-10599)”