Блог пользователя gojira

Автор gojira, 7 лет назад, По-русски,

268A - Матчи

При ограничении в 30 команд самое простое решение заключается в симуляции всех поединков:

for i = 1 to N
  for j = 1 to N
    if i != j and h[i] = a[j] then
      ++ans

Существует также решение, работающее за O(N + M), где M — длина диапазона номеров цветов (то есть 100 при данных ограничениях). Для начала нужно посчитать для каждого цвета i количество команд cntH[i], у которых домашняя форма цвета i, и количество команд cntA[i] с выездной формой цвета i. Ответ задачи — сумма произведений этих количеств для каждого отдельного цвета, то есть сумма cntH[i] * cntA[i] по всем i.

268B - Кнопки

Для начала озвучим наихудший сценарий. Более-менее очевидно, что в худшем случае при угадывании i-ой (1 <= i <= n) по счёту кнопки Манао должен допустить n-i ошибок, потому что после этого становится понятно, какая кнопка правильная.

Посчитаем, сколько в сумме нажатий потребуется Манао прежде, чем он поймёт, какая именно последовательность кнопок правильная. При угадывании первой кнопки он допускает n-1 ошибку, но "цена ошибки", то есть на сколько кнопок нужно нажать чтобы её допустить, равна 1 нажатию. При угадывании второй кнопки цена ошибки уже 2 нажатия, потому что каждый раз приходится набирать первую (уже известную) кнопку. Продолжая в том же духе, получается что при угадывании i-ой по счёту кнопки Манао сделает (n-i) * i нажатий.

После того, как Манао понял правильную последовательность, ему остаётся её один раз ввести, что требует ещё n нажатий.

Отсюда получается алгоритм за O(n): просуммировать (n-i)*i для i=1, ..., n-1, и добавить к полученному числу n.

При значениях n, которые не выходят за диапазон 32-битных целых чисел, можно решать задачу и за O(1)*. Раскроем сумму (n-i)*i = n*i - i*i. Сумма первых слагаемых — это n*(1+...+n-1), где нам поможет сумма арифметической прогрессии. Сумма вторых слагаемых — это сумма квадратов от 1 до n-1, что вычисляется с помощью кубического полинома: http://pirate.shu.edu/~wachsmut/ira/infinity/answers/sm_sq_cb.html

*Единственная проблема — что ответ при больших n не умещается даже в 64-битный целый тип данных, но можно например вычислять его остаток при делении на что-нибудь.

268C - Красивые множества точек

Очевидно, что когда в множестве есть некоторая точка (x', y'), в нём не может быть никакой другой точки с x=x' или y=y', потому что тогда между этими двумя точками обязательно было бы целое расстояние. Есть всего n+1 различных x-координат и m+1 различных y-координат. Соответственно, размер искомого множества не может превосходить min(n, m) + 1.

Без условия x+y>0 нам бы подошло множество из точек (i, i) (0 <= i <= min(n, m)). Расстояние между точками (i, i) и (j, j) равно |i-j|*sqrt(2) и может быть целым только при i=j. С другой стороны, таких точек min(n, m) + 1, а мы уже знаем, что больше взять невозможно.

Раз точку (0, 0) использовать нельзя, сменим "диагональ": будем использовать точки (i, min(n, m) - i).

268D - Шведская стенка

Те, кто хорошо знаком с динамическим программированием, могут скроллить сразу вниз до "Итогового решения". Те, у кого есть некоторый опыт в этой теме, могут почитать мою попытку объяснить, как дойти до итогового решения. У кого опыта нету, тем наверное большого смысла это читать нету :)

Представим себе решение, которое перебирает все возможные дизайны, постепенно добавляя ступеньки снизу вверх. Например, допустим что оно уже выбрало направления для первых 10 ступенек и они вот такие: 2123412413 (то есть первая палка торчит в направлении 2, вторая — в направлении 1 и так далее). Теперь есть четыре варианта продолжить эту последовательность, приписав к ней '1', '2', '3' или '4'. Для каждой из 4^n стенок-строк нам нужно проверить, что для хотя бы одного символа выполняется следующее условие: первое его вхождение в строку не дальше позиции h, каждое следующее отстоит от предыдущего не более чем на h позиций, а последнее далее позиции n-h.

