Форум DL

Мой профиль

Отсчёт на данный момент:
Задачи G,K,D, на мой взгляд, решены полностью. Задача B в разработке. До задачи J не дошёл.

Мой профиль

E 2020
Предположим, есть координатные оси x и y
начальная позиция в т.(0,0)
Пусть мы находимся в т.(i,j)
мы можем вывести '(' и переместиться в (i+1,j+1)
мы можем вывести ')' и переместиться в (i+1,j-1)
Наш путь должен оканчиваться в т. (2<=n<=36)
если провести линии через всех точки что мы пошли и взять линию от (0,0) до (0,n), то мы получим некоторую фигуру у которой есть центр масс в точках 0<x1<n и 0<y1<n
Нужно используя '(' и ')' построить фигуру у которой центр масс будет в т.(x1,y1) с погрешностью не более 10^-7
Прикол:
данный нам центр имеет погрешность не более 10^-9
Ввод:
n=6 x1=3.4 y1=0.6
Вывод:
()(())

Как будет выглядеть фигура
^y
|
| /\
|/\/ \
+------->x
Идеи и вопросы:
Во первых в условии не сказано что нельзя опускаться по y ниже 0, что довольно странно
Центр масс может находиться за площадью фигуры
Любую фигуру можно разбить на прямоугольные равнобедренные треугольники, основание которых параллельно Оx (Площадь равна 1)
у этих треугольников центр масс находиться на середине основания по x и на 1/3 по y от основания
2 треугольника можно объединить в ромбы c центром масс в т. пересечения его диагоналей (Площадь равна 2)
Когда мы выбираем '(' мы строим треугольник если находимся на (i,0) или ромбы(ромб) и треугольник если находимся на (i,k) k>0
Максимально кол-во ромбов и треугольников равно 171
Формула для нахождения центра масс всей фигуры зная центры масс фигур из которых состоит данная нам фигура
X=(x1*s1+x2*s2+...+xn*sn)/(s1+s2+..+sn)
Y=(y1*s1+y2*s2+...+yn*sn)/(s1+s2+..+sn)
Скорее всего тут делается как-то через дихотомию, перебором вряд ли т.к. будет очень много вариантов
HELP

Мой профиль

J 2020
Тесты:
__#_____
--------
2
3 2

_#
--------
-1

___
--------
0

#_#
--------
2
1 1

##
--------
1
2

#
--------
1
1

###_###_#
--------
3
3 3 1

__#___#____
--------
3 3 1

Мой профиль

Егор Короткевич:

E 2020
...
Во первых в условии не сказано что нельзя опускаться по y ниже 0, что довольно странно.
...

В условии сказано, что "Consider a balanced bracket sequence s with one type of brackets: ‘(’ and ‘)’."
"balanced bracket sequence" значит, что открывающая скобка всегда перед закрывающей, т.е. у нас не может быть последовательности "))(()(".
Таким образом, мы не можем опуститься ниже 0 по y.

"()(())" будет выглядеть вот так:

 ()(())
|
|   /\
|/\/  \
+------->x

Тут интересный момент. n <= 36.
Т.е. пар скобочек у нас только 18.
Из комбинаторики я знаю, что количество правильных(сбалансированных, т.е. тех, которые в нашей задаче) скобочных последовательностей равно числу каталана.
В нашем случае количество возможных вариантов правильных скобочных последовательностей = C_18 = 477638700 = 4*10^8.

Число 10^8 является намёком от автора задачи на то, что задачу нужно решать перебором.
Но в каждой итерации для заданной скобочной последовательности нужно будет находить центр масс, а это довольно трудоёмкая операция. Нужно как-то написать достаточно быстрый код, чтобы оно успело просчитать все варианты.

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

Мой профиль

Егор Короткевич:

