Internet Problem Solving Contest

• Correct output – B2
• A faster version of the B2 program

For the easy input, there were three possible solutions:

Solution #1: "i--" replaced by "n--". Thus n is decreased until the test i<n fails.

int i, n=42;
main() {
  for(i=0; i<n; n--) {
    printf("*");
  }
}

Solution #2: "i<n" replaced by "-i<n". While i decreases, -i increases.

int i, n=42;
main() {
  for(i=0; -i<n; i--) {
    printf("*");
  }
}

Solution #3: "i<n" replaced by "i+n". Clearly i+n is zero iff i is -42.

int i, n=42;
main() {
  for(i=0; i+n; i--) {
    printf("*");
  }
}

---

The key to solving the hard problem lies in understanding that the five-element arrays in the program are used just to hold positive integers written in base-100 representation. For example, number 1048576 corresponds to the array {76, 85, 4, 1, 0}. The functions f1()-f9() perform some standard arithmetical operations on these numbers:

• f1(x) – Increase "x" by one. If "x" exceeds "rex", it is set to zero (i.e. the calculation is performed modulo (rex+1))
• f2(x) – Tests "x" for equality to zero.
• f3(x) – Assigns 0 to "x".
• f4(x) – Decreases "x" by one; if "x" drops below zero, sets it to "rex".
• f5(x, y) – Sets "x" to be equal to "y"-th power of "x" (modulo rex+1) and resets "y" to zero.
• f7(x, y) – Assign "y" to "x".
• f8(x, y) – Sets "x" to be equal to x*y+1 (modulo rex+1) and resets "y" to zero.
• f9(x, y) – Sets "x" to be equal to x+y+1 (modulo rex+1) and resets "y" to zero.

The last function, f10(x), performs the actual decryption of the hidden message. Basically, it consists of two parts:

1. First, it sets rex to 100`000`000 (i.e. the calculations will be performed modulo 10⁸+1).
2. For the i-th element of the array rpl[], the function repeats (i+1)^4 times the assignment c=(c*x+1) modulo (rex+1); starting with c=2. Finally, it XORs i-th element for rpl[] by second least-significant digit in base-100 representation of "c".

So, if you want to find the correct value of x and the hidden message, you should first rewrite the program, in order to make it fast enough (it was deliberately written to be incredibly slow). Then, you can perform an exhaustive search for the value of x, each time checking whether the just-decrypted element of rpl[] meets the criteria given in the specification (only upper-case letters, spaces and certain punctuation characters).

Finally, there was one small catch in the program – all the functions work with base-100 numbers, so after seeing this piece of code:

f3(b); b[0]=x%100; b[1]=x/100;

it might seem reasonable to assume that x must be smaller than 100*100. This is not the case -- the only operations applied to "b" during the execution are f4() and f2() and neither of them assumes that the number is written in its proper base-100 representation.

So, here are the correct answers:

Value of the constant: 195936285
Hidden text: IPSC IS A GREAT COMPETITION, ISN'T IT? IF YOU CAN READ THIS, YOU'RE ALMOST DONE.