Естественно, такое решение при больших значениях n за разумное время не работает, но от него можно оттолкнуться в поисках лучшего подхода. Заметим, что проверку строки можно делать при добавлении каждого нового символа: если оказалось, что где-то посередине строки для всех четырех символов нужные условия уже не выполняются, то не имеет смысла перебирать её до конца. Также заметим, что нам не нужна вся строка для того, чтобы проверять при добавлении символа выполнение условий. Достаточно лишь знать, когда в последний раз встретился каждый из символов '1', '2', '3' и '4', и выполнялись ли для них условия до сих пор. Но тогда получается, что два префикса, у которых [каждый из символов в последний раз встретился на одних и тех же позициях] и [для каждого из символов выполнение/невыполнение условий совпадает], абсолютно эквивалентны с точки зрения дальнейшей работы такого перебора. То есть например при h=4 следующие два префикса можно окончить (то есть дополнить их до любой длины n) равным количеством способов:

44123424132
12424224132

Последний раз каждый из символов встретился на одной и той же позиции, символы '1' и '3' для обеих строк уже "потеряны", то есть условия для них уже не выполняются, а символы '2' и '4' ещё могут обратить строку в удовлетворительную.

На основе сделанных наблюдений уже можно построить полиномиальный алгоритм, основанный на принципе динамического программирования. Пусть ways[curN][i][j][k][l][ii][jj][kk][ll] будет количеством дизайнов стенки, в которых есть curN штук ступенек, последняя ступенька, торчащая в направлении 1, была на высоте i, в направлении 2 — на высоте j и так далее; ii, jj, kk, ll — boolean переменные, обозначающие, выполняются ли до сих пор условия для ступенек в соответствующих направлениях. Направив ступеньку на высоте curN+1 в одном из направлений, мы получим дизайн с curN+1 ступеньками, где эта последняя ступенька будет на высоте curN+1, а другие останутся на своих местах. Выполнение условий тоже можно и нужно пересчитать. Учитывая, что curN всегда равен одному из {i, j, k, l}, можно получить алгоритм со сложностью O(n^4). Так как это слишком медленно, подробно его разбирать не стану.

Сделаем следующее наблюдение: если мы сейчас рассматриваем палку на высоте curN, а последняя палка в некотором направлении была раньше чем curN-h палок назад, то нас не интересует, на какой конкретно высоте она была — это направление уже непригодно. Получается, что количество состояний в нашем алгоритме можно сделать порядка O(n*h^3). Более того, параметры, отвечающие за выполнение условий в каждом из направлений, коррелируют с высотами последних ступенек в этих направлениях, так что при желании от них можно (почти) избавиться, уменьшая количество состояний ещё в несколько раз.

На основе сделанных наблюдений можно наверное построить в некоторой степени разные решения, я расскажу своё.

Итоговое решение

Как ни странно, давайте заведём пятимерную динамику :) Пусть ways[curN][alive][last1][last2][last3] будет количеством таких дизайнов, где:

  • Ровно curN ступенек

  • Если то направление, в котором торчит последняя ступенька, всё ещё "живое", то alive = 1, в противном случае 0. Живое направление — это в котором первая ступенька была не выше h, а каждая следующая была не больше чем на h над предыдущей.

  • last1, last2 и last3 содержат информацию об остальных трех направлениях. Направления никак не пронумерованы. lasti = 0 в двух случаях: если в соответствующем направлении ступенек не было вообще, или если последняя была более чем h ступенек назад. В остальных случаях в lasti записано, сколько ступенек назад была ступенька в этом направлении, то есть разница между curN и высотой последней ступеньки в данном направлении.

В целях оптимизации можно иметь last1<=last2<=last3, что уменьшает количество состояний примерно в 6 раз. Тем не менее, это усложняет код и в этой конкретной задаче особого выигрыша не давало (потому что обработка переходов стала более долгой). Переходы я буду рассматривать без учета данной оптимизации.

