Grand Prix of SPb 2015

9 лет назад, # ^ |

Answers for n <= 10:

answers

→ Ответить

Anastasko

9 лет назад, # ^ |

wow, how did you receive them?

→ Ответить

9 лет назад, # ^ |

+57

I'm developer of the problem :)

→ Ответить

9 лет назад, # ^ |

We had used Burnside's lemma... But it's long story with Gaussian Elimination and dynamic programming...

→ Ответить

Shapo

9 лет назад, # ^ |

There is no need in Gaussian Elimination :Ь
Code.
It computes answers for all N up to 60 in less than 2 seconds (about 1.5 seconds), that's why it may look ugly.

→ Ответить

9 лет назад, # ^ |

Nice!

→ Ответить

Petr

9 лет назад, # ^ |

Thanks! Apparently my answers match for n<=10 :(

What's the answer for n=60?

→ Ответить

9 лет назад, # ^ |

24697351

→ Ответить

Petr

9 лет назад, # ^ |

Interesting, this one is completely different. Will keep debugging.

→ Ответить

dragoon

9 лет назад, # ^ |

Can you please give more insight for C? Thanks.

→ Ответить

PERNEKHAN

9 лет назад, # |

How to solve L?

→ Ответить

Madiyar

9 лет назад, # ^ |

← Rev. 10 →

Find centroids of the first tree, can be one or two centroids, try both.
Find centroids of the second tree. If there are two centroids try both.
We will try all combinations of centroids. Let's denote centroid of the first tree as v and centroid of the second tree as u.

Now, we will assume that the vertex v is the vertex u in the second tree.

We try to compare two subtrees recursively,

bool isSame(v, u);

Here, subtree u in the second tree should have one more vertex than subtree v.

Now, we will compute hashes of subtrees of children u and v, after that try to match two arrays of hashes, there should remain exactly one non-matching subtree from both tree. Check them recursively.

P.S. I may miss something. :)

→ Ответить

Djez

9 лет назад, # ^ |

Hi! Please can you tell why we cannot do that:

Find all powers of first tree ( A )
Find all powers of second tree ( B )
Sort both of them in non-increasing orded.
Iterate through all leaf ( power == 1 ) from second tree and check next condition:
Get power of parent of that leaf ( x )
Find first power which equal x and descrease it by 1
Sort B again
Compare two arrays A and B if they are equal we have leaf number and remember minimum of that's numbers
If A!=B increase first power in B which equal x-1 by 1.
Next iteration

Sorry for my English, hope you understand me.

→ Ответить

Madiyar

9 лет назад, # ^ |

← Rev. 8 →

Shortly, your proposition is: If degree sets of both trees are equal, then you conclude that trees are also equal? If I understood correctly, this should be Counter Example:

First Tree:
1-2, 1-3, 2-4, 2-5, 3-6

Second Tree:
1-2, 1-3, 2-4, 2-5, 5-6

Be the way, how to upload a picture to Codeforces?

→ Ответить

Djez

9 лет назад, # ^ |

Yes, I suggest it. Thank you for your answer. But this part is hard for me because I cannot find some counter examples.

Anyway, thank you much.

→ Ответить

ZloyNegr

9 лет назад, # ^ |

How do you compute hashes of subtrees?

→ Ответить

-emli-

9 лет назад, # |

Как решить H и G?

→ Ответить

9 лет назад, # ^ |

G — 1. Искал (перебирая) пары таких клеток, которые обменяв местами, две клетки становились на свои места. 2. Если таких больше небыло, тогда обменивал любую пару нетронутых клеток, так чтоб одна встала на правельное место, и возвращался на первый пункт.

→ Ответить

9 лет назад, # ^ |

← Rev. 3 →

-8

Кстати, я тут получил "Presentation error test 2", когда послал решение, которое ничего невыводит в указанный для вывода файл "puzzle-swap.out", а выводит ответ в stdout, непонимаю, как прошел тест нр. 1.

→ Ответить

vas.and.tor

9 лет назад, # ^ |

Тестирующая система принимает стандартный ввод-вывод вместо файлов. Всегда так пишем. Не знаю можно ли комбинировать: чтение из файла, а вывод в stdout.

→ Ответить

9 лет назад, # ^ |

Я читал из файла, а выводил в stdout. А про выше написаное — незнал, зачем тогда вообще эти файлы указанны.

→ Ответить

Gassa

9 лет назад, # ^ |

Presentation Error — это нарушение формата. Формат можно нарушить, выведя не туда, а можно и как-то ещё. Второй тест — скорее всего, минимальный (уже отсортированная таблица, ответ 0).

→ Ответить

Fcdkbear

9 лет назад, # ^ |

← Rev. 2 →

В G почемуто заходит следующее:

1) Перебрем все перестановки строчек.

2) Внутри 1) переберем все перестановки столбиков.

3) Выполним эти перестановки. Потом все оставшееся добьем перестановками элементов.

H — будем перебирать шаг, на котором число N может вычеркнуться, начиная с 2. Пусть это шаг равен k. Если N делится на k — ответ -1 (мы вычеркиваем наше число). Иначе, до него есть ровно N/k чисел, которые вычеркнутся, значится позиции уменьшится на N/k. Моделируем до тех пор, пока k не превзойдет N. Можно запустить эту программу и увидеть, что для N = 10¹² делается около миллиона операций (это без учета того, что ответ может быть -1, то есть это оценка сверху)

→ Ответить

http://pastebin.com/1UVBmJgZ

9 лет назад, # ^ |

В G ясно, что это должно заходить. Пусть мы сперва поменяли какие-то элементы, а потом строки. Тогда ясно, как изменить порядок на обратный. Аналогично для столбцов/элементов. Строки и столбцы вообще независимы. Итого, из правильно ответа легко получить правильный ответ такого вида

