Discussion @ 1425. Queen 2 @ Timus Online Judge

if n=1 Alexander Kouprin 8 Apr 2007 16:09

What I must write if n=1?
Please, give me answers for tests:
1 1
1
(yes, it's uncorrect ;)

1 2
1

1 3
1

1 4
4

Edited by author 08.04.2007 16:10

Re: if n=1 KIRILL(ArcSTU) 8 Apr 2007 19:37

Hi evil cheater!:)
my prog out
1
3
4

Re: if n=1 Alexander Kouprin 8 Apr 2007 20:19

Hi, friend! =)
My prog out 1 3 4 too, but I get WA#6.
I using hash.
You have any good (or evil :) tests for me?
And what answers for this:

5 2
1 1 1 1 1
-> 22

4 12
1 5 3 5 11
-> 1781

5 45
18 33 1 1 45
-> 41312

n=2
-> s*s

Edited by author 08.04.2007 20:31

Re: if n=1 KIRILL(ArcSTU) 8 Apr 2007 21:36

http://acm.timus.ru/forum/thread.aspx?space=1&num=1425&id=14845&upd=633082670369048750

5 2
1 1 1 1 1
my prog: 16

It's hard problem for hash
I losed much time for it
try to store all positions

:) Alexander Kouprin 8 Apr 2007 22:30

I solved it!

It's not hard as you think.
Using hash, you must deleting 1-step queen places only.

My time is 1.687
Thanks!

Re: :) Denis Koshman 15 Aug 2008 18:47

There're about 3e+6 positions before reduction to 1e+6. So, it's too compacted for hasing. You'll either get TLE or ML, or you're lucky :)

My solution eats 2.4 sec, but it spends most of its time inside qsort. And I couldn't do any bucketing due to ML :(

Discussion of Problem 1425. Queen 2