Chef and sum

help
1

Can’t understand what’s wrong in my code

cook your dish here

import itertools
t=int(input())
for _ in range(t):
n=list(map(int, input().split()))
k=list(map(int, input().split()))
lis=list(itertools.combinations(k,2))
j = list(map(sum,lis))
if ((n[1] in set(j))==True):
print(“yes”)
else :
print(“no”)

It gives me WA and TLE for subtask 1 and subtask 2 respectively

2

It gives WA in Subtask 1 because you have to capitalize the first letter of “Yes” and “No” while printing.

It gives TLE in Subtask 2 because you are generating all combinations of the array. There are \frac{n\cdot (n-1)}{2} such combinations which for n=10^4 turns out to be ~10^8. You also have to do this for 100 test cases which makes it around 10^{10} total operations. You cannot run that many operations in 2 secs on codechef machines ( or most machines for that matter ) even in much faster languages like C.

You have to think of a different solution that accomplishes the same task in much less number of operations. You might also want to read about time complexity. The intended time complexity for this question is O(n \log n) per test case I think.

Some advice for future posts:

  1. Don’t copy-paste your unindented, unformatted code here even if it is short. Provide a submission link instead (CodeChef: Practical coding for everyone in your case).
  2. Try to explain very briefly what you have done too. It may be easier to understand what a short code like this does but that is not true not for longer, harder problems. Explaining will help out anyone who wants to help you tremendously.
3

Thanks a lot. Subtask 1 error was the disturbing one. I knew I had to optimize my code better but was not able to do it since it was giving WA.

Definately. I will keep your suggestions in mind