I'm a python programmer and I genrally happens that some problem on CF does not have any submission in Python, it is either Python 2 or Python 3 but ...
This problem that needs simple dfs ( sorry for spoiler but right now I'm not asking for help in solution ) gives Run Time Error on test 15.
After failing to get several times on this problem , I went for the accepted submissions then I found most of them having same result as mine ( Run Time Error on test 15 ) and there is no Accepted solutions in Python.
I'm here to ask may someone correct or find the error why it is getting RE or tell me the exact reason.
Although this problem is from Educational Round 1.
I don't know at that time CF allows submissions in python or not. Somehow I managed to get AC using C++.
Sorry for my poor english. Thank You.
You've just found one of the biggest gripes I have with Python. It is completely worthless at recursion. What do you think the default recursion limit is? Maybe 107 or 108? NOPE, it is 1000.
It is possible to change this number by using sys.setrecursionlimit() but the problem is that this limit is set because of a reason. Not only are function calls slow in Python but it uses a ton of memory, it is so bad that by default they've forced the recursion limit to only be 1000. I'm not entirely sure of the details, just know it is really bad.
So how do you do something as easy as a dfs in Python? The way I do it is that I manually use a stack. For example I changed your code into this and now it passes. Didn't do much more than removing the recursion. This is the only way I've been able to implement dfs algorithms in Python. I don't like this solution but as I said this is my biggest gripe with Python.
I just did sys.setrecursionlimit(10^6) and 10^7 and 10^8 again it is showing RE. :(
That is my point, even if you change the recursion limit it wont work. With the recursion limit set high then maybe it will handle a depth of 10000 before crashing, but it will never get up to 106 or 107.
I haven't seen anything wrong with your code other than Python being bad at deep recursion.
now I got it thanks.
But this works
My Solution is great now
Hope you don't mind it :)
No problems =)
However note that there are two reasons to not write DFS this way:
It doesn't look nearly as clean as doing it with function calls.
If you ever want the DFS to return a value, like for example if you want to count the number of nodes in a tree, you are going to have a problem switching out recursion by having your own stack in this way. There are still ways of doing it but it's messy.
I'd say that if there ever is a time you really need to do deep recursion, then don't use Python.
This may be today's last.
I was solving this problem
I just used acos(-1) for pi and took atan2(y,x) for the angle made by x-axis
Submitted my solution but got WA on test 127.
Then I check the case where the angles difference between two vectors was something like ~10^(-10) and it can not observe that difference.
The atan2 function return a float value that is 16 places after the decimal and I was unable to get Ac with that.
The same logic implemented in C++ just using atan2( (long double) y , (long double) x).
Just wondering how can I get these float values till that decimals places which I wants.
I can print with it using str.format() but it changes out decimal values to string that can not be used to get difference.
Any method to get more precise value of float in python Sir?
The problem is that c++ got long double but python only have double (called float in Python), long double is dependent on what system you use so I guess that Python didn't want to bother with that. Note that double only got like 16 digits of precision, so I don't think it is a good idea to look at more digits than that.
The way I would solve that problem is to not directly calculate the angle, but instead calculate cos(angle)^2 using scalar products, as that can be done completely using integers, it is a rational number.