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

11-th International Zhautykov Olympiad, Computer Science section
Автор mexmans, 9 лет назад, По-английски

General information

Official website of the olympiad: http://izho.kz

This year computer science section of the olympiad will be hosted by Kazakh-British Technical University.

In addition to the official onsite contest, an unofficial online contest will also be available to everyone. To participate in the online contest you need to register here. Logins and passwords will be distributed closer to the contest dates.

Contest rules are generally the same as on IOI, though we do not follow the syllabus exactly.

Allowed programming languages: C/C++, Pascal and Java.

Task statements will be available in English and Russian.

You can find some information about past olympiads here: 2014, 2013, 2012, 2011, 2010, 2009.

Online contest schedule

Schedule for the online contest (all times are in Almaty timezone, GMT+6):

Registration until January 10, 11:59pm Practice session January 12, 00:00am — 11:59pm
Contest day 1, session 1 January 13, 3:00pm — 8:00pm
Contest day 1, session 2 January 14, 3:00am — 8:00am
Contest day 2, session 1 January 14, 3:00pm — 8:00pm
Contest day 2, session 2 January 15, 3:00am — 8:00am

Note, that contestants should participate in only one session for each contest day.

We do not expect any changes in the schedule, but, please, check this page closer to the contest dates to see that times are still the same.

All additional information will be published on this page. Contest environment

Information about the server software:
1. Contest system: CMS;
2. Operating system: Ubuntu 14.10 x64
3. Available compilers: FreePascal 2.6.4, GNU C/C++ 4.9.1, Oracle JDK 1.8.0_25
Onsite contest server (physical server): 2 x Intel Xeon X5570 @ 2.93GHz.

Online contest server (virtual server on Amazon EC2, c3.large): 2 vCPUs, each is HT from Intel Xeon E5-2680 v2 (Ivy Bridge).

Computers configuration for onsite participants (note, versions of compilers are a bit different from the compilers on the server):
1. Operating system: Microsoft Windows;
2. Available compilers: FreePascal 2.6.4, MinGW GNU C/C++ 4.8.1, Oracle JDK 1.8.0_20;
3. Available software: Google Chrome, Code::Blocks 13.12, Eclipse 4.4.0 (Luna), Far Manager 3.0.4040, Python 3.4.1, gVim 7.4.
If you have any questions, feel free to ask: [email protected].

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

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

Результаты первого тура X Международной Жаутыковской олимпиады
Автор mexmans, 10 лет назад, По-русски

Ссылка

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

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

2011-2012 Waterloo Local Contest, 24 September, 2011 Разбор задач A,B,D
Автор mexmans, 12 лет назад, По-русски

A.  Bridges and Tunnels

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

Итого сложность O(N) либо O(Nlog(N)).

В этой задаче нужно было перевести число в десятичную систему счисления. После перевести данное число в систему счисления, которое дано во входных данных. Ничего сложного, но у большинства людей, включая и меня, решавших эту тренировку возникали проблемы, и они сдавали ее со 2-5 попыток. Проблема была с 0.
Хотелось бы отметить наличие в Java, встроенных функций, считывания числа в системах счисления от 2-36, и вывода числа в системе счисления 2-36. Коротко можно было написать примерно вот такое:
int x = nextInt();
int y = nextInt();
long z = Long.parseLong(nextToken(),x);
System.out.println(Long.toString(z,y).toUpperCase());

Итого сложность O(log(z)).

В этой задаче можно было поступить следующим образом:
Научимся за O(1) находить количество плохих клеток в произвольном прямоугольнике. Для этого заведем массив d[i][j], где d[i][j] равно количеству плохих клеток в прямоугольнике от (0,0) до (i,j). Это легко сделать за O(n^2) по вот такой рекуррентной формуле d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + (bad[i][j] ? 1 : 0); Теперь для того, чтобы посчитать количество плохих клеток, в квадрате длинной l, правый нижний угол которого имеет координаты (i,j), используем следующую формулу d[i][j] - d[i - l][j] - d[i][j - l] + d[i - l][j - l]; Легко видеть, что возможность найти квадрат фиксированной длины, в нашей мозайке есть монотонная функция. Воспользуемся бинарным поиском по длине квадрата. Проверяя для фиксированной длины можно ли найти такой квадрат. То есть для каждого положения проверить, что d[i][j] - d[i - l][j] - d[i][j - l] + d[i - l][j - l] <= L.
 
Итого сложность O(N^2log(N)).

Хотелось бы услышать, разбор задач C,E.

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

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

Применение теоремы Шпрага-Гранди
Автор mexmans, 13 лет назад, По-русски
1) Задача
Двое играют в следующую игру:
В ряд выстроены N белых камней, за один ход разрешается перекрасить один белый камень в черный, если соседние камни белые, проигрывает тот кто не может совершить ход.
2) Что я делаю? 
Пишу рекурсивную функцию подсчета функций Гранди, следующим образом:
если N = 0 то ответ очевидно 0 иначе
если N <= 3 то сопоставляю ним-число 1 (Выигрышная позиция) иначе
создаю пустое множество A
Запускаю цикл i от 1 до N если перекрасить i ый камень то мы придем в состояние из двух независимых игр меньшей размерности i - 2 и n - i - 1, считаю для каждой из них функцию Гранди и добавляю в множество A исключающее или двух полученных значений функции, обрабатывая граничные случаи.
Нахожу из данного множества минимальное неотрицательное число не встречающееся в нем. Возвращаю ответ.
3) Некоторые тесты
    4 проигрышная позиция (ок)
    5,6,7 выигрышная позиция (ок)
    8 проигрышная позиция (на что моя программа возвращает неверный результат) 
4) Что-то я делаю не правильно. Подскажите как можно свести эту игру к ним-игре и/или подскажите ошибку в моих рассуждениях. Спасибо.

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

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