Форум DL

Мой профиль

У меня два предложения

1) Начиная с этой олимпиады все задачи, которые не решил никто, я копирую в курс
"Подготовка к IOI 2013"
- предлагаю сдавать ТАМ тоже те задачи, которые дорешиваете.

2) После дорешивания пытаться коротко описывать решения в форуме
(хотя бы так, как Леша Ропан делал еще недавно).

Убежден, это и Вам будет полезно, и всем другим олимпиадникам Гомеля (и не только)
текущего и последующих поколений.

Ну и заодно, надеюсь, возродим и оба конкурса
- Подготовка к IOI
- Программирование-профи (Р/О)

Мой профиль

Федор вопрос задал.
Дима и Вадим - пожалуйста, помогите найти на него ответ.

Мой профиль

Сдал H. http://dl.gsu.by/task.jsp?nid=1055387&cid=840
Разбор.Общая идея. Перебираем все комбинации строк и для каждой комбинации вычисляем сумму элементов в одинаковых столбцах. Помечаем, что такая сумма была найдена, запоминаем номер столбца и запоминаем для этой суммы номер комбинации строк. Вычисляем разницу той суммы, что надо и той, что вычислили. Смотрим в массиве маркировок была ли эта разница уже вычислена для данной комбинации строк. Если была,то мы шашли ответ.
Алгоритм

Заведем матрицу меток из 4000000 столбцов и 2 строк(Mar).
В первой строке этой матрицы будем запоминать номер столбца в котором получилась сумма равная индексу столбца матрицы, во второй номер комбинации строк.

Номер комбинации строк изначально равняется 1.

Перебираем 2 строки двумя циклами(i-первая строка, j-вторая).
Идем циклом по столбцам с конца матрицы.

Суммируем элементы S=A[i,k]+A[j,k].

Запоминаем в массиве маркировок Mar[s,1] номер
текущего столбца,а в Mar[s,2]= номеру текущей
комбинации строк.

