 I am getting Runtime Error in the problem "PINBS"

https://www.codechef.com/problems/PINBS

My solution link :- Solution: 56207178 | CodeChef

Only partial solution is correct.For rest there is a runtime error

Out of bounds access for the following test input:

1
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1 Like

Sorry, but I am not getting what you are trying to say.

If I use this input , output says YES
1
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

for(i=1;i<=l;++i)
{
for(j=0;j<=(l-i);++j)
{
r[k]=s.substr(j,i);
//cout<<r[k]<<" ";
++k;
}
}

For string of length 10, this nested for loops run for 54 times , for l=20, it runs for 209 times. This means this loops run for n*(n+1)/2 -1 times. So the time complexity would be O(n^2).
Anyhow it would result in TLE for greater length.

It is giving SIGABRT error because string r array is not large enough to store all the substrings that are being calculated in above nested for loops.
You can try increasing the size of this array.

I tried to increase the size of array, but after the size of 10^5 I am getting all testcases wrong. And upto 10^5 atleast partially got correct

Instead of using static array for storing strings, you can use vector<string> for storing those substrings.
It won’t give any WA (will also give you partially correct answer), but, it would result in TLE as the time complexity of your code is O(n^2).

1 Like

My submission:-

import math
def sieve_of_eratosthenes(n):
#returns all prime numbers upto n
array = [True] * n

result = []

result.append(2)
for i in range(4, n, 2):
array[i] = False;

for i in range(3, int(math.sqrt(n) + 1), 2):
if array[i]:
for j in range (i*i, n, i * 2):
array[j] = False;

for i in range(3, n, 2):
if array[i]:
result.append(i)
return result

pri=(sieve_of_eratosthenes(1000))
xy=[]
for i in range(len(pri)):
mn=bin(pri[i])
kp=mn[2:]
xy.append(kp)

for _ in range(int(input())):
st=input()
flag=0
for i in range(len(xy)):
if(xy[i] in st):
flag=1
break
else:
pass

if(flag==0):
print('NO')
else:
print('YES')