| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| How to solve this problem? | Aram Shatakhtsyan | 1480. Талоны | 5 авг 2010 02:32 | 3 |
Someone who solved this problem, give some ideas, please. The answer is n^2 + floor(n/2) + 1. Place n^2 in top-left corner and proceed row-by-row, column-by-column. For every cell choose maximal unused value, such that its sum with left and upper numbers is <= that minimal sum.
I have no idea why that works. The formula above was found empirically - these are minimal values when this greedy algorithm converges.
Edited by author 24.07.2008 15:00 Real cheat! With this formula the problem is VERY easy! IMHO, without it - it would take much more time and efforts to get AC. |
| Idea | ilyamit | 1480. Талоны | 18 ноя 2009 16:02 | 6 |
Idea ilyamit 5 ноя 2007 15:38 What is idea for this priblem?
I fill matrix for chess:
n = 4
0101
1010
0101
1010
0 - smoll number
1 - big number
Why my solve is wrong?(((
I got WA4. Re: Idea Loky_Yuri [USTU Frogs] 6 ноя 2007 10:54 During the contest our team didn't solve this problem because of the same logic. Now I understand that the same idea but with putting the biggest number in the conner is so simple... Re: Idea AlexF [USTU Frogs] 6 ноя 2007 10:59 Thanks! I got AC.
Is true idea (for 4):
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
Edited by author 27.11.2007 15:37
Edited by author 27.11.2007 15:38 Re: Idea Roman Peshkurov (It-Team) 18 ноя 2009 16:02 i am using BFS with queue |
| I have WA#2. Please, help me. | Tkach Andriy | 1480. Талоны | 18 мар 2007 22:37 | 2 |
I think that matrix have some stucture but I don't now this. It is so easy try only with yourself it's always better :) |
| How to prove? | SpaceFlyer | 1480. Талоны | 11 окт 2006 06:10 | 1 |
|