Теперь рассмотрим обработку переходов из конкретного [curN][alive][last1][last2][last3]. Обрабатывать состояния мы будем в порядке от curN = 1 до curN = n-1. ways[1][1][0][0][0] (то есть поставлена лишь первая ступенька) положим равным четырем, как базисный случай. Так вот:

  • Если следующей мы ставим ступеньку в том же направлении, что и последняя (та, что на высоте curN), то мы грубо говоря получаем состояние [curN+1][alive][last1+1][last2+1][last3+1]: curN увеличилось на 1; направление, в котором поставили последнюю ступеньку, если было "живое", то определенно так и осталось и не могло "ожить" если не было; все lasti увеличились на один. Тут надо уточнить, что если lasti было равно 0, то его увеличивать нельзя (этой ступеньки или не была, или была но слишком давно). Также надо уточнить, что при lasti=h-1 оно превращается в 0 (последняя ступенька уже слишком низко).

  • Если следующей мы ставим ступеньку в направлении, где последней была ступенька на высоте last1, то получаем состояние [curN+1][last1 > 0 || curN < h][alive][last2+1][last3+1]. Расшифровка: если last1>0, тогда это направление "живое". Также last1 может быть 0, но количество имеющихся ступенек быть меньше h — тогда это может быть лишь первой ступенькой и поставив её, мы будем иметь "живое" направление. На месте направления, за которое отвечал параметр last1, теперь то, в котором смотрела последняя ступенька. Соответственно, она была 1 ступеньку назад и надо написать там [1]. Но возможно, что это направление уже было мертвое и тогда надо написать [0]. Получается, что оно совпадает со старым значением alive. last2 и last3 меняются как и в прошлом пункте.

  • Направления last2 и last3 обрабатываюся аналогично направлению last1.

Когда мы переходим по переходу этой динамики, новому состоянию добавляется количество вариантов, которым получалось старое. Итоговый ответ — сумма по всем [n][1][a][b][c], где 0<=a,b,c<h, плюс сумма по всем [n][0][a][b][c], где хотя бы одно из a, b, c ненулевое. Таким образом, у нас есть алгоритм со сложностью O(n*h^3), которому нужно асимпотически столько же памяти. Если его неаккуратно реализовывать (особенно на Java), то он словит ML. Лечится это дело несложно: так как для вычисления значений [i][][][][] нужны лишь значения [i-1][][][][], можно в любой конкретный момент запоминать лишь O(h^3) состояний.

Да уж, до написания разбора она мне такой громоздкой не казалась :)

Можете посмотреть решение пользователя GagGuy: 3027309, там довольно компактная реализация похожей идеи.

268E - Плейлист

Для начала давайте найдём ответ для фиксированной последовательности песен. Рассмотрим любые две песни, которые стоят в плейлисте на местах i и j, i < j. Если Манао понравилась песня i и не понравилась j, то произойдёт повторное прослушивание песни i. Соответственно, длина процесса с вероятностью p[i]*(1-p[j]) увеличится на L[i]. Сумма L[i]*p[i]*(1-p[j]) по всем парам (плюс сумма всех длин песен, потому что Манао их один раз послушает точно) и есть мат. ожидание для фиксированного порядка.

Получается, что из двух песен (l1, p1) и (l2, p2) следует поставить раньше первую, если l1*p1*(1-p2)>l2*p2*(1-p1), и вторую в противном случае. Если у нас всего две песни, то это очевидно. Если у нас есть ещё песни, то можно сказать — а вдруг, несмотря на то что это неравенство выполняется, есть ещё третья песня (l3, p3), для которой с первой песней неравенство определит, что надо её ставить до этой первой, а для второй — что после второй? Тогда было бы непонятно, какой из порядков даёт максимальное мат.ожидание. Посмотрим на этот случай пристально:

l1*p1*(1-p2)>l2*p2*(1-p1)
l1*p1*(1-p3)<l3*p3*(1-p1)
l2*p2*(1-p3)>l3*p3*(1-p2)
<=>
l1*p1/(1-p1)>l2*p2/(1-p2)
l1*p1/(1-p1)<l3*p3/(1-p3)
l2*p2/(1-p2)>l3*p3/(1-p3)

(Тут я закрыл глаза на факт, что p[i] могут быть равны 0 или 1, но это не важно)

Что за фигня, у нас противоречие! Видимо таких случаев не бывает :)

Далее, рассмотрим некоторый порядок песен (l[1], p[1]), ..., (l[n], p[n]), где существует пара соседних песен i и i+1, для которых не выполняется l[i] * p[i] * (1 - p[i + 1]) >= l[i + 1] * p[i + 1] * (1 - p[i]), и допустим, что этот порядок оптимален. Очевидно, что при замене местами песни i и i+1, ответ изменится на ту величину, которую в него вносила именно эта пара песен (имеется в виду величина l[i] * p[i] * (1 - p[i + 1])). Все остальные песни остались относительно каждой из песен i и i+1 в том же порядке. Но мы имеем l[i] * p[i] * (1 - p[i + 1]) < l[i + 1] * p[i + 1] * (1 - p[i]), значит, поставив песню i+1 перед песней i, мы получим большую величину. Таким образом, получаем противоречие — изначальный порядок был неоптимален.

Получается, что надо всего лишь упорядочить песни по убыванию l[i]*p[i]/(1-p[i]) для достижения перестановки с максимальным мат.ожиданием. Осталась проблема вычисления ответа для конкретной перестановки: до сих пор мы это умели делать только за квадрат, что при n=50000 многовато. Тут можно использовать идею, которая наверное тоже в какой-то мере является примером динамического программирования. Допустим, мы зафиксировали j и считаем, сколько песня j добавляет к ответу, если Манао она не понравится. Это величина (l1*p1 + l2*p2 + ... + l[j-1]*p[j-1]). Для j+1 аналогичная величина будет иметь вид (l1*p1+...+l[j-1]*p[j-1]+l[j]*p[j]). Раз эти величины отличаются на 1 слагаемое, можно их пересчитывать за O(1), если рассматривать j один за другим по возрастанию. Идею вычисления ответа для фиксированной перестановки можно выразить вот так:

lovedLenExp = 0.
answerExp = 0.
for j = 1 to N
  answerExp += l[j]
  answerExp += lovedLenExp * (1 - p[j])
  lovedLenExp += l[j] * p[j]

Вот в принципе и всё :)

 
 
 
 
  • Проголосовать: нравится
  • +150
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Только в С размер множества не превосходит min(n,m)+1

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

У меня есть вопрос по доказательству решения Е.

Вот мы придумали отношения порядка: одна песня меньше другой, если Li * Pi / (1 - Pi) < Lj * Pj / (1 - Pj). Естественно, оно транзитивно, это понятно. Казалось бы, надо ещё доказать, что если у нас есть какой-то порядок песен, в котором песня i по нашему отношению порядка больше песни j, то если мы их поменяем местами, целевая функция увеличится — без доказательства этого факта я не понимаю, с чего бы решению с сортировкой работать. Однако этот факт мне видится неверным: между песнями i и j могут находиться какие-то другие песни, и соответствующие слагаемые в общей сумме для них могут как уменьшиться, так и увеличиться.

То есть я расписал, на сколько изменятся слагаемые между парами мест i-k и k-j после такого обмена, и у меня вышла величина (Li * Pi - Lj * Pj) * (1 - Pk) + Lk * (Pj - Pi). Она может быть как больше нуля, так и меньше в зависимости от Pk и Lk

UPD:

Я понял. Вроде как, нужно сказать чуть больше, чем написано в доказательстве. Нужно сказать приблизительно следующее. Любая пара песен i, j в зависимости от порядка, в котором они стоят, даст вклад L[i] * P[i] * (1 — P[j]), либо L[j] * P[j] * (1 — P[i]). То есть, больше чем сумма по всем парам песен max(L[i] * P[i] * (1 — P[j]), L[j] * P[j] * (1 — P[i])) мы никак не получим. С другой стороны из-за транзитивности отношения, которое мы ввели, существует перестановка, в которой это значение достигнется. Поэтому это максимум.