J 2020
Если в начале массива есть 1 или в конце массива есть 1, то закидываем во множество кол-во единиц в начале и в конце массива, убираем из массива эти единицы и один 0, в итоге у нас получается начало или конец массива в другом, повторяем это пока это возможно, в случае если массив станет иметь 0 элементов выводим -1

Не понимаю, следующее:

Убираем из массива эти единицы и один 0.

Один ноль с начала, с конца, с начала и конца?

Мой профиль

Я придумал решение E.
Для генерации правильных скобочных последовательностей длины N действуем по следующему алгоритму:
1) Пусть у нас есть отрезок [0, N-1]
Пример для N=6: [0, 5]
2) Мы перебираем 2^(N/2 - 1) способов разбиения его на подотрезки скобками ")("
Пример для N=6: (....), (..)(), ()(..), ()()()
Соответствующие отрезки:

(....) -> [1, 5]
(..)() -> [1, 2]
          [6, 5] -- пустой отрезок
()(..) -> [2, 1] -- пустой отрезок
          [3, 4]
()()() -> [2, 1] -- пустой отрезок
          [4, 3] -- пустой отрезок
          [6, 5] -- пустой отрезок

3) Повторяем операцию рекурсивно(по выбору разбиения) для каждого набора отрезков.
Но не для каждого отрезка отдельно, а для всего набора отрезков одним махом.
Я не уверен, что знаю, как это объяснить, но мы как-бэ строим скобочки так, чтобы треугольники строились по уровням.
Типо bfs, а не dfs.
Вот рисунки:

N = 6
|......
|         -- мы ещё не построили ни одного уровня треугольников
|     6
+-------->x 

Выбираем разбиение (....)
|(....)
|         -- мы уже построили 1-ый уровень 
|/----\
+-------->x 

Выбираем разбиение (()())
|(()())
| /\/\    -- мы уже построили 2-ый уровень
|/    \
+-------->x 

Больше разбиений выбрать нельзя, поэтому возвращаемся к предыдущему уровню
|(....)
|         -- 1-ый уровень 
|/----\
+-------->x 

.Больше разбиений выбрать нельзя(которые мы не выбирали раньше), поэтому возвращаемся к предыдущему уровню
|......
|         -- 0-ый уровень 
|      
+-------->x 

Выбираем разбиение (..)()
|(..)()
|         -- мы уже построили 1-ый уровень 
|/--\/\
+-------->x 

Выбираем разбиение (())()
|(())()
| /\      -- мы уже построили 2-ый уровень
|/  \/\
+-------->x 

Больше разбиений выбрать нельзя, поэтому возвращаемся к предыдущему уровню
|(..)()
|         -- 1-ый уровень 
|/--\/\
+-------->x 

.Больше разбиений выбрать нельзя(которые мы не выбирали раньше), поэтому возвращаемся к предыдущему уровню
|......
|         -- 0-ый уровень 
|      
+-------->x 

Выбираем разбиение ()(..)
|()(..)
|         -- мы уже построили 1-ый уровень 
|/\/--\
+-------->x 

Выбираем разбиение ()(())
|()(())
|   /\    -- мы уже построили 2-ый уровень
|/\/  \
+-------->x 

Больше разбиений выбрать нельзя, поэтому возвращаемся к предыдущему уровню
|(..)()
|         -- 1-ый уровень 
|/\/--\
+-------->x 

Больше разбиений выбрать нельзя(которые мы не выбирали раньше), поэтому возвращаемся к предыдущему уровню
|......
|         -- 0-ый уровень 
|      
+-------->x

Больше разбиений выбрать нельзя(которые мы не выбирали раньше), поэтому завершаем рекурсивное выполнение

Таким образом мы генерируем все возможные пары скобочек.
При этом на каждом этапе мы может определить минимальный и максимальный y, который получится у центра масс в конце
Например для такого разбиения:

|(....)(....)
|            
|/----\/----\
+------------->x 

