38
Awesome Team
Stefan Pochmann
http://www.stefan-pochmann.info/
Last seen 15 hours ago
Member for 9 years, 2 months, 2 days
Difficulty Normal
Recent solutions I'm happy with (just starting/trying this):
[Words Order](https://py.checkio.org/mission/words-order/publications/StefanPochmann/python-3/short-dict-subsequence/share/5bbb2df54ec5a810d36d7f70ae7e92da/)
Dang it no markdown here?
First one is my simplification of agave’s, see [here](https://leetcode.com/problems/ugly-number-ii/discuss/69397/Sharing-very-simple-and-elegant-Python-solution-using-heap-with-explanation/71469).
More
Binary search. Takes almost no memory at all. Solved n=10^6 in 0.35 seconds and n=10^9 in 15 minutes on a 2.25 GHz CPU.
More
Solved n=10^6 in 0.07 seconds and n=10^9 in 120 seconds on a 2.25 GHz CPU (using 493 MB memory for 10^9).
The following version is my fastest, solved n=10^9 in 114 seconds, but it's more complicated and I don't like it much. It simulates the main deque with two lists.
```
from collections import de
More
Binary search. Takes almost no memory at all. Solved n=10^6 in 0.35 seconds and n=10^9 in 15 minutes on a 2.25 GHz CPU.
More
Solved n=10^6 in 0.07 seconds and n=10^9 in 120 seconds on a 2.25 GHz CPU (using 493 MB memory for 10^9).
The following version is my fastest, solved n=10^9 in 114 seconds, but it's more complicated and I don't like it much. It simulates the main deque with two lists.
```
from collections import de
More
Checked all solutions, didn't see anybody doing this. Even though quite a few people used the inefficient `a = a[:-1]`. Weird.
More
Very nice, and you inspired me to write a [min version](http://www.checkio.org/mission/gcd/publications/StefanPochmann/python-3/min-/) :-)
More
Shorter (by 6 chars) version:
```
len({*accumulate(discs[::-1], max)})
```
More
I sweep two "/" diagonals from the top-left corner and from the bottom-right corner until they meet in the middle.
`d` tells how many of these diagonals are free (0, 1 or 2).
`e` tells how many of the "\\" diagonals intersect the two "/" diagonals and are free.
More
This is an optimized version of this already fast solution:
```python
def count_discs_loop(discs):
count = R = 0
for r in reversed(discs):
if R < r:
R = r
count += 1
return count
```
That one updates the largest radius `R` and the `count` every time a la
More
I expect all solutions to be O(1) and I don't think Speedy solutions are particularly interesting in this mission, but then someone else posted one so here is mine :-)
Was among the fastest in my testing (executed on CheckiO):
```
1.26 ± 0.00 ms flights1b2
1.26 ± 0.00 ms flights1c
1.26 ± 0.00
More
Using `Decimal` circumvents the length limitation for `int`-to-`str` conversion.
More
We should have a "Tardy" category for highly inefficient solutions like this :-P
More