На всякий случай напоминаю, что раунд состоится в 20:00 по Московскому времени. Первая тысяча проходит дальше.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.05.2024 20:58:31 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Мне одному В показалась гораздо проще С?
В С большой риск закопаться(что я с успехом и делал 1.5 часа), а в В практически негде.
Как B решалась кстати?
Простая — перебором всех вариантов. Потом над результатом можно 5 минут пошаманить и увидеть закономерность.
Можно заметить, что всё разбивается на горки вида /| (вторая тоже наклонная). Назовём их уровни. Пока один уровень не заполнится, следующий не начнётся. Находим в каком мы уровне — его длина с одной стороны около 1500. Смотрим, в каком уровне мы хотим закупится: меньше — 1.0, больше — 0.0, иначе делаем ДП по одному уровню, где a[i][j] — вероятность бросить i+j бриллиантов, чтобы слева оказалось i, а справа — j.
Место 962, Мне повезло! писал точно такое решение, но массив для дп задал маленьким и large не прошло :(
Source
Можно вместо динамики еще явную формулу по схеме Бернулли применить. Я сам динамику написал, только потом понял.
Собственно, вероятность того, что всего упало n кубиков и правый слой оказался высоты ровно k, в данных условиях равна Cnk·2 - n, если не ошибаюсь. Ну и суммируем по всем k, бОльшим высоты нашего камня.
При таком подходе еще надо аккуратно учесть случай, когда одна сторона уже наполнилась и тогда на вторую кубики падают с вероятностью 1. У меня из-за этого семплы не проходило, я забил и написал динамику.
Хм, да, и правда. Не подумал про него. Тогда навскидку не знаю, как делать.
Мне потом рассказали, там примерно так же. Просто когда мы зафиксировали количество кубиков с нашей стороны, мы можем однозначно узнать количество с другой. После этого мы руками из той стороны перекидываем лишние кубики на нашу и смотрим, покрыло ли после этого оно клетку на нужной высоте. В итоге, все вероятности сложатся и мы получим правильную сумму.
Так, кстати, можно решить за
, то есть за количество алмазов во внешнем слое.
Только считать все нужно в логарифмах (по крайней мере я не умею без них).
Заходит и без логарифмов, если считать цешки треугольником Паскаля и в каждой следующей строке делить на 2 относительно предыдущей.
Но это другая асимптотика, не?
Это да:( А вот интересно, насколько точное значение дает локальная теорема Муавра-Лапласа? А то ведь и за О(1) можно;)
Мне кажется наоборот, если в задаче есть какие-то формулы и случаи, то в них можно набажить и потом долго искать ошибку. Там, правда, семплы неплохие, так что много чего можно было на них отловить.
В B-hard меня испугало то, что почти все ответы 0 или 1. Несколько минут поискал где потерял что-нибудь. Не нашел — забил.
С-hard сгенил за S*5*SumLen. За 6 минут отработало. Кто-то умеет что-то более приличное делать?
А писать прилетев через 10 минут после начала в Пулково, и просдев по undefined причине час в самолете смешно.
У меня теоретически тоже S*5*SumLen но константа 5 тут появляется только тогда, когда слово из словаря совпало с подстрокой нашей строки полностью, т.е. достаточно редко, отработало чуть меньше чем за 2 минуты.
Ну там в словаре все слова длины не более 10. Можно сделать динамику по тому, сколько букв уже прошли и сколько символов назад мы сделали последнее исправление (ясно, что если больше 4, то обрезаем до 4). При переходе перебираем длину очередного слова, не более чем 2 позиции исправлений в нем и сами буквы, на которые исправляем. В 4 потока посчитало все тесты за 13 секунд.
Если перебирать очередное слово с помощью trie, то отрабатывает моментально.
Можно заранее сильно сузить список слов, по которым мы пересчитываем динамику в каждой позиции, заметив, что среди трех первых символов в любом слове два должны совпадать с тем местом в строке, куда мы будем ее прикладывать. Ниже чуть подробнее отписал.
Да, в B-hard я все восемь минут тоже искал какой-нибудь баг. Потому что интересных ответов не получилось, все вероятности, кроме одной, были кратны 1 / 4. А руками до этого я более интересные тесты нашёл.
А в C-hard можно хранить только достижимые состояния: (сколько букв ещё нельзя менять, позиция в строке, вершина бора), тогда работает быстро. А потом падает на проверке :) . Сижу теперь, жду, пока доработает решение с обычным массивом вместо ассоциативного.
Почему это неверно для n<=20? задача B 3670070
Потому что если у нас последний слой с какой-то стороны полностью заполняется, то все следующие квадратики падают уже в одну конкретную сторону с вероятностью 1.0, а не 0.5.
Я учел это
Посмотри ответ на свой тест(правильные решения уже можно скачать) и увидишь.
А как скачать ответы?
Скачать чужое правильное решение и запустить на своём тесте?
Никак. Но ты можешь скачать коды тех, у кого зашло. И протестить на своих input'ах. Совет: качай только large. Бывают случаи, что между small и large правятся баги, а small с ними зашло.
Нашел, логическая ошибка
Нужно уметь написать правильное решение и не отправить его... :) Я про задачу B.
A решается быстрее, чем за квадрат?
У меня только сортировка.
Понятно, что если мы берем какое то число имея число А, то добавлять стоит только А-1.
Понятно, что если мы отказываемся от чего то, то и от большего мы тоже откажемся.
Идем по отсортированному массиву и смотрим два случая: откидываем все, что осталось или берем следующее число, в таком случае нужно число А несколько раз увеличить(но понятно, что оно экспоненциально растет). Да, еще случай А = 1 нужно не забыть.
Понятно, что операцию удалить имеет смысл делать только в конце, когда мы решаем, что дальше есть не будем ничего. Тогда сортируем данные и симулируем: можем есть — едим, не можем — создаём новое существо на 1 меньше себя (если мы размера 1 — симуляция закончилась) и едим его. После каждого шага, пытаемся также удалить всё оставшееся и проверяем а не выгоднее ли это. O(N log N).
Да, жадно. Отсротируем. Заметим, что если мы кого-то выкидываем, то и всех, что после него, тоже. Теперь по очереди пытаемся съесть очередного врага и храним текущую сумму. Если не можем съесть, добавляем к сумме (сумму — 1) и увеличиваем счетчик добавленных на 1. На каждом шаге релаксируем ответ с величиной "счетчик + сколько осталось до конца".
Вроде бы за O(NlogN) не сложно. Отсортируем все числа по неубыванию. Ясно, что удалить нам нужно несколько последних чисел, а остальные все мы возьмем. Будем идти по массиву слева направо и помнить, какое наименьшее количество чисел нужно докупить, чтобы мы смогли взять первые k чисел. Попробуем все остальные N - k чисел выкинуть и обновить ответ. После этого нам надо купить сколько-то чисел, прежде чем мы сможем взять k + 1-е. Для этого мы каждый раз будем покупать максимальное возможное число, почти удваивая при этом наше текущее.
UPD: опередили
А как за квадрат то делать? (так чтобы еще было неочевидно как быстрее)
Ну, я писал динамику f[i][j] — максимальный размер нашего шарика, когда мы прошли первых i частиц и сделали j действий. За O(NlogN) неочевидно после этого.
Еще можно на хешмапах делать F(сколько прошли, размер текущего шарика) = минимальное число операций чтобы получить такой шарик
I've solved problem B large but got Wrong Answer because of silly problem my code
when I divide my long double-type variable by 2 million times it becomes too small and tend to zero after that when I multiply it by some numbers it still zero.
actully what I wanted to compute is [ C(n,k)+C(n,k+1)+C(n,k+2) .... + C(n,n) ] / 2^n for some numbers n,k
fails large input file but my algorithm is correct.
What I did was compute c(n,k)=C(n,k)/2^n in a table of doubles. The combination of multiplication and division by large doubles can be tricky, so it's good practice not to use it — most of the time, it can be replaced by simple multiplication and summation.
В "B" задаче не заходила задача из-за того что не написал
if(x<0)x*=-1;
Через минуту после конца зашел и small, и large:(
Я -- лох:(
I played with Google Charts and made the following map: Google CodeJam 1st round statistics. It's just an experiment to learn Google Charts for this occasion. It shows
1000 * Round2 / (Round1A + Round1B)taken from Google CodeJam Statisics.Single person statistics can be kinda tricky, if you notice the blue countries... good job anyway
А у меня наоборот все...
я честно решил В small input(после контеста уже к сожалению, в течение не успел) за что в "дорешке" получил заслуженный вердикт "Correct!". мой код
по приколу скачал large input и запустил. отправил, даже не посмотрев на вывод. НО ОНО ТОЖЕ ВЫДАЛО "Correct!"!!!
спустя минуту я кинул своей проге тест 54 10 0, на который она по понятным причинам выдала -9101.27343750. Как вы понимаете таких тестов на которых она упадет можно напридумывать тысячи...
поэтому вопрос. К счастью это не влияет ни на чей рейтинг и проход дальше, однако серьезный удар по составителям тестов(или это был рандом???). Но у кого-то могла таким же образом задача и приняться. что лучше делать? написать им чтоб они перетестили задачу В на большее полном наборе тестов? но с их
тупойне интеллектуальной системой проверки это вряд ли возможно. или что?Нужно лучше читать правила.
На large input ваша программа тестируется после окончания тура. Соответственно то, что вы восприняли как Correct, означало лишь то, что ваш ответ принят на проверку. То есть при отправке проверяется всего-лишь соответствие формату выходных данных, и ничего больше. Зайдите и посмотрите на свои результаты в итоговой табличке — у вас там скорее всего стоит минус.
А про неинтеллектуальную систему проверки вообще непонятно. На GCJ весьма приличный мультитест — если поглядите глазками на тест, увидите какое-то количество ручных тестов, какое-то количество рандомных. Что не так-то?
Во первых, он писал про дорешивание, а там все тестируется сразу.
А в B-large тесты действительно отстой.
Насколько я понял, ситуация уже после контеста, когда система сразу говорит вердикт. А во время контеста она никогда на large не говорит Correct, насколько я помню.
UPD: и перетест B-large по большому счёту ни на что не повлияет, так как А и B-small это уже проход, а перетест на small совсем неполиткорректно. Получается, что подавляющее большинство получившие АС по B-large уже в 1000, и там же и останутся, даже если этот АС убрать.
да, я понимаю что перетест В-large ни к чему не привидет(в плане standings), но как бы и оставлять без внимания это не хочется, ведь я мог успеть сдать мой "правильный" аутпут и во время контеста, никому не сказать и занять чье-то заслуженное место в следующем раунде
как вам уже сказали, речь идет о "дорешке", когда вердикт говорится сразу
про мультитест : может быть он и приличный в общем, но на этой задаче конкретно, он какой-то странный. потому что(ну на мой взгляд, что видно по решению) сначала идет куча отсечений где ответ bool, после чего остается нетривиальный случай, где надо именно считать вероятность. видно, что я ее считаю нормально только для ооооочень маленьких значений, которые только для маленького инпута, однако ни одного теста в large на такое не встретилось, что очень печально, потому что это самая существенная часть задачи, которую я не решил, за что должен был получить заслуженный WA, однако почему-то не получил.
да и потом, раз дорешка, могли бы сделать тестов и побольше, раз таймера нет(хотя все равно решение в секунду точно уложится)