Hello,

So the Truveo challenge is over and my application scored 25th place out of 96(Good enough for second prize). Here you can see my entry: click here. Also there is a post on Studio Blog click here . Also AOL made an interview about my application. So it’s all good.

Hey, GCJ is in few hours (Round 2). From 2400 only 1000 will advance, so I hope I will perform good. Yea will see.. later!

So this week is practice week, because in 4-5 days GCJ Round 2 will take place. The level of problems will be higher and it will be a tough round because out of 2400 competitors only 1000 will remain in game (which is 41%).

So I start this practice week with simulating Round 1 Sub Round 3 of GCJ. After doing the set I realized it was a nice set and slightly easier then SubRound 2 and SubRound 1. I was able to do all 3 problems perfectly in 1:27 hours(if I were in contest this would’ve place me 15th). I liked  all 3 problems. But I think  B was the most crazy one, even thou I coded A + B in half an  hour, and C took me longer.

Let’s talk about B before I finish this post.So after reading it quickly it clicked in my mind that this is DP. If you read the problem you will know what I will be talking about. Quickly I calculated how many DP states are there so I got 2 * 3 * 5 * 7 * length. And for large input length was <= 40. So it was just perfect. Ok here is the recurrence I used. DP[length][two][three][five][seven] = how many are there if I used first length digits, and I have modulo 2 = two, modulo 3 = three, modulo 5 = five, modulo 7 = seven. Ok I will end this post leaving my source code here to see it (P.S: Wednesday is my 19th Birthday )

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
typedef unsigned long long LL;

void go();

LL DP[44][2][3][5][7];

int main()
{
freopen("file.in", "r", stdin);
freopen("file.out", "w", stdout);
int T;
scanf("%d", &T);
while (T--) go();
//fclose(stdin);
//getchar();
return 0;
}

int Case = 0;
int f(string s, int M) {
int ret = 0;
int i;
for (i = 0; i < s.size(); ++i) ret = (ret * 10 + s[i] - '0') % M;

return ret;
}
void go() {
//clean
int v[4];
int i;
for (i = 0; i < 44; ++i) for (v[0] = 0; v[0] < 2; ++v[0])
for (v[1] = 0; v[1] < 3; ++v[1])
for (v[2] = 0; v[2] < 5; ++v[2])
for (v[3] = 0; v[3] < 7; ++v[3]) DP[i][v[0]][v[1]][v[2]][v[3]] = 0;
DP[0][0][0][0][0] = 1;
string s;
cin >> s;
int n = s.size();

int j, k;
for (i = 1; i <= n; ++i)
for (j = 1; j <= i; ++j) {
//afla module
int m[4];
m[0] = f(s.substr(j-1, i - j + 1), 2);
m[1] = f(s.substr(j-1, i - j + 1), 3);
m[2] = f(s.substr(j-1, i - j + 1), 5);
m[3] = f(s.substr(j-1, i - j + 1), 7);
//+ sau -
for (v[0] = 0; v[0] < 2; ++v[0])
for (v[1] = 0; v[1] < 3; ++v[1])
for (v[2] = 0; v[2] < 5; ++v[2])
for (v[3] = 0; v[3] < 7; ++v[3])       {
//add with m
int sum[4];
for (k = 0; k < 4; ++k) sum[k] = (v[k] + m[k]);
sum[0]%=2; sum[1]%=3; sum[2]%=5; sum[3]%=7;
DP[i][sum[0]][sum[1]][sum[2]][sum[3]] += DP[j-1][v[0]][v[1]][v[2]][v[3]];

for (k = 0; k < 4; ++k) sum[k] = (v[k] - m[k]);
sum[0]+=2000; sum[1]+=3000; sum[2]+=5000; sum[3]+=7000;
sum[0]%=2; sum[1]%=3; sum[2]%=5; sum[3]%=7;
DP[i][sum[0]][sum[1]][sum[2]][sum[3]] += DP[j-1][v[0]][v[1]][v[2]][v[3]];
}
}
LL total = 0;
for (v[0] = 0; v[0] < 2; ++v[0])
for (v[1] = 0; v[1] < 3; ++v[1])
for (v[2] = 0; v[2] < 5; ++v[2])
for (v[3] = 0; v[3] < 7; ++v[3]) if (v[0] * v[1] * v[2] * v[3] == 0) total+=DP[n][v[0]][v[1]][v[2]][v[3]];
printf("Case #%d: ", ++Case);
cout << total / LL(2) << '\n';

}

