УРКОП 2011 - Обсуждение

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

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

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

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

№	Пользователь	Рейтинг
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	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Всё →

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

→ Прямой эфир

Детальнее →

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

УРКОП 2011 - Обсуждение

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

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

Сслыка на задачи/результаты: http://acm.timus.ru/monitor.aspx?id=100

обсуждение, уркоп 2011

goryinyich
13 лет назад
74

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

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

goryinyich

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

У кого-нибудь были проблемы с тестом #57 в задаче C? Надо полагать, он на точность. Но никакие шаманства не помогли сдать задачу...

→ Ответить

eik0u

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

Я подгоном точности дошел до 62-ого... с 57-ым не было проблем. Мой епсилон - 1e-5.

→ Ответить

goryinyich

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

У меня там при любых EPS 1e-2 ~ 1e-6 получалось ВА57...

→ Ответить

Alex_KPR

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

у меня прошла только с EPS = 1e-9

→ Ответить

goryinyich

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

Странно. Я делал все вычисления до исчерпания точности, но начиная с 1e-7 получал ВА на более ранних тестах. Ты как ее решал (мой подход описан внизу)?

→ Ответить

Alex_KPR

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

мой подход тоже описан внизу)

→ Ответить

tunyash

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

Нас выручил эпсилон 1e-8. Был 1e-6.

→ Ответить

olpetOdessaONU

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

Задача С решается в целых числах. Главное - в нужных местах использовать лонг лонг.

→ Ответить

pkhaustov

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

-7

Меня больше удивляет задача J. Я написал решение, в котором не мог найти ошибку всю заморозку, но так и не прошел дальше второго теста. Условие было написано отвратительно, но для тимуса это привычно. Вообще, я до сих пор не уверен, что удаление одного символа занимает одну секунду. Надеюсь, что это так. Поправьте меня, если я ошибаюсь. Те, кто решил эту задачу, пожалуйста, поделитесь тем, как решали ее, может быть это подскажет мне где же я ошибся.

→ Ответить

Alex_KPR

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

аккуратно написал Дейкстру на куче

→ Ответить

pkhaustov

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

То есть можно было теоретически выбрать слово какое-то стрелочками ("вверх" или "вниз") и при этом считалось бы, что у нас набрано это слово целиком? То есть после того, как мы выбрали слово стрелочками, мы могли бы удалить из него пару букв и заменить их?

→ Ответить

Alex_KPR

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

нет

состояние описывается парой (индекс, количество набранных букв)

→ Ответить

hydrastuff

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

а какие у тебя веса в графе? не единичные что ли?

→ Ответить

oversolver

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

а как сделать единичные?

→ Ответить

hydrastuff

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

← Rev. 2 →

кажется можно ввести другие состояния и добавить новый переход - изменение последней буквы (например "a" -> "b", "b"-> "c", из "с" нет перехода).

→ Ответить

oversolver

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

а, ну такое в голову приходило, но почему-то показалось, что будет 26*100000 состояний, и это в итоге даже дольше работать будет.

→ Ответить

Alex_KPR

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

веса не единичные

→ Ответить

goryinyich

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

← Rev. 2 →

Не туда

→ Ответить

mexmans

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

Как решать задачу G, ставил вместо вопросов одинаковые символы и релаксировал ответ ВА 30?

→ Ответить

goryinyich

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

Нужно было рассмотреть 2 случая: когда в обоих строках вместо вопросов один и тот же иероглиф, и когда в каждой строке - какой-то свой иероглиф (но один и тот же для каждой строки). Такое решение зашло.

→ Ответить

pkhaustov

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

У нас прошло следующее решение:

Найдем самый популярный символ C1 в первой последовательности. Найдем самый популярный символ во второй последовательности C2.

Теперь выберем лучшее из следующих решений:

1) Заменить все нули в первой последовательности на C2, а во второй - на C1.

2) Заменить все нули в первой и второй последовательности на C (где C принимает все возможные значения от 1 до 100000).

Проверку несложно осуществлять за O(1).

→ Ответить

AlexanderBolshakov

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

Какая самая распространенная ошибка в L?

→ Ответить

Alex_KPR

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

возможно, она проявляется на тесте:

100

→ Ответить

AlexanderBolshakov

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

У меня ответ 0.0000000000, он правильный?

→ Ответить

Alex_KPR

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

уву, правильный

→ Ответить

Alex_KPR

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

может это поможет?

→ Ответить

Creed

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

1.2600000?

→ Ответить

aropan

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

1
8
0
0.0000000000

1
7
0
2.1600000000

→ Ответить

AlexanderBolshakov

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