y_min достигается если сделать так:
|(()())(()())
|
| /\/\  /\/\        y_min = (какая-нибудь формула, которую мы потом с Егором придумаем)
|/    \/    \
+------------->x 

y_max достигается если сделать так:
|((()))((()))
|
|  /\    /\
| /  \  /  \        y_max = (какая-нибудь формула, которую мы потом с Егором придумаем)
|/    \/    \
+------------->x

Т.е. на каждом этапе можно вычислять y_min и y_max
И если нужная нам y не входит в отрезок [y_min, y_max], то можно дальше это разбиение не рассматривать.

Таким образом мы значительно сократим количество скобочных последовательностей, которые нужно перебрать.

Мой профиль

Владислав Хамков:

Я придумал решение E.

Формула для нахождения центра масс:
X=1+Z[(4i+1+ji)/(4i+3-ji)] (Z от i=2 до i=n/2)
Y=n/4-Z[1/(f^2+f+1)]/6 (Z от i=1 до i=n/2)
f=2i-ji-1
Z - знак суммы
i - какая по счету '('
ji -номер '(' в строке

Мой профиль

С 2020
Дан кактус (неориентированный граф в котом каждое ребро принадлежит максимум одному циклю (может и не принадлежать вообще))
нужно сделать этот кактус сильным - добавить минимальное кол-во ребер так чтобы это был все еще кактус и нельзя было добавить еще какое-то ребро чтобы он был все еще кактусом
Граф не может иметь несколько ребер между двумя точками
ВВод(дано несколько тестов идущих до 0 0):
1<=n<=10^5 0<=m<=10^5 (вершины пронумерованы от 1 до n, и содержат m путей,)
k1 a1 a2 a3 ... ak1 (кол-во и номера вершин образующие путь т.е. есть ребра a1=a2 a2=a3 a3=a4 ... ak-1=ak = - Знак связи)
k2 a1 a2 a3 ... ak2
...................
km a1 a2 a3 ... akm
//- остальные тесты
0 0 (конец тестов)
Вывод:
f (кол-во добавленных ребер)
aj aj1
ao ao1
.....
aq aq1 (номера вершин образующие данные ребра)
// - остальные ответы
Пример:
6 1
7 1 2 5 6 2 3 4
3 1
4 1 2 3 1
5 2
3 1 3 5
3 1 2 4
7 2
6 1 2 3 4 5 3
3 6 5 7
0 0
--------------------
1
1 4
0
1
5 4
2
1 3
6 7
Решение:
Решение заключается в поиске концов (тупиков) графа и создании циклов
Ищем точку принадлежащую любому циклу из которой можно добраться до любой вершины не проходя по ребру принадлежащему этому циклу.
Будем называть эту точку - точкой связи
Пока из точки связи можно попасть в другую точку связи путем не принадлежащим ни одному циклу, то выполняем алгоритм 2 иначе выполняем алгоритм 1
Алгоритм 1:
Предположим что у точки связи есть n тупиков
тогда соединим каждые 2 тупика,главное чтобы 2 тупика были соединены только друг с другом и не с кем более.
Если остается 1 тупик, то соединяем его с точкой связи
Проделываем это с каждой точкой связи
Алгоритм 2:
Если у обоих точек связи есть тупики то мы соединяем 2 тупика(один из первой точки связи, второй из второй точки связи) и переходим к Алгоритму 1 для каждой из этих точек, если у них остались еще тупики
Если только у одной есть тупики, то соединяем его с другой точкой связи и переходим к Алгоритму 1 для точки, если у нее остались еще тупики
Если у обоих точек связи нет тупиков то соединяем эти точки связи
Итог: мы получили что хотели
Возможные проблемы:
если тупик соединен одним ребром с точкой связи и более нет других тупиков, то его нужно связать с данной точкой связи и в итоге у нас получится что две вершины связаны двумя ребрами (В условии сказано что данный нам граф не имеет более 1 ребра между двумя вершинами, но не сказано что мы так не можем делать)
если вершина одна, то ее не нужно связывать с самой собой(m может быть равно 0)
Т.к. у одной точки связи может быть несколько путей, то нужно выполнять Алгоритм 2 для каждой пары точек связи(путь между которыми не принадлежит ни одному циклу), а не для каждой точки связи и выполнять Алгоритм 1 для какой-либо точки связи, если больше нет точек связи связанных с данной(путь между которыми не принадлежит ни одному циклу)

