Доброе утро/день/вечер, Codeforces.

Добрый день, Codeforces.

Доброе утро/день/вечер.

Сегодня увидел в одном магазине Саратова интересную вешь, сфоткал её и получилось следующее:
http://imagebin.org/128307

Матрица инцидентности или матрица инциденций - это один из способов задания графа.

Это матрици размера n· m, - где n - количество вершин, а m - количество ребер.

В позиции (i, j) стоит 1 если i-я вершина является началом дуги j, -1 если i-я вершина является концом дуги j и 0 в всех остальных случаях. 

Эта структура за всю мою практику не разу не применялась, однако она настойчиво упоминается в различной литературе. 

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

Доброго утра/дня/вечера/ночи.

Сегодня, во время тренировки от ИТМО, результатов некоторых сабмитов приходилось ждать около 20-ти минут. Конечно, эти 20 минут я уделял другим задачам, но потом приходил WA и я переключался обратно, правил, сабмитил и опять возвращался к задаче, над которой работал. Получилось любопытно.

Вот и пришла мне в голову идея для какого-нибудь первоапрельского контеста.

Правила ACM, только результаты приходят не сразу, а через n минут после сабмита(ну или по окончанию контеста).

Как вам идея?

С уважением, Иван.

A. Bender Problem
Solution by Polichka
Let's look at the first nail. If it is occupied by the fold place, then Bender will put next fold place on the third nail, then on fifth and so on. Else, is the first nail occupied by end, than second, fourth, sixth and so on nail will be occupied by the fold places.
Let's see, if we can complete our polyline with the first nail, occupied by rhe fold place. It means we should check, if we have an unused pod with length dist(nails[n], nails[1]) + dist(nails[1], nails[2]). Then check the third nail and so on.
If we have completed the polyline, then we have an answer. Else repeat previous procedure, but starting from the second nail.

B. pSort
Solution by Polichka
Let's consider a graph. Vertexes will correspond to place of the permutation. Places will be connected by an edge if and only if we can swap theirs values. Our problem has a solution when for every i, vertex p[i] can be reached from vertex i.

C. Bath Queue
Solution by Fefer
This problem is solved by dynamic programming
Consider the following dynamics: d[i][j][k].
i --- number of not yet processed students,
j --- number of not yet processed rooms,
k --- maximum queue in the previous rooms.
The value we need is in state d[n][m][0]. Let's conside some state (i, j, k) and search through all c from 0 to i. If c students will go to jth room, than a probability of such event consists of factors: C^c_i --- which students will go to jth room.
(1 / j)^c· ((j - 1) / j)^i - c --- probability, that c students will go to jth room,and the rest of them will go to the rooms from first to j - 1th.
Sum for all ñ from 0 to i values of
(1 / j)^c· ((j - 1) / j)^i - c· C^c_i· d[i - c][j - 1][mx]. Do not forget to update maximum queue value and get the accepted.

D. Do not fear, DravDe is kind
Solution by RAD
Let's split all trucks into different classes by the sum of l_i + c_i + r_i. Answer sequence consists of trucks from only one class, so let's solve problem for different classes independently.
Let's loop through trucks from fixed class in the order, then follow in the motorcade and update values in dynamics z[k] - maximum profit we can get, if last truck has r_i = k.
Truck with number i can update two values:
it can update value z[r_i] with value z[r_i + c_i] + v_i. It means this truck continued some motorcade, started from some previous truck.
if l_i = 0 it can update value z[r_i] with v_i. It means this truck started motorcade. Answer will be in z[0]
To restore the trucks included in the answer, we can keep with the maximal sum in z the index of last truck that updated this sum. Also we store the ancestor p for each truck that updated something in z. This ancestor is calculated when we consider i-th truck and doesn't change further: p[i] = -1 if truck i became beginning of the motorcade, otherwise p[i] = last truck that updated z[r_i + c_i]. We start restore of the answer from last truck updated z[0]. After that we restore everything using only p.

E. DravDe saves the world
Solution by Gerald
Problem by RAD
Let's look at geometrical locus where DravDe can land. It can be eigher an angle or a line(half-line).
1. Locus is an angle if and only if projection of vector v and vector u on Oxy plane is not collinear. This angle is easy to calculate. Angular vertex is DravDe starting point and one of half-lines is collinear with place speed vector projection. Second half-line is easy to calculate:
A_z + V_z· tv + U_z· tu = 0
A_x + V_x· tv + U_x· tu = B_x
A_y + V_y· tv + U_y· tu = B_y
where A - starting point, B - landing point. Consider tv equal to 1 and calculate tu from first equation. From second and third calculate point B. This point lies on the second half-line of the angle.
2. If plane speed projection and wind speed projection is collinear, locus is half-line or line, depending on the difference between this two speeds.
If the answer exist, than polygon and locus have at least onecommon point. And t1 and t2 is minimal on edge points. So now let's cross all segments with locus, calculate t1 and t2 for each intersection point and select minimal answer.

