Timeline for A simple challenge
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 7, 2015 at 19:23 | comment | added | Tom van der Zanden | Yes, but please don't ask me to implement it because it would be really annoying :-) | |
| Sep 7, 2015 at 19:17 | comment | added | Elliot Gorokhovsky | Last bonus question: can your method be modified to find how many strings contain exactly 2 words? | |
| Sep 7, 2015 at 19:15 | vote | accept | Elliot Gorokhovsky | ||
| Sep 7, 2015 at 19:09 | comment | added | Elliot Gorokhovsky | OK, so if it was naively implemented it would take exponential time, but with memoization it's polynomial. | |
| Sep 7, 2015 at 19:07 | comment | added | Tom van der Zanden | The reason the time isn't exponential is because of \emph{dynamic programming} (this is a very important technique, you should learn it!). Intermediate values can be memorized and reused. You can download the source code here. You are right, to be completely correct $|\Sigma|$ should show up in the running time. I ignored it because it is small compared to the rest. | |
| Sep 7, 2015 at 18:59 | comment | added | Elliot Gorokhovsky | Why doesn't $|\Sigma|$ show up in the time complexity? | |
| Sep 7, 2015 at 18:51 | comment | added | Elliot Gorokhovsky | I don't understand why the time isn't exponential, though, because of the last case. Also, can you include a proof sketch? | |
| Sep 7, 2015 at 18:51 | comment | added | Tom van der Zanden | I'm sorry... :( | |
| Sep 7, 2015 at 18:49 | comment | added | Elliot Gorokhovsky | Now it's correct... unfortunately... | |
| Sep 7, 2015 at 18:44 | history | undeleted | Tom van der Zanden | ||
| Sep 7, 2015 at 18:44 | history | edited | Tom van der Zanden | CC BY-SA 3.0 |
Fixed the mistake.
|
| Sep 7, 2015 at 18:27 | history | deleted | Tom van der Zanden | via Vote | |
| Sep 7, 2015 at 18:10 | history | edited | Tom van der Zanden | CC BY-SA 3.0 |
deleted 3 characters in body
|
| Sep 7, 2015 at 18:07 | comment | added | Tom van der Zanden | Why don't we continue this discussion in the chat? | |
| Sep 7, 2015 at 17:44 | history | answered | Tom van der Zanden | CC BY-SA 3.0 |