The total sum of all values of n and the total sum of all values of m
throughout the input both do not exceed 10^5

Мой профиль

I 2020
Ставки!
есть 1<=n<=1000 человек, они делают ставки 0 или 1, мы также делаем ставку 0 или 1.
мы делаем ставку последними и знаем, на что поставили другие
Далее нам дают правильный ответ: 0 или 1
всего 1<=m<=10000 ставок
Нам нужно допустить не более b*1.3+100 ошибок, где b - это минимальное среди остальных игроков кол-во допущенных ошибок.
Программа является интерактором
Пример:
n=3 m=4
000 - ставки других игроков, где i-тое число - ставка i-того человека
------
0 - наша ставка(вывод)
------
1 - правильный ответ
100 - следующие ставки других игроков
------
0 - наша следующая ставка
------
1 - следующий правильный ответ
001
------
1
------
0
111
------
1
------
1
Итого: мы допустили 3 ошибки, минимальное кол-во ошибок других игроков - 1, 1*1.3+100=101.3>3
Идеи:
Вариант, где мы берем ставку наибольшего кол-во людей допустивших наименьшее кол-во ошибок не сработает
т.к. в худшем случае мы допустим 10^4 Ошибок, а минимальное кол-во ошибок других игроков - 1111
1111*1.3+100=1544<10^4
Также в условии сказано, что всего будет 200 тестов

There are 200 test cases in this problem.

что наталкивает мысль о использовании вероятности(рандома)
HELP

Мой профиль

B 2020
Тесты:
2 2
10
11
-------
2
0 1

3 4
001
111
101
011
-------
6
2 0 R 1 2 0

1 1
1
-------
1
0

001
011
101
010
111
--------
6
2 0 3 R 1 2

Мой профиль

C 2020
6 1
7 1 2 5 6 2 3 4
3 1
4 1 2 3 1
5 2
3 1 3 5
3 1 2 4
7 2
6 1 2 3 4 5 3
3 6 5 7
0 0
---------
1
1 4
0
1
5 4
2
1 3
6 7

15 6
13 1 2 3 4 1 5 6 7 8 9 7 10 5
2 10 11
2 10 12
2 9 13
2 9 14
2 9 15
1 0
2 1
2 1 2
0 0
--------
4
4 5
13 14
9 15
11 12
0
1
1 2

4 1
5 1 2 3 1 4
5 1
6 1 2 3 1 4 5
6 2
6 1 2 3 1 4 5
2 4 6
0 0
--------
1
3 4
1
3 5
2
3 5
4 6

Мой профиль

E 2020
Тесты:
6 3.4 0.6
-----------
()(())

4 2 0.66666666
-----------
(())

Мой профиль

I 2020(Проверка: кол-во ошибок <1.3b+100)
Тесты:
3 4
000
1
100
1
001
0
111
1
Так-как минимальное кол-во ошибок равно 100, То нам минимум нужен тест из 101 ставки, вообщем тесты лучше генератором тестов делать

Мой профиль

Егор Короткевич:

С 2020
Ищем точку принадлежащую любому циклу из которой можно добраться до любой вершины не проходя по ребру принадлежащему этому циклу.

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

Мой профиль

Илья Либуркин:

Егор Короткевич:

С 2020
Ищем точку принадлежащую любому циклу из которой можно добраться до любой вершины не проходя по ребру принадлежащему этому циклу.

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

можно и так сказать