10125 - Sumsets
Moderator: Board moderators
10125 - from a novish
can it be done in this way, without dp , using optimization?
i am novish to dp, again can you plz explain me just the way by which can be done in dp? i will be greatly helped! understanding dp is a great deal to me right now!
i am novish to dp, again can you plz explain me just the way by which can be done in dp? i will be greatly helped! understanding dp is a great deal to me right now!
Code: Select all
/*
* 10125 sumsets
* submission 1 TLE
* coded at 9:29am 26th dec 05
*
*/
#include <stdio.h>
int main() {
long a, b, c, d;
long max_d;
int n;
long list[1000];
while(scanf("%d",&n) && n) {
max_d=-1;
for(int i=0;i<n;i++)
scanf("%ld",&list[i]);
//i am confused, can i omit those continue statement??
for(a=0;a<n;a++) {
for(b=0;b<n;b++) {
if(a==b) continue;
for(c=0;c<n;c++) {
if(c==b || c==a) continue;
for(d=0;d<n;d++) {
if(d==a||d==b||d==c) continue;
if(list[a]+list[b]+list[c]==list[d])
if(list[d]>max_d) max_d=list[d];
}
}
}
}
if(max_d==-1) printf("no solution\n");
else printf("%ld\n",max_d);
}
return 0;
}
fahim
#include <smile.h>
#include <smile.h>
10125WA
I have got WA many times!
I didn't find the mistake...
I use many test data to test...But can't find the error.
Who can help me?
I have find my mistake and got AC...
I didn't see that find the largest d..............
I didn't find the mistake...
I use many test data to test...But can't find the error.
Who can help me?
I have find my mistake and got AC...
I didn't see that find the largest d..............
Code: Select all
find the (largest d) such that a + b + c = d where a, b, c, and d are distinct elements of S.
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
10125
i tried so many times but i m getting TLE.
so where is my fault? is there any tricks??
help would be appreciated.
so where is my fault? is there any tricks??
Code: Select all
removed
Last edited by asif_rahman0 on Wed Jun 07, 2006 3:44 pm, edited 1 time in total.
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
the problem is a+b+c=d
Code: Select all
for(all a)
for(all b)
insert (a+b) at data structure
for(all d, starting from higher to lower)
for(all c)
if(d-c) is at the data structure... :D
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
----------------
the world is nothing but a good program, and we are all some instances of the program
I need some test cases:)
Please, can anyone provide me some test cases? I 've got 10 straight WAs in this problem ![:-?](./images/smilies/icon_confused.gif)
[EDIT]
just after the previous post, I 've found my error, in some cases, I was printing more than one answer, Should have breaked the loop earlier ![;)](./images/smilies/icon_wink.gif)
![:-?](./images/smilies/icon_confused.gif)
[EDIT]
![:)](./images/smilies/icon_smile.gif)
![;)](./images/smilies/icon_wink.gif)
Last edited by nymo on Fri Jun 09, 2006 8:23 am, edited 1 time in total.
-
- Learning poster
- Posts: 63
- Joined: Tue Sep 20, 2005 12:31 am
- Location: Dhaka
- Contact:
10125 WAAAAAAAAAAA
Please gime me some I/O:
For my worng code::
Input:
5
2
3
5
7
12
5
2
16
64
256
1024
5
1
2
3
4
5
5
5
4
3
2
1
10
1
1
1
1
1
1
1
1
1
1
1
5
2
5
6
3
5
6
7
4
5
6
7
8
4
6
3
2
1
5
-8
4
10
11
14
4
-1
0
1
0
0
WA Output::
For my worng code::
Input:
5
2
3
5
7
12
5
2
16
64
256
1024
5
1
2
3
4
5
5
5
4
3
2
1
10
1
1
1
1
1
1
1
1
1
1
1
5
2
5
6
3
5
6
7
4
5
6
7
8
4
6
3
2
1
5
-8
4
10
11
14
4
-1
0
1
0
0
WA Output::
Code: Select all
12
no solution
no solution
no solution
no solution
no solution all Output is correct ( after edit)
no solution
no solution
no solution
6
10
0
Last edited by mohsincsedu on Wed Sep 06, 2006 9:21 pm, edited 4 times in total.
Amra korbo joy akhdin............................
-
- Learning poster
- Posts: 63
- Joined: Tue Sep 20, 2005 12:31 am
- Location: Dhaka
- Contact:
AC
I got AC.
I have a stupid mistake......
Thanks to all.
I have a stupid mistake......
Thanks to all.
Amra korbo joy akhdin............................
-
- New poster
- Posts: 1
- Joined: Sun Mar 04, 2007 8:53 am
10125
i am newbie
can you help me to solve my problem ?
please
can you help me to solve my problem ?
please
Code: Select all
#include <stdio.h>
void swap( int *a, int *b );
void bubble1( int n );
void bubble2( int n );
void search( int n1, int n2 );
int e[1000];
int a[500000];
int b[500000];
int x[500000];
int main( void )
{
int number;
int count;
int i,j;
while (1)
{
count=0;
scanf( "%d", &number );
if ( number == 0 )
return 0;
while ( count < number )
{
scanf( "%d", &e[count] );
count++;
}
bubble1( number );
count=0;
for( i=0; i<number; i++)
{
for( j=i+1; j<number; j++ )
{
a[count]=i;
b[count]=j;
x[count]=e[i]+e[j];
count++;
}
}
bubble2( count );
search( number, count );
}
}
void bubble1( int n )
{
int i,j;
for( i=0; i<=n-2; i++)
{
for( j=0; j<=n-i-2; j++ )
{
if( e[j]<e[j+1] )
swap( &e[j], &e[j+1] );
}
}
}
void bubble2( int n )
{
int i,j;
for( i=0; i<=n-2; i++)
{
for( j=0; j<=n-i-2; j++ )
{
if( x[j]>x[j+1] )
{
swap( &x[j], &x[j+1] );
swap( &a[j], &a[j+1] );
swap( &b[j], &b[j+1] );
}
}
}
}
void swap( int *a, int *b)
{
int temp;
temp=*a;
*a=*b;
*b= temp;
}
void search( int n1, int n2 )
{
int ub,lb,m,key;
int i,j,k;
for( i=0; i<n1; i++ )
{
for( j=0; j<n1; j++ )
{
key=e[i]-e[j];
lb=0;
ub=n2-1;
while( lb <= ub )
{
m=(lb+ub)/2;
if( key<x[m] )
ub=m-1;
else if( key>x[m] )
lb=m+1;
else
{
if( !( (a[m]==b[m])||(a[m]==i)||(a[m]==j)||(b[m]==i)||(b[m]==j)||(i==j) ) )
{
printf("%d\n",e[i]);
return;
}
k=m;
while( key==x[k+1] && k+1<n1 )
{
k=k+1;
if( !( (a[k]==b[k])||(a[k]==i)||(a[k]==j)||(b[k]==i)||(b[k]==j)||(i==j) ) )
{
printf("%d\n",e[i]);
return;
}
}
k=m;
while( key==x[k-1] && k-1>=0 )
{
k=k-1;
if( !( (a[k]==b[k])||(a[k]==i)||(a[k]==j)||(b[k]==i)||(b[k]==j)||(i==j) ) )
{
printf("%d\n",e[i]);
return;
}
}
break;
}
}
}
}
printf("no solution\n");
}
There are some threads on this problem..
Do not create a new thread if there is one already..
http://online-judge.uva.es/board/viewtopic.php?t=2460
http://online-judge.uva.es/board/viewtopic.php?t=10824
Do not create a new thread if there is one already..
http://online-judge.uva.es/board/viewtopic.php?t=2460
http://online-judge.uva.es/board/viewtopic.php?t=10824
Re: 10125 - Sumsets
I got TLE
I thought it would pass O(n^4)algorithm
here is the part of the code:
is this ok? can it be done in this way without using DP
pls give some suggestion
I thought it would pass O(n^4)algorithm
here is the part of the code:
Code: Select all
for(a=0;a<n;a++){
for(b=0;b<n;b++){
if(a==b)continue;
for(c=0;c<n;c++){
if(c==a || c==b)continue;
for(d=0;d<n;d++){
if(d==a || d==b || d==c)continue;
if(num[a]+num[b]+num[c]==num[d])
if(num[d]>max)max=num[d];
}
}
}
}
if(max==0)printf("no solution\n");
else printf("%d\n",max);
pls give some suggestion
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
http://akanoi.webs.com/