Странно, что никто еще не создал эту тему...
Предлагаю здесь обсудить задачи.
Свои результаты вносите сюда, не стесняйтесь.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
14:18:54
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
14:18:54
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 03:16:06 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Можно ссылку на задачи?
как я понимаю, в открытом доступе их пока что нет. А с собой забирать, к сожалению, не разрешали.
Кому нет, а кому разрешали :) Ниже Romchela залил условия.
Да, было бы очень интересно узнать, как решается четвертая. Подозреваю, что там что то вроде N * M * log(N).
Была идея на 60 с террнарником и бинпоиском. Это должно работать за O(N*N*M*log(M)). Из-за переполнения проверить идею не удалось :(
Задача элементарно решается за N3 (два указателя) и довольно просто за N2log2N (2D фенвик)
Спойлер.И вправду элементарно)
За куб понятно. А за N^2 * log^2 N, я думаю, не влезет в TL.
конечно, но баллов наберёт больше 60ти (возможно)
Вообще имелся ввиду NMlog или аккуратный NM*log^2. Решение yeputons за NMlog^2 во всяком случае по плану, должно было получать 100.
Так а как за NMlog решать?
Бинпоиск по ответу. Теперь надо минимизировать длину при фиксированном количестве.
Переберм i,j — два начала. Тогда есть отрезок валидных концов на правой половине — таких, что соответствующий левый конец с таким ответом где-то в адекватном месте. При фиксированных i,j чтобы была минимальная длина надо минимизировать x + y + \sqrt{(x-y)^2+d}. Это запрос минимума на диагональном отрезке в матричке.
Если перебирать i,j сначала по сумме, то можно соответствующий такой сумме диагональ в матрице выписать и делать обычное дерево отрезков
Получается NM*log^2.
Дальше из этого делается NM*log либо SparceTable'ом либо аккуратным слежением за валидными и очередью с минимумом. Вроде без этого набирало 100.
У нас один товарищ умудрился получить 96 баллов без структур данных. Понять его решение до конца мы не смогли :-)
Мне I_love_natalia сказал, что умеет пропихивать куб на 100. Обидно конечно, но непонятно как пихать без онлайн тестирования.
мне всегда нравились такие ответы, от вашей сложности проще не стало, и как ее решать тоже понятней не стало, ответ в стиле — я ахуен_й, смотрите, как могу
так а смысл расписывать неполные решения для понимания решения?
Вообще то эта асимптотика просто N*N*M*log() с бинпоиском без всякого тернарника: фиксируем три вершины и подбираем третью.
На 60 сделали без проблем, как раз таки за N ^ 3 без лишних мучений :)
Я так и делал, перебирал а1 и а2, b1 находил тернарником и b2 бинарным поиском, но видимо где-то набажил, набрал мало баллов. Но асимптотика должна быть O(N^2*log^2(M))
По-моему, там функция имеет не один экстремум, чтобы запускать тернарный поиск по b1...
Не должно это работать. Я честно стрессом подбирал тесты против неверного предположения о выпуклости.
Вообще 4-ю задачу можно решать за O(N ^ 2), но я сильно не уверен, что такое решение будет работать быстрее O(N ^ 2 log N). Но теоретически довольно интересно. Давайте зафиксируем число деревьев, которое мы хотим покрыть. Пусть это будет Х. Тогда если зафиксируем начало одного отрезка i, начало второго отрезка j, конец первого k, конец второго l. Тогда если d[i][j] — расстояние между i-м деревом одной части аллеи и j-м деревом другой части, то длина веревки для покрытия деревьев будет равна d[i][j] — a[i] — b[j] + d[k][l] + a[k] + b[l]. Также k — i + 1 + l — j + 1 = X, т.е. k + l = i + j + X — 2. Т.е. если мы возьмем матрицу C[i][j] = d[i][j] + a[i] + b[j], то k + l = i + j + X — 2 — это диагональ этой матрицы (не стоит забывать про то, что k >= i, l >= j). На этой диагонали нам нужно взять минимум. Если мы будем использовать Sparse Table или очередь, то получим решение O(N ^ 2 log N). А теперь подумаем и поймем, что бинпоиск нам не нужен. Давайте рассмотрим каждую диагональ как отдельный массив. В нем нужно уметь находить минимум. Для этого можем свести нахождение минимума к нахождению LCA, а находить LCA мы умеем за O(1) на запрос и O(N) на препроцесс. Теперь положим X = 1. Будем перебирать i и j, для каждой фиксированной пары (i, j) пробуем увеличить X на 1, проверяем за O(1) минимум на соответствующей диагонали. Если веревки хватает, то увеличиваем X на 1. Легко понять, что операций у нас в итоге будет O(N ^ 2). Для каждой пары (i, j) мы делаем проверку за O(1). И суммарно X у нас увеличится O(N) раз. Для каждого увеличения будет еще одна проверка. Итого получили решение за O(N ^ 2), но это на контесте не надо было писать ни в коем случае =) В решении активно пользуемся тем, что для фиксированной пары (i, j) если можем покрыть K деревьев, то K — 1 мы также можем покрыть.
http://zalil.ru/34183767 вот условия
НЕ все регионы провели 1 тур сегодня.
Какие, например?
Е-бург
Е-бург провел РАНЬШЕ или еще не провел?
Не провел
Гм. Это вообще-то повод полностью дисквалифицировать результаты Екатеринбурга.
Update: информация была проверена и не подтвердилась.
Денис, успокойся. Андрею явно доверять можно, в отличии от какого-то непонятного анонимного тролля, зарегистрированного 37 минут назад.
Ну это не совсем непонятный анонимный тролль, а вполне конкретный и знакомый мне человек.
Информация, впрочем, действительно не подтвердилась.
Я почему-то не верю, что это тот, кем он представился своим ником. Впрочем уже неважно значит.
Ну я когда прочитал сообщение за подписью L_Wolf про Екатеринбург подумал, что это Лёня Волков. Потом понял, что вряд ли Лёня такой ерундой сейчас будет заниматься.
Нет, это не Лёня Волков, но известный мне человек.
в том году делали табличку с результатами, может и в этом кто сделает?
насчет общей пока ничего не известно
что-то мне кажется, или в тестах D не было n = 2000, везде n ≤ 1000
Нет не верно. Правда везде было n+m <= 2000, что почему-то не указано в условии. Странно.
А как решалась третья на 100 баллов?
4ёх мерное ДП f[len][i][j][carry] — сколько существует подходящих пар длиной len, если первая цифра числа A=i, первая цифра B=j, carry=1, если i+j дают перенос в следующий разряд, иначе carry=0. Переходы расписать или выложить решение на Java ?
Выложи лучше решение
j можно не хранить, она однозначно определяется
РЕШИЛ АНАЛОГИЧНО
на разборе было что то странное, мне казалось такое не заходит
Динамика: Состояние-предыдущие цифры в А и В и единица переноса. Переход-приписываем вправо цифры. Upd. Перепутал право и лево. Надо влево дописывать.
Как решать A? :)
для двойки: понятно, минимум из 3х
для единицы: найдем минимальное пересечение a и b (блондинов и высоких), это max(0, a + b - n), теперь найдем минимальное пересечение c с блондинами и высокими, это снова max(0, c + max(0, a + b - n) - n)
Можно просто
max(0, a + b + c - 2 * n):)это было региональный этап — мы извращались как могли)
Ахаха. На самом деле, мне почему-то весь контест чудилось, что у меня неправильное решение по ней, и я почти каждые 15 минут открывал код, чтобы удостовериться, что все верно :)
-
если n == 1, то max(n-(n-a)-(n-b)-(n-c), 0) если n == 2, то min(a, min(b, c))
Подскажите, пожалуйста, где бага в решении, никак не могу найти. http://pastie.org/5725885 Или просто идея неверна? Вкратце: фиксирую два начала, а затем двумя указателями "натягиваю" веревку на оставшиеся березы.
upd. Нашел — переполнение инта в вычислении расстояния между березами. Но неужели это все? Проходит очень мало тестов.
Мой куб с переполнением в этом месте получает около 30.
А нет идей, в чем бага? Или у меня кривой код, в котором лень копаться?)
Не до конца разобрался, но по моему ты не учитываешь возможность взять одно дерево с одной из сторон. А сколько баллов оно набирает?
8 баллов. Ну, смотри. Я перебираю все пары деревьев, расположенных на разных сторонах аллеи. Для каждой пары сначала проверяю, что эту пару я могу взять. Если так, то тогда я одним указателем набираю, сколько можно, деревьев с левой стороны. А потом цикл: пока во множество ответа включается хотя бы одно дерево с левой стороны, набрать деревьев с правой стороны, обновить ответ и убрать одно дерево с левой. Так я для каждой пары перебираю все возможные варианты. По времени выходит O(N*M*(N+M)), 60 баллов должно набирать.
Ну да. С переполнением 28 у меня набирает. Где-то бага. Но сходу не видно.
А можешь показать свой код, если у тебя то же самое?
Ответил в переписку.
Тоже использую два указателя и 8 баллов
А что, уже есть тесты? Можешь поделиться?
Можете ли выложить архив с тестами?
У меня нет тестов. Есть лишь протокол тестирования.
У меня по D — 0. Решение следующее представим все в виде полного графа (посчитав расстояние между всеми парами берёз) и найдём цикл не больше заданной длины. TL по всем тестам (на тестах из условия + на моих, в т.ч. больших, но рандомных работает) — Почему?
Обратитесь к вашему региональному жюри. Возможно вы не так назвали файлы или что-то подобное.
Нет, файлы были названы правильно — это было первое предположение.
Ну по такой информации сложно что-либо сказать. Вы не сказали примерно ничего — ни сложности решения, ни даже региона на худой конец. Если будет код — я могу попробовать разобраться. Если нет, то что я сделаю? На 30 баллов вроде должно что угодно почти проходить.
Ну я не знал нормального способа искать циклы кроме перебора(знаю что асимптотика ужасна, но не на ВСЕ же TL).
Код не помню. Решение такое: запишем все координаты в массив x[n+m] — посчитаем все расстояния (с учётом w). Запустим поиск в глубину из a[1..n]. Будем идти во все непосещённые вершины, пока лента не закончится и поддерживать максимум.
Там все тесты с суммой n+m хотя бы 50. Правда есть тесты, где одно из двуз очень маленькое.
Кто-нибудь собирается делать общую таблицу, как в прошлом году?
https://docs.google.com/spreadsheet/ccc?key=0AlDEWw_0SrJldDZPcGctclJjcGZ0SlVLdF80c1R5T1E#gid=0
Треш же
https://docs.google.com/spreadsheet/viewform?formkey=dC0yNUlQTDhlTkk1TDlmUlRpc0FSb1E6MQ Можете пока что заполнять эту форму, через некоторое время появится сводная таблица.
Там есть фильтр треша?
Он будет ручной. Я буду в таблицу сводную ручками иногда переносить рез-таты.
А где саму таблицу можно посмотреть?
Здесь: https://docs.google.com/spreadsheet/ccc?key=0Aokc0nqfW2I1dEVBYk5qRUszUGw1NXYwMlYxeGt2WkE#gid=0
Имя предопределено :)
Спасибо, исправил) Кто не заметил в таблице стали появляться результаты второго тура: https://docs.google.com/spreadsheet/ccc?key=0Aokc0nqfW2I1dEVBYk5qRUszUGw1NXYwMlYxeGt2WkE#gid=0
У меня вот вопрос к авторам задач Для четвертой задачи предполагалось, что решение n*m*log^2(n+m) — полное? Просто у нас на сервере жюрисол с деревьями решений не заходит в две секунды, а в разборах написано, что это нормальное решение Мы приняли решение поднять TL до 3с
Вроде предполагалось.
Хмм, а можете сказать мне, почему мое решение за NMlog^2 падает по времени на 31 тесте?:( Неужели такая неаккуратная реализация?
Выглядит очень хорошо. Но мне совершенно не нравятся вычисления корня в самом вложенном месте. А может и моё решение не проходит на серверах Вашего региона.
Спасибо большое! На самом деле на регионе я получил 6 баллов из-за переполнения...Интересно то, что ТЛЕ у меня на сервере кодефорсес. Попробую предпосчитать длины всех ребер. UPD: не помогло:( вот
Возможно, проблема в том, что логарифм у Вас возникает из-за тернарного поиска и получается раза в два больше, нежели двоичный.
Такое решение работает в два-три раза дольше моего и, по-видимому, не должно было заходить.
Понятно, спасибо!
Да, предполагалось. А сколько работало мое решение за NMlogN?
Ваше за NMlogN — 1.508
es с NMlog^2N — 2.656
процессор: Intel(R) Celeron(R) D CPU 430 @ 1.80GHz
Ну конечно тогда 3 секунды надо было. В рекомендациях вроде же как раз прописан двухкратный от main?
Да, вы правы
Из чего в третьей задаче следует, что оба слагаемых должны иметь ту же разрядность, что и сумма?
Из условия. Второе предложение третьего абзаца.
Из условия?
Теперь можно обсуждать второй тур?
Он должен был начать во всех регионах уже 6 часов назад. Даже если были задержки, то учитывая то, что участники не должны иметь доступа на CF, тут уже должно быть безопасно обсуждать. Так что пожалуйста!
Для начала — резы Питера!
Кто-нибудь вообще решил последнюю (кроме составителей)?!!
Ответ: да, Петрозаводск — Воронецкий Егор
Да, поделитесь кто-нибудь решением/идеями. На контесте придумал только очевидное решение за O(n^3). Когда вышел из здания ИТМО, придумал решение за O(nd), что есть O(n^2). Хотя и не уверен, что оно бы зашло. А как там можно за O(nlogn), ума не приложу. Какая-нибудь хеви-лайт декомпозиция, которую мне так и не довелось пока изучить?
А не мог бы кто-нибудь выложить условия? Ну или рассказать вкратце условия двух последних задач.
Upd: условия
А ты не писал?
Мне кажется, что в этой задаче нужно для каждой вершины хранить некоторые величины(количество вершин на расстоянии d от текущей + ещё что нибудь). Тогда для пересчета этой величины нам нужно слить информацию от потомков этой вершины. И, если я не ошибаюсь, если все время сливать массивы в наиболее большой, то можно добиться линейной асимптотики алгоритма.. (кажется на Петрозаводских сборах не редко всплывают задачи, в которых применяется подобная идея)
Насколько я понимаю, основная идея такая же, как и на задаче K прошлого ВКОШПа. Нужно знать, сколько у данной вершины в поддеревьях вершин расположено на нужном нам расстоянии. Это можно узнать так: запомним времена входа и выхода в DFS. Отсортируем все точки сначала по возрастанию расстояния до них, потом по временам входа и выхода. Теперь, заходя в данную точку, мы перебираем все ребра, исходящие из нее. С помощью бинпоиска в полученном отсортированном массиве мы выделяем множество вершин, расположенных на нужном нам расстоянии, путь до которых от данной вершины лежит через через выделенное нами ребро. Тут возникает одна проблема — как посчитать множество вершин, не находящихся в поддереве данной вершины? Собственно, об этом нам очень долго и не особо понятно рассказывали на разборе :) Далее нам нужно за линию научиться искать произведения всех троек, что не особо трудно математически вывести. Итого получается N log N, плюс недосказанный мною кусок задачи. А вообще, очень скоро будет видеоразбор, советую его посмотреть :)
Я видел авторское решение (у нас разбор проводил I_love_natalia, спасибо ему за это). Там такое шаманство: если у нас есть множества с полезной информацией о детях, а ответ для вершины — это объединение этих множеств (в данном случае не объединение, но смысл такой же), то будем добавлять в большее множество меньшее. Так мы испортим информацию в детях, но она нам уже не нужна. Все это выполнится за NlogN. Доказательство проскакивало где-то на кф и вроде бы есть на e-maxx (насчет последнего не уверен).
Никакого шаманства.
NlogN — потому что надо просуммировать перекладывания по элементам, а не по итерациям. При каждом перекладывании множества элемента удваивается, значит их не более лога.
Никакого шаманстваЭто образно. Кстати Костя использовал именно этот термин. Упихать правда квадрат в 10^5 он уже не смог, как в 1 дне на последнюю задачу. Зато я запихал куб для N <= 5000 сегодня.
Почему моё решение за куб получило 20 баллов?
p.s. Написал флойда + перебор за куб = 2*N^3
Набагал где-то, это должно получать 40 баллов.
http://ideone.com/HramHv
Также 10 тестов (на CF) — 20 баллов. В чём баг?
Ссылка битая.
По ссылке — пусто.
у меня открывается... ВОТ
Тьфу, что я несу.
При составлении задач я рассчитывал, что большинство сильных участников придумает следующее решение за квадрат:
Возможно, существуют более простые решения за квадрат. Но такое решение ведет к верному — осталось научиться делать пункт 2 быстро!
Для этого используются всякие различные шаманства с деревом. Пока оставлю эту задачку на подумать — думаю, скоро кто-нибудь придумает как это делать.
upd. Посмотрев разбор Дениса Павловича, понял, что не то придумал. Но была похожая идея. За O(n^2) можно было написать. Жаль, что не написал.
Что, в общем, хочется сказать по поводу региона. Из-за невнимательности пролетаю мимо всероса (потерял на этом 61 балл в 3 задачах). Что ж, это справедливо, я считаю :)
http://codeforces.net/problemset/problem/161/D — не?
Кстати давать баяны не хорошо, т.к. если не решил задачу + не понял разбор — не решишь, а у кого-то наоборот будет преимущество.
Там другая задача, и она проще. Тут существенно, что надо найти для каждого поддерева отдельно. Это сильно усложняет ситуацию.
Если бы каждая задача, похожая идея решения которой уже когда-то была, отсеивалась бы, то сомневаюсь, что олимпиады бы еще проводились...
Идея что задачи должны уже скоро закончиться по рассказам ходят еще с начала 2000-ых годов. Я думаю еще раньше. Как видим, пока не закончились.
Дорешать задачи можно в тренировках:
Студенты могут их порешать в ICPC-режиме, тоже весело.
Когда примерно будет известен проходной балл на всеросс? И какой примерно он будет?
В разборе Денис Павлович сказал, что примерно в начале марта. Не знаю, на сколько это правда. А проходной балл, думаю, будет высокий, потому что набрать баллов 500 было совсем не сложно.
Надеюсь не больше 590
Для какого класса?
Для 10
Вряд ли будет больше 590 для 10 класса. Для справки в 2012 году были следующие проходные баллы: 9 — 495 10 — 535 11 — 573
Пишите в этой ветке, какие баллы ожидаете проходные. По классам.
По задаче 6 квадрат на сколько должен был проходить?
40 баллов. Можно открыть условия, которые выше скинул Михаил, и там самому посмотреть.
Ребят, помогите разобраться, почему такое решение валится на WA на первой группе (n <= 50) тестов. http://pastebin.com/FxtAdftS. У нас в области тестирования ещё не было, поэтому решил сам посмотреть, чего ждать) Пока в тренировках WA-5. Идея примерно такая: зафиксируем три точки (две переберем, одна — номер 1). Построим окружность, отметим точки, которые на ней лежат. Найдём первую неотмеченную точку. Пусть теперь она первая, опять переберем две точки, построим ещё окружность и посмотрим, захватывает ли новая окружность все неотмеченные точки. Если так, то выходим. Спасибо
Upd. Как вариант — когда три точки лежат на одной прямой, а я пытаюсь искать центр опис. окр.
Попробуйте тест
Спойлер.
Кто-нибудь ещё кроме меня писал выпуклую оболочку в 7?
У меня появилась такая идея, но потом я понял, что дальше с этой выпуклой оболочкой каши не сваришь. Вот ты, например, что делал?
Перебирал все тройки соседних точек, лежащих на оболочке, строил по ним окружность и помечал из оставшихся точек те, которые лежат на этой окружности.
Если все непомеченные точки лежат на одной окружности, то есть ответ (в конце проверяю точки первой окружности на принадлежность ко второй).
Случаи для
n <= 4рассматривал отдельно.PS. Прошло на 100.
Ну и зачем тут выпуклая оболочка?
Во время олимпиады не смог придумать, как по-другому перебирать тройки точек быстрее, чем за N3
Зачем минусовать? Я написал своё решение, которое может быть не оптимально, но проходит на 100 баллов.
Я тоже об этом думал, но меня вот такой тест завел в тупик.
Почему-то никто не спросил про C первого дня, чувствую себя совсем тормозом, но... Как решать?
Если кому нибудь нужен архив с авторскими решениями, тестами и разбором — то вот он.
Кто нибудь знает, где и в какие сроки будет проводится всеросс,
Не уверен, что у нас здесь присутствуют авторы решений и разборов задач, которые входили в материалы олимпиады, но хотелось бы отметить следующее:
Уважаемые авторы исходников и авторы разборов — не могли бы Вы в будущем стараться
Максимально синхронизировать разборы сложных технических задач с исходниками. В этом году материалы по решению задач 4 и 8 были подготовлены так, что понимание этих решений и воспроизведение без копипаста требует крайне серьёзных умственных затрат. Не надо стараться писать разбор как поэму, чтобы её потом можно было зачитать по бумажке. Лучше описать всё так, чтобы после сравнения исходника и разбора даже у менее продвинутых людей не оставалось вопросов, не было опечаток в индексах. Каждая такая нестыковка сильно давит по нервам, особенно когда задачи приходят за пару дней до туров. Для проверки качества разбора можно применить старый способ — дать его кому то прочитать (например автору других задач) и спросить — всё ли он понял.
Оформлять исходные коды максимально подробно. Давать переменным человеческие имена. Чтобы исходник не выглядел как будто писался автором на каком-то соревновании. Комментарии приветствуются.
Как верно подмечено в материалах олимпиады — разбор задач является важной частью соревнований и чем лучше вы сможете объяснить менее продвинутым жюри в регионах идеи задач, тем качественней последние проведут разбор да и сами узнают много нового и интересного.
Извините, наболело за эти дни.
Не только присутствуют, но и занимают весьма высокие места в рейтинге CF (я не про себя). Можете, кстати, по суффиксам решений погадать, кто там есть :)
Я согласен с замечаниями и понимаю, что разбор получился не лучший :( К сожалению, тут проблема в том, как готовится региональный этап. Скажу лишь, что все материалы от нас требовали к 15 ноября, кажется... В итоге кто умел — писал решения, другой — разборы, кто-то приводил это хоть к какому-то адекватному виду. Скажем, есть человек, который хорошо решает и пишет код, но не умеет формулировать (особенно, на бумаге) решение...