→ Ответить

mamka

9 лет назад, # ^ |

← Rev. 2 →

Примитивное решение было.
1)Для каждого числа при счёте запоминаем его координату в первый массив. 2)теперь создадим ещё нейкий массив, в котором будем для числа хранить его координату(которую это число должно иметь в отсорченом массиве) 3)теперь просто перебор бежим i от 1 до 16 и смотрим если координаты i числа из первого массива не равны координатам i числа из второго массива то производим замену чтобы найти то число на которое нужно поменять пробегаем от j 1 до 16 снова и если координаты этого j числа из первого массива равны координатам i из второго массива то меняем местами эти две ячейки

→ Ответить

romanasa

9 лет назад, # |

+13

how to solve K, E, H, F ?(div2)

→ Ответить

akashin

9 лет назад, # |

+11

Кому-то удалось сдать K в div2? Мы постоянно получаем WA2, даже при попытке заслать правильное решение из div1 с поправкой на то, что корень всегда в вершине с номером 1.

Идея нашего решения: для каждого ребра посчитать количество запросов, которые через него проходят. Это можно сделать стандартным трюком с lca и динамикой по дереву. Потом суммируем количество запросов по всем ребрам и вычитаем самое тяжелое ребро выходящее из каждой вершины.

→ Ответить

9 лет назад, # |

← Rev. 2 →

Расскажите пожалуйста, а зачем в интерактивной задаче создаются файлы input.txt, если они не работают? https://www.diffchecker.com/azmuvqut

Час дебажили буквально, потому что приходит WA1 и абсолютно непонятна причина.

→ Ответить

9 лет назад, # ^ |

А что написано в условии задачи?

→ Ответить

9 лет назад, # ^ |

стандартный ввод или input.txt

→ Ответить

9 лет назад, # ^ |

В PDF?

→ Ответить

9 лет назад, # ^ |

В pdf stdin.

Но это же не дело, когда в pdf одно, в Яндекс.Контесте другое. Мое решение работает и с stdin, и с input.txt. Оно не работает только в случае "есть input.txt, который не используется".

→ Ответить

9 лет назад, # ^ |

В Яндекс.Контест вообще условия на этом Гран-При не загружались.

→ Ответить

9 лет назад, # ^ |

Ну я вот эти читал: http://imgur.com/4wgKnYw

→ Ответить

9 лет назад, # ^ |

Интересно; возможно, что загрузили сами авторы; как минимум, я никаких условий, кроме pdf, не загружал.

→ Ответить

9 лет назад, # ^ |

Ну я без претензий, если что, просто в целях улучшения системы.

→ Ответить

witua

9 лет назад, # ^ |

+41

Нам одним пришлось решить задачу G без условия, только по сэмплу, и считать что это нормально?

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

← Rev. 2 →

+21

Not bad :)

В самом начале был клар " Statements can be uploaded as PDF file.", и в той pdf-ке условие есть — и в английской, и в русской версии)

→ Ответить

HellKitsune

9 лет назад, # ^ |

+36

О_О" Там есть условие!

Не одним.

→ Ответить

witua

9 лет назад, # ^ |

← Rev. 2 →

'can be', but not 'should be' :)

Они еще назвали ее «Головоломка», все сходилось.

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

+29

Пора уже привыкнуть ко всем этим яндексовским фишкам:)

Кстати, без условия мне эта задача больше нравилась. В этом была какая-то изюминка что ли :)

→ Ответить

tyamgin

9 лет назад, # ^ |

+28

Лол. Я думал суть задачи как раз догадаться до условия.

→ Ответить

PavelKunyavskiy

9 лет назад, # ^ |

+41

Да, я загружал, потому что lperovskaya попросила. А с этой задачей не справился, потому что табличка в условии, а как делать в yandex.contest таблички, я так и не понял. Ну и копировабельные сэмплы тоже приятный бонус.
Но да, написать "посмотрите pdf версию" я не догадался. То, что задача оказалось удачной для решения без условия это интересный эффект.

→ Ответить

9 лет назад, # |

В задаче "J" нечитал пояснения к примеру, так как он был понятен и непротиворечил условию задачи. Написал то чего просили в условии — незашло.

→ Ответить

Um_nik

9 лет назад, # |

+72

Есть способы бороться с тем, что перед каждой посылкой мы должны менять язык со Scala на плюсы? Раньше что-то мы с такой проблемой не сталкивались.

→ Ответить

Zlobober

9 лет назад, # ^ |

Поддерживаю, словили бревно из-за этого :(

→ Ответить

9 лет назад, # ^ |

Не CE?

У нас вроде с этим было ОК

→ Ответить

dragoon

9 лет назад, # |

What about F?

→ Ответить

9 лет назад, # ^ |

It's extended Euclid algorithms. You should write it with bitsets and optimize until done.

→ Ответить

Jacob

9 лет назад, # ^ |

I think I know solution with complexity $\text{[math]}$ (uses sqrt-decomposition and Karatsuba algorithm, also can benefit from bit operations). It's highly unlikely that in Java O(n²) solution would pass, and I don't want to implement my idea, so it would be very nice if one of the contest authors could comment.

→ Ответить

PavelKunyavskiy

9 лет назад, # ^ |

We had $\text{[math]}$ in java working 0.8 on YandexContest

→ Ответить

http://pastebin.com/3ZCRK88W

9 лет назад, # ^ |

← Rev. 2 →

Did you have shift-and-xor as a single operation for that?

Anyway it'd nice to see the code.

→ Ответить

niyaznigmatul

9 лет назад, # ^ |

Just submitted, and got accepted with running time 0.64 seconds using Oracle Java 8 compiler on Yandex.Contest.

→ Ответить