I use pairwise because I always import itertools. I'm not sure it's really better than zip(arr, arr[1:]) - just a bit more explicit about what it's doing. (If you have a just a single-pass iterator you'll want itertools.pairwise of course.)
For part two, if you spot an issue at an index, you only need to test removing that index or the next, and if the faulty index is 1, you additionally need to check index 0 because that determines the asc/desc. So, unless the issue is at index 1 to 2, you only need to check 2 variations
Great video! I really enjoy looking at your solutions after solving the challenge. One small comment: for the second part, I think there is no need to test for each subsequence of n-1 elements. While verifying if a report is valid, we can examine each level one by one and decide whether to include it in the sequence or ignore it, based on whether it’s safe. This way, with a single pass, you can decide whether there exists a valid subsequence or not. By having a counter, you can easily keep only sequences that are safe when removing 0 or 1 elements. The only special case is when the first level needs to be removed, which requires separate handling.
I myself initially went for a single pass solution, but the logic I tried implementing ended up being a lot more complex and cost a lot more time than just testing each subsequence would have cost me.
@@YuumiGamer1243 What logic did you use? In my case, it isn't much more than what is in the video, and indeed, after checking both codes, I get ~2.5x faster.
@@kayebennett7867 Definitely not the best way: I kept track of what locations had a problem, and if there was only a singular location that had a problem, both on going only up or only down, and no more difference than 3, I removed the element on the location - 1, and the location (because of the way the comparisons were done either could be the issue). And just looped through both again. my brain didn't really manage to figure this one out properly nor quickly. So the time I ment wasn't about the execution time, rather the time to write it. writing this one brute force would have been a lot faster.
I like your idea, but had a hard time on deciding on the definition of a 'bad level'. For instance, in `7 1 4`, which level is 'bad'? Is it 7 or is it 1? It seems to depend on what direction you deem 'good', either ascending (`1 4`) or descending (`7 4`).
this is clever; i may discuss optimizations in future videos; it's not really worth it at this scale this early on for these inputs but a single-pass solution was definitely possible and would be an interesting segment. i usually focus on strategies that are good for the competition primary objective, but it's worth looking into some alternative focus areas. thanks for the comment!
yep, of course! i upload python videos because that is the language i use for this competition, but any language is allowed! you only need to provide an answer; a mix of languages, working parts of it out on pen and paper, or any other method you can think of are all allowed!
you can also use pairwise instead of zip with 2 arrays
I use pairwise because I always import itertools. I'm not sure it's really better than zip(arr, arr[1:]) - just a bit more explicit about what it's doing.
(If you have a just a single-pass iterator you'll want itertools.pairwise of course.)
Your Python is just next level.
pause
Thank you so much for this additional explanation! It's very helpful, I really appreciate it!
For part two, if you spot an issue at an index, you only need to test removing that index or the next, and if the faulty index is 1, you additionally need to check index 0 because that determines the asc/desc. So, unless the issue is at index 1 to 2, you only need to check 2 variations
Great video! I really enjoy looking at your solutions after solving the challenge. One small comment: for the second part, I think there is no need to test for each subsequence of n-1 elements. While verifying if a report is valid, we can examine each level one by one and decide whether to include it in the sequence or ignore it, based on whether it’s safe. This way, with a single pass, you can decide whether there exists a valid subsequence or not. By having a counter, you can easily keep only sequences that are safe when removing 0 or 1 elements. The only special case is when the first level needs to be removed, which requires separate handling.
I myself initially went for a single pass solution, but the logic I tried implementing ended up being a lot more complex and cost a lot more time than just testing each subsequence would have cost me.
@@YuumiGamer1243 What logic did you use? In my case, it isn't much more than what is in the video, and indeed, after checking both codes, I get ~2.5x faster.
@@kayebennett7867 Definitely not the best way: I kept track of what locations had a problem, and if there was only a singular location that had a problem, both on going only up or only down, and no more difference than 3, I removed the element on the location - 1, and the location (because of the way the comparisons were done either could be the issue). And just looped through both again.
my brain didn't really manage to figure this one out properly nor quickly. So the time I ment wasn't about the execution time, rather the time to write it.
writing this one brute force would have been a lot faster.
I like your idea, but had a hard time on deciding on the definition of a 'bad level'. For instance, in `7 1 4`, which level is 'bad'? Is it 7 or is it 1? It seems to depend on what direction you deem 'good', either ascending (`1 4`) or descending (`7 4`).
this is clever; i may discuss optimizations in future videos; it's not really worth it at this scale this early on for these inputs but a single-pass solution was definitely possible and would be an interesting segment. i usually focus on strategies that are good for the competition primary objective, but it's worth looking into some alternative focus areas. thanks for the comment!
I thought I knew python pretty well, before I saw any of your videos. Thank you for the great explanation!
love this series 🔥
holy crap this she can dev
I solve this using the Longest Increasing Subsequence algorithm
Great explanation as always!
great teacher!
can this be done in C language ?
yep, of course! i upload python videos because that is the language i use for this competition, but any language is allowed! you only need to provide an answer; a mix of languages, working parts of it out on pen and paper, or any other method you can think of are all allowed!
@hyper-neutrino thank you , btw your explanation and python skills are really great . I learnt something new today . Thank you for sharing 😁