Round 1A
I usually try not to advance during the first of the three round 1s. Because at the end you don't earn an advancer spot, you lose the chance to participate in other two matches. I also try not to fail round 1B though, because relying only on 1C is too risky. This year was different. I figured that this year it would have been very convenient to advance in round 1A. Because I had a important lunch on Saturday so I would not have been able to attend to 1B, and the schedule for 1C was... very inconvenient for me. 5:00 AM. I really intended to advance in 1A. It did not happen.
1A-A Freecell statistics
I initially tried many things related to doing fancy magic using modular stuff. Started off trying to solve the easy version. It had a small value of N so you could iterate from 1 to N for the number of rounds played that day. From then you would be able to guess if PD is possible. For a while, I tried to calculate the number of total rounds necessary to match everything once you had N, and (N*PD)/100. Using binary search and plenty of things. It was failing even the second example.
I noticed that the second example was pretty trivial (100% total rounds and non-100% rounds last day is impossible). Sometime during the implementation of the complicated, non-working solution it started to occur to me (what if there is always possible to have an appropriate total number of rounds provided that N*PD is divisible by 100?) It turned that it was almost true, you also needed to avoid mistakes when PG=0% or 100%. So, I gave it a try.
bool solve(int N, int pd, int pg) {
if ( pg == 100 && pd != 100 ) {
return false;
}
if ( pg == 0 && pd != 0 ) {
return false;
}
//D <= N
// (D*pd) % 100 = 0
for (int D = 1; D<=N; D++) {
if ( (D * pd)%100 == 0) {
return true;
}
}
return false;
}
It worked, so then I noticed that all that matters about number N is for there to exist an D <= N such that (N*D) is divisible by 100. If we use D=100, it will always be divisible by 100. So, we only need to try all Ds until 100. It solves even the ultra large cases. So, I modified my code and submitted the large version.
At the end of the match, I was very unpleasantly surprised to see the solution fail. I had already proven it so it made no sense. Then after some debugging using the practice inputs, I learned that I had made the most noobish mistake in the book. N can exceed 32 bits integers.
It led me to rethink many things. The error should have been very easy for me to find if I did something as simple as reading the output file before submitting it (All the results in that output were "possible"). I took some measures like making sure my upload script (see bellow) would show me the file before I decide to upload it.
Today I thought that I needed more protection. In retrospect this was a very silly mistake, because the overflow was in the input itself.
Template
If you were reading source codes from the contest, you will see that a lot of people solve the problem right away and the input/output part of the program is not separate from the program itself. In part this may be because it is much easier to code that way. The resulting code turns very small which gives it certain level of glamour when people new to contests read it.
On the other hand, I cannot stand doing it. I don't like having I/O mixed with program logic, so I split the two. The solver is usually a function the I/O part calls after doing all the reads. So I keep the skeleton of the code in a template.
init();
int TestCases;
cin>>TestCases;
for (int _i=1;_i<=TestCases;_i++)
{
/* read input goes here */
if( (mode==0) || ( (mode!=2)== (_i*2<=TestCases) ) )
{
cerr<<"["<<_i<<" / "<<TestCases<<"]"<<endl;
/* program call goes here */
cout<<solve()<<endl;
/* output result goes here */
cout<<"Case #"<<_i<<": ";
}
else if(mode!=2) break;
assert(cin);
}
One of the advantages is that keeping the algorithm in a separate function makes it slightly easier to replace the algorithm without modifying the I/O stuff. Then there is the other advantage and it is that my template is dual-core capable. That is where the if( (mode==0) || ( (mode!=2)== (_i*2<=TestCases) ) ) stuff comes from. When I need to use both cores (when the solution is slower than 8 minutes but not slower than 14 minutes). It is easy to split the
test cases in two using the template and then run both copies at the same time.
What I just did was add this line to my template after a test case is processed: assert(cin);. It actually detects the overflow when you have a lame mistake like the one I had during 1A. Using cin as a boolean is overloaded in a way that makes it return true if everything was ok when reading it so far or false otherwise. So, if at some point in the file you have cin>>x. x is a 32 bits integer and the x in the file is a large number 2729290020282, cin will consider it a mistake and the next time you do assert(cin) the program will fail.
1A - B - The Killer Word
It seemed easy to do B-small through just simulation, and in a way it was, but I had a failed submission. It took me a long time to notice the bug in my code. It was that when the guessed letter is wrong, all the words with that letter have to be ignored from then on. Then the other mistake was that when you guess 's' and get "s__s_s", you also need to ignore words like "sussus" because the s don't fully match the positions. It was a long time to debug B. But the scores were such that I was very confident I was going to qualify thanks to finally solving B-small. Of course, I didn't count on failing A-large...
To me it was clear that B-small was harder than A-small and A-large combined, so 10 points seemed small in comparison to A's total 20.
1A - B - (large)
I think my mistake was to stick with C-small even though I didn't have any actual idea about it, yet B-large seemed to have some important ideas behind. I was trying to find an algorithm that would calculate the wanted words for all the alphabets simultaneously. Whereas the solution was actually to do it for all the words simultaneously. It is a very clever solution. Even though the contest analysis is kind of vague, it eventually just works.
The idea is as follows:
* Solve B-small by simply repeating this for every alphabet:
** For every word, calculate the score the other player would get. To do it, just keep a list of all the dictionary words, and simulate the game, at every step remove all the words that do not match the resulting pattern. (Do not forget to remove words with letters that failed in your guesses, also consider removing words that are inconsistent with the pattern : For example, the "sussus" case I mentioned above.
* Pick the word with the best score.
To solve B-large. We do the process for all words at the same time. For example, if you started with words "xxxx" or "yyey", then the first pattern would be "_ _ _ _". This means that before the first turn, you cannot differentiate one of the words from the other.
As you proceed with the game, we will eventually ask if there is an e in the word. Then for xxxx, the pattern will not change and you will get a penalty, but for "yyey", the pattern will change to "_ _ e _". This means a bifurcation. Suddenly, the words do not belong to the same class anymore.
The same happens for example with "aaa", "bab", "dddd", "dddx". At first, there are two classes: "_ _ _" and "_ _ _ _". Let us say the alphabet begins with character "a". For class "_ _ _", it makes sense to ask for letter a. Then if the word was "aaa", the pattern will become "a a a", and you won, but else the pattern will become "_ a _". For class "_ _ _ _", there is no need to ask for "a", because none of the words that begin to that class contain a.
The advantage of this is that for every letter in the alphabet. You will need to process each word in the list exactly twice. Once, to verify if the word has the letter and another time to calculate its new pattern. In total the complexity become O(N * |L|). Which is great.
#define for_each(q,s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
using namespace std;
//=========================================================
// program:
//
int N, M;
string dictionary[10000];
string list[100];
string result[100];
map<string,int> dictpos;
//A group/class of words. All the words that match a given pattern. They
// all share the same score.
struct words {
int score;
string pattern;
vector<string> dic;
words( string p, int sc) {
score = sc;
dic.resize(0);
pattern = p;
}
words() {}
};
//Should we use letter ch as a guess for a certain pattern if it contains word?
bool shouldUse(char ch, const string& pattern, const string& word) {
for (int i=0; i<word.size(); i++) {
if ( (word[i] == ch) && (pattern[i] == '?') ) {
return true
}
}
return false;
}
map<pair<int, string>, int> patternIndex;
// Adds a word to an appropriate element of vec matching (pattern,score)
void addWordPattern( const string& pat, int score, const string& word, vector<words> & vec ) {
int x = 0;
pair<int,string> key = make_pair(score, pat);
if (patternIndex.find(key) == patternIndex.end() ) {
x = vec.size();
vec.push_back(words(pat, score));
patternIndex[key] = x;
} else {
x = patternIndex[key];
}
vec[x].dic.push_back( word );
}
// Updates the pattern after a guess ch when the word is "word".
string simulateStep(char ch, const string & word, string pattern)
{
for (int i = 0; i < word.size(); i++) {
if ( word[i] == ch ) {
//The guess was correct, update
pattern[i] = ch;
}
}
return pattern;
}
string solve(const string & L) {
//The patternIndex map just remembers the correct index for a given
// (pattern,score) pair.
// wordPartitions is a vector that holds all our word classes, we need
// patternIndex to know the correct positions in the vector. We only
// use two indexes of it at any time to save memory (probably not necessary).
// wordPartitions[i%2] holds the classes before L[i] is processed.
patternIndex.clear();
vector<words> wordPartitions[2];
//init
for (int i=0; i<N; i++) {
string pat( dictionary[i].length(), '?');
addWordPattern(pat, 0, dictionary[i], wordPartitions[0]);
}
for (int i=0; i<26; i++) {
int cur = i%2, nxt = (i+1)%2;
wordPartitions[nxt].resize(0);
patternIndex.clear();
for_each(q, wordPartitions[cur]) {
//should L[i] be used?
bool use = false;
for_each(s, q->dic ) {
use |= shouldUse(L[i], q->pattern, *s);
}
if ( use ) { //test it.
for_each(s, q->dic ) {
string newpattern = simulateStep(L[i], *s, q->pattern);
int score = q->score;
if (newpattern == q->pattern ) {
// The guess was not correct
score --;
}
addWordPattern(newpattern, score, *s, wordPartitions[nxt]);
}
} else {
// Do nothing
for_each(s, q->dic ) {
addWordPattern(q->pattern, q->score, *s, wordPartitions[nxt]);
}
}
}
}
//After all the letters in the alphabet are used,
//each class will match a word in the dictionary..
// Use the dictpos map to remember the position of the word in the dictionary
// (for tie breaking).
pair<int, int> best = make_pair(1,0);
for_each(q, wordPartitions[0]) {
best = std::min(best, make_pair(q->score, dictpos[q->pattern]) );
}
string res = dictionary[best.second];
return res;
}
void solve() {
dictpos.clear();
for (int i=0; i<N; i++) {
dictpos[ dictionary[i] ] = i;
}
for (int i=0; i<M; i++) {
result[i] = solve(list[i]);
}
}
Round 1B
So, all my plans trembled after the failure in 1A. I didn't have enough time to go through all of Round 1B. Only the first half of its scheduled time. I decided to try it anyway, because the 5:00 AM match involved plenty of risk. In theory, all that is necessary to advance is A-small, A-large and B-small, and I thought it was perfectly doable to do them in 75 minutes.
1B - Problem A
This problem was very easy actually. You just need to implement the formulas as they say. There is a catch in that naively implementing them will probably end up calculating the same value plenty of times. You can do memoization or something to avoid doing such calculations. But I think even without optimizations, it passes.
It surprisingly took me 18 minutes to implement. I am not sure how it happened. I did take around 4 minutes triple checking everything before doing A-large, I was not going to make the same mistake as round 1A.
1B - Problem B
This was harder. Even B-small seemed non-trivial at first. Anyway, I began noticing that although the result is a double, you will at most always need only multiples of 0.5. Multiplying every number by 2, calculating using only integer for target positions and finally dividing the cost by 2.0 solves the problem.
I came up with a dp that takes advantage that the total length of the street is not actually very long and there are only at most 100 vendors. For any meter x in the street, you can decide to place a vendor, or you may not. If you place a vendor, you have to skip to x+D because you cannot put any vendor between that space.
Calculating the total extra street size necessary required me to do some guesses. Like you need at most D*N meters to the left and to the right of the extreme initial points of the vendors.
I passed, and it was still 1:04, I was happy. Because that was all that I needed - A-small, A-large and B-large. Plus I knew A-large was correct. My prediction was correct, If I left the match at that moment, with only A-small/large and B-small I would have gotten position 794. But ... I made the mistake of actually reading C out of curiosity. It seemed very complicated at first, with geometry and a complex problem. Then I noticed that the constraints for C-small were very small.
* * * DARN * * *
The solution for C-small came to me : All I needed was a way to recognize the small closed polygons. And then a bruteforce algorithm to assign the colors so that each polygon has one of the colors and I find the combination that works best. With N=8 all of that was pretty possible.
For some reason, I thought that it should be possible to implement those things on time. Perhaps I would get delayed by a couple of minutes, but it was doable.
It was not. I ended up taking 30 minutes on it. So I was late to the launch by about 20 minutes. While coding I knew it was late and it forced me to rush which forced me to add new mistakes. Once I debugged my code and I was ready to submit, I thought to myself "ok, if this is not correct, we leave anyway" (I talk in first person plural when talking to myself). Fortunately, it passed.
The bright side was that with the addition of C-small to the equation I was VERY sure I would advance. So I was able to be calmer at the lunch.
How did I find the polygons in 1C?
It was easy. N<=8 gives you plenty of freedom. You can just do a bruteforce for all the subsets of corners. If there is a path that connects them with exactly T edges (such that T is the number of elements in the subset), they form a polygon. If the subset contains a smaller subset that is also a polygon, ignore it, because you are only interested in the rooms, which are minimal polygons.
I actually did it differently, I counted all the walls that connected vertices in the subset. They have to be EXACTLY T. And it works too.
The GCJ command line tool
The command line tool is probably the best improvement to the Google code jam experience since.. 2008? I implemented it and practiced with it a little before round 1. And it was a time after 1B that I noticed why it really is a good thing. It is not because of the time you save dealing with firefox, telling it where to save your input files and where to get your output files from.
The real advantage is that it makes you unable to upload the wrong source code or the wrong output. (As long as you don't mess the names of your files, I guess).
It does have some issues, like very large file names for its scripts. But it is just easy to make shortcuts. I made a single gcj.sh script which takes parameters like "init 24553" , "down A small 0" or "up B large 1" and does all the magic. I also adapted the source code of the tool so that it uses ANSI colors when telling me things like "Correct" or "Incorrect", makes life easier.
No comments :
Post a Comment