#152 Latin Square Slicing

[clgv]

Problem #152 "Latin Square Slicing" always times out on me.
I already tried to optimize runtime to make it pass in time.

On my machine my solution needs less than 700ms for all test cases on a fresh REPL on the first run (much less for consecutive runs).

How big is the timeout there? Is the timeout per test case or on the whole set of test cases?
I would love some feedback on how much time my solution needed per test case to see where it times out on the server.

Greetings.
Gunnar

[clgv]

I have the same timeout problem with #124 "Analyze Reversi".
This time my code runs in less than 30ms on my machine but times out on 4clojure.

[hak]

Am Sonntag, 8. Juli 2012 16:12:29 UTC+2 schrieb clgv:

I have the same timeout problem with #124 "Analyze Reversi".
This time my code runs in less than 30ms on my machine but times out on 4clojure.

 

Same for me with #117 (For Science!)  runs in 30ms on my laptop with clojure 1.3.0, but always times out on 4clojure

[ctzsm]

I am stuck with the same question.

my solution to problem 152 runs very fast now, and it takes only 30+ms on ideone.com and in my REPL

Even in the slowly lighttabel, it takes just 110+ms.

If you solved this problem, could you please give me some hint?

[ctzsm]

OK...I had passed the problem one hour ago. my solution need 27ms to the last test case on ideone.com now. 

but what surprised me is that other people's solutions need more than 100ms (some need 600ms) to the last test case on ideone.com.

That means I should passed this problem yesterday, because my first edition of this problem's solution need less than 600ms to the last test case.

[fbmnds]

my solution took 3.79s on ideone.com (http://ideone.com/3HtuO3); I used mapv from clojure 1.4.0

[fbmnds]

My updated solution took 2.18s on ideone (http://ideone.com/lNdPZ6) which relates to 600ms on my T61p, obviously not good enough to pass on 4clojure.

@ctzsm: would you mind to share your solution strategy?

Am Montag, 1. Oktober 2012 10:31:33 UTC+2 schrieb ctzsm:

[fbmnds]

The accepted solution of _pcl takes 1.88s (http://ideone.com/L96buo) versus mine taking now 2.05s (http://ideone.com/cLGx2u), which is still rejected, although the solutions were clearly on par with ~360ms on my laptop during several tests. 

Any comments on the time out threshold?  

[ctzsm]

Hi,

There is a function 'time' in the core of clojure, so I always use it to test my codes' time costs.

I think it's more accurate than ideone's estimation method, therefore the 2.05s on ideone may just cost hundreds of msecs.

If you really want to know my method, it's just based on an obvious observation.

The original idea to the problem is to check all the matrices the square contains.

But in fact, to the big data, most of the matrices doesn't contribute to the answer, they are redundant.

So in order to decrease the time, you can just check some of the matrices.

Then there is a question. How to know which set of matrices we need?

If you have some experience in random algorithm, that's it.

Yours.

[fbmnds]

Hi ctzsm,

thank you for sharing the hint on random algorithms which lack experience with. This explains your super fast solution.

With ~360 ms on my T61p it is 10x slower than yours, but on par with other already accepted solutions (~200ms and ~380ms on my laptop). I think you mentioned in a former post that your first solution was accepted with a runtime of ~600ms.  

I added the timing information on ideone.com because it might be interesting for those who are using that platform. In other threads of this forum, this is information is also shared as a reference, as 4clojure only provides passed/failed. 

It is kind of frustrating not to know what the time limit of a problem is. It should be part of the problem description. 

If 4clojure were more education oriented than a competition platform, a less restrictive time limit would be reasonable. I think, the run time of solutions would be better reflected in the ranking. 

Bye,

-fb

[ctzsm]

Hi,

Yes, I agree with you, the time limit should not be that strict, I think there is something wrong with the sandbox of 4clojure.

Hope the administrator can fix it.

For the time limit or even memory limit, I think the developers can learn from such as poj.org, acm.sgu.ru, or other online judge websites.

BTW, I mentioned the time function, I mean to use it on ideone.com. :-)

Yours.

[0x89]

On Wednesday, November 14, 2012 2:34:27 AM UTC+1, ctzsm wrote:

  I think there is something wrong with the sandbox of 4clojure.

 

Yes, it is probably a clojail issue, see  https://github.com/4clojure/4clojure/issues/66 and https://github.com/4clojure/4clojure/issues/211

So if you are just looking for a workaround, do not use the for macro. It can be replaced by (much uglier) combinations of map, mapcat, filter and take-while, e.g.

(for [a collection-a

       b collection-b]

   [a b])

Is the same as:

(mapcat

  (fn [a]

    (map

      (fn [b]

        [a b])

      collection-b))

  collection-a)

Other constructs, like Math/pow, Math/sqrt might also slow things down.