Дальше от той суммы, что надо получить отнимем
S и запомним результат` в S1.

Посмотрим если Mar[s1,1] было помечено для
текущей комбинации строк, т.е. Mar[s1,2]=текущая
комбинация, то выводим ответ (i,k,j,mar
[s1,1]).Все можно написать exit.

Если нетто переходим к следующему столбцу.

Когда цикл по столбцам закончится мы переходим к следующей комбинации строк увеличив на 1 номер этой комбинации.

Если мы перебрали все комбинации строк и ответа не нашли то -1.

Пример.
1 2 4 3
3 4 5 2
1 3 2 2

Сумма=8
Например i=1 j=3. Это будет 2-я комбинация строк.
Рассматриваем столбец 4.
S=3+2=A[1,4]+А[3,4]=5 Помечаем Mar[5,1]=4 Mar[5,2]=2;
S1=8-5=3 Mar[3,1] для текущей комбинации не помечен. Переходим к следующему столбцу
S=4+2=6 Mar[6,1]=3 Mar[6,2]=2;
S1=8-6=2 Mar[2,1] для текущей комбинации не помечен. Переходим к следующему столбцу
S=1+1=2 Mar[2,1]=1 Mar[2,2]=2;
S1=8-2=6 Mar[6,1] для текущей комбинации помечен так как Mar[6,2]=номеру текущей комбинации. Выводим ответ.

Как то так. Если кому не понятно будет постараюсь написать лучше.

______________________
Work hard and win a prize

Мой профиль

Отлично, Федор

Несколько просьб:

1) На условиях задачи нажимать ссылку "Обсудить задачу в форуме"
(тогда прямо с условия задачи будет прямой доступ к этому ее обсуждению для всех последующих читателей и писателей)

2) К сожалению, ПОКА автоматически не вставляется тема - поэтому нужно ВРУЧНУЮ скопировать в это поле информацию о задаче на розовой полосе, например

Россия-И. Командные\10_Rup6 - "oil" 108840

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

Мой профиль

Стало намного лучше, чем было.
Но еще две просьбы, Федор

1) Enter нажимать (после 70 символов).
В том тексте, который находится внутри тега PRE
У тебя наверно очень большой монитор. Я сейчас сижу на обычном, и твою общую идею читать очень неудобно - приходится каждую строку скроллировать вправо-влево.

2) Лучше писать НОВОЕ сообщение, а не заменять старое.
Спасибо

Мой профиль

Дима сдал G,H,I.
Вадим сдал B,E.
Федя сдал D.

Долги:
Дима:
олимпиада 02.09.2012
- D,E,F,J
олимпиада 09.09.2012
- C,F.

Федор:
олимпиада 12.08.2012
-D
олимпиада 26.08.2012
-A,B,I,J
олимпиада 02.09.2012
-B,D,E,F,J
олимпиада 09.09.2012
-E

Вадим:
олимпиада 26.08.2012
- I,J
олимпиада 02.09.2012
- D,E,F,J
олимпиада 09.09.2012
- C,F.

1. Решения пишут по очереди, пока сдают.
2. Чем ближе к концу олимпиады, тем больше тестируем перед отсылкой.
3. Для каждой задачи делать отдельную папку.
4. Если ты работал над задачей и уверен решении, то нет смысла отправлять писать другого.

______________________
Never say never.

Мой профиль

А еще Вы вчера ушли не проделав анализ ошибок

E +5
G +2
H +7

Насколько я помню, Вадим говорил про две свои ошибки
- неправильно считал память (недопонимал, как она выделяется)
- не поставил Int64

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

Мой профиль

F+2 - Вадим. Не внимательно прочитал условие.
G+1 - Вадим. Не рассмотрел случай.
H+2 - Дима. Опечатка.
I-12 - Не предусмотрели крайний случай. Градиентный спуск на бесконечности.

Долги:
Дима:
олимпиада 02.09.2012
- D,E,F,J
олимпиада 09.09.2012
- C,F.

Федор:
олимпиада 12.08.2012
-D
олимпиада 26.08.2012
-A,B,I,J
олимпиада 02.09.2012
-B,D,E,F,J

Вадим:
олимпиада 26.08.2012
- J
олимпиада 02.09.2012
- D,E,F,J
олимпиада 09.09.2012
- C,F.

Мой профиль

A - ее сдавало мало команд, поэтому мы ее не решали.
F - сначала была неправильная идея, Кун нельзя писать для поиска макс потока мин. стоимость.
G - в начале неправильно вывели формулу.
K - сдали(не внимательно прочитали условие)
L - сдали
M - сдали

Д.з.
Диме - разобраться с ограничениями на применение Куна.
Вадим - вспомнить и найти область применения с Венгерским алгоритмом.
Федя - решать то что хорошо сдается.
______________________
Never say never.

Мой профиль

Обсуждение GP of Belarus на Codeforces

F — задача о назначениях, которая решается Венгерским алгоритмом http://e-maxx.ru/algo/assignment_hungary

Мой профиль

A+6:Ошибки в коде.
B+4:3 раза посылали не на ту машину.
C+:придумали,написали.
D-9:писали и отлаживали...
E:сдали.
G+1:не наша вина.
J+3:Ошибки в коде.
Д/з:
Дима: D,H,I.
Вадим: D,H,I.

P.s. внимательнее продумывать детали реализации.

Мой профиль

Альтернативное решение задачи A

Покороче Вашего будет ...

Мой профиль

OpenCup (14 октября) обсуждение на Codeforces

Мой профиль

Авторские разборы Отборочной ко ВКОШП 2012

Мой профиль

Насколько я понял, правильные идеи Вы могли (или даже смогли?) придумать ко всем (или почти ко всем? задачам).
Получается Ваша проблема номер 1 - "выпрямлять руки".
То есть, закрепить навыки писать быстро, без ошибок, учитывать "ТОНКИЕ МОМЕНТЫ".
Это реально делается за 20 дней интенсивной практикой самостоятельного решения непростых задач.
НАПРЯГИТЕСЬ!!!

Цель напряженной подготовки - побороться за медали на ВКОШП-2012.