Instructions to Interactive Problems

General Instructions for UVa OJ

From contestant's perspective, the difference between interactive problems and traditional (batch) problems is that the input to your program (client) is not statically stored in a file: it is produced dynamically by another program (server), and the output of the client is immediately sent to the server, which can be used by the server to compute its next output (which is in turn sent to the client).

For example, in a "guess the number" problem, you're requested to guess an integer between 1 and 1000 in 20 turns. Each time you can ask an integer, the server will tell you whether it's bigger, smaller or exactly same.

In UVa OJ, the client should read from standard input, and write to standard output. The communication between the server and the client is line oriented. That means after printing each line to the standard output, you should flush the output, by calling fflush(stdout) or cout << flush in C/C++, flush(output) in Pascal and System.out.flush() in Java. This way, your output will be sent to the server immediately. The server will also flush the output after each line, but you don't have to read a whole line at a time.

In short, the only important thing you should know is: always flush your output after printing a line. Everything else is the same as traditional problems.

Interactive problems are usually harder to solve, so UVa OJ kindly provides some more verdicts in addition to the traditional ones like AC (Accepted), WA(Wrong Answer) and TLE(Time Limit Exceeded):

BC = Broken Communication
PV = Protocol Violation
PLE = Protocol Limit Exceeded

The first one means the server failed to read a line or write a line, which usually means your program exited presumably. The latter two are defined for each problem separately, which is usually quite intuitive.

Note that servers can exit presumably when there is no need to continue.

Interactive Problems in Rujia Liu's Present 7

Here are the instructions for interactive problems that are valid only in this contest. However, I find these instructions very helpful not only to the contestants, but to the problem authors. So if you want to author an interactive problem, please read on careful.

In the gift package, all the source codes of the servers are provided. There was also an example problem: guess the number, mentioned above. You can find the problem description, server code, correct (AC) client code in C++, Pascal and Java, and some incorrect code (WA, PV and PLE etc).

Each server can be run in two modes: manual mode and auto mode. In manual mode (which is the default mode), the server reads from the standard input and writes to the standard output. So before coding, you can play with the server manually, which may help you understand the behavior of the server.

However, after you finished your client, it's difficult to test your client with the server. You have to open two windows, one running server and one running client, and manually send (type with keyboard or copy/paste) the output of server to the input of client, and the output of client to the input of server. Isn't it terrible?

So auto mode comes to rescue. In auto mode (which can be enabled by defining AUTO_MODE when compiling the server), the server (now it's called autoserver) launches your client as a child process. With some magic, your client's input automatically comes from the server, and your client's output automatically goes to the server. With the debug information printed by the server ("Correct" or some error message), you can easily judge your client by yourself. Attention: the debug information printed in your client's standard error will be swallowed. Any debug information from your client should be printed to files.

However, all the servers in this contest need an input file (see the source code for more details). The format of this input file is not described anywhere, so you have to figure it out by yourself. Then you can test your program with different input files, just like traditional problems.

The interaction protocols in this contest are all text-based. Formally speaking, for each test case, your client should read some initial data (just like traditional problems), then your client should issue some commands, read their results, until the test case is solved. There should be one single space between tokens (command name and arguments).

The commands are very similar to function calling in programming languages. The command always starts with a command name, then zero or more arguments (typically in the same line), and the result is always zero or more arguments (usually integers).

We advice you to wrap the communications in functions. Suppose there is a command Query:

Then you can wrap it in a function like this:

int query(int i, int j) {
  printf("Query %d %d\n", i, j);
  fflush(stdout);
  int x;
  scanf("%d", &x);
  return x;
}

This way, solving interactive problems are very similar to solving traditional problems: you read initial data as usual, and call these "wrapped" functions, until you're done.

Sometimes the server will exit before you expect it to do so. That's usually after your client sent something wrong (wrong command format or incorrect answer). We strongly encourage you to check the return values of your I/O functions and exit immediately when those functions failed to read/write data, otherwise your program may face some junk data (due to bad read) and receive Runtime Error instead.

Note that debugging your client is a bit harder than before, because you can't simply make a file and use redirection to feed it to your client. One way is to re-use the interactlib that the server codes depend on, then your client can launch the server (in default mode) and your cin/cout automatically connects to the server's output and input, respectively. However, interactlib has a serious restriction: you can only use C++ and use cin/cout exclusively for I/O. You can't use other languages and you can't use stdio stuffs (scanf/printf etc).