I am getting Runtime Error in the problem "PINBS"

1

Problem Link:-

My solution link :- CodeChef: Practical coding for everyone

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

2

Out of bounds access for the following test input:

1                
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1 Like
3

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

If I use this input , output says YES
1
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Please help

4 
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[10000] 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.

5

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

6

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).

codechef
codechef1205×950 35.9 KB

1 Like
7

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')