Kvark161's blog

By Kvark161, history, 4 years ago, In Russian,

Заметил странное поведение, если со стороннего ресурса (например, vk) перейти по ссылке в контест группы с правами менеджера, то перенаправит на codeforces.com, а если отключить менеджера в контесте, то все окей.

Ссылка вида: codeforces.com/group/{groupId}/contest/{contedId}

Тоже самое происходит с ссылками на посылки в контестах группы: codeforces.com/group/{groupId}/contest/{contedId}/submission/{submissionId}

Всем хорошего настроения! =)

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By Kvark161, history, 4 years ago, In Russian,

Задача: дан ориентированный граф. У каждой вершины есть некая величина H, нужно для каждой вершины посчитать H', равное минимуму из всех значений H вершин, до которых можно добраться из текущей. Количество вершин и ребер до 105.

Например, граф

1->2
2->3
2->5
3->4
5->6

H1 = 3, H2 = 30, H3 = 5, H4 = 1, H5 = 20, H6 = 10

Ответ:

H1' = 1, H2' = 1, H3' = 1, H4' = 1, H5' = 10, H6' = 10

И есть такое презабавное решение

G[N]; // список смежных вершин
H[N]; // те самые H
used[N] = {false}

dfs(v)
    used[v] = true
    suffle(G[v])
    for to in G[v]
        if used[to] = false
            dfs(to)
        H[v] = min(H[v], H[to])

main()
    for step = 0..25
        used = {false}
        P[N] = {0,1,2...,N-1}
        shuffle(P)
        for v in P
            dfs(v)

Завалить решение без shuffle довольно просто, а как быть с shuffle? Кто-нибудь умеет делать тесты для подобных решений? Или кто-нибудь может посчитать вероятность того, что решение выдаст правильный ответ? =)

Read more »

 
 
 
 
  • Vote: I like it
  • +32
  • Vote: I do not like it

By Kvark161, 4 years ago, translation, In English,

There is a list of the youngest chess grandmasters. What about codeforces? Let's make a list of the youngest codeforces grandmasters! =)

Read more »

 
 
 
 
  • Vote: I like it
  • +76
  • Vote: I do not like it

By Kvark161, 4 years ago, In Russian,

lunawyll наткнулась на прикольное поведение c++11. Попробуйте угадать, что будет выведено, если использовать c++11?

#include <set>
#include <iostream>

using namespace std;

struct S {
    int a;
    int b;
    
    S(int a = 0, int b = 0): a(a), b(b) {};

    friend bool operator < (const S& first, const S& second) {
        return first.a < second.a;
    }
};

int main() {
    set<S> s;
    s.insert({2, 1});
    cout << s.size();
}

Неожиданный результат, но в сет будет добавлено 2 элемента (a=2, b=0) и (a=1, b=0).

Почему это так? Дело в том, что в c++11 был добавлен еще один метод void insert (initializer_list<value_type> il);. Получается, что {2, 1} преобразуется в initializer_list<S> с двумя элементами (a=2, b=0) и (a=1, b=0) с помощью неявного преобразования int в S, используя конструктор, который мы описали.

GNU g++ 4.9.2 (не c++11): в сете будет один элемент (a=2, b=1).

MS VC++ 2010: ошибка компиляции.

Всем добра! :)

P.S. Каким-то образом я умудрился удалить пост, написал его заного...

UPD: О том, как я удалил пост. В английской версии сайта при редактировании поста есть кнопочка "discard" — это разве не переводится как "отмена"? Оказалось — "удалить".

Read more »

 
 
 
 
  • Vote: I like it
  • +65
  • Vote: I do not like it

By Kvark161, 5 years ago, In Russian,

Можно ли как-то запретить другим пользователям отправлять мне личные сообщения? Или можно добавить кого-то в черный список? А то некоторые пользователи слишком назойливые.

Добавьте, пожалуйста, такую возможность, команда Codeforces.

Read more »

 
 
 
 
  • Vote: I like it
  • +30
  • Vote: I do not like it

By Kvark161, 6 years ago, In Russian,

Раз организаторы соревнования до сих пор не сделали анонса на codeforces, то решил написать я, как студент ЮФУ.

Началась регистрация на VIII Открытую олимпиаду ЮФУ по программированию.

Соревнование как личное, так и командное.

Разрешенные языки программирования:

C/C++;

Pascal;

C#, VisualBasic .NET;

Java.

Регистрация участников открыта до 13.03.2014 включительно.

Отборочный тур 14-17 марта 2014 в онлайн режиме. 25 лучших участников и команд проходят в финал.

Основной тур 19-20 апреля 2014 в Таганрогском кампусе ЮФУ.

Участие в олимпиаде бесплатное для всех категорий участников!

Подробнее здесь.

Read more »

 
 
 
 
  • Vote: I like it
  • +20
  • Vote: I do not like it

By Kvark161, 6 years ago, In Russian,

Извините, если уже данная тема поднималась, я нигде не нашел.

Есть ли на codeforces подобные таблички или что-то похожее, связанное с рейтингом?

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By Kvark161, 6 years ago, In Russian,

Задача: В очень большом целочисленном массиве (n > 10^9, |ai| <= 10^18) найти число, которое не повторяется (гарантируется, что оно есть и такое единственное).

Пример ввода:

7 11 26 7 11

вывод:

26

Если повторов каждого числа четное количество (кроме одного, которое нужно найти), то можно применить XOR последовательно ко всем элементам. А как можно быстро найти искомый элемент, если числа могут повторяться нечетное количество раз.

Пример ввода:

1 17 5 17 1 17

вывод:

5

UPD: Числа можно считывать повторно, они хранятся в файле, с которым можно делать все, что хочется. Ограничений на время и память нет.

Read more »

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it