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

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

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

Сегодня я, сдавая задачу 89D - Космические мины на С++, задумался о том, что у в моем коде много коротких функций, которые вызываются по много раз, и о том, что это может повлиять на производительность. Я всегда пишу относительно короткие функции с inline. inline-функция (или встроенная функция) на этапе компиляции заменяется в коде не на вызов функции, а прямо на тело, т.е. как макрос, только на уровень ниже. 
Но если написать inline int f(){ //some code}, это не гарантирует, что компилятор сделает функцию f() встроенной, это только как бы намекает компилятору, что стоило бы сделать эту функцию таковой, а он уже сам решает стоит это делать или нет. 
Поэтому я решил проконтролировать компилятор и посмотреть, действительно ли все функции типа inline double dist(const point& a, const point& b) { return sqrtl(sqr(a.X - b.X) + sqr(a.Y - b.Y)); } стали встроенными. В результате небольшого гугления я получил следующие решения:
  • На g++ есть опция -Winline, которая генерирует warning, если функция, перед которой написано ключевое слово inline, не была сделана встроенной
  • На Visual C++ есть аналогичный warning 4-го уровня. Также можно писать перед функциями __forceinline. Если компилятор не сделает встроенной функцию с __forceinline, то он сгенерирует warning 1-го уровня.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

Автор Fefer_Ivan, 13 лет назад, По-русски
Добрый день, Codeforces.

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

И тут я вспомнил TopCoder, в котором баллы за задачу начисляются сразу, а уже если задача не прошла систесты, снимаются. Таким образом баллы участника невозрастают со временем и когда все мои задачи на TopCoder'е протестируются я буду наблюдать, как моё положение в таблице будет только расти, так как у кого-нибудь сверху будет что-нибудь падать. Наблюдать это гораздо приятнее, согласитесь ))

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


Полный текст и комментарии »

  • Проголосовать: нравится
  • +90
  • Проголосовать: не нравится

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

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


Сегодня я обнаружил, что папка, в которой я храню весь олимпиадный код занимает 2,5 Гб. Причем 97% этого места занимают какие-то непонятные файлы, которые оставляет после себя Visual Studio. 
Следующий скрипт на Python уменьшил размер упомянутой выше папки до 55 Мб:

import re, os
dir = "D:\\Projects\\Olymp\\"

pattern = "(.+\.txt)|(.+\.cpp)|(.+\.java)|(.+\.py)|(.+\.h)"
goodFile = re.compile(pattern)

for root, dirs, files in os.walk(dir):
    for name in files:
        fullname = os.path.join(root, name)
        if goodFile.match(name):
            print "Kept " + fullname
        else:
            os.remove(fullname)
            print "Deleted " + fullname

Кто-нибудь знает, может быть можно как-нибудь настроить вижак, чтобы такие скрипты стали ненужными?
С уважением, Иван.

P.S. Надо добавить в скрипт список исключений, а то я вместе с мусором удалил свой проект-болванку для задачи.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор Fefer_Ivan, 14 лет назад, По-русски
Доброе утро/день/вечер/ночь, Codeforces!

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

Пусть нам нужен массив 2 на 2.

Пишем:
a = [[0]*2]*2
print "Before:"
print a
a[0][0] = 1
print "After:"
print a

Получаем:
Before:
[[0, 0], [0, 0]]
After:
[[1, 0], [1, 0]]

Вопрос: почему изменился второй список?

Если написать немного по-другому:
a = [[0]*2]
a.append([0]*2)
print "Before:"
print a
a[0][0] = 1
print "After:"
print a

Получаем:
Before:
[[0, 0], [0, 0]]
After:
[[1, 0], [0, 0]]

Вопрос: в чем разница?

Windows 7, 32-bit, Python 2.7.1
Строка запуска: python solution.py < input.txt

Полный текст и комментарии »

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

Автор Fefer_Ivan, 14 лет назад, По-русски
Доброе утро/день/вечер/ночь.

В последнее время на Codeforces появилось очень много постов вида "помогите" или с другими односложными названиями. Во время написания этого поста, я заглянул в прямой эфир и нашел там посты "TopCoder", "Взлом". Или обратная сторона медали - пост "Тот, кто немного шарит в комбинаторике, помогите!" и "Задача (помогите, если не трудно)". 
Поймите, что главная цель заголовка - информативность, чтобы, прочитав его, пользователь понял, о чем сейчас будет (или не будет) читать в посте. 
Например, по-моему, пост TopCoder лучше назвать "Как участвовать в TopCoder?".
"Взлом" - "Что такое взлом?". Вообще, такие темы лучше просто не создавать, но сейчас разговор не об этом.
Если в посте вы пишите про задачу и просите помочь, то назовите пост названием задачи и ссылкой на Online Judge. Иначе, можно просто упомянуть тип задачи: "Задача по комбинаторике" или "Задача на структуры данных". 
Фразы, типа "Помогите пожалуйста. Спасибо." - это хорошо, но не информативно, так что если вы просите помощи, спасибо напишите лучше в конце поста. 
Спасибо за внимание (да, например, так)
Информативных и лаконичных заголовков вам.
С уважением, Иван.


Полный текст и комментарии »

  • Проголосовать: нравится
  • +50
  • Проголосовать: не нравится

Автор Fefer_Ivan, 14 лет назад, По-русски
Доброго утра/дня/вечера/ночи.
В этом сообщении я хочу рассказать почему я занимаюсь олимпиадным программированием и задать соответствующий вопрос вам.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

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

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

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

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

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

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

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

Как вам идея?

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

Автор Fefer_Ivan, 14 лет назад, перевод, По-русски

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: Cci --- 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· Cci· 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 li + ci + ri. 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 ri = k.
Truck with number i can update two values:
it can update value z[ri] with value z[ri + ci] + vi. It means this truck continued some motorcade, started from some previous truck.
if li = 0 it can update value z[ri] with vi. 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[ri + ci]. 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:
Az + Vz· tv + Uz· tu = 0
Ax + Vx· tv + Ux· tu = Bx
Ay + Vy· tv + Uy· tu = By
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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

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

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

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

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

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


Полный текст и комментарии »

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

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

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


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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

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

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. Число с заданным количеством делителей
Рассмотрим число, являющееся ответом и разложим его на простые множители. Получим такое произведение p1a1· p2a2· ... · pkak. Произведение по i всех ai + 1 и будет числом делителей. То есть если мы возьмем десять простых и перемножим, то уже получим число с 1024-мя делитемяли. Отсюда следует, что нам понадодиться максимум первые десять простых чисел для того, чтобы построить нужное число.
  Рассмотрим следующую динамику: d[i][j] = наименьшее число с i делителями и составленное из первых j простых чисел. Для вычисления состояния (i, j) переберем степень с которой j-е простое число войдет в ответ. Если j-е простое число входит со степенью k, то d[i][j] = d[i / (k + 1)][j - 1] * prime[j]k. По всем возможным переходам надо выбрать минимум.
Во время реализации надо быть предельно осторожным, так как все вычисления происходят на грани переполнения.

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

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

Добрый день, 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. Необходимо не меняя маштаба дорисовать сбоку полоску с некой информацией.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

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

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

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

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.

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

Полный текст и комментарии »

Теги c++
  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор Fefer_Ivan, 15 лет назад, По-русски
Несмотря на все полезные навыки, которые дает нам университет и олимпиадное программирование, некоторые вещи, необходимые в промышленном программировании, для меня покрыты туманом. Так что я решил заняться собой.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

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

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

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

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

Почему "rt"? 

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

Полный текст и комментарии »

Теги c++
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится