Croatian Olympiad in Informatics

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

формат ACM?

→ Ответить

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

Нет. IOI, причем старый. То есть тестирование только на тестах из условия во время тура.

→ Ответить

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

Ага, т.е. окончательное тестирование в конце + неполные решения.

→ Ответить

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

← Rev. 2 →

doublepost

→ Ответить

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

Контест длится 5 часов, а не 3. Во всяком случае так написано в письме, которое мне пришло.

→ Ответить

Tranvick

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

← Rev. 3 →

Странно, обычно COCI 3 часа шли.

UPD. Почему ничего не сказано здесь?

→ Ответить

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

← Rev. 2 →

Цитата из письма.
As part of the COCI series, we are hosting an Internet online contest with problems from the Croatian Olympiad in Informatics 2011.The contest is primarily intended for high school contestants, but is open to all interested!

This contest is used in Croatia to select members of the IOI team.There will be 5 tasks and the contest will be 5 hours long.It will be held on Saturday, May 14, starting at 13:00 (GMT/UTC).Contestants may use Pascal, C/C++ or Java as your programming language of choice.

→ Ответить

Tranvick

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

Название второй задачи просто супер =)

→ Ответить

mmaxio

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

Не думаю, что будет сильно плохо и нечестно, если я напишу, что задача Telka у меня прошла все тесты из фидбека, только когда я стал выводить ответы println'ом вместо printf'а. (язык Java)

→ Ответить

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

А за какое время работает твоя программа ?

→ Ответить

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

До конца контеста осталось еще целых 25 минут. Давайте потерпим :)

→ Ответить

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

ОК. Но давайте после контеста все же поделимся решениями :)

→ Ответить

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

Разумеется. Разбора у них, думаю, как обычно, не будет.

→ Ответить

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

Ух, ты! У кого еще 70 по первой?

→ Ответить

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

К сожалению всего 25 по второй :(

→ Ответить

KADR	14 лет назад, # ^ \| 0 У меня 70. Оказывается, разворачивать циклы не всегда оптимально :) → Ответить

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

Да. Оптимальный ответ - 2:
2 3 1 5 4 7 6

→ Ответить

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

А как вы писали первую ?

→ Ответить

ACube

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

Там можно все циклы за одну операцию объединить в один. Достаточно выбрать в циклах по одному элементу и сделать сдвиг.

→ Ответить

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

Сразу не воткнул :) Можно чуть подробней ?

→ Ответить

ACube

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

Нужно сделать граф из заданного массива. Из позиции i ребро в a[i]. Выйдет так, что граф состоит из циклов (и только!). За одну операцию можно поставить на место все элементы цикла (сдвинуть элемент вперед по ребру).

Оптимальное решение:

Выбрать по одному элементу в каждом цикле (если у цикла только одна вершина, его не рассматриваем), и сделать их сдвиг. В итоге получается один цикл. Делаем его сдвиг. Вот моя реализация: http://pastebin.com/HAEMuFMF.

→ Ответить

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

Спасибо :)

→ Ответить

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

