Correct idea is HERE
Just use diagonal painting:
1 2 3 ... k ... (total n times)
2 3 4 ... 1 ... (total n times)
. . . ... . ... (total n times)
Calculate, how many 1,2, ... k in this table. Answer will be minimal
of them(every rectangle 1xK covers K different colors).
I don't no is this mathematically correct, but this solution got AC.
Don't forget, that if N < K answer is 0.
P.S. Sorry for bad English.
Thanks!I got AC.
Posted by
Tony 8 Jun 2003 13:15
> Just use diagonal painting:
> 1 2 3 ... k ... (total n times)
> 2 3 4 ... 1 ... (total n times)
> . . . ... . ... (total n times)
> Calculate, how many 1,2, ... k in this table. Answer will be minimal
> of them(every rectangle 1xK covers K different colors).
> I don't no is this mathematically correct, but this solution got AC.
> Don't forget, that if N < K answer is 0.
> P.S. Sorry for bad English.
Not the simpliest way, my solution is O(1) and I can prove it. (-)
Can you please tell more about it?
email me: caa@baga.ac.net.ru
I want to know fast solution too !
>>> vasilisk_voin@mailru.com
Thank you.Your algorithm makes me come up with a O(1) idea.But why the minimal color is the answer?
Because each 1xK rectangle contains K cells, colored in different K colors.
Re: Correct idea is HERE
Posted by
Nilrem 28 Oct 2005 21:55
Can anybody give me example for this table?Please...
For example what table will be if n=5 k=3 ?
Re: Correct idea is HERE
if N=5 and K=3 the correct answer is 8 but not 7. To see the solution don't use the square (3,3) in the 5*5 grid
Edited by author 13.11.2005 13:39
Edited by author 13.11.2005 13:39
Re: Correct idea is HERE
Posted by
svr 31 Dec 2007 10:18
Why such found minimal value really
achivable in all cases?
Re: Correct idea is HERE
Posted by
maksay 3 Jan 2008 18:41
its because for each number in the table there you can put 1*K piece so that it won't intersect with others.And answer is minimum value because each piece lays on K diffirent numbers so you can't put more pieces that numimum value of 1...k
PS. Thanks! It's really easy to solve with O(1) time with your tips!
Re: Correct idea is HERE
Posted by
svr 3 Jan 2008 20:00
This is only your belive...
Told property has only minimal number.
Re: Correct idea is HERE
please tell your idea more in detail
Re: Correct idea is HERE
Posted by
hoan 21 Nov 2010 19:53
thanks, i got AC when i use your idea.
but i dont why it's true?
who's know?
Re: Correct idea is HERE
THE PROOF
1) if you "stack" the coffins, you use up all of the graveyard, except for N%K square in the corder.
2) if you "spiral" the coffins, you leave N-2(N%K) square in the middle after the first spiral, N-4(N%K) square after the second spiral, until you use up all of the graveyard, except for (N-2(N%K))%K square in the middle.
(N-2(N%K))%K = (-N)%K = K-N%K
3) if we use the better of the two strategies, we use up all of the graveyard, except for M=min(N%K, K-N%K) square. How many colors will it have?
The first row will be colored 1..M, the second 2..M+1, the last M..2M-1
All K colors will be present iff 2M-1>=K
4) M=min(N%K, K-N%K) guarantees M<=K/2
Therefore, the remaining square will not have all K colors.
This proves that using the better of the two strategies exhausts at least one of the K colors, QED.
