Обсуждение @ 1656. Войско Тридевятого царства @ Timus Online Judge

59838AD what is the algorithm :? [5] // Задача 1656. Войско Тридевятого царства 18 ноя 2008 21:43

Artem Litvinenko SSU Re: what is the algorithm :? [1] // Задача 1656. Войско Тридевятого царства 19 ноя 2008 01:11

the algorithm consist of transposition the most high soldier to the centre of the line and to the centre of the column. in cycle from 1 to n gives bubble sorting.

melkiy Re: what is the algorithm :? // Задача 1656. Войско Тридевятого царства 11 мар 2009 07:05

Please can you explain how to do bubble sort in 2-d array here?

melkiy algorithm [2] // Задача 1656. Войско Тридевятого царства 11 мар 2009 07:14

I constructed such an algorithm. It requires the soldiers to be sorted by their height downwards.

When the soldiers are sorted, take them one by one and fill the square diamond by diamond, starting from center.
A "diamond" contains those cells (x,y) for which
|x - x_center| + |y - y_center| == C,
C ranges [0; n-1].

Edited by author 11.03.2009 08:54

Michail Yudin Re: algorithm // Задача 1656. Войско Тридевятого царства 11 апр 2009 19:42

it's no solution

Daniel Mahu Re: algorithm // Задача 1656. Войско Тридевятого царства 10 дек 2011 04:47

There is a much simpler method, which also uses less memory.

Hint: try a O(n) sort.
Also try not to store n*n elements in memory (print line by line instead).

Обсуждение задачи 1656. Войско Тридевятого царства