ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1255. Graveyard of the Cosa Nostra

Correct idea is HERE
Posted by Vlad Veselov 6 Jun 2003 18:48
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. (-)
Posted by Mad Mouse 8 Jun 2003 20:27
Can you please tell more about it?
Posted by Alex[LSD] 10 Jun 2003 10:34
email me: caa@baga.ac.net.ru
I want to know fast solution too !
Posted by King Without Kingdom 16 Jun 2003 05:53
 >>> 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?
Posted by Yu YuanMing 26 Sep 2004 15:24
Because each 1xK rectangle contains K cells, colored in different K colors.
Posted by Vlad Veselov [PMG17, Vinnitsa - KNU, Kiev] 27 Sep 2004 17:12
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
Posted by ilucian1 13 Nov 2005 13:38
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
Posted by Rumter (3) 26 Nov 2008 19:35
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
Posted by tyomitch 18 Jan 2013 17:48
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.