On Monday, May 7, 2018 at 11:12:02 AM UTC-5, Pablo Heiber wrote: > Hi everyone, > > > I won't comment on specific solutions, but I just want to let you all know > that our policy as to what is possible to pass remains the same: for most > problems, especially in earlier rounds, we aim to make sure they can be > passed with most languages. In this particular case, we do have solutions in > Python that pass comfortably without using any special optimization, and I > have no idea why yours wouldn't if the complexity is indeed the expected one. > > > However, as we have stated in the past, using faster languages does give you > an advantage some times, and it's possible that in some problems you have to > work harder to have them in Python, either by doing constant optimizations or > by just requiring the linear solution while the n log n passes in C++ (just > an example, does not apply to this problem). Notice that Python has its own > advantages (like built-in long integers and lots of string and list > manipulation functions) so knowing multiple languages will give you an even > bigger advantage by letting you chose which one to use for each problem. > > > As a final note, remember than in at least some languages some ways of > reading input are (somewhat surprisingly) a *lot* slower than others, so you > might want to check which one you use for your language or languages of > choice. > > > Best, > Pablo > > > On Mon, May 7, 2018 at 8:54 AM David Bradley <debr...@gmail.com> wrote: > So I became a bit obsessed yesterday tying to get this to pass. Late last > night, I finally got a solution that barely passed. My solution inverts the > order of the two variables vs. your solution (stack height vs. "first i" > ants). My key function is shown below. > > > > def solve(inp) : > > (n,w) = inp > > w6 = [6*x for x in w] > > dp = list(itertools.accumulate(w,min)) > > for stackSize in range(2,n+1) : > > olddp = [1e99] + dp[:n] > > candidates = [ 1e99 if x6 < odp else x + odp for x,x6,odp in > zip(w,w6,olddp) ] > > dp = list(itertools.accumulate(candidates,min)) > > if dp[-1] == 1e99 : return "%d" % (stackSize-1) > > return "%d" % n > > > > The performance key was to try to accomplish work that was normally done in > "inner" loops with itertools.accumulate or list comprehensions. > > > > I would be very curious as to why the problem posers selected a time limit > that made it very hard to make python solutions pass. Is there really a > competing "inferior" algorithm that required these limits for C++? > > > > More generally, Code Jam has a tradition with being quite tolerant of a wide > range of programming solutions (with historical 4/8 minute limits). With the > loss of the "multiprocessing" trick python trick for parallelism, and with > these tight time limits (perhaps without good reason?), I'm afraid that > python will be at a significant disadvantage vs. the past. > > > > -- > > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code...@googlegroups.com. > > To post to this group, send email to googl...@googlegroups.com. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/8d808d8f-be39-4f39-85e2-004f43c8ba70%40googlegroups.com. > > For more options, visit https://groups.google.com/d/optout.
Could someone tell me what those slow-input-output languages are? Just wanted to make sure I don't accidentally use them for large IO problems. Thanks! -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/ab2785cc-8e94-423c-8606-519bb0aceba5%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
