Pull to refresh

Comments 8

Это нужно в хаб "ненормальное программирование"! :)

Не стал вчитываться в решение, но заценил размах замысла. Красотища.

Оставлю тут решение по первой части, чуть быстрее решения Маэстро)

WITH

tbl AS

(

SELECT

a::int,

i

FROM

regexp_split_to_table('2333133121414131402','')

WITH ORDINALITY T(a, i)

),

encoded AS (

SELECT

--разворачиваем, вычисляем значения и нумеруем

(CASE WHEN i % 2 = 1 THEN ((i-1)/2)::TEXT ELSE '.' END) AS a,

ROW_NUMBER() over() n

FROM

tbl,

generate_series(1,a)

)

,

swaps AS

(

SELECT

--координаты точек

UNNEST(array_agg(n) FILTER (WHERE a = '.') ) AS p,

--значения замены с координатами в обратном порядке

UNNEST(array_agg(a::int ORDER BY n DESC) FILTER (WHERE a != '.')) AS d

FROM

encoded e

)

SELECT

--если требуется перестановка, подставляем значения цифры в соответвствующей позиции

sum

((CASE

WHEN s.p IS NOT NULL THEN s.d

ELSE u.a::int

END) * (n - 1))

FROM

encoded AS u

LEFT JOIN swaps AS s ON s.p = u.n,

--кол-во перестановок

(SELECT count(*) AS c FROM swaps WHERE p IS NOT NULL) AS lp,

--общее кол-во элементов

(SELECT count(*) AS c FROM encoded) AS le

WHERE

--точки в конце нас не интересуют

n <= le.c - lp.c

В первом приближении, оно считает неправильно - выдает 2003 на тестовой последовательности вместо 1928 согласно постановке.

Странно, может буквы убежали при редактировании. У меня результаты 1928 и 6241633730082.

По времени:

Execution Time: 283.704 ms

Execution Time: 467.829 ms

Если развить предложенный подход и избавиться от лишних операций со строками, то можно сделать вот так:

WITH map AS (
  SELECT
    row_number() OVER() pos
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid
  FROM
    regexp_split_to_table(
      '2333133121414131402'
    , ''
    )
      WITH ORDINALITY T(sz, n)
  , generate_series(1, sz::integer)
)
, remap AS (
  SELECT
    u.*
  , lim
  FROM
    (
      SELECT
        array_agg(pos ORDER BY pos) FILTER(WHERE fid IS NULL) free
      , array_agg(fid ORDER BY pos DESC) FILTER(WHERE fid IS NOT NULL) file
      FROM
        map
    ) T
  , array_length(file, 1) lim
  , unnest(free, file) u(pos, fid)
)
SELECT
  sum((pos - 1) * coalesce(map.fid, remap.fid))
FROM
  map
LEFT JOIN
  remap
    USING(pos)
WHERE
  map.pos <= (SELECT lim FROM remap LIMIT 1);

Получается вот такой план - 182ms вместо 326ms, то есть примерно в 2 раза быстрее чем в статье:

Если совсем предельно экономить, можно выжать еще пару процентов:

WITH map AS (
  SELECT
    row_number() OVER(ORDER BY n) pos
  , CASE
      WHEN n % 2 = 1 THEN n / 2
    END fid
  FROM
    regexp_split_to_table(
      '2333133121414131402'
    , ''
    )
      WITH ORDINALITY T(sz, n)
  , generate_series(1, sz::integer)
)
, remap AS (
  SELECT
    array_agg(fid ORDER BY pos DESC) FILTER(WHERE fid IS NOT NULL) rpl
  , count(*) FILTER(WHERE fid IS NOT NULL) lim
  FROM
    map
)
SELECT
  sum((pos - 1) * coalesce(fid, rpl[rplpos]))
FROM
  (
    SELECT
      map.*
    , count(*) FILTER(WHERE fid IS NULL) OVER(ORDER BY pos) rplpos
    FROM
      map
    WHERE
      pos <= (SELECT lim FROM remap)
  ) T
, remap;

А если вот так поменять кусочек, то еще 10мс долой:

, remap AS (
  SELECT
    array_agg(fid ORDER BY pos DESC) rpl
  , count(*) lim
  FROM
    map
  WHERE
    fid IS NOT NULL
)

Круто! Спасибо, что причесали мой подход!
И еще спасибо за челлендж! Один бы не полез в эти задачи.. Интересно самому решить, а после сравнить с другим вариантом.

Я добавил UPD к первой части, применив еще пару затейливых техник.

Sign up to leave a comment.