6 kyu
Reducing a pyramid
161 of 252FArekkusu
Loading description...
Algorithms
Performance
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.
Great kata about performance and math.
This kata is about perfomance
This comment has been hidden.
This comment has been hidden.
Scala translation
my code is three lines and can't handle big data
You may need to upgrade your lines.
This comment has been hidden.
Write out the calculations for a small number (like 4) on a piece of paper, trace what factors appear and disappear from the coefficient and in what order. You'll see that you are still calculating way too much, and as numbers become huge, every operation counts!
This comment has been hidden.
for those, who are not familiar with Pascal Pyramid, this is definitely not 6 kyu
I made a linear solution, but it also fails the test .. maybe you could give advice? I have no one to ask, since I study everything on my own .. I would also like to say this is clearly not level 6. This task was worth devide into two, with and without a performance test.
You should post your solution in a comment so it could be reviewed. Maybe you're missing something, and your algorithm is not actually linear.
This comment has been hidden.
You're doing
reduce(...) // reduce(...) for i in range(...), that's a nested loop, henceO(n^2).done, Completed in 1037.57ms :)
This comment has been hidden.
Your second approach is correct, but the overall algorithm is bad. You have to make it fully linear.
I am getting errors in python where the answer is so big that python thinks it is +ve infinity. Anyone know how to solve this? My code completes all of the tests it can do very fast and I can see no way of making it more efficent.
Hi Can someone help me? My code has complexity about
O(n)but is timeouted. Might you give me some hints?it cannot be O(n) because the expected O(n) solution passes the tests in something like 2s. So you must have missed something that makes your code O(n²).
Nobody can give you any hints without seeing your code. As B4B said, the linear solution (if we ignore the fact that arbitrary-length math affects the performance) takes approximately
1 - 1.5 secin all languages, so your solution is a lot less efficient than you think.This comment has been hidden.
I don't think there's a library with such fuctionality available on CW.
I keep getting Response received but no data was written to STDOUT or STDERR in Python.
Your solution is inefficient.
Is there an error on the fixed tests with Javascript? I left the sample code unedited.
TypeError: Do not know how to serialize a BigInt at JSON.stringify ()
Evidently there are performance requirements... Input range or expected asymptotical complexity should be specified then.
Added a note in the description.
nisn't defined, but even assuming it'slen(base), arbitrary precision arithmetic can't be done in O(1) native operations...Indeed. Replaced that note with the performance tests specification to avoid this ambiguity.