5 kyu
Jump to zero (Subtask 4)
51 of 60TLEojxSunlight
Loading description...
Mathematics
Algorithms
Dynamic Programming
Performance
Number Theory
View
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
javascript translation
4kyu imo
In Python
;
is not used as line terminator. It is a separator user to fit multiple lines into one.;
should be removed from initial solution (2 places):return ans;
fixed
Do not print the input and output to the console for arrays that are bigger than
1000
elements or such. It gives aMax Buffer Size Reached (1.5 MiB)
and makes it impossible to debug and check the sizes of the lists that are being passed (this should be in the description).There are tons of kata which pass large arrays as inputs, are you saying this warning should be added to all of them?
Yes, I do believe that ideally every Python kata with large arrays as input should hide them when they are too large. Of course, it's difficult to fix every single one of them, but that doesn't undermine the concern.
If you wish, you can look for every single kata with this problem and leave this same issue there, I believe my point stands.
Sorry, I misunderstood your first post. I thought you were saying the author should add a warning to the description that warns users not to print every input. I see now that you meant that the tests should not output the full contents of very large arrays.
Oh, I understand. No worries my wording could have been better.
Yeah, that warning would be very unnecessary. What the user does is their problem.
Is this for Python, I don't see such logs?
Yes, this is regarding Python. Just have a solution like
jump_to_zero = lambda x: x
and hit attempt. It will reach max buffer size.Lua translation!
was approved some time ago
Amazing coding challenge to exercise some really interesting programming concepts with.
Please change the subtask url, don't make it directly open the trainer since it would be better for the user to read the constraint/problem first and let the user decide whether they want to train on the kata or not.
done
It's interesting you like to show us how to keep improving an algorithm. But using 6 different kata's it's unmaintainable to guard kata's against solutions from more advanced versions of the kata.
I suggest you only upload kata 4 (normal version) and 6 (extreme version).
I hosted a contest in my page (TLEoj) and I saw my contestants stuck in different subtasks except subtask 3 (maybe nobody use dp top-down, you can check the ranking of that contest here: https://tleoj.edu.vn/contest/024/ranking/ , problem 5). So that I think 6 katas for 6 subtask is ok to test how good you can impove your algorithm. This is such a nice problem that i think the points for solving a 1-kyu problem is not enough =))) You can try to solve the 6th subtask :D
Anyway, I think I will not post the subtask 5 because of the memory limit. In my page subtask 5 n will be up to 10 ** 9 and this will lead to a memory limit exceed if you use an array of a billion integers. But to make this problem suitable with Python language, I have to reduce the limit and subtask 5 will not be any tricky.
Thanks for your suggestion.
Maybe I can unpublish subtask 2. I think it can be tricky to improve the sum digit count from subtask 3 to subtask 4.
It's impossible for mods to constantly monitor 6 kata's and hide solutions that spoil other versions of the kata. Hence, I strongly suggest you pick at most 2 of the 6 kata's, and unpublish the others.
"So that I think 6 katas for 6 subtask is ok to test how good you can impove your algorithm"
Solutions from subtask 3 and 4 cannot solve subtask 1, so that I think publish subtask 1 is okay. I unpublished subtask 2 and maybe I will unpublish subtask 3 too.
Thanks for your suggestion.
6 versions of the same concept are definitely not going to work. I would suggest to keep 1 (questionable), 3/4 (pick one), and then 6 (whatever that is...).
Subtasks 4 and 6 seem enough to me as well. The techniques involved will be suitably different.
Subtask 4 could check the candidate solutions for "over-performance": if the solution passes huge inputs too quickly, it can be failed, with a suggestion to use a simpler algorithm. I faintly remember one of myjinxin's katas doing something similar. (Edit: I realized such a test won't be trivial to implement.)
If you use the solution of subtask 6 to solve subtask 4, it will return the
Time limit exceed
verdict, since it has to precalculate a lot of things and has a big complexity per query with both small and large number.