Circumstances got in the way this time, and I think I couldn't enjoy IPSC as much as I would have wanted.
I am still battling with my chronic headache. Although it is getting better lately. But I am still trying to keep a strict sleep schedule. This week was when I noticed that this schedule was going to be a problem. IPSC starts at 6:00 in my timezone, and I am supposed to always sleep from 11:00 to 7:00 now. I was willing to make an exception, but with some bad luck I had to sleep at 12:00 AM last night because of other bad combination of circumstances. So today I actually woke up at 6:45. I couldn't begin working with IPSC right away though. You know, breakfast, stuff and ... more circumstances that had to distract me for a while.
The solution booklet is already up, so this blog post is not the best place for explanations.
Problem C: Code inception
Around 8:00 AM-ish, I took a look to the standings. The last place had C1 solved, so I decided to open problem C. In this problem, there are two codes (c++ or python) that are supposed to "eventually, at some point" return a single English word. So the only output you need to send to the server is that English word (two versions of the problem, one for 1 point and another for 2).
The codes used are insane and the ultimate proof that misof is a deranged mad genius. Here is the code:
#include <algorithm>
#include <iostream>
#include <vector>
int B[] = { 1894607624, 1927505134, 1861486949, 2052221263, 1953703270, 1772249212, 1704106159, 1607055075, 1829198849 };
std::vector<int> A(B,B+9);
long long t(long long n) {
long long z=n;
for (long long a=2; a<n; ++a) if (t(a)>=a) if (n%a==0) { z/=t(a); z*=t(a)-1; }
return std::min(z+1,n);
}
int main() {
sort( A.begin(), A.end() );
for (int i=0; i<4; ++i) A[i+5] ^= t(A[i+1]-A[0])>>7;
long long z = std::max( t(A[0])-1, A[0]+1-t(A[0]) );
for (long long i=0; i<z; ++i) std::rotate( A.begin(), A.begin()+1, A.end() );
A.insert( A.begin()+1, z );
for (long long x=8; x<1e7; ++x) {
int y = A[x/4]>>(18-6*(x%4))&63;
if (!y) break;
if (y<60) std::cout << char(31+y); else std::cout << A[y-60];
}
}
Of course, if you try to run this code it will take too long to give the answer. I guess it takes years. I felt confident , because this is my sort of problem. I really thought I could do it. The trick is to avoid trying to understand the code and just look for optimization points. The first thing I noticed is this:
for (long long i=0; i<z; ++i) std::rotate( A.begin(), A.begin()+1, A.end() );
This use of std::rotate will just shift the array left. If you repeat this thing z times, it is the same as doing it only z % A.size() times. So we can just change the loop to repeat it ( z % A.size() )
The second thing was that the t function is quite expensive. But this also depended mostly on one line:
for (long long a=2; a<n; ++a) if (t(a)>=a) if (n%a==0) { z/=t(a); z*=t(a)-1; }
The trick is to notice that the contents of the if do important things only when a divides n. In a moment of sheer stupidity, I thought this meant we only needed to try values of a less than or equal to sqrt(n), that was dumb. You'll see why later.
It is also possible to make it only call t(a) once instead of thrice.
After I made these fixes. The output was not a word, it was a sentence. CHANGE ?????? to ???????, where the ?????? were large integers that I do not remember specifically. Ok, IPSC is being a trickster again, I thought. The statement does say that the code will output something eventually and at some point, so maybe we are supposed to change the integers. Certainly, the first ????? was in the b[] array, so what if we change it? I made the change, and a new instruction to change something with something else appeared. Then I did it again, and it happened again. Decided to make a program to change stuff for me until it stops saying something like CHANGE X TO Y....
So I modified the program to do that, and then it showed me that it does print plenty of CHANGE X TO Y lines, but eventually it didn't show that anymore. In fact, it showed complete giberish. Like Z@#½#~Z or something like that. Tough luck, something is wrong which my code :(. I tried tons of things to find the mistake. I even tried CHANGE and TO, because maybe you weren't supposed to follow the instructions. This probably stole an hour of my time until I gave up and decided to work on other problems.
When the match ended, I went to the solution booklet. But in the process of skipping to problem C, because I was really curious why I was wrong, suddenly I noticed. No, not all divisors of a number are smaller than or equal to the square root. That is stupid. (I guess my morning brain got confused and used the logic that is used to optimize primality check). But the square root is useful. If we check only number y <= sqrt(x), then divisors are either y or x/y. So we can still use a O(sqrt(n)) loop to optimize this, but making sure to consider n/a as well as just a.
This is the final code that outputs "MATTER"
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;
int origB[] = { 1894607624, 1927505134, 1861486949, 2052221263, 1953703270, 1772249212, 1704106159, 1607055075, 1829198849 };
long long t(long long n) {
long long z=n;
// First optimization, consider a <= sqrt(n)
for (long long a=2; a<n && a*a <= n; ++a) {
if (n%a==0) {
// But remember that n/a is also a divisor:
long long aa[2] = {a, n/a};
for (int i=0; i<2; i++) {
long long b= aa[i];
// We only need to call t(b) once:
long long x = t(b);
if (x>=b) {
z/=x; z*=x-1;
}
}
}
}
return std::min(z+1,n);
}
string tostr(int x)
{
ostringstream st;
st << x;
return st.str();
}
int main() {
long long B[9];
for (int i=0; i< 9; i++) {
B[i] = origB[i];
}
while(true) {
std::vector<int> A(B,B+9);
sort( A.begin(), A.end() );
for (int i=0; i<4; ++i) A[i+5] ^= t(A[i+1]-A[0])>>7;
long long z = std::max( t(A[0])-1, A[0]+1-t(A[0]) );
for (long long i=0; i<z%A.size(); ++i) std::rotate( A.begin(), A.begin()+1, A.end() );
A.insert( A.begin()+1, z );
// Instead of printing, save the result to a string
string s = "";
for (long long x=8; x<1e7; ++x) {
int y = A[x/4]>>(18-6*(x%4))&63;
if (!y) break;
if (y<60) s += char(31+y); else s += tostr(A[y-60]);
}
// Print the string:
cout << s << endl;
// Parse it
istringstream st(s);
string w1, w2;
long long i1, i2;
if (st >> w1 >> i1 >> w2 >> i2) {
// Follows CHANGE X TO Y format:
for (int i=0; i<9; i++) {
if (B[i] == i1) {
B[i] = i2;
}
}
} else{
// Something else, break:
break;
}
}
}
Problem A
So there were only around two hours left, I needed points. Most people seemed to solve A1 and A2. These are easy problems, just greedily take the largest coin denomination until you no longer need coins. I rushed though and submitted a code with an obvious error . It was printing the result wrongly :)
Problem K
I looked at standings, and people near the bottom seemed to solve K1. It turns out it was a classic dp problem. K2 though is not so easy.
The trick is to use dynamic programming to decide the upwards movement AND at the same time decide whether or not you will use the step you are using again when going down.
I was having issues implementing this. The solution is correct, but it can be confused to implement. So I decided to rework the approach.
Consider two binary strings of n elements: Like 11010110001100011 and 110100101100101. The first string determines the steps you will use when going up, and the second the steps you will use when going down. The second must be a subset of the first. Also, the last step should be 1 in both strings. In the first string, there can not be two consecutive zeros. In the second string, there can not be four consecutive zeros. The problem is to count the number of ways to fill these two strings. You can just go from bit 0 to n-1 and decide the bit for both of them at each position. In order to correctly fill the first one, you need to remember the last bit. In order to correctly fill the second one, you need to remember the last three bits. We can use dynamic programming:
const int MOD = 1000000009;
const int X = 3;
struct solver
{
long dp[100001][1<<X][2];
int n;
long rec(int p, int mask, int last)
{
long & res = dp[p][mask][last];
if (res == -1) {
res = 0;
if (p == n) {
res = last && (mask&1);
} else {
res = 0;
//after moving to p+1, we need to shift the bits of the downwards
//string by 1, and include the new result:
int shuf = (mask << 1) & ( (1<<X) - 1);
if (last && (mask != 0) ) {
//can put 0 in the upwards string:
// 0 is forced in the downwards one:
res = rec(p+1, shuf, 0);
}
//put 1 in the upwards string:
if (mask != 0) {
// Put 0 in the downwards one:
// Only possible if at least one of the last 3 bits is 1:
res += rec(p+1, shuf, 1);
}
// Put 1 in the downwards one:
res += rec(p+1, shuf|1, 1);
res %= MOD;
}
}
return res;
}
long solve()
{
memset(dp, -1, sizeof(dp));
return ( rec(0,1,1) ) % MOD;
}
L1
Then it seemed that many people had L1 solved. So I opened it. And it was about playing a labyrinth javascript game. All fun stuff. I manually solved the easy cases. The large cases were massive though.
B1
15 minutes left, and I decided to open problem B. I only had time to solve the easy one. Which was really just simulation which could be optimized with precalculation.
Conclusion
Even though I could only see few problems and didn't have as much time as usual, this was still a fun round. IPSC is still one of the best yearly competitions.
No comments :
Post a Comment