Thank you for your participation. Good luck with upsolving and incoming contests. Luck - is very useful and it is good to have it.
With best regards, Ivan.

Сегодня поставил себе Visual Studio 2010.

Такой добрый инсталлятор обратил внимание на язык моей ОС и поставил русский вариант интерфейса. Посмотрел я на него, зашел в опции, открываю "Выбор языка" и вижу список из 2-х элементов: "русский" и "язык ОС". Ну ладно, русский так русский.

Начал настраивать интерфейс. Запустил дебаг. Все лишнее не-олимпиадное закрыл. "Надо открыть Watch", - подумал я. Перерыл все менюшки. Нету. Открыл параметры - добавить кнопку ну или что-то в этом роде. Внимательно просмотрел списки. Никаких слов типа "просмотр значений" или синонимов я не нашел. В конце концов на правильный ответ меня натолкнул символ в виде очков и как же я удивился, когда нашел всем нам привычный Watch под названием...

Попробуйте отгадать как назвали это диалоговое окно в русском переводе Visual Studio 2010?

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

C. Очереди к умывальникам
Задача решалась с помощью динамического программирования.
Рассмотрим такую динамику: d[i][j][k].
i --- количестов еще не обработанных человек,
j --- количестов еще не обработанных комнат,
k --- максимальная очередь в предведущих комнатах.
Наш ответ находиться в состоянии d[n][m][0]. Так же, когда j равно 1, ответ равен максимуму из очереди в последней комнате и наибольшей очереди из предведущих.
Теперь рассмотрим какое-то промежуточное состояние.
 Переберем количество человек, которое пойдет в j-ю комнату. Пусть из i человек пойдет c. Тогда вероятность такого перехода состоит из 2-х сомножителей:
C^c_i --- какие именно студенты пойдут в j-ю комнату.
 (1 / j)^c· ((j - 1) / j)^i - c --- вероятность того, что c студентов пойдут в j-ю комнату, а остальные в комнаты с 1-й по (j - 1)-ю.
Сумма по всем с от 0 до i значений вида
 (1 / j)^c· ((j - 1) / j)^i - c· C^c_i· d[i - c][j - 1][mx] и даст ответ. Не забудте пересчитать максимум и тогда задача пройдет.

Спасибо за участие. Удачи на дорешивании и на предстоящих соревнованиях. Ведь без неё никуда.
 С уважением, Иван.

A. Следующий тест
Эта простая задача решается следующим образом. Заведем массив boolean used[1..3001] и заинициализируем его значениями false. Для каждого из n данных нам чисел, соответствующий элемент массива used присвоем true. Далее пройдем по массиву, начиная с 1 и найдем первое число, для которого значение used - false. Это и есть ответ.

B. Турнир
 Для решения данной задачи сначала найдем такие числа A и B, которые встретились во входных данных не n - 1, а n - 2 раз. Если переформулировать условие, то можно заметить, что отношение победившего и проигравшего транзитивно - то есть если X, выиграл Y, а Y выиграл Z, то X выиграл Z. Значит, чтобы определить кто круче - A или B, попытаемся найти такое C, у которого результат игры с A и результат игры с B различный. Если мы нашли такое С, то того игрока, который выиграл, надо вывести первым. Если такого С не существует, то любой исход матча А против B удовлетворяет условиям задачи.

C. Неотсортированная подпоследовательность
Сначала заметим, что ответ всегда либо 0, либо состоит из 3-х элементов. Однако за кубическое время искать ответ слишком долго. Вот решение за линейное время.
Будем идти по последовательности и во время каждой итерации поддерживать минимум на префиксе. Когда мы рассматриваем текущий элемент, достаточно проверить не образовавает ли этот элемент хорошую подпоследовательность с текущими максимумом и минимумом. Это не сразу очевидно, но легко доказывается. Подумайте сами над этим как домашнее задание.

D. Кольцевая 2
Рассмотрим все дороги как отрезки на числовой прямой. Дороге из города a в город b будет соответствовать отрезок [min(a, b), max(a, b)]. Для каждой пары отрезков есть 3 варианта расположения: оба конца одного отрезка внутри второго, оба конца одного отрезка вне второго и только один из концов одного внутри второго. В первых двух случаях положение дорог, соответствующих отрезкам не зависимы друг от друга. В третьем же случае дороги должны проходить по разные стороны от кольца.
Построим такой граф: вершины будут соответствовать дорогам, а ребро между вершинами i и j будет означать, что эти дороги должны лежать по разные стороны. Мы свели задачу к следующей: есть неориентированный граф. Необходимо раскрасить все его вершины в 2 цвета так, чтобы никакие 2 вершины одинакового цвета не соединялись ребром. Это делаеться при помощи, например, dfs'са. Изначально цвет каждой вершины - -1. Циклом for пойдем по вершинам. Если цикн натыкается на -1-вершину, то присваивает ей цвет 0 и запускает из неё dfs. dfs просматривает все соседи, переданной ему вершины. Если видит -1-вершину, то красит её в цвет, противоположный цвету текущей вершины и запускается из неё, иначе он сравнивает цвета текущей вершины и рассматриваемого соседа. Если они совпали, то выводим Impossible. После такого dfs'а получим ответ.

