MikeMirzayanov's blog

By MikeMirzayanov, 6 years ago, translation, In English

Hello, Codeforces!

Today I’ve released an important update of the Polygon — partial support for advanced properties of resources. The main task that is being solved by this update is to support the development of problems with graders.

In most competitions, participants need to submit a complete solution code, including reading an input reading and an output writing. For example, in Codeforces rounds you solve such kind of problems. However, in some competitions another approach is using: a participant needs to implement the required function or interface.

For example, in a problem statement can be written that in a C ++ solution you need to implement a function that has prototype int sum (int a, int b) and submit the implementation. In this case, a participant has to submit a source code that contains the implementation of this function. Then, in the process of judging this solution for such a problem, an online judge should compile and link into a single executable file the file sent by the participant and a special jury-prepared file that contains the rest of the necessary code (in particular, there will be the function main).

In the case of problem ``A + B’’, such file, which is called a grader, might look like (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;
}

A solution might look like:

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

Therefore, a grader cannot be independently compiled into an executable file: it also needs a solution to the problem.

And now basic support for such problems in Polygon has been implemented (thanks to PavelKunyavskiy and cannor147 for the help!). I've started with C++ support only.

In order to add grader files, you must upload them as resources, specifying additional advanced properties: that resources are applicable to cpp.* language group, that they are compile-time resources and that solutions need to be compiled with them.

After adding such resources, while compiling solutions, they will be in the same folder with the solution, and those resources that are C++ files will be appended to the compiler command line.

Please note that all additional information for resources is available in the problem descriptor file problem.xml. Also, API is updated (see the documentation for the methods problem.files and problem.saveFile).

Later, the support of some other languages will be added. Also, I’ll add a feature to attach resources in a similar way not to solutions only, but also to validators/integrators/checkers. Of course, you can expect support for such kind of problems on Codeforces. I note that such problems can be used not only in olympiads/contests but also in the educational process. For example, I can easily imagine an exercise on Java, where you need to implement a given interface, and all other routines (unit tests and other things) are hidden in resources files.

P.S. The support of graders appeared for a special reason: today in Russia begins the IOI training camp. The best high school students will compete for the right to represent Russia on International Olympiad in Informatics. I hope, this feature will help the scientific committee to write new problems. And I wish participants every success and luck!

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

»
6 years ago, # |
  Vote: I like it -103 Vote: I do not like it

We all hate TopCoder :)

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -46 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -46 Vote: I do not like it

      idk... :(

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +62 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Cool Fitch, thanks Mike.

»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
  Vote: I like it -29 Vote: I do not like it

i did not understand it. any short explaination !

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it -16 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you can try and it should work. Please, inform me about the result.