Polygon Guide

This is a guide to using Polygon for the South Pacific Regionals written by Darcy Best.

First Steps

Polygon is a problem development website. For those of you who are familiar with problemtools (this is what we used in previous years), this is a website that does strictly more than problemtools does, and is laid out in a nice website and should cause fewer headaches. When developing problems, the core judging team will create a problem on Polygon for each problem, this will be shared to the problem creator for development. Issue tracking and discussion will be done through Polygon.

At first, using Polygon feels a little abnormal because you have to find the locations of items, and the words that they use are not always the best (mainly because it was originally written by non-English speakers and translated over). But it is a very nice system that we will use in the South Pacific Regionals.

You will first need to make a user account on Polygon.

Here is a quick way to get your problem up and running (you may want to follow along by implementing a simple “Hello World” problem first).

Step 1: Get the problem statement going

Click Start to get into the problem. In the back end, they are using a Git repo, so you can edit items on your own branch without affecting anyone else. Later, you will commit your changes. The “Start” button is roughly equivalent to “Clone”.
Leave everything in General Info alone (you may want to adjust the time limit eventually, but not now).
Click Statement at the top.
Create an English problem.
This is where you will write your problem statement. There are 4 places that you will need to edit: Name (the problem’s name), Legend (this is the main text of the problem), Input format and Output format. Each of these accepts LaTeX commands (try not to use weird libraries).
After writing your problem, save your problem (button near the bottom). Then, click “In PDF” near the top. This will compile your problem statement for you. If there are LaTeX errors, this is when it will complain.
A PDF should open with your problem statement. Congrats! Step 1 is done! Note that every time you refresh the PDF page, it recompiles the problem, so you don’t need to keep clicking “In PDF”.

Notice that there are no Sample Input/Outputs yet. Let’s go make those!

Step 2: Get sample I/O

Go to Tests at the top.
Click the Add Test link (middle of the page).
In the Data box, put the sample input (for the actual problem, you will need to fill in the Description, but don’t worry about it for right now). Click the In Statement box (this is what makes it a Sample Input rather than a Secret Input). Click “Create”. Note that it did not ask you for Sample Output (we’ll deal with that next).
If you click back into Tests at the top, you should see that your test case has been added.
Polygon generates all of the output for you from a correct submission–this means that you do not have to make an output file yourself. So let’s go deal with that. Click Solution files at the top and Add solutions in the middle of the page. Upload a correct solution to the problem. This will become your Main Correct Solution, and all output files will be generated from this program.
Polygon requires a program to validate the output of your program. This is called a Checker. Click Checker at the top. Choose the Checker that is most appropriate. “wcmp.cpp” is basically diff. Use “rcmpX.cpp” if your problem requires floating point outputs. You will have to write your own Checker if your problem does not have unique outputs. (but we can deal with that later)
If you go back to your PDF, you should now see the Sample Input/Output. Congrats! Step 2 is done!

That’s it! You’re on your way! The next steps include:

Make a bounds.h file. This will make everyone’s life much easier!
Make secret dat a (possibly using generators).
Write a validator (to test that your input is valid).
Write code that you expect to be TLE (and mark it as TLE in the Solution files tab).
If you ever want to test your code against the I/O, that is what Invocations is.
We will track progress of the problem (positive and negative) through the Issues tab.
You can run solutions against randomly generated inputs to see if a solution is wrong/slow (This is Stress at the top).
At any point, you can commit your changes by clicking the “Commit” button in the bottom right. Please (please) include a commit comment of what you have changed.

bounds.h

We will assume you have read the First Steps tutorial.

For every problem for the South Pacific Region, we would like everyone to create a Bounds file. In this file, you will include all bounds related to your problem. If there is a bound specified in the problem statement, it should be here as well! This file shall be called “bounds.h”. Here is an example bounds.h:

#ifndef BOUNDS_H #define BOUNDS_H const int MIN_N = 1 , MAX_N = 100000; const int MIN_M = 1 , MAX_M = 100000; #endif

Note: If you are not used to writing headers through C++, the lines starting with “#” ensure that this piece of code is only included once during compilation.

This file will be available to be included in nearly all files on Polygon, including for Validators, Checkers, Generators. The file will NOT be available for the problem statement or solutions. The main reason to use this file is that often through the course of developing a problem, you want to change the parameters’ sizes to see how far you can push different algorithms. Without bounds.h, you would need to adjust this constant in several places throughout Polygon. By having this file, all you need to do is

#include "bounds.h"

and all constants defined in that file will be included in your programs. =) Please use these constants everywhere in your code. There should be no “magic numbers” appearing in your Validators, Checkers, Generators, etc.

For readability and consistency, we would appreciate if you could keep the same format as above, with bounds for each variable appearing on one line (unless there is a good reason not to) and each variable of the form “MIN_X” and “MAX_X”, instead of MINX, minx or min_x.

Making data (including generators)