Мда, я редкостный идиот: неправильно посчитал минимальное расстояние, на котором можно переходить дорогу перед машиной - 28.8 вместо 8 :(.

→ Ответить

goryinyich

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

← Rev. 2 →

Кто как решал задачу С (Angry birds)?

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

Для двух данных обезьян угол и скорость, под которыми нужно стрелять, я находил так: угол ищем бинарным поиском. При данном угле из несложного уравнения получаем (точно) скорость, которую нужно развить, чтобы "убить" первую (левую из двух) обезьяну. После этого смотрим: если выстрел прошел под второй (правой) обезьяной, угол выстрела нужно уменьшать, а если над - то увеличивать.

→ Ответить

Alex_KPR

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

два бинпоиска вложенных, один по составляющей vx, другой - по vy

еле затолкал из-за точности =)

→ Ответить

goryinyich

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

По сути, подход тот же. Может, они не любят тригонометрию в решениях...

→ Ответить

Alex_KPR

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

у меня нет никакой тригонометрии

я даже корни нигде не извлекаю :)

→ Ответить

goryinyich

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

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

→ Ответить

Stigius

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

Все авторские решения, что у нас были, просто строили уравнение параболы в явном виде и работали уже с ним. Бинпоиски и тригонометрию действительно было упихать сложно. Тесты 57-62 - на проверку точности и некоторых граничных случаев.

→ Ответить

2222

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

← Rev. 2 →

У меня отличие в том, что когда зафиксировали 2ух обезьян, получаем систему линейных уравнений относительно {p, q²}:

p · x_i - q²· x_i² = y_i

p · x_j - q²· x_j² = y_j

Проверяем q² > = 0, после чего подставляем остальных обезьян в уравнение. Это всё делается в целых числах, чтоб не было проблем с переполнением брал по разным простым модулям.

→ Ответить

Fdg	13 лет назад, # \| ← Rev. 2 → 0 Почему в G не проходит такое решение? Нам нужно максимизировать сумму cnt1[i]*cnt2[i], где i=1...100000. На каждом шаге, пока не останется знаков вопроса, я выбирал такое число, чтобы сумма была максимальной. В итоге ВА13. → Ответить

aropan

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

← Rev. 5 →

Рассмотрим тест:
7
0 0 1 1 2 2 2
9
0 0 1 1 1 1 2 2 2

30

11
0 0 0 1 2 2 2 3 3 3 3
11
0 0 0 1 1 1 1 2 2 2 3

77

10
0 0 1 2 2 2 3 3 3 3
11
0 0 0 1 1 1 1 2 2 2 3

72

Нули из первой строки ты будет превращать в 1, т.к. это будет максимизировать твою сумму, а нули из второй строки в 3... Но лучше будет все нули превратить в 2.

UPD. Шутканул, после того как ты поставишь 1 в первой строке, во второй ты тоже выберишь 1, сейчас додумаю...

→ Ответить

Fdg	13 лет назад, # ^ \| ← Rev. 2 → 0 У меня тоже ответ 30. Сначала нули из первой строки превращаются в 1, а потом у нас в первой строке уже больше 1 и нули из второй строки тоже превращаются в 1. UPD: Спасибо, я понял → Ответить

aropan

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

Вот так должен быть фэил....

→ Ответить

Fdg	13 лет назад, # ^ \| 0 На втором тесте тоже падает → Ответить

Alex_KPR

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

+56

→ Ответить

goryinyich

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

Я автора знаю, с удовольствием посмотрел бы раунд бокса между вами =)

Задача на аккуратное прочтение =)

→ Ответить

Kostroma

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

мы с +2 сдали)))

→ Ответить

droptable

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

А то ты меня не знаешь :)

→ Ответить

Alex_KPR

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

знаю, но я же от лица Чаки писал =)

→ Ответить

droptable

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

→ Ответить

Creed

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

Как решать задачу K. На контесте были идеи, но писать не осмелились

→ Ответить

Ripatti

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

как то так:

	sort(Z+1, Z+n+1);
	cout << 5 << "\n";
	cout << -o_O << " " << o_O << "\n";
	cout << -o_O << " " << -o_O << "\n";
	cout << Z[k].FI << " " << -o_O << "\n";
	cout << Z[k].FI << " " << Z[k].SE << "\n";
	cout << Z[k].FI-1 << " " << o_O << "\n";

правда, это решение не совсем верно (можно подобрать тест когда одна сторона будет иметь длину 0)
но оно как то зашло))

→ Ответить

Alex_KPR

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

и каким образом можно подобрать такой тест? ;)

→ Ответить

Ripatti

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

+10

надо чтобы
Z[k].FI = -o_O+1

→ Ответить

Alex_KPR

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

хм, и правда, моё решение выводит две одинаковых точки =)

→ Ответить

goryinyich

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

← Rev. 2 →

Я подобрал даже до первого сабмита. Правда, все равно +1, потому что сначала выводил вершины в порядке по часовой стрелке =)

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

