6 ms·
My answers in 31 lines of code: https://gist.github.com/1025860 https://gist.github.com/1025860 I am either misreading the third problem's description, or I ha
by llimllib 15y ago
My answers in 31 lines of code: https://gist.github.com/1025860 https://gist.github.com/1025860
I am either misreading the third problem's description, or I have a bug I can't for the life of me see, because the answer my program puts out is not accepted.
- DanielStraight 15y agoThe third problem is looking to partition the entire sequence of numbers into contiguous subsequences, all of which add up to the same sum. In other words, if the list were 23415, you subsequences could be 23, 41 and 5, all equaling 5. But the subsequences have to use up the entire string and they can't overlap.
- hugh3 15y agoDid anyone else do that one without writing any code?
- genesiss 15y agoYou mean with smart guessing? That's no fun!
- hugh3 15y agoYeah. It took me three guesses to get it right. :)
- wbhart 15y agoYou didn't need 3 guesses. The sum of each partition has to be a factor of the number. In particular the sum of the first partition has to be a factor. Then the second. That already gives you the answer I think.
- hugh3 15y agoSure, but then I'd actually have to look at the numbers. My solution works without having to download the file! ;)
- deleted 15y ago[deleted]
- llimllib 15y agoThey can't overlap! I don't think the problem specifies that? You have to interpret "break up" to mean "non-overlapping" to claim that the problem means what you're saying it means; I found 341 "contiguous subsequences such that the sums of each of the subsequences are equal", but they overlap. (If you had said "partition" I suspect I would have got what you meant)
- DanielStraight 15y agoContiguous implies non-overlapping.
- apaprocki 15y ago> #pip install python-levenshtein > from Levenshtein import distance That doesn't seem in the spirit of the challenge.
- ithayer 15y agoCan you do it in linear time in the length of the input?
- drdo 15y agoIt's not hard to prove that that's impossible
- ithayer 15y ago:) I meant linear, but I'd review a proof :)
- amalcon 15y agoIt's possible if RAM isn't a constraint, using a bitset of all possible five-letter strings. The bitset would take up 4G of RAM (128G for extended ASCII, more for unicode). In practice, that would actually be slower on this input, because of the cost of initializing the bitset. But that is not dependent on the input, so computational complexity is unaffected. edit: Removed description. Yes, you're right, you can't even look at the whole input in constant time.
- kilburn 15y ago