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

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

Привет, Codeforces!

Сегодня мной было выпущено важное обновление Polygon – частичная поддержка расширенных свойств ресурсов. Основная задача, которая решается этим обновлением – это поддержка разработки задач с грейдерами.

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

Например, в условии задачи может быть написано, что в решении на С++ надо реализовать функцию, которая имеет вот такой прототип int sum(int a, int b) и отослать реализацию. В таком случае, участнику достаточно отправить исходный код, который содержит реализацию этой функции. Затем при тестировании решения по такой задаче система должна скомпилировать и слинковать в единый исполняемый файл присланный участником файл и специальный подготовленный жюри файл, который будет содержать весь остальной необходимый код (в частности, там будет функция main).

В случае задачи A+B такой файл, который и называется грейдером, может выглядеть так (grader.cpp):

#include <iostream>
int sum(int a, int b);
int main() {
	int a, b;
	std::cin >> a >> b;
	std::cout << sum(a, b) << std::endl;
}

Решение такой задачи может выглядеть так:

int sum(int a, int b) {
    return a + b;
}

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

Теперь в Полигоне реализована базовая поддержка таких задач (спасибо PavelKunyavskiy и cannor147 за помощь!), я начал с поддержки только C++.

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

После добавления таких ресурсов, при компиляции решений они будут находиться в одной папке с решением, а те ресурсы, что являются C++-файлами, будут переданы в командную строку компилятору.

Обратите внимание, что вся дополнительная информация для ресурсов доступна в дескрипторе задачи problem.xml, а также реализована поддержка нововведения в API (смотрите документацию по методам problem.files и problem.saveFile).

Позже будет добавлена поддержка некоторых других языков, возможность подобным образом прицеплять ресурсы не только к решениям, но и к валидаторам/интеракторам/чекерам. Конечно, следует ожидать поддержку таких задач на Codeforces. Отмечу, что подобные задачи могут найти своё применение не только в олимпиадном движении, но и просто в образовательном процессе. Например, я легко могу представить учебную задачу на Java, в которой требуется реализовать заданный интерфейс, а вся рутина (unit-тесты и прочие вещи) спрятаны в коде ресурсов.

P.S. Поддержка грейдеров появилась не просто так — сегодня начинаются сборы школьников по подготовке к международной олимпиаде школьников. Полагаю, что возможность подготавливать задачи с грейдерами в Полигоне поможет научному комитету сборов. А всем участникам я желаю удачных туров!

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

»
6 лет назад, # |
  Проголосовать: нравится -103 Проголосовать: не нравится

We all hate TopCoder :)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -46 Проголосовать: не нравится

    So many downvotes on cohr3141592654s comment? Why? TopCoders interface seems bad compared to codeforces, he is right I think

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -46 Проголосовать: не нравится

      idk... :(

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +62 Проголосовать: не нравится

      I won't downvote if he says " I hate TopCoder " and gives reasons. However, he said " We all hate TopCoder " without any reasons. I don't think one can use "We all" without asking for others' opinion.

      What's more, I don't think Polygon improvements have anything to do with TopCoder, though you may compare TopCoder with Codeforces when seeing this post.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится

      True code arena been out for more than 4 years and still on beta and buggy.

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Great feature. In this case, can I use stdout to show intermediate result?

»
6 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Cool Fitch, thanks Mike.

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Tips: After uploading the grader to resource files, check (or, select) the grader, then there will be "Remove" and "Advanced" instead of "Actions".

It took me minutes to find where the "advanced properties" is...

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Can We use graders to implement Interactive problems? Programmers can ask queries using functions instead of buffering, like IOI or other informatics Olympiads? If possible, it'd be great!

Sample Problem From oj.uz

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You should assume that participants solution has access to all the data grader has. Using grader which gets linked with participants solution to hide date or limit access is inherently insecure. Don't do this unless its only for practice, or test grader (for running locally on participant's computer). See CMS documentation about communication and batch task types https://github.com/cms-dev/cms/blob/master/docs/Task%20types.rst .

    Doing interactive problems properly requires two appropriately sandboxed executables — one being participants solution, other being manager. Where solution can only communicate with manager and manager has access to task data. Two executable communication task can be used in combination with grader that gets compiled with participant's solution to simplify the communication interface for participant. All the limitations and hidden data should be applied in manager which is in separate executable.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Full setup would look like this:

    Use communication task type in online judge.

    Manager — executable which has access to task input data, enforces limitations on queries, computes hidden data. Communicates with GraderA over a pipe.

    GraderA — gets compiled with participants solutions. Provides convenience functions for communicating with Manager. Interface between GraderA and Manager should be designed so that if grader was skipped and solution communicated directly with Manager it wouldn't get any advantage. That is grader isn,t used for hiding data or enforcing limitations.

    GraderB — merges functionality of GraderA and manager skipping communication over pipe. This is provided to participant for local testing and debugging. Can be only used for tasks that don't require manager implementing the same algorithm as solution.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Do you have any sample problems on Codeforces to try this?

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I have always felt independent the earlier way. This change kind of restricts me to follow standards. Also there are situations when making a separate function for a question seems useless. I myself have seen this on many websites, but I have no clue as to why this paradigm gained so much popularity.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    There are many benefits, such as --

    • It frees you from writing useless stuff as taking input and writing output, the grader does that for you and you write only the core parts.
    • It is easier to force online solutions to some problems using graders, that is much more convenient than things like "xor the input with previous answer". And also easier to make data sets for it.
    • In interactive tasks you don't need to "print the answer, flush output stream, take reply". Instead you just call a function and get the reply.
    • And many more ..
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How can we force the online solutions using grader? I cannot imagine, can you give me any example?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        For example you make the next query available only through a function which can be only called only if the contestant has already answered the previous query correctly (except for the first query, since there is no query before it).

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        The statement asks you to implement function, something like int solve(int l, int r), and grader calls it multiple times. You need to return the answer immediately, so offline isn't possible.

»
6 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

i did not understand it. any short explaination !

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

    tl;dr — In near future, you might see problems on codeforces where you only need to provide a function to solve the problem. Take this problem as an example.

    Advantage — People will no more cry about changing cin/cout to scanf/printf gives AC.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      I don't plan to use such problems on typical rounds, but they will be supported. For example, it can give better support for some IOI-like problems in GYM.

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

MikeMirzayanov Do you have any plans to support output-only tasks? Currently the most limiting factor for them is 64 kb source limit. Instead of submiting output file you can easily ask to submit a program, which contains file data in source code and print this data to stdout. But this way you can't submit files with size more than 64 kb, because of source limit.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it possible to add big template libraries (like Eigen)? If one wants to create a course for numeric optimizations, for example, it would be more than perfect.