DCODE

[Pascal]

I have a few questions...

When a rule has been executed, does it try the next rule in the list, or the first rule again ? On an example:
if 0==0 then { C1 };
if 0==0 then { C2 };
is the execution C1,C1,C1... or C1,C2,C1,C2... ?

On the 100 limit per day, is it 100 rules per day or 100 executions of the code ? (this is meaningful only in the second case above)

I find it strange that a,b and color contain random values at startup, because we have no way of telling reliably if this is the very first run or not ! This prevents from coding some interesting algorithms requiring an initialisation step. It would be much practical if there was some predefined value.

Btw, nice problem but why is the simulation so slow, even on very simple programs ?

[Adrian Kosowski]

is the execution C1,C1,C1... or C1,C2,C1,C2... ?

The execution is C1,C2,C1..., so the following code is acceptable:

Code: Select all

if l0==0 then {l0:=0;};
if l1<98 then {l0:=1; l1:=l1+1;};

I think Łukasz will be more competent to answer all your questions .

[kuszi]

On the 100 limit per day, is it 100 rules per day or 100 executions of the code ? (this is meaningful only in the second case above)

100 executions of the code

I find it strange that a,b and color contain random values at startup, because we have no way of telling reliably if this is the very first run or not ! This prevents from coding some interesting algorithms requiring an initialisation step. It would be much practical if there was some predefined value.

In this approach to distributed computing we consider the system as unreliable.
We give an algorithm assuming that the initial state of the system is unknown.
This is a rigorous and, as you mentioned, prevent us from coding some interesting algorithms, but on the other hand we have at least to advantages:

we do not need initialization
after some perturbations the system should converge to legitimate state without any external intervention.

This approach is called Self-stabilization and was introduced by Dijkstra in 1974.

Btw, nice problem

I am happy you like it.

but why is the simulation so slow, even on very simple programs ?

It is my fault, I've coded the parser, which interprets the rules, rather inefficiently. Please be patient. We will do our best to improve it in future.

[overwise]

Wow, I got the first "wrong answer" to this problem, but... how?
I thought that even the usage of numbers not in {0, ..., nr-1} would merely result in 0 points instead of WA, but I tried to make sure that my answer is a valid coloring...

[Adrian Kosowski]

Wow, I got the first "wrong answer" to this problem, but... how?

This is a bit of a feature which will really be difficult to fix. What it means is either "judge crash" or "simulation timeout" (far more likely that it is the latter ).

[Adrian Kuegel]

Is the mina function interpreted like described in the problem?
It seems that mina<a always evaluates to false.
I checked that with the following program:
if (l0<97 and (mina<a and Eceq(color))) then {l0:=0;};
if (l0<97) then {l0:=l0+3;};

I got a result of 0 points, no time limit exceeded. I think that indicates that the first statement was never executed.

[Adrian Kosowski]

Is the mina function interpreted like described in the problem?
It seems that mina<a always evaluates to false.
I checked that with the following program:
if (l0<97 and (mina<a and Eceq(color))) then {l0:=0;};
if (l0<97) then {l0:=l0+3;};

I got a result of 0 points, no time limit exceeded. I think that indicates that the first statement was never executed.

I guess everything was OK. Since values of all variables are random ints at the beginning, Eceq(color) will always evaluate as false, and you never change the color yourself afterwards.

Detecting whether it is the first day of simulation can be a bit tricky, and you have to look for a workaround (but it is possible, considering that the test conditions are deterministic). This behaviour is intentional, but perhaps, as Pascal has suggested, it has turned out a little pointless. After the contest is over we may consider adding k to the list of available constants.

[Adrian Kuegel]

Ah, ok, I forgot that the inital colors don't have to be between 0 and nr-1. Thanks for your answer.