We will assume you have read the First Steps tutorial and the bounds.h tutorial.

Here will be some instructions for how to create data on Polygon. Rather than uploading huge data files that were created by a program (called a generator from here on out), you can just upload the generator to Polygon and it will create the data for you!

Step 1: Write your generator

Like last year, we will be using testlib (http://codeforces.com/testlib). This is a library that works hand-in-hand with Polygon (they were developed by the same person). Testlib includes many features for you–random number generators, parsers, bounds checking, etc. On the Files tab on Polygon, there are 3 example generators. We would recommend looking at those to see how easy it is to use.

Here is another very simple example. This creates a random graph with n vertices and m edges. Note that the random seed is based on the command line arguments, so if you run the program as “./A 10 5”, it will produce a different random seed than “./A 100 2”. If you want two different graphs with the same n and m, just add a string on the end: “./A 10 5 a” and “./A 10 5 b” will produce different graphs.

// Generates a random undirected graph on n vertices and m edges. // Usage: "gen_graph n m" #include "testlib.h" #include <bits/stdc++.h> using namespace std; int main(int argc, char* argv[]) { registerGen(argc, argv, 1); // This should be the first line of every generator int n = atoi(argv[1]); // Number of nodes int m = atoi(argv[2]); // Number of edges // There can only be (n choose 2) edges in the graph. assert((long long)n*(n-1)/2 >= m); // (n choose 2) can overflow--don't forget to cast to 64-bit!! set<pair<int,int> > edges; while((int)edges.size() < m){ int u = rnd.next(1,n); // generates a random number between 1 and n, inclusive int v = rnd.next(1,n); if(u == v) continue; // Can't have a self loop if(edges.count(make_pair(u,v)) != 0) continue; // We already have this edge already if(edges.count(make_pair(v,u)) != 0) continue; // We have the "backwards edge" already edges.emplace(u,v); // This is equivalent to "edges.insert(make_pair(u,v));" } // In the set, the edges are sorted. Let's shuffle the order. vector<pair<int,int> > edges2(edges.begin(),edges.end()); // This copies the set<> into a vector<> shuffle(edges2.begin(),edges2.end()); // Shuffles edges2 randomly. // Now we output! cout << n << " " << m << endl; for(int i=0;i<m;i++) cout << edges2[i].first << " " << edges2[i].second << endl; return 0; }

We want to emphasize that this isn’t necessarily the best way to generate random graphs. For example, think about a near-complete graph. It may take a while to find edges near the end. But this is a good start! Let’s call that file “gen_graph.cpp”. To upload it to Polygon, go to Files. This is a Source File, so you can add it now.

Step 2: Call your generator

Now go to Tests. In the Script box at the bottom, type in:

gen_graph 10 20 > $ gen_graph 20 30 > $ gen_graph 30 4 > $

This will create 3 test cases, the first with n=10 and m=20, the second with n=20 and m=30 and the third with n=30 and m=4. Click “Save Script” at the bottom. Now let’s see if it worked! Click Preview Tests in the middle of the page. You should see the tests showing up (along with whatever tests you had added in manually). The “$” in the script just means “assign this test case to the next available test case number”.

We would recommend not doing much bounds checking in your generators–leave that for the Validator. Just do enough checks to make sure your code will run given reasonable inputs.

Reminder: for every problem, we will need fully random input. This means that your generator must assume nothing other than the bounds of the problem and generate input. The above code could be modified slightly to do this:

// Generates a random undirected graph // Usage: "gen_random_graph" #include "testlib.h" #include "bounds.h" // see the tutorial about bounds.h (Important!!) #include <bits/stdc++.h> using namespace std; int main(int argc, char* argv[]) { registerGen(argc, argv, 1); // This should be the first line of every generator ///////////////////////////////////////////////////////////////////// // The only changes are here // Number of nodes int n = rnd.next(MIN_N,MAX_N); // MIN_N and MAX_N are defined in bounds.h // Number of edges int max_edges = MAX_M; if(max_edges > (long long)n*(n-1)/2) max_edges = (long long)n*(n-1)/2; int m = rnd.next(MIN_M, max_edges); // MIN_M and MAX_M are in bounds.h ///////////////////////////////////////////////////////////////////// // There can only be (n choose 2) edges in the graph. assert((long long)n*(n-1)/2 >= m); // (n choose 2) can overflow--don't forget to cast to 64-bit!! set<pair<int,int> > edges; while((int)edges.size() < m){ int u = rnd.next(1,n); // generates a random number between 1 and n, inclusive int v = rnd.next(1,n); if(u == v) continue; // Can't have a self loop if(edges.count(make_pair(u,v)) != 0) continue; // We already have this edge already if(edges.count(make_pair(v,u)) != 0) continue; // We have the "backwards edge" already edges.emplace(u,v); // This is equivalent to "edges.insert(make_pair(u,v));" } // In the set, the edges are sorted. Let's shuffle the order. vector<pair<int,int> > edges2(edges.begin(),edges.end()); // This copies the set<> into a vector<> shuffle(edges2.begin(),edges2.end()); // Shuffles edges2 randomly. // Now we output! cout << n << " " << m << endl; for(int i=0;i<m;i++) cout << edges2[i].first << " " << edges2[i].second << endl; return 0; }

with this as our bounds.h file:

#ifndef BOUNDS_H #define BOUNDS_H const int MIN_N = 1 , MAX_N = 100000; const int MIN_M = 1 , MAX_M = 100000; #endif

First, upload “bounds.h” (in Files as a Resource File, then upload “gen_random_graph.cpp” as a Source File. Now go back to Tests. Your first instinct will be to do this:

###### THIS IS WRONG ###### gen_graph 10 20 > $ gen_graph 20 30 > $ gen_graph 30 4 > $ gen_random_graph > $ gen_random_graph > $ gen_random_graph > $ gen_random_graph > $

Remember, the random seed depends on the command line arguments! So all of these will create the same graph. To get around this, just give them all different arguments:

gen_graph 10 20 > $ gen_graph 20 30 > $ gen_graph 30 4 > $ gen_random_graph 1 > $ gen_random_graph 2 > $ gen_random_graph 3 > $ gen_random_graph purple? you can put whatever you want here > $

Step 3: Making descriptions

For every manual test case, you will need to provide a description! Note that this description is only visible to other judges, not the contestants. Data created through generators do not need descriptions so long as the filename of the generator is descriptive enough for what you’re doing.

That’s all, folks! Test case generation should be a breeze now. =)

Writing a validator

We will assume you have read the First Steps tutorial and the bounds.h tutorial.

After you have written the data, you will need to write a program which ensures that your data is valid. The most common mistake is doing whitespace incorrectly. For example, every program must end with a newline character, so “3 2” is an invalid input, while “3 2\n” is valid. Polygon provides very simple to use tools to write your validator. Here is an example to read two integers, n and m, separated by one space:

#include "testlib.h" int main(int argc, char* argv[]) { registerValidation(argc, argv); inf.readInt(1, 100, "n"); // Ensures there is an integer between 1 and 100, inclusive. inf.readSpace(); // Ensures there is a space character inf.readInt(0, 25, "m"); // Ensures there is an integer between 0 and 25, inclusive. inf.readEoln(); // Ensures there is a new line character inf.readEof(); // Ensures the file ends }

The validators are extremely picky! Every character in the file must match exactly what is required by the validator.

The above piece of code uses the constants 1, 100, 0 and 25–these are magic numbers! We should be using the bounds we set in “bounds.h”. Here is a slightly more complicated validator, which reads in an undirected graph and checks for loops and multi-edges:

#include "testlib.h" #include "bounds.h" #include <bits/stdc++.h> using namespace std; int main(int argc, char* argv[]) { registerValidation(argc, argv); int n = inf.readInt(MIN_N, MAX_N, "n"); // Number of nodes inf.readSpace(); int m = inf.readInt(MIN_M, MAX_M, "m"); // Number of edges inf.readEoln(); set<pair<int,int> > edges; for(int i=0;i<m;i++){ int u = inf.readInt(1,n,"u"); inf.readSpace(); int v = inf.readInt(1,n,"v"); inf.readEoln(); ensuref(u != v, "Graph cannot contain a loop"); // Program crashes if u == v ensuref(edges.count(make_pair(u,v)) == 0,"Edge between u=%d and v=%d already exists.",u,v); ensuref(edges.count(make_pair(v,u)) == 0,"Edge between u=%d and v=%d already exists (reversed).",u,v); edges.emplace(u,v); } inf.readEof(); }

Now before you blindly throw your validator at your secret data, you should write some tests for you validator.

For example:

1 0

and

2 2 1 2 2 1

should fail the above code, so let’s make sure. On the Validators page, you should add several cases to test that your validator behaves as you expect. After you add all the tests, click Run tests to ensure that it is working.

Testing your data

In the Tests page, if you click Preview Tests, it will generate all of your tests and run them against the validator. Another way of doing this is via Invocations. For example, with the input “1 0\n”, this error occurs:

ERROR: Unexpected verdict Validator 'validate-connected.exe' returns exit code 3 [FAIL Integer parameter [name=m] equals to 0, violates the range [1, 100000] (stdin)]CRASHED. Input: 1 0

Why did I put “n” as the last parameter of readInt()?

First of all, if the validator finds an error, the message that it outputs is much more useful to you as a human. But much more importantly, when you are testing you problem (through Invocations), Polygon will tell you if your test data has hit each of the extremes for each variable! So in the example above, Polygon will ensure that in some test case, n=1 and in some test case, n=100000. This check is not done for unnamed readInt’s. This check is immensely important (otherwise you’re either missing data or your bounds should be changed in the problem statement). For example, in test-program, run an Invocation that tests the programs. You will see an error at the bottom that n is never equal to the min-value.