CountZero's blog

By CountZero, history, 5 months ago, translation, In English,

borrowed from https://gist.github.com/jdarpinian/1952a58b823222627cc1a8b83a7aa4e2

This trick is for linux/mac/wsl. Just add one comment to the top of your source file

C++

run chmod +x test.cpp and that's it, you can use it as an executable:

$ ./test.cpp
hello world

you can do this with java too:

Java

Enjoy!

Read more »

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

By CountZero, 4 years ago, In Russian,

Update (29.05.15)

This script doesn't work anymore because of recent security upgrade from codeforces team. If you have any suggestions about Codeforces API, please read this marat.snowbear's blog post: /blog/entry/18185

==================================================================================================

Hi. Recently I decided to write such script, and it turned out to be very simple task.

Here it is

Setup

First of all, install requests library into your python 3.x (I didn't tested it under 2.x) distribution. Just like that: pip install requests.

Second, edit x_user and csrf_token variables. Look for X-User in your browser cookies, and for X-Csrf-Token in this page source. Update them every time you login.

Third, your submission language will be determined by file extension. By default, .java is bound to codeforces Java 8, .cpp to GNU C++ 0x 4, and .py to Python 3.3. If you want to change this behavior, edit ext_id variable.

If you prefer codeforces.ru over codeforces.com, set cf_domain variable to ru.

Usage

python cfsubmit.py C:\contests\123a.cpp
python cfsubmit.py 123B.py

Solution filename have to be in exactly this format. Case doesn't matter.

Good luck!

Read more »

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

By CountZero, 4 years ago, In Russian,

Всем привет! Решал на днях задачу 400E - Inna and Binary Logic, и ее получилось свести к следующему:

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

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

Заведем дерево отрезков и будем поддерживать в каждой его вершине следующую информацию:

  • (ans) количество единичных подотрезков (это, собственно, и будет ответом на запрос)
  • (len) длина отрезка
  • (pre) длина максимального единичного префикса
  • (suf) длина максимального единичного суффикса

При объединении двух отрезков left и right все это очень легко пересчитывается: к ответу добавляются все подотрезки, у которых левый конец находится в суффиксе left, а правый — в префиксе right.

newAns = left.ans + right.ans + left.suf · right.pre,

и так далее.

Я хотел использовать дерево отрезков, которое всегда состоит ровно из N вершин и реализует все операции без рекурсии. Оно подробно описано в этом посте Urbanowicz, также код на Java есть на сайте indy256.

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

Попробуем это исправить. Нарисуем дерево отрезков:

          1

    2           3

 4     5      6    7

8 9  10 11  12 13

Значения, соответствующие отрезкам длины 1, хранятся в листьях — в вершинах 7 - 13. Чтобы получить значение в вершине 1, нам придется правильно скомбинировать вершины 2 (8 9 10 11) и 3 (12 13 7 или 7 12 13) — очевидно, при такой конфигурации этого никак не добиться.

Теперь провернем трюк: циклически сдвинем массив так, чтобы его первый элемент находился в позиции с номером 2k - N, где N — длина массива. Тогда получится дерево, эквивалентное следующему:

          1

    2           3

 4     5      6    13

7 8   9 10  11 12

В нем листья идут в нужном порядке, и все будет работать как надо. Пишущие на C++ могут воспользоваться встроенной функцией std::rotate, чтобы сдвинуть массив. Разумеется, надо правильно поддерживать циклический сдвиг и для последуюших запросов к дереву:

modify_new(pos) = modify((pos+shift) % n);
query_new(l, r) = combine(query(l+shift, n-1), query(0, r+shift-n)); //l+shift < n && r+shift >= n

Отлично, проблема решена. Теперь рассмотрим функцию запроса значения на отрезке:

Value query(int l, int r) {
	Value res = NEUTRAL_VALUE;
	for (l += N, r += N; l <= r; l = (l + 1) / 2, r = (r - 1) / 2) {
		if (l % 2 != 0) res = combine(res, tree[l]);
		if (r % 2 == 0) res = combine(res, tree[r]);
	}
	return res;
}

Этот код также не годится для некоммутативных операций. Если нарисовать дерево и отмечать запрашиваемые вершины, то мы получим два отрезка: один растет все время влево, другой — вправо, и на последней итерации эти отрезки сливаются. Остается только модифицировать функцию очевидным образом:

Value query(int l, int r) {
	Value resl = NEUTRAL_VALUE, resr = NEUTRAL_VALUE;
	for (l += N, r += N; l <= r; l = (l + 1) / 2, r = (r - 1) / 2) {
		if (l % 2 != 0) resl = combine(resl, tree[l]);
		if (r % 2 == 0) resr = combine(tree[r], resr);
	}
	return combine(resl, resr);
}

Вот, собственно, и всё. Моя посылка: 6006570.

Всем удачи на контестах!

Read more »

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

By CountZero, 5 years ago, In Russian,

Всем привет. В этом посте я хотел бы рассказать о паре, похоже, мало кому известных, но важных моментов, касающихся написания контестов на языке Go.

Среда

Установка среды

Существуют официальные сборки Go для Linux, OS X и Windows. Их можно скачать с офсайта или установить через пакетный менеджер. Например, в случае Windows можно воспользоваться Chocolatey.

Также на офсайте есть масса отличных руководств и онлайн-IDE.

Редактор и отладчик

Среди пишущих на Go наибольшей популярностью пользуется Sublime Text 2 или 3 с плагином GoSublime — вы получите очень удобный редактор с автоформатированием, подсветкой синтаксиса и ошибок, продвинутым автодополнением, сниппетами, и некоторыми возможностями рефакторинга.

Отладка. Если неохота пользоваться GDB из консоли (см. статью), то можно установить LiteIDE.

Язык

Обобщенные вычисления

Формально в Go есть универсальный тип interface{}, в/из которого можно преобразовать что угодно. Однако это преобразование выполняется настолько медленно, что любой ваш код с его использованием неизбежно получит TL. Поэтому в стандартной библиотеке Go из пригодных для использования контейнеров есть только хэш-таблицы, реализованные на уровне языка без использования interface{}.

Массивы против слайсов

Никогда не используйте массивы в Go — по сравнению со слайсами у них нет никаких преимуществ кроме недостатков.

Во-первых, слайсы можно наращивать, точно так же как std::vector в С++:

slice := make([]int, 3) // slice == [0, 0, 0]
slice = append(slice, 1) // slice == [0, 0, 0, 1]

Во-вторых, слайсы можно передавать в функции с переменным числом аргументов, например в упомянутую выше функцию append:

slice1 := []int{1, 2, 3}
slice2 := []int{4, 5}
slice1 = append(slice1, slice2...) //slice1 == [1, 2, 3, 4, 5]

Вложенные функции

Функции в Go ничем не отличаются от типов — их можно объявлять внутри других функций, присваивать, передавать в качестве параметров (см. ниже пример с двоичным поиском). Есть единственная тонкость: объявление рекурсивных вложенных функций, которое выполняется следующим образом

func main() {
    var fib func(i int) int
    fib = func(i int) int {
        switch i {
        case 0: return 0
        case 1: return 1
        default: return fib(i-1) + fib(i-2)
        }
    }
} 

Стандартная библиотека

Ввод-вывод

В тех единицах сабмитов на Go, которые я видел на CF, для ввода-вывода используется пакет fmt. Это фатальная ошибка: там не используется буферизация, зато используется тип interface{}, о котором я написал выше. Поэтому, навсегда забудьте про fmt и пользуйтесь пакетом bufio:

var scanner *bufio.Scanner = bufio.NewScanner(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func ReadInt32() int {
    scanner.Scan()
    ans, _ := strconv.Atoi(scanner.Text())
    return ans
}

func PrintInts(ints ...int) {
    for _, value := range ints {
        writer.WriteString(strconv.Itoa(value))
        writer.WriteByte(' ')
    }
}

func main() {
    defer writer.Flush() // очищает буфер при выходе из функции main
    scanner.Split(bufio.ScanWords) // заставляет scanner считать отдельными токенами слова, разделенные пробелами
                                   // также имеются функции bufio.ScanLines и bufio.ScanBytes
    var n, m int = ReadInt32(), ReadInt32()
    PrintInts(n, m)
    writer.WriteByte('\n')
    slice := []int{1, 2, 3, 4, 5}
    PrintInts(slice...)
}

Файловый ввод-вывод:

func main() {
    fi, _ := os.Open("input.txt") // открывает файл для чтения
    fo, _ := os.Create("output.txt") // открывает файл для записи
    scanner := bufio.NewScanner(fi)
    writer := bufio.NewWriter(fo)
    defer fi.Close() // закрывает файл при выходе из функции main
    defer fo.Close()
    defer writer.Flush()
    scanner.Scan() // считывает следующий токен
    writer.WriteString(scanner.Text()) // пишет текущий токен в вывод
}

Обратите внимание: отложенные (помеченные ключевым словом defer) функции выполняются в порядке "снизу вверх" (LIFO). Это значит, что в случае их написания в таком порядке

defer writer.Flush()
defer fi.Close()
defer fo.Close()

файл будет закрыт ДО очищения буфера, и в него ничего не запишется. Кроме того, отложенные функции не будут вызваны, если работа программы будет завершена вызовом функции os.Exit(0).

Также стоит отметить, что у структуры (в Go нет такого понятия как класс) Scanner есть ограничение на максимальный размер токена 65535 символов. Если вы хотите использовать ее для чтения более длинных строк, то единственный выход — это скопировать ее исходный код в шаблон решения, увеличив значение константы MaxScanTokenSize.

Сортировка и двоичный поиск

Соответствующие функции содержатся в пакете sort. В пакете есть функции, позволяющие сортировать по возрастанию слайсы из типов int, float64 и string. Если вам понадобится отсортировать что-то другое, то придется обернуть это что-то в структуру, реализующую методы Len, Less и Swap, и вызвать функцию sort.Sort:

type Int64Slice []int64
func (slice Int64Slice) Len() int           { return len(slice) }
func (slice Int64Slice) Less(i, j int) bool { return slice[i] < slice[j] }
func (slice Int64Slice) Swap(i, j int)      { slice[i], slice[j] = slice[j], slice[i] }

func main() {
    slice := []int64{5, 3, 4, 2, 1}
    sort.Sort(Int64Slice(slice))
    // slice == [1, 2, 3, 4, 5]
}

Для двоичного поиска используется функция Search(n int, f func(j int) bool) int, возвращающая наименьшее j из диапазона [0..n] такое, что f(j) == true. Пример можете посмотреть в одном из моих сабмитов

Прочие пакеты

Полное описание пакетов стандартной библиотеки приведено на офсайте

Пакеты, которые вам, скорее всего, понадобятся:

  • os — доступ к файлам и потокам, в т.ч. stdin/stderr/stdout; функция os.Exit(0)
  • bufio — буферизованный ввод-вывод;
  • sort — сортировка и двоичный поиск;
  • math — математические функции, длинная арифметика, ГСЧ, комплексные числа;
  • strings, strconv — работа со строками;
  • time — работа с датой и временем;
  • index/suffixarray — поиск всех вхождений строки в текст за время ;
  • container/heap — двоичная куча. Работает очень медленно из-за использования interface{}, однако с недавних пор ничего не мешает скопипастить код оттуда и заменить interface{} на int или что-то еще

Read more »

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