→ Ответить

Ripatti

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

← Rev. 2 →

не туда

→ Ответить

aropan

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

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

→ Ответить

Jokser

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

← Rev. 2 →

Я выпуклую оболочку написал для первых k точек в порядке сортировки. В конце надо рассмотреть тонкие случаи, когда в оболочке вышло 1 или 2 вершины.

→ Ответить

tunyash

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

← Rev. 2 →

Делали так же, только добавили в выпуклую оболочку точки (-1e9+1, -1e9) и (-1e9,-1e9+1). Все случаи отпадают.

→ Ответить

Ripatti

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

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

→ Ответить

AlexanderBolshakov

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

Я написал через другое предположение: палки образуют тупоугольный треугольник с углом 135 градусов, третья сторона которого - гипотенуза равнобедренного прямоугольного треугольника (катеты - береза и земля). То, что прямоугольный треугольник должен быть равнобедренным, доказывается элементарно, угол 135 градусов - через дифференцирование. Угол 135 градусов опирается на дугу в 270 градусов, а это оставшаяся часть окружности.

→ Ответить

Ripatti

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

А, ну да, дифференцированием можно

А как нибудь красиво это доказывается?:)

→ Ответить

AlexanderBolshakov

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

Я глубоко подумал: по-моему, красивее дифференцирования ничего найти не получится (т.к. хотя бы то, что из всех прямоугольников наибольшая площадь у квадрата, доказывается как раз через дифференцирование).

→ Ответить

Stigius

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

Это же школьный контест. Конечно, доказывается.

Разобьём наш 4-угольник на 2 треугольника диагональю, соединяющей точки примыкания палок к берёзе и к земле. Пусть длины палок - a и b. Зафиксируем какую-то длину этой диагонали L. Тогда максимум площади нижнего треугольника очевидно достигается, когда эта диагональ идёт под углом 45. Тогда эта площадь равна 1/4*L^2.

Пусть теперь угол между палками равен p. Тогда площадь верхнего треугольника равна 1/2*a*b*sin(p). L^2 = a^2+b^2-2*a*b*cos(p). Итого суммарная площадь 1/2*a*b*sin(p) + 1/4*(a^2+b^2-2*a*b*cos(p)) = 1/4*(a^2+b^2) + 1/2*a*b*(sin(p)-cos(p)) = 1/4*(a^2+b^2)+1/sqrt(2)*a*b*sin(p-45). Максимум синуса достигается в 90, т.е. при p=135. Итого ответ 1/4*(a^2+b^2)+1/sqrt(2)*a*b

→ Ответить

aropan

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

а я то думаю почему мои тернарники и градиент так плохо запихиваются....

→ Ответить

goryinyich

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

У меня с тернарником по L (в терминах доказательства выше) никаких проблем не возникло

→ Ответить

Kostroma

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

мда, тупо 2 вложенных тернарника по проекциям на оси заходят...

→ Ответить

AlexanderBolshakov

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

Я тоже об этом подумал, но предпочел все-таки вывести формулу и написать решение за O(1).

→ Ответить

72VanVector_SevNTU

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

Хотелось бы узнать, как по-человечеки Кубик-Рубика решать?? (решал bfs)

→ Ответить

Kostroma

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

← Rev. 3 →

ну это почти по-человечески

мы просто для каждого слоя искали его нужный сдвиг (перебрав сначала общую картинку)

скидываем цвета, проходясь по кругу, в вектор, и с такими векторами уже все просто

→ Ответить

Alex_KPR

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

+13

for(int i=0;i<6;i++)

{

cin>>x;

if (i!=2 && i!=3) v.pb(x);

}

int ans=100;

for(int i=1;i<=4;i++)

{

int now=0;

for(int j=0;j<v.sz;j++)

{

int m=min((i-v[j]+16)%4,(v[j]-i+16)%4);

now+=m;

}

ans=min(ans,now);

}

cout<<ans;

→ Ответить

tunyash

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

← Rev. 2 →

Рассмотрим левый верхний квадрат 2*2. Заметим, что если в нем все цвета одинаковые, то картинка такая, какая нужна. Тогда переберем цвет, который в нем будет. Каждая из четырех клеток квадрата лежит на отдельном слое, а каждый слой представляет из себя зацикленную посл-ть 1, 2, 3, 4. Пусть у нас в некоторой клетке верхнего квадрата стоит число i, а мы хотим получить j. Понятно, что мы можем циклически сдвинуть последовательность 1-2-3-4 вправо или влево. Собственно, перебираем цвет левого верхнего квадрата и банально считаем стоимость сдвига его элементов в нужный цвет.

→ Ответить

Alex_KPR

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

код этот идеи тут :)

→ Ответить