Присоединяюсь к негодованию... =(

→ Ответить

mmaxio

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

За третью 40, все-таки на яве писать такие олимпиады пока довольно рискованно

→ Ответить

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

А во второй сколько ?

→ Ответить

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

Ладно, а кто умеет решать 4-ую и 5-ую?

→ Ответить

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

Я умею четвёртую. А в пятой у меня неправильное тупое решение. Сейчас послал - получило тоже 10 баллов за один тест. Умное выдаёт такие же неправильные ответы :(
Могу набросать план в Вики.

→ Ответить

KADR	14 лет назад, # ^ \| 0 В четвертой у меня 5я степень, но набрало 90 из-за того что рекурсии много :( Локально на макстесте успевает. В 5й сдал на 40 баллов. Чуть позже могу написать свое решение четвертой. → Ответить

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

У меня в 4-ой 6-ая. Тоже 90 баллов.

→ Ответить

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

Вот у меня по 4 тоже 5 степень, но только 70 баллов всего(

→ Ответить

maksay

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

Хотя у меня 5я упала полностью, но идея, по-моему, верная, и не ТЛила:

Для начала выберем доступные позиции для каждого слона, повернем на 45 градусов. Выйдет что-то вроде:

00хх00

0хххх0

хххххх

0хххх0

00хх00

х - достижимые клеточки.

Переберем битмаску заюзанности столбцов. Для каждой строки посчитаем величину: сумма всех элементов - сумма всех элементов на пересечении с выбранными столбцами.

Теперь разобьем все столбцы на две группы - те, которые можно достичь из начальной позиции за 1 шаг ( простым вертикальным ходом), и те, которые за два (ходим в самый центральный активный столбец, из него уже можно достичь все строки). Те, которые достичь из центрального столбца нельзя, вообще выкинем.

Будем добавлять к ответу сначала строки из первой группы, в порядке убывания стоимостей, а затем, когда выгоднее станет потерять 1 ход и перейти в центральный столбец, сделаем это и будем выбирать уже из отсортированного объединенного множества строк.

Очевидно, что значение (макс сумма за Т шагов) релаксируется величиной (Сумма в выбранных столбцах + Сумма величин в выбранных (Т-П-1) строках, где П - количество выбранных столбцов+сумма оригинальной строки). -1 - из-за того, что одна строка уже была выбрана изначально.

Ну и все, перебираем затем, сколько мы ходим первым и вторым. Сложность - O(2^2N * NlogN), или как там мы сортируем Н чисел. У меня локально пахало за 0.9.

→ Ответить

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

← Rev. 2 →

~~Что-то мне не нравятся ваши достижимые клеточки....~~ Не правильно понял.

→ Ответить

maksay

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

010101

101010

010101

101010

010101

101010

1-ки как раз и образуют такую фигуру, если повернуть на 45 градусов по часовой. ( В первой диагональке 2 единички, затем 4, 6, 4, 2).

→ Ответить

KADR

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

← Rev. 2 →

За пятую у меня так (думаю, что можно короче, но это то что я на контесте писал):

Путь из S в T можно ассоциировать со скобочной последовательностью, в которой 26 разных типов скобок, а так же есть пустые ребра. Эта последовательность "почти" правильная, т.к. в конце могут остаться еще некоторые открывающие скобки, но везде разность между открывающими и закрывающими скобками каждого типа неотрицательна.

Заведем несколько динамик.

f(i,j,len,zero) - количество путей из i в j длины len, причем если zero=1, то еще накладывается ограничение чтобы последовательность скобок была правильной, т.е. баланс в конце должен быть нулевым

f0(i,j,len,zero) - то же самое, только теперь в дополнение ко всему не может быть закрывающих скобок

f2(i,j,len,first,zero) - то же что и первое, только последнее ребро в пути соответствует закрывающей скобке и еще если first=1, то первая скобка в пути не обязательно матчится с какой-то закрывающей, а если first=0, то обязательно

f0 считается очень просто - перебираем куда пойдем из i и суммируем.

f считается просто за квадрат - перебираем куда мы идем при помощи f2, а так же длину этого пути, после чего идем при помощи f0.

Основная задача посчитать f2. Для пути этого типа может быть 3 случая:

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

2) Первая скобка матчится с последней.

3) Первая скобка матчится с какой-то, но не последней.

Первый случай возможен только если first=1 и тогда перебираем ребро, выходящее из i и делаем переход.

Второй случай мы тоже отнесем к варианту когда first=1 и тогда переберем ребро из i и ребро в j (они должны соотв. открывающей и закрывающей скобкам одного типа), а между ними идем при помощи f с zero=1 (баланс должен быть равен 0).

Третий случай возможен только когда first=0. Он разбивается на 2: мы либо сразу делаем переход в f2 с этими же параметрами, но first=1, либо же перебираем вершину до которой мы идем из i при помощи f2 с first=0, а от нее идем в j при помощи f2, но уже с first=1. Ну и перебираем какой длины первая часть пути, а вторая это len минус эта длина.

Получается O(N⁵).

→ Ответить

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

Кто подскажет как решить 1, 2 на 100% ?

→ Ответить

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

Сейчас появится вот тут.

→ Ответить