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 1480. Coupons

How to solve this problem?
Posted by Aram Shatakhtsyan 18 Apr 2007 15:11
Someone who solved this problem, give some ideas, please.
Re: How to solve this problem?
Posted by Denis Koshman 24 Jul 2008 14:51
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
Re: How to solve this problem?
Posted by Alexander Samal 5 Aug 2010 02:32
Real cheat! With this formula the problem is VERY easy! IMHO, without it - it would take much more time and efforts to get AC.