So if I knew Python before I could easily get C-small. So here is my first complete program in Python solving the small C.

import decimal as dc

def f(t):
if t == 0: return dc.Decimal(1)
if t == 1: return dc.Decimal(3) + dc.Decimal(5).sqrt()
return (dc.Decimal(3) + dc.Decimal(5).sqrt()) * f(t-1)

dc.getcontext().prec = 1000
IN = open("file.in", "r")
OUT = open("file.out", "w")
line = '0'
line = IN.readline()
counter = int(line)
i = 1
while i <= counter:
line = IN.readline()
s = 'Case #' + str(i) + ':' + ' %03d' % (int(f(int(line))%1000))+'\n'
OUT.write(s)
i = i + 1

IN.close()
OUT.close()
print "done"

GCJ Sub Round 1A will start in less than 5 minutes. I hope I will make it in top 800. If not I will have one more chance! Later!

////+++Later Edit++++////

So sub-round 1A is over. And guess what? I made it in top 840 (as required for advancing). My results weren’t that great, but important was to be in top 840. I don’t know exactly how many competed in this sub-round, but I know  there were almost 4000 competitors registered at it and only 2394 managed to have non-zero score.

Ok, so here you can find the problems: click here

So let me tell you what I did in contest. So for problem A if you read it you have to minimize sum(x[i], y[i]) i = 0…n where x and y are the two given vectors, and being allowed to permute any of the vector.

For small input I coded quickly a solution with next_permutation as n was very small. But for Large input obvious this solution won’t work. That’s why I did a greedy which worked just fine. The minimal sum was given if you sorted the first vector in decreasing order and the second vector in increasing order. A small thing to be careful was that the sum would not fit on int, so long long was preffered.

For second problem that I read was C because it had a short statement. If you read C you will see that this is a math problem. So if you calculate (3 + sqrt(5)) ^ n is equal with X + Y * sqrt(5). Where X is always calculated modulo 1000 and Y would fit on Long Long. But it looks like still it looses precision. So I failed doing the small-input. Then I tried to find a good precision calculator online, and I decided to use Google Calculator for small (as n <= 30.) But guess what still I failed. After that I just gave up and read problem B. BTW: the solution was based on the fact that (3 + sqrt(5))^N + (3-sqrt(5))^N is an integer and (3-sqrt(5))^N < 1. (I won’t give more details )

For problem B, I saw the obvious solution (brute force in 2 ^ N, as N <= 10). But for large input I though only a max flow will solve it. But looks like a greedy would work, because there is a small detail in statement telling that a malted shake could be in a list of favorite of a person maxim one time.

For those that will participate in Sub-Round 1B and C, I wish good luck. See you in 2nd Round.

Hope you all know about Google Code Jam if not. visit http://code.google.com.

Qualifications Round is over for more then a week now. And I was one of the ~6400 competitors who advanced.  Next round which is Online Round 1 consists of 3 sub-rounds from which I am allowed to participate in maximum 2. From this round only ~2400 people will remain in the game (~800 from each sub-round), so 4000 competitors will have to wait one more year. Wish me luck because I want to remain in competition.

The first sub-round will start in about 16 hours and 45 minutes from now! I will get back after the rounds and I will post out some results. Also please leave a comment if you are a contestant too, let me know if you advanced or not Other than that more posts will be coming soon!

.vladut

I will try to come back on this blog. So yeah..

After finishing all the homework which I’ve been procrastinating on it for a while (recunosc), I’m debating on doing or not the design for Client Landing Page on Topcoder Studio (http://www.studio.topcoder.com). It may be a good opportunity to get some TCO points (there are few submissions and the deadline is in few hours). I don’t really feel like designing anything tonight, but I guess I will do. I will let you know in morning if I did it or not.

ZZZzzZzzzZZZzzzzZZZZzzz

Uite.. mi-am facut si eu. blog.

Yeah dude. So yeah, just an other blog. I don’t know exactly what will be about but I will just write things.

So numa bine si noroc!