Hackerearth May circuit 2019

help
, ,
7

Can you share one recursive dfs-based python solution ?

Most of them are iterative dfs.

8

I am using recursion and code is of O(n) complexity.

import sys
sys.setrecursionlimit(2000000000)
def trav(st,end,par):
global s,ss
ind=st+1
while ind<end:
node=s[ind]
del s[ind]
ss[node[0]]=par+1
if node[1]-ind==1:
ind=node[1]
continue
else:
trav(ind,node[1],node[0])
ind=node[1]

n=int(sys.stdin.readline())
st=list(map(int,sys.stdin.readline().split()))
end=list(map(int,sys.stdin.readline().split()))
co=0
s={}
for i,j in zip(st,end):
if i==0 and j==n:
root=co
s[i]=[co,j]
co+=1
del st,end
ss={root:0}
trav(0,n,root)
for i in range(n):
print(ss[i],end=" ")
print()

My approach is right as I am getting no WA but RE(SIGSEGV) on 4 test cases.Like most take test cases took more than 1 second to solve but these with RE stop before 0.5 second only. Can you tell why SIGSEGV occurs and why is it occuring in my case

9

hello, I’m able to solve this with full 100pts…Yes, there is some error in the test cases I don’t know because when I submit the code in c++14 then it got AC and when I submit the same code with python3, Java8, C it got RE in 2-3 test cases…

BTW the question was quite easy …One simple recursive dfs will able to give to AC in just O(N) time complexity…

you can check my solution here…

link:

10

Well I mentioned the reason -

Your code is OK.

Its because of stack Overflow Error.

11

I think this contest is quite good for me …I’m able to solve all 8 questions this time (only 1 question with 52pts)

but the explanation of problem statements was terrible this time…every question have some amount of ambiguity in the statements…

1 Like
12

There is no error in test cases.

13

yes, but I don’t know why it fails on other programming language other than c++14

14

even in C language it was failed and got RE…(don’t know the reason till now!!)

15

I don’t know about C but for Java and Python, I’m preety sure.

1 Like
16

I think you can Unlock any problem without solving it…but it will cost to detect all your marks from that question

17

here is my recursive python 3 code…but RE in 5 test cases:

18

Yup, this is what I mean to say. Try with iterative DFS and it will run fine with all AC.

2 Likes
19

but I don’t think Iterative solution to the problem of this type was good practice…

I think HackerEarth need to resolve this problem…

BTW thanks…I never expect these type of errors…

20

Ikr… I would rather solve it before unlocking… will get back here if I get any other reason for runtime error

21

This is strange… If c++ passes why not c

1 Like
22

this is the reason…

23

In short, recursive solution is the reason for the RE (stack overflow)

24

solution in C:

same solution in C++:

25

Yeah I read everything but then why is c++ solution passing ??

26

that’s an HackerEarth thing…so much c++ centric