Javascript.
This solution uses the exponentiation operator (**) which was not available at time of contest :( So it is not accepted by the official grader but I know it works if you test it in Node.js.
I’ll be covering the partial solution for this problem (IPSC 2015 M, Make me an integer). Basically you have to form JS expressions that evaluate to integers 0 to 1000 using only chars ![]+-*. No whitespace.
This solution is predominantly math based (no string concatenation and other cool tricks like described in the official) and unfortunately only works with the easy subtask.
Some observations:
![] == 0
+![] === 0
+!![] === 1
!![] + !![] === 2
[!![] + !![]] * [!![] + !![] + !![]] === 6
[2]**[3] === 8
We use Langrange’s four-square theorem to figure out that we can break our integer into 4 square numbers. We know that if our original number is n, every square is <= sqrt(n). So we can brute force all potential squares (nested iterating 4 times from sqrt(n) to 0). Here’s the C++ code to do this:
#include<bits/stdc++.h>
using namespace std;
int w,x,y,z;
void solve(int n) {
for(int a = sqrt(n); a >= 0; a--) {
for(int b = sqrt(max(n-a*a,0)); b >= 0; b--) {
for(int c = sqrt(max(n-a*a-b*b,0)); c >= 0; c--) {
for(int d = sqrt(max(n-a*a-b*b-c*c,0)); d >= 0; d--) {
if(a*a+b*b+c*c+d*d == n) { w=a,x=b,y=c,z=d; return; }
}
}
}
}
}
signed main() {
freopen("sfour.out", "w", stdout);
for(int i = 1; i <= 1000; i++) {
solve(i);
printf("[%d, %d, %d, %d]\n", w, x, y, z);
}
}
An upper bound for the time complexity is O(sqrt(n) ^ 4) which is O(n ^ 2), acceptable since n <= 1000. Our squares are much smaller than the original number (<= 31). But it’d be too inefficient to keep breaking each of these into 4 more squares.
But since the numbers are small, let’s come up with a bunch of short ways to form small numbers. For example 16 can be 2^4 and 25 can be 5^2. Call these waypoints (in the code I called it “tb”). We can always add/subtract 1s from waypoints to get our desired number. For each number, we’ll do this process for each waypoint and return the minimum length string we can find.
For ease of implementation I’ve also added boilerplate to help with checking validity of solutions and debugging. Also, I represent !![] as 1 in strings and then convert it back to !![] internally, when needed.
The maximum length of our generated strings is 194. You can probably improve on this with tweaks in the algorithm.
Node.js code:
//There's A LOT of console output...
function print(...x) {
console.log(...x);
}
function assert(x, msg) {
if(!x) throw new Error(`AssertionError: ${msg}`);
}
function check(s, i) {
s = conv(s);
assert(typeof(eval(s)) == 'number', "s not number");
assert(s.length <= 200, "len > 200");
assert(eval(s) == i, "s not eval to " + i);
}
function conv(s) {
let res = "";
for(let i = 0; i < s.length; i++) {
if(s[i] == '1') res += '!![]'; else res += s[i];
if(s[i] != '1' && s[i] != '!' && s[i] != '-' && s[i] != '+' && s[i] != '*' && s[i] != '[' && s[i] != ']') throw new Error("Invalid charset: " + s);
}
return res;
}
function smol(x) { //Small number solver
let d = Number.MAX_SAFE_INTEGER;
const tb = {
"1": "+1",
"2": "1+1",
"4": "1+1+1+1",
"6": "[1+1+1]*[1+1]",
"8": "[1+1]**[1+1+1]",
"16": "[1+1]**[1+1+1+1]",
"32": "[1+1]**[1+1+1+1+1]",
"9": "[1+1+1]**[1+1]",
"12": "[1+1+1]*[1+1+1+1]",
"27": "[1+1+1]**[1+1+1]",
"24": "[1+1]**[1+1+1]*[1+1+1]",
"20": "[1+1+1+1+1]*[1+1+1+1]",
"25": "[1+1+1+1+1]**[1+1]"
}
let res = "[".repeat(200);
for(const en in tb) {
const num = parseInt(en);
let s = tb[en];
if(x-num > 0) {
for(let i = 0; i < x-num; i++) {
s += "+1";
}
} else {
for(let i = 0; i < num-x; i++) {
s += "-1";
}
}
if(conv(s).length < conv(res).length) res = s;
}
check(res, x);
return res;
}
const fs = require('fs');
const allFileContents = fs.readFileSync('sfour.out', 'utf-8'); //Read in solved squares
const lines = allFileContents.split(/\r?\n/);
let maxlen = 0;
const bad = [];
const sol = fs.createWriteStream("ans.txt", {flags: 'a'});
const sub = fs.createWriteStream("res.txt", {flags: 'a'});
function answer(x) {
sol.write(x + "\n");
sub.write(conv(x) + "\n");
}
for(let i = 1; i <= 1000; i++) {
let res = "";
JSON.parse(lines[i-1]).forEach(el => {
if(el == 1) {
res += "+1";
} else if(el == 0) {
//do nothing
} else if(el == 2) {
res += "+1+1+1+1";
} else {
res += `+[${smol(el)}]**[1+1]`;
}
});
if(i != 1) res = res.substring(1); //remove leading plus sign
check(res, i);
print(res, i);
answer(res);
const cr = conv(res).length;
maxlen = Math.max(maxlen, cr);
if(cr > 75) {
bad.push(i);
}
}
print(maxlen);
print(bad);