ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1021. Sacrament of the Sum

Posted by Grigorenko Vlad 5 May 2012 22:55
#include<stdio.h>

int main(void){
long n,m,i,j;
int flag;
int A[50001],B[50001];
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%d",&A[i]);
scanf("%ld",&m);
for(j=1;j<=m;j++)
scanf("%d",&B[j]);
flag=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(A[i]+B[j]==10000)
flag=1;
if(flag)
printf("YES");
else
printf("NO");
return 0;
}
Posted by Andrew Shmig aka SyFyKid [Vladimir SU] 6 May 2012 00:23
not an optimal algo... O(n^2), this problem can be solved with O(n+m)
you should think a little more.

If you need code, send an email on andrewshmig@gmail.com

Edited by author 06.05.2012 00:27
Posted by Vladimir Plyashkun [CSU] 8 May 2012 00:18
or u can use BinarySearch to search second value.

for example in the first test:
1) u take -175 value,
2) try to find 10175 in second list (using binary search) (because -175 + 10175 == 10000)
...
good luck!

Edited by author 08.05.2012 00:20
Posted by Andrew Sboev 2 Jun 2012 20:52
>not an optimal algo... O(n^2), this problem can be solved with O(n+m)

This problem can be solved with O(n). )

Edited by author 02.06.2012 20:52