SPb IFMO Training 6 - Codeforces

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

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

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

→ Трансляции

Leetcode BiWeekly Contest 144 — Solution Discussion

Shayan

До начала 15:18:22

Codeforces CodeTON Round 9 (Div 1 + Div 2) — Solution Discussion

Shayan

До начала 16:48:22

Всё →

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

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

Всё →

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

→ Прямой эфир

Детальнее →

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

SPb IFMO Training 6

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

Problems of October 01, 2011 Contest

Team standings of today's contest

Personal standings of today's contest

06, neerc, trains

luckyi
13 лет назад
32

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

Показать архивные | Написать комментарий?

luckyi

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

Может кто-нибудь рассказать как в J - Abstract Thinking придумывалось/доказывалось решение C(n, 6) + C(n, 5) * 5 + C(n, 4) * 4. Или может есть другое решение?

→ Ответить

Jughead

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

Просто выбираем множество точек, которые будут образовывать хорды:

1) из 6 точек можно одним образом соединить точки так, чтобы они попарно пересекались и каждая точка была использована. Таких комбинаций C(n, 6)

2) из 5 точек надо сделать три хорды, так чтобы ровно две хорды имели одну общую точку и все хорды попарно пересекались, таких способов всего 5 (отличаются поворотом), а выглядит способ, как буква "А", то есть угол, пересеченный третьей хордой.

3) из 4 точек. Ну и тут порисовав, можно понять, что всего 4 способа расстановки хорд, которые отличаются поворотом.

→ Ответить

luckyi

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

непонятно почему рассматриваем именно 4,5,6 точек и на них останавливаемся?

→ Ответить

Jughead

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

Окей, рассмотрим 3 точки, из которых можно собрать три хорды, которые пересекаются и имеют "хорошую" точку пересечения, таких комбинаций нет, потому что пересекающиеся хорды из трех вершин - это треугольник, он не подходит. 2, 1 тоже понятно почему. 7 и более, естественно тоже, потому как хорды в худшем случае занимают 6 вершин, а мы рассматриваем множества вершин, которые все будут заняты хордами.

→ Ответить

luckyi

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

я наверно совсем тугой... но почему хорды в худшем случае займут 6 вершин?

→ Ответить

Jughead

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

По задаче нужно найти количество способов выбрать три хорды с "хорошим" условием, в худшем случае каждая хорда занимает 2 вершины, не так ли?

→ Ответить

zurg

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

← Rev. 2 →

Нам дан правильный, выпуклый многоугольник, где никакие три вершины не лежат на одной прямой $\text{[math]}$ на любой прямой лежат максим две вершины многоугольника, а хорда - часть прямой, где концы это наши ровно две вершины.

И вообще, хорда в окружности соединяет ровно две точки с окружности!

3 хорды — 3 * 2 = 6 вершин.

→ Ответить

luckyi

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

понял. спасибо!

→ Ответить

Jokser

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

-8

Допустим точек 6. Тогда по первому случаю, все хорды пересекутся в одной точке. Эту точку нужно было считать треугольником?

→ Ответить

Jughead

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

Нет, это означает, что вот эти три хорды хорошие, потому что они имеют в пересечении внутреннюю точку. По задаче треугольник - это три хорды

→ Ответить

Jokser

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

Блин, а я прицепился к слову треугольник и такие точки вычитал из ответа.

→ Ответить

aropan

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

"...1) из 6 точек можно одним образом соединить точки так, чтобы они попарно пересекались и каждая точка была использована. Таких комбинаций C(n, 6)..."

нам же нужно не попарно пересекались, а чтобы хотя бы одна пара хорд пересекалась... не?

→ Ответить

Jughead

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

Нет, нужно попарное пересечение - в условие так написано, а для шести точек хотя бы пара хорд пересекаться будет - все будут пересекаться.

→ Ответить

pva701

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

как решалась F?

→ Ответить

luckyi

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

← Rev. 3 →

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

2) каждый блок обработаем независимо друг от друга

3) в блоке посчитаем кол-во отрицательных чисел. пусть будет k. Если k не четно, вычтем из него 1. Перемножим префикс блока, ~~пока не встретятся k отрицательных чисел~~ точнее пока не встретим k+1ое отрицательное число, его не обработаем. Аналогично с суффиксом. Запомним максимум

4) ответ довольно большой, поэтому все в длинных числах

→ Ответить

CherryTree

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

Можно не перемножать каждый раз, а находить сумму логарифмов(это быстрее). И перемножить все числа входящие в ответ в конце.

→ Ответить

pva701

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

можешь поподробнее? а то из-за этого только и не сдал, что не придумал, как неперемножая каждый раз?

→ Ответить

CherryTree

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

← Rev. 3 →

Можно считать не A1*A2*A3*A4...*An - это надо будет хранить в длинном числе и считать долго, а считать ln(A1)+ln(A2)+ln(A3)+ln(A4)...+ln(An) - это можно хранить в дабле и считать за O(R-L+1). ln тут - это натуральный, логарифм, например. И сравнивать тогда надо не длинные числа а даблы. Это правильно потому, что A*B = exp(ln(A)+ln(B)), где exp(x) - е в степени x(совсем не умею пользоваться LaTeX'ом).

upd: мой код

→ Ответить

pva701

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

надо будет это изучить, я в принципе понимал(был уверен даже), что что-то такое есть, но не знал что именно, ну спасибо за объяснение!

→ Ответить

pva701

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

ну до первых трех частей я догадался, но разве при перемножении суффиксов и префиксов тле не словится?

→ Ответить

luckyi

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

ну если в качестве основания брать не 10, а 10^k(хотя бы 10^6), то нет.

→ Ответить

pva701

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

странно, я вообще 10^15 пробовал - тле12

→ Ответить

luckyi

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

ну 10^15 могут лонги тормозить, не знаю. Может вектора там какие-нибудь?..

→ Ответить

pva701

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

да я и 10^9 пробовал, ну наверное где то накосил кроме длинки((

→ Ответить

aropan

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

могло быть переполнение при умножении на три так как 3 * 10⁹ > 2³¹

→ Ответить

dalex

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

Если F - вот эта задача (http://acm.timus.ru/problem.aspx?space=1&num=1587), то давным-давно я написал это решение: http://pastebin.com/HG6WdW6k, там, кажется, вычисляются лучшие степени положительных и отрицательных единиц, двоек и троек, и только в самом конце - сравнение в даблах и ответ в BigInteger.

→ Ответить

CherryTree

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

Расскажите, пожалуйста, как решать C.

→ Ответить

mr146

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

← Rev. 2 →

mincost-maxflow. Можно разбить поле на группы по 4 клетки, получающиеся поворотами друг из друга. Вершины сети - буквы и группы. Стоимости и пропускные способности считаются несложно. Как-то так.

→ Ответить

aropan

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

"...Вершины сети - клетки исходного поля, буквы, группы..."

А почему клетки исходного поля будут вершинами?.. У меня из истока идут ребра в буквы, из букв в группы и из групп в сток...

→ Ответить

mr146

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

Прошу прощения. Fixed.

→ Ответить