То есть это такое мощное соображение. Ответ всяко не больше чем что-то, а в силу транзитивности отношения порядка, это что-то достигается. Это весьма интересно.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Да, главную штуку я оказывается не доказал. Я добавил в разбор несколько другое доказательство, возможно более простое для понимания.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Можно было просто сказать, что T[i]=l[i]*p[i], B[i]=1-p[i]. Тогда это стд задача Джонсона, надо максимизировать Sum(i=1..n,B[i]*Sum(j<i,T[j]))

»
7 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Editorial to this contest was posted before editorial of previous contest D&E problems :D

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Nice and fast editorial, pretty cool explanation too, thanks for that :)

Well, I am having problems with probability (+ expected value problems) and game theory. Can't find any good article on them, so I hope you can suggest me and help me, from where did you learn and how did you improve your skills and how to approach to these kind of problems. I know solving problems and analyzing highly ranked coders coeds is the way, but I am newbie, so I need to know from where and how to start, I wanna be at the top too!! Thanks again :) :)

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Я понял, что не могу решать тервер и динамику. Спасибо за контест. Но зачем в Д 4 направления, если для трех решение по сути не меняется, но становится короче и приятнее?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Ну вообще я просто представлял себе эту лестницу/стенку именно как штуку с четырьмя сторонами. Идея была точно не в том что "три измерения слишком мало, надо гробастее, гробастее!" :)

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

This is one of the best written editorials I've seen on Codeforces.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    +1. it can be very useful for Div.2. In order to attract green, gray and blue coders to the tutorial (half a year ago i hate to read tutorials on my own), it should be very detailed. Usually it's short and vague "explanations"...

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Читаю разбор по С и как вроде решал другую задачу. Почему размер множества не превышает min + 1 если всего точек n * m и мы исключили n + m — 1 точек(крест с точкой в центре). Я так понимаю вы подразумеваете что подходят точки которые как бы на диагоналепроходящей через точку. Но почему остальные точки не подходят?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

    В каждой строке не более одной точки.

    Всего, кстати, точек (n + 1)(m + 1) - 1

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      после вашего комментария сразу все прояснилось), спасибо.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Представь, что ты выбрал во множество какую-то точку. Тогда нельзя добавить во множество точки, лежащие на той же горизонтали и вертикали, поскольку до них расстояние — заведомо целое число. Всего у нас n + 1 вертикаль и m + 1 горизонталь. Пусть n <= m. Тогда если поставить больше, чем n + 1 точку, то, по принципу Дирихле, найдётся вертикаль с двумя стоящими на ней точками. Этого делать нельзя, но максимум, что сделать можно — поставить в каждую вертикаль по точке. Всего n + 1, больше сделать нельзя точно. Зато известно, как сделать эти самые n + 1 — выбрать все точки с какой-то диагонали квадрата (n+1)x(n+1).

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Для одной точки мы исключили один крест, для второй — ещё один (у которого правда есть две общие точки с первым) и так далее. Легче видимо так посмотреть: если у нас во множестве есть две точки (x1, y1) и (x2, y2), у которых x1=x2 или y1=y2, то расстояние между ними целое. А если у всех точек различные x- и y- координаты, то (при том что 0<=x<=n и 0<=y<=m) их не может быть больше n или больше m.

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Great contest as expected :)

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Вопрос снят. Не понял этот момент: "Также надо уточнить, что при lasti=h-1 оно превращается в 0 (последняя ступенька уже слишком низко)". i ход динамики: curN, alive, 0, 0, h — 1. i+1 ход динамики: curN + 1, alive, 0, 0, h. т.е. last3 не превышает h, как и положено .

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Мы ведь уже поставили ступеньку на высоте curN+1, так что когда будем ставить следующую, даже если поставим её в направлении last3, будет уже поздно: разница получится h+1.

    Конкретный пример: h=3, поставленные ступеньки = "123". Соответствующее состояние вроде бы [3][1][0][1][2]. Теперь если мы поставим ступеньку не в направлении 1, тогда оно уже потеряно. Поэтому в состоянии last3 поменяется не на 3, а на 0.

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Nicely explained editorial :)

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Nice!

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can SomeOne Plz tell me In Beautiful Set Prob. how the size of the greatest set sought is (min(n,m)+1). Thanks...

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Two points can't share the same x- or y-coordinate, because then the distance between them would be integer. But there are only n+1 distinct x-coordinates and m+1 distinct y-coordinates. Therefore, the smaller of them is the maximum number of points we can possibly take.

    Since you are not the first who is asking this question, I've updated the editorial.

