10520  Determine it
Moderator: Board moderators

 New poster
 Posts: 23
 Joined: Sun Jun 15, 2003 4:45 pm
 Location: Ukraine
10520  Determine it
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
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

 New poster
 Posts: 20
 Joined: Thu Apr 10, 2003 10:53 pm
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 notquiteobviouswithouttesting fact answers can be larger than 2^32.
Anyway, this problem is straightforward, aside from the notquiteobviouswithouttesting fact answers can be larger than 2^32.

 New poster
 Posts: 23
 Joined: Sun Jun 15, 2003 4:45 pm
 Location: Ukraine
Some tests
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
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

 New poster
 Posts: 7
 Joined: Sun Apr 13, 2003 8:39 am
 Location: Buet, Bangladesh
 Contact:
Sorry
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
it was my mistake.
sorry.
Shihab Uddin
problemsetter of 10520

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
10520...check my I/O
can someone check my following Input/output.
my code gives the following answer:
Output is now corrected.
rabbi
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
rabbi
Last edited by asif_rahman0 on Sun Aug 06, 2006 12:09 pm, edited 2 times in total.

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

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
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;
}
Re: 10520  Determine It
i checked your program in my pc with all possible inputs. and after comparing with my ac program's output, my judge program printed
which astonished me! i am not sure why its not working in judge.
i used devcpp, and it works fine in my pc.
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>
#include <smile.h>
Re: 10520  Determine It
I solved this using topdown dynamic programming (memoization). I was wondering, is it possible to solve this in a bottomup 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
Are you dreaming right now?
http://www.dreamviews.com