So I decide to register to the contest and it's 15 hours late. What are even the rules? Is it the same as usual? What's the cut-off? It turns out everything is mostly the same. I need 30 points and just the small inputs are enough to give you 37 points. So it should be easy to qualify.
Perhaps it's too similar to previous editions? I think 1000 t-shirts is pretty low, considering how much the attendance has grown since this number was established. Actually when I look at the past I think I would have never really put as much work on programming contest if, ages ago, when I was getting started, there weren't as many small rewards for simple things as they were. In the past, in codejam or topcoder open, qualifying to the elimination rounds was worth a t-shirt and there were extra little rewards for advancing in other rounds. In fact, the first codejam done using Google's own site had regional semifinals so if you were in the top 500 you'd already win a paid trip to a google office.
Back to the present. Qualifying, even 15 hours late should be pretty easy for a
Problem A (Large)
Problem Statement
This is a straight-forward problem, you just need to simulate the steps until all digits are found. A pressing question is what's up with impossible cases? Well, I actually just coded right away and tested all 1000001 possible inputs from 0 to 1000000, with a maximum number of 1000 steps to find all digits. Even then, the simulation is very fast and the only case that doesn't reach all digits is `N = 0`, which will always be 0 no matter how far you go. So with that knowledge I just submitted an easy code:
const int MAX_ITERATIONS = 1000;
long solve(long x)
{
long y = x;
set<char> s;
for (int i = 0; i < MAX_ITERATIONS; i++) {
ostringstream st;
st << y;
for (char ch: st.str()) {
s.insert(ch);
}
if (s.size() == 10) {
return y;
}
y += x;
}
return -1;
// not pictured: I/O stuff including translating -1 to "impossible"
}
Problem B (Small and Large)
Problem Statement
Well, the small version can be solved using a Breadth-First Search. Just consider a string of +/- as a vertex in some graph and each possible step is an edge between its initial setup and its resulting setup. Then you want to find the shortest path between the input and +++++...+ . With `N <= 10`, there are at most `2^10 = 1024` vertices in the graph, so this is quite doable.
But I wanted to solve the hard version. Clueless as I often are, I just did the small version hoping that it would help me think of the hard solution. I concluded some greedy approach was needed because all permutations of cookies are reachable from any initial setup so cutting the search space wouldn't work (for me).
After coding the small version and being able to see some of the solutions it generates, I noticed a very obvious pattern:
+++-++---+--+
----++---+--+
++++++---+--+
---------+--+
++++++++++--+
------------+
+++++++++++++
Basically keep flipping the largest sequence of cookies at the top that have the same sign (+ or -) as the top-most cookie. You will eventually have a bunch of happy cookies. And this is the optimal solution. Because this is the optimal strategy in a different problem where a step consists only about changing the sign of a prefix of a string, and the other options in the real problem are not better.
int solve(string s)
{
int n = s.size();
int step_count = 0;
while (s != string(n, '+') ) {
int t = 1;
while ( (t < n) && (s[t] == s[t-1]) ) {
t++;
}
for (int i = 0; i < t; i++) {
if (s[i] == '+') {
s[i] = '-';
} else {
s[i] = '+';
}
}
step_count++;
}
return step_count;
}
/* _Used this to think of the real strategy which was pretty obvious in
hindsight ... */
int solve_slow(string s)
{
int n = s.size();
map<string, int> dist;
queue<string> Q;
dist[s] = 0;
Q.push(s);
map<string, string> parent;
while (! Q.empty()) {
string s = Q.front();
Q.pop();
for (int t = 1; t <= n; t++) {
string ss = s;
reverse(ss.begin(), ss.begin() + t);
for (int i = 1; i <= t; i++) {
char & ch = ss[i - 1];
ch = ( (ch == '+') ? '-' : '+' );
}
if ( dist.count(ss) == 0) {
dist[ss] = dist[s] + 1;
Q.push(ss);
parent[ss] = s;
}
}
}
string w = string(n, '+');
assert( dist.count(w) == 1 );
{
stack<string> S;
string x = w;
while (true) {
S.push(x);
if (parent.count(x) == 1) {
x = parent[x];
} else {
break;
}
}
while (! S.empty()) {
cout << S.top() << endl;
S.pop();
}
}
return dist[w];
}
Problem C (Small and Large)
Problem Statement
My initial hunch was that a huge majority of the possible binary strings are valid coins. Because really, primes tend to be hard to find and we want strings that aren't primes. Even though they can't be primes in many bases. But I still thought it would take a while to find 500 coins. So I decided to do something with threads. I find threads easier in python so I used python. When I finished coding it and tested, it turned out that the code was very fast, so the threads weren't needed :/, but it's still a cool looking solution:
N = 32
J = 500
NUM_THREADS = 4
EASY_PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]
import random
import threading
import sys
mutex = threading.Lock()
seen_coins = dict()
def add_if_new(coin, divisors):
with mutex:
if coin not in seen_coins and len(seen_coins) < J:
seen_coins[coin] = divisors
sys.stderr.write( str(len(seen_coins)) + ' already!\n' )
sys.stderr.write( str(attempt_count[0]) + ' attempts\n' )
sys.stderr.flush()
def work_done():
with mutex:
if len(seen_coins) >= J:
return True
else:
return False
def random_coin():
x = [ random.randint(0,1) for i in range(N) ]
x[0] = 1
x[-1] = 1
return tuple(x)
def is_divisor(coin, b, d):
m = 0
p = 1
for x in reversed(coin):
if x == 1:
m = (m + p) % d
p = (p * b) % d
if m == 0:
return True
else:
return False
def get_divisors(coin):
divisors = []
for b in xrange(2,10 + 1):
for d in EASY_PRIMES:
if is_divisor(coin, b, d):
divisors.append(d)
break
else:
return None
return divisors
attempt_count = [0]
def worker():
while not work_done():
coin = random_coin()
divisors = get_divisors(coin)
if divisors != None:
add_if_new(coin, divisors)
with mutex:
attempt_count[0] = attempt_count[0] + 1
#sys.stderr.write( str(attempt_count[0]) + ' attempts\n' )
threads = [ threading.Thread(name='worker%d'%i, target=worker) for i in range(NUM_THREADS) ]
for t in threads:
t.start()
for t in threads:
t.join()
sys.stdout.write( 'Case #1:\n')
for x in seen_coins:
for y in x:
sys.stdout.write( str(y) )
for div in seen_coins[x]:
sys.stdout.write( ' ' + str(div) )
sys.stdout.write( '\n')
sys.stdout.flush()
I think one thing that improves the execution is I only test if the coin is a multiple of a small list of primes. Instead of looking for coins that are any composite number , I add the condition that they are a multiple of small primes. Most composite numbers are multiples of small prime numbers, so this shouldn't be an issue in theory, and in practice, it isn't.
Problem D (Small and Large)
Problem Statement
First the small problem is super trivial. Because `S = K`, so you can just test positions 1,2,3,...`S` and it will be enough. Because if there is any G in the initial string, then the final string will definitely have a G in that same position.
The larger solution is more complicated but not that much. Even though it took me a couple of hours to think of it .
If you want to be able to find any case that contains a G, then we should focus on the hardest cases, the ones that have only one G in the input: GLLL, LGLL, LLGL, LLLG. It turns out that if you include a G in position 1, it spreads to many positions in the later iterations. So imagine we had four positions: ABCD in the first string. We want to find which positions of the second string would be effected by positions A, B, C and D (E.g: If there is a G in position A, then the second position of the second string will contain a G. If there is a G in position B, then the second position of the second string will also contain a G, so position 2 of the second string can be classified as AB. If you repeat this you will find: A, AB, AC, AD, AB, B, BC, BD, AC, BC, C, CD, AD, BD, CD, D. Perhaps it will be easier if you read it as: AA, AB, AC, AD, AB, BB, BC, BD, AC, BC, CC, CD, AD, BD, CD, DD. In fact, with 3 steps we have: AAA, AAB, AAC, AAD, ... DDD. And so and so, it's the same as thinking of numbers in base K. So for C = 3, if we want positions that cover as many initial Gs as possible then we want the positions that have ABC and DAA (or DAB or ADC, anything containing a D). You can get the position index by converting from base k to base 10. This explanation is probably very bad. Sorry, I can't do better without drawings.
long translate(vector<int> digits, int K)
{
long res = 0;
long p = 1;
for (int i = 0; i < digits.size(); i++) {
res += p * digits[i];
p *= K;
}
/*for(auto x: digits) cout << " " << x;
cout << " -> "<<res<<endl;*/
assert(res >= 0);
return res;
}
list<long> solve(int K, int C, int S)
{
list<long> res;
int p = 0;
while (p < K) {
vector<int> digits;
for (int i = 0; i < C; i++) {
if (p < K) {
digits.push_back(p);
p++;
} else {
digits.push_back(0);
}
}
res.push_back( 1 + translate(digits, K) );
}
if (res.size() > S) {
//assert(false);
return {};
} else {
return res;
}
}
Final results
As I was typing, the round ended, let's check the final results...
All my large solutions were okay. But tons of people had them okay as well. I am barely in position 1246. That's pretty low, but I did start the round 15 hours late... (excuses)