»
7 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Best Editorial ever seen!

Thanks XD

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hope all editorials for div2 are so circumstantial and easy to understand like you.

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Разбор хорош, все его хвалят, но вы меня не переубедите, самый лучшый разбор, который был, это от tunyash. А в целом, спасибо таким авторам, который расписывают идею решения чуть ли не до кода, всё объясняют и доказывают.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Great Contest! Great Editorial! It's really good to be able to read complete explanation and proofs in the editorial. Thanks gojira.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Thanks. :)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very well written and explained.

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Very well written and explained.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This problem analysis is good,maybe the best one I have ever seen in coderforces.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C: 4133871 I know why my submission is wrong, the distance between (96,0) and (12,13) is an integer, but why is (i, min(n, m) — i) true and why such a mistake doesn't occur for this set of points? Please give me some math proofs. Thank you :)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Correctness of (i, min(n, m) — i) is proven mathematically in the editorial, please, read it.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It says since we cannot use (0,0) (1,1) and so on we must use diagonally made pair of points. "Since point (0, 0) is restricted, we can take the other "diagonal", i.e. use points (i, min(n, m) — i)." So it is right and I have used (0,1) (1,2) and so on. But my answer is incorrect as I pointed above. he distance between (96,0) and (12,13) is an integer, and this occurs on testCase: 96 96 But what author of editorial said as just an example: (i, min(n, m) — i) is true, but why? I can't understand! Thanks for notice :)

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The points you take do not lie on a diagonal, the last point (96, 0) lies elsewhere. Note that points (i, min(n, m)-i) always lie on the same diagonal.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Hmm you're right. But why only diagonals are true? What is the proof?

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Noone says only diagonals are valid — there are probably many other solutions for each particular board. Diagonals are just a generalized and simple solution.

            The distance between any two points on the same diagonal is k*sqrt(2), where k is an integer. Integer multiplied by sqrt(2) can't yield an integer (unless it is equal to 0).

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              As I've got, is seems like a square. if (n !=m) we can assume a random square inside that rectangle and use its main diagonal. But when (n == m) we cannot use main diagonal, since we use the other diagonal with (i, n-i) formula. Thank you so much :)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A simple recursive solution for problem 268B - Buttons :

5291793

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope this thread is not dead.

I was trying the diagonal approach for C-Beautiful set of points. Since we cannot take (0,0), I shifted the diagonal by 1 unit to the right. This also meant that the last point of the diagonal will not lie in the min(n,m) square. The last point could then lie on the (min(n,m),0) So for n = 4, m = 4 (0,1) (1,2) (2,3) (3,4) (4,0)

However, this approach does not work on the values n= 96 m = 96 Points (12,13) and (96,0). I can't wrap my head around why this approach does not work, since I'm still considering diagonals. Any ideas?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    its late but let me explain it won't work at 6,6 also

    (0,1) (1,2) (2,3) (3,4) (4,5) (5,6) (6,0)

    here if you take (3,4) and (6,0) you will get x=3,y=4 after subtracting, which is a pythagorean triplet, ie distance is sqrt( 3*3+ 4*4 )= 5, which is an integer .

    The question specifically says that distance should be non-integer