TC SRM 577 - Codeforces

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
39:57:45
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
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

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

TC SRM 577

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

Через полчаса (в 19:00 по Москве) состоится SRM #577.

Предлагаю обсудить задачи здесь по окончанию.

topcoder, srm, 577

Zlobober
12 лет назад
21

Комментарии (21)

Написать комментарий?

BekzhanKassenov

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

-8

Хммм, интересно, что тогда здесь?

→ Ответить

Zlobober

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

Подтверждение моей невнимательности. Скрыть пост?

→ Ответить

BekzhanKassenov

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

-11

Ох как яростно меня заминусовали :) Ладно, больше не буду ~~указывать красным на их ошибки~~ кидать ссылки на заминусованные (и кривые) посты.

→ Ответить

pirevitch

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

+30

судя по заголовку, поздний анонс 557го раунда

→ Ответить

HolyInq

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

← Rev. 5 →

Кто умеет доказывать, что в 1000 див2 мы всегда можем разделить двумя числами?
А то послал какую-то хрень, а она зашла о_О
Формально, что для любых двух l,r(l<r) работает один из трёх случаев:
- gcd(l,r) = 1;
- существует l<x<r, т.ч. gcd(l,x) = gcd(x,r) = 1;
- существуют x и y, т.ч. l<x<y<r и gcd(l,x) = gcd(x,y) = gcd(y,r) = 1.

→ Ответить

Fcdkbear

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

+21

Как решать 500 и 1000 див1?

→ Ответить

cmd

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

+16

500 в дорешке так досдал: повернем все на 45^, тогда расстояния это максимумы из разностей координат. будем делать 4х мерную динамику: (x1, y1, x2, y2) — суммарная стоимость операций, переход такой: перебираем новый камень, который не входит в этот прямоугольник, расширяем до него: (nx1, ny1, nx2, ny2) и суммируем стоимости для всех камешков которые попадают в первый прямоугольник и не попадают во второй.

→ Ответить

Jacob

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

1000 — mincut.

Захотим, чтобы вершина принадлежит множеству S, если через неё проходит вертикальная полоса, T — если горизонтальная.

Добавим рёбра пропускной способности 1 от вершины до всех соседних. Если с некоторой стороны соседа нет (клетка, которую не надо красить), то добавляем ребро в сток или исток в зависимости от того, соединён ли сосед по вертикали или по горизонтали.

В полученном графе mincut равен удвоенному ответу на задачу.

→ Ответить

KADR

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

+32

1000 можно было свести к минимальному разрезу в графе. Проведем ребра пропускной способности 1 из истока к закрашенным клеткам у которых соседняя сверху клетка не закрашена (или ее нет). Аналогично, проведем ребра проп. спос 1 из всех закрашенных клеток, слева от которых нет закрашенной клетки в сток. Теперь проведем ребра проп. спос 1 из каждой закрашенной клетки в соседнюю с ней клетку слева и снизу (если они закрашены). Утверждается, что мин. разрез в этом графе и будет искомым ответом.

Теперь о том, почему это работает. Каждая клетка, которая попадет в одну долю с истоком будет покрашена горизонтальным мазком, а все остальные клетки — вертикальным. Если слева от клетки край таблицы или не закрашенная клетка, то при горизонтальной покраске эта клетка будет началом отрезка и прибавит +1 к ответу. Аналогично, прибавляют +1 к ответу все клетки, которые мы красим вертикальным образом, у которых сверху нет закрашенного соседа. Дополнительно, +1 к ответу прибавляют соседние клетки, которые покрашены разным образом (здесь нужно их учитывать аккуратно, чтобы ничего не посчитать 2 раза).

→ Ответить

Fcdkbear

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

Вроде бы понятно, очень круто, спасибо.

→ Ответить

shindo

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

По 500 зашло такое: будем не добавлять камни, а удалять, тогда (возможно) на каждом шаге нам нужно удалить один из двух камней, расстояние между которыми максимально. Рекурсивно перебираем какой камень из двух будем удалять.

→ Ответить

mmaxio

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

Жесть, и как в такое поверить на контесте?

→ Ответить

dalex

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

-32

Почему все так плохо порешали первую? Я минут 20 потерял на миспрочтении и исправлении баги в 1 символ, а получилось не самое маленькое 185 место.

→ Ответить

EarlOfDitches

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

Можете объяснить решение?

→ Ответить

Fcdkbear

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

+20

Сначала узнаем чему равно r. Теперь посмотрим все группы по r элементов в отсортированом по убыванию массиве. Будем считать не ожидание среднего значения, а ожидание значения суммы. Понятно, что каждая группа по r элементов добавит к сумме среднее арифметическое своих элементов, если там нету Элли (если есть — просто добавляем ее рейтинг).

Теперь посмотрим на остаток. Если его нет — возвращаем сумму деленную на количество человек в каждой комнате. Иначе, если он есть, и мы не выбирали еще Элли, добавляем к сумме рейтинг Элли, и делим на количество участников в комнате с учетом Элли. Иначе же есть два варианта: человек из остатка не попадет в комнату к Элли (с вероятностью (left-r)/r, где left — размер остатка) или попадет(каждый — с вероятностью 1/r). Аккуратно учитываем оба случая.

→ Ответить

I_love_Tanya_Romanova

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

← Rev. 2 →

Все те, кто решил первую еще хуже, или же вообще ее не решил — в ярости жмут на минус)))

Относительно решения — я матч не писал, но вроде бы можно даже проще, чем описано чуть ниже, без разбора случаев, если раздвоить матожидание (в стиле быстрого подсчета шансов в покере), сейчас в практисе попробую и отпишусь.

Upd. Нет, нельзя. События все же зависимые( Все же надо разбирать 2 случая.

→ Ответить

I_love_Tanya_Romanova

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

← Rev. 3 →

Столкнулся со странной фишкой.

250 я кодил не на том шаблоне, и по ошибке объявил переменные внутри класса, а не глобально, как я делаю обычно. Т.е. у меня было вот так:

class EllysRoomAssignmentsDiv1
{ 

public:  
double exp_sum,exp_size;
long r,n,rsum[20000];
vector<pair<long, long> > v;
string temp;
long s;
long el,elmas;

double getAverage(vector <string> rat){

В rsum у меня хранились суммы рейтингов пользователей, которых рассматриваем на определенной итерации. Вроде бы логично, что rsum используется с индексами 0..19. У меня 20000 — с запасом) Но решение упорно падает на 39 тесте.

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

Оказывается, если этот массив размера 20000 — он по дефолту заполнен какой-то ненулевой ерундой в 39 тесте, но вполне себе нулевой (по крайней мере, в тех местах, которые использую я) в предыдущих 38. А в 39 каждый раз одна и та же ненулевая ерунда, если его не занулить — получается лажа и WA39.

Если массив размера 200000 — все тесты проходит.

И теперь вопрос — должны ли эти переменные вообще быть обнулены, если я объявил их таким образом? Я подозреваю, что нет... Если да, то какого хрена оно не так в 39 тесте?:) Если нет, то каким чудом оно доходит до 39 теста, и почему увеличение размерности позволяет ему проходить вообще до конца?

→ Ответить