Apr 2010
8 / 8
Apr 2015
Apr 2015
islandcoder_sof
Apr '10

Hi,

I was getting a TLE on spoj.pl/problems/VONNY/1 with an inefficient recursive solution. So, I fixed up the solution quite a bit, and still have a recursive set up. It now runs crazy fast.

I have randomly generated 1000 grids both totally randomly with cells from 0-6 (which is sort what the problem states), and also by simulating the layout of tiles (which is what I think the solution implies.) My solution runs the 1000 simulated tile down tests in a about 27 seconds with no exceptions on my workstation.

Is is hard to code to a black box. Can someone please advise on how to deal with this? Shall I post my solution?

  • created

    Apr '10

  • last reply

    Apr '15
  • 7

    replies

  • 568

    views

  • 4

    users

  • 1

    link

numerix
Apr '10

As you can see there are (only) two AC Python solutions for VONNY. So, it IS possible to solve it with Python, but it is NOT SO EASY to get it AC with Python because of
- large I/O
- recursion (not so fast in Python)
- perhaps not using optimal data structure
- not using psyco

As you can see looking at the memory usage, both AC solutions use psyco - you didn't. If I submit my solution without psyco, it runs out of time. So as I see it: This problem cannot be solved using pure python with a recursive approach.

Runtime of you workstation is uncomparable with the slow SPOJ servers. To get a hint to the relation in runtime, you could choose problem PRIC (challenge), which is not so difficult so "solve" and output 1101010 ... for about 20 SPOJ seconds - and then compare to your local time. Could be a shock open_mouth

If you are a Python beginner you should perhaps choose some problemsets, where runtime isn't a problem.

islandcoder_sof
Apr '10

Hi numerix,

Thanks for the reply and tips.

I noticed that someone has completed VONNY with 178M of memory running Java in 5.56.

I have added psyco, and it has gone from 27 seconds to do 1000 random tests on my location machine, to 8 seconds. Quite a speed up.

However, I get NZEC with .21 time and 37M of memory. Note, my solution is not running out of time, so I'm guessing pysco wouldn't be the answer.

I believe I have memory under control, I have a good fast implementation of recursion. I have reworked my data structures to make sure full scans of data are done as few times as possible. And I'm using pysco.

I will do PRIC like you suggest.

What is puzzling me is that I get a runtime error... I don't think it's running out of memory. I have run it with all manner of different sets of numbers, and it doesn't crash, blow up, or otherwise slowdown.

islandcoder_sof
Apr '10

I did PRIC in python. Initially I put it in a "while True" loop, because I interpreted the instructions to say let it run and the max correct answer you output is your score.

That didn't work. It produced a TLE. (A bit confused about that.)

So I limited it to 3000 numbers, and it completed. It took about 22 seconds. On my locat machine that takes just under 3 seconds. So, I see what you mean about the speed difference. I'll estimate that I need to be about 1/7th of the time limit when comparing against local runtime.

Gene

numerix
Apr '10

That was the idea ...

According to VONNY: It won't be a problem of memory. You'll have to post your code to get help with an NZEC. Or try once more on your own:
Take parts of your code into a try..execpt-clause until NZEC changes to WA, so you can find out, where the problem occurs.

islandcoder_sof
Apr '10

Excellent idea. I'm somewhat new to spoj, and figured lots of WA's would be a bad thing. So, I've tried not to use techniques like that to solve the problems. Am I wrong? Is a WA not a big deal?

25 days later
suteerth
May '10

Hi islandcoder, although spoj has a ranking system in place, please do not think about it as a contest but more like a place to practice.
And trying lots of techniques and experimenting with your code is the only way you will learn. WA is certainly not a big deal and in fact
even if you are worried about your rank, it wont be affected by the number of submissions so experiment away my friend. Tell you what,
you are thinking about WA's but lots of people on spoj including me resubmit code plenty of times even after getting ACCEPTED to make
it more and more efficient and cut down on the execution time.

As far as NZEC is concerned, you can post your code here if you want and I am sure there are many to have a look at it and help you.
Also if its getting a NZEC because of some boundary case, try to figure out such boundary cases and test your code on them.

Best of luck and please don't lose confidence in this site smile

4 years later
aron1
Apr '15

That could be odd in case correct. list1 += list2 is usually list1. extend(list2) plus the other is usually concatenation. Within the very first situation people modify list1, from the 2nd you receive a whole new checklist. Although both equally final results offer the identical components.