E. Число с заданным количеством делителей
Рассмотрим число, являющееся ответом и разложим его на простые множители. Получим такое произведение p₁^a₁· p₂^a₂· ... · p_k^a_k. Произведение по i всех a_i + 1 и будет числом делителей. То есть если мы возьмем десять простых и перемножим, то уже получим число с 1024-мя делитемяли. Отсюда следует, что нам понадодиться максимум первые десять простых чисел для того, чтобы построить нужное число.
  Рассмотрим следующую динамику: d[i][j] = наименьшее число с i делителями и составленное из первых j простых чисел. Для вычисления состояния (i, j) переберем степень с которой j-е простое число войдет в ответ. Если j-е простое число входит со степенью k, то d[i][j] = d[i / (k + 1)][j - 1] * prime[j]^k. По всем возможным переходам надо выбрать минимум.
Во время реализации надо быть предельно осторожным, так как все вычисления происходят на грани переполнения.

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

Добрый день, Codeforces.

В этом году я как-то затянул с курсовой. Сделал это зря, потому что сейчас уже все экзамены позади, хочеться отдыхать и все такое. Но победив лень я реализовал все необходимые алгоритмы на Java. Осталось мне только сделать GUI для удобной работы с программой, собрать материал и написать собственно работу. 

Я использую eclipse в качестве среды. Подскажите пожалуйста какой плагин использовать для удобного и быстрого создания интерфейса.

Я уже искал в интернете и наткнулся на множество подобных плагинов. Как выбрать не знаю. 

UPD: скачал и установил плагин 

http://www.instantiations.com/windowbuilder/swingdesigner

Пробная версия на 14 дней. Пока все устраивает.

UPD: Решил переименовать тему, так как у меня появились еще вопросы. )))

2. Как изменить толщину линии в Graphics. 

Ответ нашел сам:

public void paint(Graphics gr){
Graphics2D g = (Graphics2D)gr;
//создаем "кисть" для рисования
BasicStroke pen1 = new BasicStroke(20); //толщина линии 20
g.setStroke(pen1);
g.drawLine(...);

}

3. Как создать regex, который распозновал бы точку?

В частности для того, чтобы сделать по ней split.

Обычно в regex точка - любой символ. По

Пробовал уже и \u002E, и \056. Все время возвращает пустой массив строк.

UPD:

4. У меня созрел еще один вопрос. Даже не знаю как забить его в гугл. Есть изображение в JPEG. Как из JPEG файла создать объект класса BufferedImage я знаю. Теперь мне надо нарисовать этот BufferedImage на JFrame-мя.

Если написать просто

window.getGraphics().drawImage(im, 0, 0, null);,

то изображение нарисуеться, но при первой же перерисовке окна, исчезнет.

UPD:

5. Как изменить размер картинки в BufferedImage?

Целиком задача такая. Есть BufferedImage. Необходимо не меняя маштаба дорисовать сбоку полоску с некой информацией.

Я тоже решил последовать за модной тенднцией. Вот задача:

Вас поймали бандиты и решили поиздеваться.

Они сказали: "Скажи нам любую фразу. Если она будет правдой - мы зарежем тебя. Если ложью - застрелим."

Что нужно сказать, чтобы выжить?

Сегодня пролистывал рейтинг CF и увидел следующее:

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

Доброе утро/день/вечер.

Только что во время дебага заметил, что написал

bool check(int x, int y){

    return 0 <= x && x < n && 0 <= y < m;

}

Программа компилировался, но работала, естественно, не правильно.

Другой подобный баг встречается чаще.

int getAns(...){

    int ans = 0;

    {

        ///Вычисление ответа

    }

     //здесь должен быть return ans; но он забыт.

}

Это тоже компилируется.

Другой более интересный пример, о котором я только слышал от Дмитрия Матова (Nerevar) :

int f = f(x1, y1, z1) + f(x2, y2, z2) + (x3, y3, z3);

Нет, я не забыл f перед третьей скобкой. Это тоже компилиться и работает.

Буквально сегодня из-за другой подобной ошибки мой напарник получал разные ответы при компиляции в g++ и  в Visual Studio.

А какие вы знаете подобные вещи в С++?

Вот что будет, если два раза нажеть на кнопку "Ответить" под чьи-то комментарием

Я думаю, каждый из нас, кто писал или пишет на С++, знаком со строкой 

freopen("input.txt", "rt", stdin);

А вопрос у меня следующий.

Почему "rt"? 

Сайт cppreference.com не дал мне ответа на этот вопрос. Более того, там даже нет "rt" как возможного значения параметра mode функции freopen. 

Сегодня у нас в Центре состоялась первая тренировка за полтора месяца. Была она по задачам с TopCoder'а, то есть полностью на английском языке.