Re: List of integers L.I.S. (SPOILER)
Thank you both for your replies. And my personal Thank you! to Mr. Hettinger for all his tremendous work! Perhaps because you are not using a real Usenet client? Yes! And I don't even know what is the beast - Usenet client. I just keep in Favorites of my browser (IE 6.0) this link: http://groups.google.com/group/comp.lang.python/ -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Tim Peters wrote: The chance that Raymond Hettinger is going to recode _your_ functions in C is approximately 0 ;-) Who is Raymond Hettinger? -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
n00m wrote: Tim Peters wrote: The chance that Raymond Hettinger is going to recode _your_ functions in C is approximately 0 ;-) Who is Raymond Hettinger? See python-dev and, wrt this thread, http://docs.python.org/whatsnew/node12.html. Reinhold -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Got it! He is a kind of pythonic monsters. Btw, why it's impossible to reply to old threads? Namely, there're no more Reply link in them. Only Reply to author etc. -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
n00m [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] Who is Raymond Hettinger? The Python developer who, in the last few years, has perhaps been the most active in coding or recoding library modules, such as itertools and sets, in C. He also partipates in development discussions, helps with SourceForge tracker items (RFEs, bugs, and patches) and occasionally posts here, especially about his modules, for which he is the expert. Terry J. Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
n00m wrote: Got it! He is a kind of pythonic monsters. Btw, why it's impossible to reply to old threads? Namely, there're no more Reply link in them. Only Reply to author etc. Perhaps because you are not using a real Usenet client? Reinhold -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Tim Peters; INCREDIBLE~ 241433 2005-09-11 04:23:40 Tim Peters accepted 3.44 7096 PYTH BRAVO! I just wonder have I grey cells enough for to understand how your algo works... and hopefully it's not your last solved problem on the contester. I'm pretty sure they're using slower HW than mine (3.4 GHz P5). As I mentioned before their 4 identical machines are PIII Xeon 700MHz. PS: each accepted solution automatically gets into Best Solutions list. -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
[Tim Peters, on the problem at http://spoj.sphere.pl/problems/SUPPER/ ] ... [EMAIL PROTECTED] INCREDIBLE~ 241433 2005-09-11 04:23:40 Tim Peters accepted 3.44 7096 PYTH BRAVO! It's different now ;-) I added the two lines import psyco psyco.full() and time dropped to 2.29, while memory consumption zoomed: 2005-09-11 18:44:57 Tim Peters accepted 2.29 42512 PYTH That surprised me: my own test cases on Windows using Python 2.4.1 enjoyed the same order of speedup, but barely increased RAM usage. Perhaps they installed an older (or newer 0.9 wink) version of psyco. I just wonder have I grey cells enough for to understand how your algo works... You do! Work out some small examples by hand, and it will become clear; be sure to read the comments before the code, because they explain it. and hopefully it's not your last solved problem on the contester. I have to stop now, else I wouldn't do anything else 0.3 wink. ... -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Tim Peters wrote: [Bryan Olson, on the problem at http://spoj.sphere.pl/problems/SUPPER/ ] I never intended to submit this program for competition. The contest ranks in speed order, and there is no way Python can compete with truly-compiled languages on such low-level code. I'd bet money that the algorithm I used (coded in C) can run with the winners. I also think I'd wager that the Python version outright trumps them on code size. Oh, it's not that bad wink. I took a stab at a Python program for this, and it passed (3.44 seconds). [...] I didn't make any effort to speed this, beyond picking a reasonable algorithm, so maybe someone else can slash the runtime Hmmm ... I used the Theta(n lg n) algorithm ... how the heck... Aha! The 'bisect' module changed since last I looked. It still has the Python implementation, but then the last few lines say: # Overwrite above definitions with a fast C implementation try: from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect except ImportError: pass Binary-search is the inner-loop in this algorithm. I wrote my own binary-search, so I was executing Theta(n lg n) Python statements. Tim's use of bisect means that his inner-loop is in C, so he does Theta(n) Python statements and Theta(n lg n) C statement. The key to fast Python: use a good algorithm, and keep the inner loop in C. -- --Bryan -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
[Tim Peters, on the problem at http://spoj.sphere.pl/problems/SUPPER/ ] Oh, it's not that bad wink. I took a stab at a Python program for this, and it passed (3.44 seconds). ... I didn't make any effort to speed this, beyond picking a reasonable algorithm, so maybe someone else can slash the runtime [Bryan Olson] Hmmm ... I used the Theta(n lg n) algorithm ... how the heck... Aha! The 'bisect' module changed since last I looked. It still has the Python implementation, but then the last few lines say: # Overwrite above definitions with a fast C implementation try: from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect except ImportError: pass Binary-search is the inner-loop in this algorithm. I wrote my own binary-search, so I was executing Theta(n lg n) Python statements. Tim's use of bisect means that his inner-loop is in C, so he does Theta(n) Python statements and Theta(n lg n) C statement. That's part of it, but doesn't account for enough. If I disable the C implementation of bisect (replace the from ... import above with a pass), the program takes about 50% longer, which would still leave it well under the 9-second SPOJ time limit. That's without psyco. With psyco, it takes about the same time with the Python implementation of bisect as with the C implementation. Proably more important was my findall() routine. It does redundant work, and its runtime seems hard to analyze, but it's conceptually simple and actual timing showed it takes about a third of the time consumed by my crack() on random 100,000-element permutations. In fact, findall() takes very close to the amount of time needed just to read a giant line of input and convert it to a list of ints (without psyco; with psyco converting the input takes longer than findall()). Possible surprise: there's a simple trick that allows rewriting findall() to produce the result list in sorted order directly, instead of building it in random order and sorting it at the end. That made no measurable difference. The key to fast Python: use a good algorithm, Absolutely! and keep the inner loop in C. Usually ;-) Add another: especially for long-term maintenance, readability, stability and performance, use a library function instead of rolling your own. The chance that Raymond Hettinger is going to recode _your_ functions in C is approximately 0 ;-) -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Bryan Olson wrote: Could be. Yet you did write: It's incredibly fast! I just was obliged to exclaim It's incredibly fast! because I THOUGHT your first version handled ALL TEN testcases from the input. But the code read from the *20-lines* input *ONLY 2* its first lines. Usually they place heavy data testcase(s) at the end of the (whole) input. Like this: 3 2 3 1 7 4 5 6 1 2 7 3 ... ... ... 10 456 2 6789 ... ... ... ... ... 55444 1 ... 234 Surely producing an answer for list [2, 3, 1] will be incredibly fast for ANY language and for ANY algorithm. My first version bombed for the zero-length sequence. That was a mistake, sorry, but it may not be one of their test-cases. In my turn I can bet there's not an empty sequence testcase in the input. I wonder how many of the accepted entries would perform properly. Info of such kind they keep in secret (along with what the input data are). One more thing. They (the e-judge's admins) are not gods and they don't warrant that if they put 9 sec timelimit for a problem then this problem can be solved in all accepted languages (e.g. in Python). I never intended to submit this program for competition. Competition is not quite relevant word here. It just LOOKS as if it is a regular competetion. There nobody blames anybody. Moreover, judging on my own experience, there nobody is even interested in anybody. It's just a fun (but very useful fun). -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Bryan; My own version also timed out. And now I can tell: it's incredibly SLOW. Nevertheless it would be interesting to compare speed of my code against yours. I can't do it myself because my Python is of 2.3.4 version. Just uncomment your part. import bisect def oops(w,a,b): for m in w: j=bisect.bisect_left(a,m) a.insert(j,m) b.insert(j,max(b[:j]+[0])+1) def n00m(n,w): a,b=[],[] oops(w,a,b) v=map(lambda x: -x, w[::-1]) c,d=[],[] oops(v,c,d) e=map(sum, zip(b, d[::-1])) mx=max(e) f=[] for i in xrange(n): if e[i]==mx: f.append(i+1) print len(f) def one_way(seq): n = len(seq) dominators = [n + 1] * (n * 1) score = [None] * n end = 0 for (i, x) in enumerate(seq): low, high = 0, end while high - low 10: mid = (low + high) 1 if dominators[mid] x: low = mid + 1 else: high = mid + 1 while dominators[low] x: low += 1 dominators[low] = x score[i] = low end = max(end, low + 1) return score def supernumbers(seq): forscore = one_way(seq) opposite = [len(seq) - x for x in reversed(seq)] backscore = reversed(one_way(opposite)) score = map(sum, zip(forscore, backscore)) winner = max(score + [0]) return sorted([seq[i] for i in range(len(seq)) if score[i] == winner]) def b_olson(sequence): supers = supernumbers(sequence) print len(supers) import random, time n=5 w=range(1,n+1) random.shuffle(w) t=time.time() n00m(n,w) print 'n00m:',time.time()-t t=time.time() b_olson(w) print 'b_olson:',time.time()-t -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
[Bryan Olson, on the problem at http://spoj.sphere.pl/problems/SUPPER/ ] I never intended to submit this program for competition. The contest ranks in speed order, and there is no way Python can compete with truly-compiled languages on such low-level code. I'd bet money that the algorithm I used (coded in C) can run with the winners. I also think I'd wager that the Python version outright trumps them on code size. Oh, it's not that bad wink. I took a stab at a Python program for this, and it passed (3.44 seconds). It just barely made it onto the list of best solutions, which I also guess is ranked by elapsed runtime. The Java program right above it took 2.91 seconds, but ate more than 27x as much RAM ;-) I didn't make any effort to speed this, beyond picking a reasonable algorithm, so maybe someone else can slash the runtime (while I usually enjoy such silliness, I can't make time for it at present). I'll include the code below. Alas, without access to the input data they use, it's hard to guess what might be important in their data. On my home box, chewing over random 100,000-element permutations took less than a second each (including the time to generate them); I'm pretty sure they're using slower HW than mine (3.4 GHz P5). My first version bombed for the zero-length sequence. That was a mistake, sorry, but it may not be one of their test-cases. I wonder how many of the accepted entries would perform properly. No idea here, and didn't even think about it. Notes: the `all` returned by crack() is a list such that all[i] is list of all (index, value) pairs such that the longest increasing subsequence ending with `value` is of length i+1; `value` is at index `index` in the input permutation. The maximal LISs thus end with the values in all[-1]. findall() iterates backwards over `all`, to accumulate all the values that appear in _some_ maximal LIS. There's clearly wasted work in findall() (if someone is looking for an algorithmic point to attack). Curiously, no use is made of that values are integers, outside of input and output; any values with a total ordering would work fine in crack() and findall(). # http://spoj.sphere.pl/problems/SUPPER/ def crack(xs): from bisect import bisect_right as find smallest = [] all = [] n = 0 for index, x in enumerate(xs): i = find(smallest, x) if i == n: smallest.append(x) all.append([(index, x)]) n += 1 else: all[i].append((index, x)) if x smallest[i]: smallest[i] = x return all def findall(all): constraints = all[-1] allints = [pair[1] for pair in constraints] for i in xrange(len(all) - 2, -1, -1): survivors = [] for pair in all[i]: index, value = pair for index_limit, value_limit in constraints: if index index_limit and value value_limit: survivors.append(pair) allints.append(value) break constraints = survivors return sorted(allints) def main(): import sys while 1: n = sys.stdin.readline() if not n: break n = int(n) perm = map(int, sys.stdin.readline().split()) assert n == len(perm) supers = findall(crack(perm)) perm = None # just to free memory print len(supers) print .join(map(str, supers)) if __name__ == __main__: main() -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Bravo, Bryan! It's incredibly fast! But your code got WA (wrong answer). See my latest submission: http://spoj.sphere.pl/status/SUPPER/ Maybe you slipped a kind of typo in it? Silly boundary cases? -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Bravo, Bryan! Looks very neat! (pity I can't give it a try in my Py 2.3.4 because of reversed() and sorted() functions) And I've submitted it but got ... TLEs: http://spoj.sphere.pl/status/SUPPER/ Funnily, the exec.time of the best C solution is only 0.06s! PS In my 1st submission I overlooked that your code handles only 1 testcase (there are 10 of them); hence its 0.13s exec. time. PPS This is the code's text I submitted: #!/user/bin/env python from sys import stdin def one_way(seq): n = len(seq) dominators = [n + 1] * (n * 1) # dominators[j] is lowest final value of any increasing sequence of # length j seen so far, as we left-right scan seq. score = [None] * n end = 0 for (i, x) in enumerate(seq): # Binary search for x's place in dominators low, high = 0, end while high - low 10: mid = (low + high) 1 if dominators[mid] x: low = mid + 1 else: high = mid + 1 while dominators[low] x: low += 1 dominators[low] = x score[i] = low end = max(end, low + 1) return score def supernumbers(seq): forscore = one_way(seq) opposite = [len(seq) - x for x in reversed(seq)] backscore = reversed(one_way(opposite)) score = map(sum, zip(forscore, backscore)) winner = max(score) return sorted([seq[i] for i in range(len(seq)) if score[i] == winner]) for tc in range(10): _ = stdin.readline() sequence = [int(ch) for ch in stdin.readline().split()] supers = supernumbers(sequence) print len(supers) for i in supers: print i, -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
n00m wrote: Bravo, Bryan! It's incredibly fast! Not compared to a good implementation for a compiled, low-level language. But your code got WA (wrong answer). See my latest submission: http://spoj.sphere.pl/status/SUPPER/ Maybe you slipped a kind of typo in it? Silly boundary cases? Hmmm ... wrong answer ... what could ... ah! Here's a problem: I bomb on the empty sequence. Correction below. I'm not a perfect programmer, but I like to think I'm a good programmer. Good programmers own their bugs. If there's another problem, I need more to go on. From what you write, I cannot tell where it fails, nor even what submission is yours and your latest. -- --Bryan #!/user/bin/env python Python solution to: http://spoj.sphere.pl/problems/SUPPER/ By Bryan Olson from sys import stdin def one_way(seq): n = len(seq) dominators = [n + 1] * (n * 1) score = [None] * n end = 0 for (i, x) in enumerate(seq): low, high = 0, end while high - low 10: mid = (low + high) 1 if dominators[mid] x: low = mid + 1 else: high = mid + 1 while dominators[low] x: low += 1 dominators[low] = x score[i] = low end = max(end, low + 1) return score def supernumbers(seq): forscore = one_way(seq) opposite = [len(seq) - x for x in reversed(seq)] backscore = reversed(one_way(opposite)) score = map(sum, zip(forscore, backscore)) winner = max(score + [0]) return sorted([seq[i] for i in range(len(seq)) if score[i] == winner]) _ = stdin.readline() sequence = [int(ch) for ch in stdin.readline().split()] supers = supernumbers(sequence) print len(supers) for i in supers: print i, -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Oops Bryan... I've removed my reply that you refer to... See my previous - CORRECT - reply. The code just times out... In some sense it doesn't matter right or wrong is its output. Btw, what is the complexity of your algorithm? Currently I'm at work and it's not easy for me to concentrate on our subject. -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
n00m wrote: Oops Bryan... I've removed my reply that you refer to... See my previous - CORRECT - reply. The code just times out... In some sense it doesn't matter right or wrong is its output. If my code times out, then they are using an archaic platform. With respect to my code, you noted: Bravo, Bryan! It's incredibly fast! I myself did not claim 'incredibly fast'; but the code should beat the 9-second mark on any currently-viable platform, even if the machine were bought on special at Wal-Mart. For this kind of low-level challenge, Python cannot compete with the speed of C/C++, nor Ada, Pascal, ML, PL/1, nor even good Java implementations. Nevertheless, even in the rare cases in which efficiency of such computations is an issue, the Python solution is usually worthy contender, and often the superior solution. Human time is more valuable than machine time. Python emphasizes human-friendly code. Alas, I would be (and, since I did cite it, was) wrong on that. My code failed for the empty sequence. Wheter or not that was one of the test cases, and whether or not it was a consideration as the problem was defined, it was a bug. As I wrote: Good programmers own their bugs. Btw, what is the complexity of your algorithm? For a list of n items, time Theta(n ln(n)), space Theta(n). -- --Bryan -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
Oh! Seems you misunderstand me! See how the last block in your code should look: for tc in range(10): _ = stdin.readline() sequence = [int(ch) for ch in stdin.readline().split()] supers = supernumbers(sequence) print len(supers) for i in supers: print i, When I submitted it (for the 1st time) without for tc in range(10): the e-judge counted the output of your code as Wrong Answer; just because the e-judge got an answer for only the very 1st testcase (I think in it was not too large input data). -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
n00m wrote: Oh! Seems you misunderstand me! See how the last block in your code should look: for tc in range(10): _ = stdin.readline() sequence = [int(ch) for ch in stdin.readline().split()] supers = supernumbers(sequence) print len(supers) for i in supers: print i, Ah, I misunderstood the input. I thought they'd run it once for each of their test cases. Handling exactly ten inputs sucks, so how about: while True: if not stdin.readline().strip(): break sequence = [int(ch) for ch in stdin.readline().split()] supers = supernumbers(sequence) print len(supers) for i in supers: print i, print -- --Bryan -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
It also timed out:( 241056 2005-09-09 20:11:19 ZZZ time limit exceeded - 7064 PYTH Btw, have a look at this nicest problem: http://spoj.sphere.pl/problems/COINS/ My py solution takes #64 place among its best solutions: http://spoj.sphere.pl/ranks/COINS/start=60 -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
PS: ALL problems in problems.PDF file (weekly updated): http://spoj.sphere.pl/problems.pdf The friendliest online contester I've ever seen! JUST A NON-SUCH. -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
n00m wrote: It also timed out:( Could be. Yet you did write: It's incredibly fast! I never intended to submit this program for competition. The contest ranks in speed order, and there is no way Python can compete with truly-compiled languages on such low-level code. I'd bet money that the algorithm I used (coded in C) can run with the winners. I also think I'd wager that the Python version outright trumps them on code size. My first version bombed for the zero-length sequence. That was a mistake, sorry, but it may not be one of their test-cases. I wonder how many of the accepted entries would perform properly. -- --Bryan -- http://mail.python.org/mailman/listinfo/python-list
Re: List of integers L.I.S. (SPOILER)
n00m wrote: Firstly I find ordering numbers when moving from left to the right; then I find ord. numbers for backward direction AND for DECREASING subsequences: Sounds good. Btw, I did it in Pascal. Honestly, I don't believe it can be done in Python (of course I mean only the imposed time limit). http://spoj.sphere.pl/status/SUPPER/ Is there a platform specified? Below is an alleged solution in Python. -- --Bryan #!/user/bin/env python Python 2.4 solution to: http://spoj.sphere.pl/problems/SUPPER/ from sys import stdin def one_way(seq): n = len(seq) dominators = [n + 1] * (n * 1) # dominators[j] is lowest final value of any increasing sequence of # length j seen so far, as we left-right scan seq. score = [None] * n end = 0 for (i, x) in enumerate(seq): # Binary search for x's place in dominators low, high = 0, end while high - low 10: mid = (low + high) 1 if dominators[mid] x: low = mid + 1 else: high = mid + 1 while dominators[low] x: low += 1 dominators[low] = x score[i] = low end = max(end, low + 1) return score def supernumbers(seq): forscore = one_way(seq) opposite = [len(seq) - x for x in reversed(seq)] backscore = reversed(one_way(opposite)) score = map(sum, zip(forscore, backscore)) winner = max(score) return sorted([seq[i] for i in range(len(seq)) if score[i] == winner]) _ = stdin.readline() sequence = [int(ch) for ch in stdin.readline().split()] supers = supernumbers(sequence) print len(supers) for i in supers: print i, -- http://mail.python.org/mailman/listinfo/python-list
