It feels like the contest system at UVA is not aging graciously. The absence of AJAX can really be felt at times. It is also frequent to see low participation in these contests even though the problems are usually good and there is always something solvable.
Problem G: February 29
This is the first problem I felt like solving. It is really mostly an implementation conondrum. I would suggest ignoring the amount of days of each month for the most part and just considering whether a given date is before, after or equal to February 29. Once you have that, also calculate then umber of leap years less than a given year. Combining these things with ad hoc magic, you get a quite simple solution:
map<string,int> monthid;
int fix(int m, int d)
{
//before, after, or equal to february 29?
if (m < 1) {
return 0;
}
if (m == 1 && d < 29) {
return 0;
}
if (m == 1) {
return 1;
}
return 2;
}
// how many leap years in years x : (0 <= x < year) ?
int before(int year)
{
// x: number of multiples of 4
int x = (year-1) / 4;
// y : number of multiples of 100
int y = (year-1) / 100;
// z : number of multiples of 400
int z = (year-1) / 400;
return x - y + z;
}
int solve(string s1, int d1, int y1, string s2, int d2, int y2)
{
int m1 = monthid[s1];
int m2 = monthid[s2];
int x1 = fix(m1,d1);
int x2 = fix(m2,d2);
if (x1 > 1) {
y1++;
}
y2 ++;
if (x2 < 1) {
y2 --;
}
if (y1 >= y2) {
return 0;
}
//cout<<"["<<x1<<" ; "<<x2<<endl;
//cout << "{"<<y2<<":"<<before(y2)<<" ;; "<<y1<<":"<<before(y1)<<endl;
return before(y2) - before(y1);
}
void init()
{
const char* s[12] = {"January", "February", "March", "April", "May",
"June", "July", "August", "September", "October", "November",
"December"};
for (int i=0; i<12; i++) {
monthid[s[i]] = i;
}
}
Problem J: Forwarding emails
It sometimes feels like the easiest problem in ACM contests is J. Why? I don't know. But it looked like a lot of people were solving this problem, so I opened it.
Every martian has exactly one martian to forward the email. Note that there are always cycles in the input. The solution is to first find all the cycles, for each martian that belongs to a cycle, save the amount of martians that are in the cycle. Once you do that, you can do the following dp-friendly recursive relation on the remaining martians. The maximum number of martians you can meet by emailing martian x is:
- Cycle size[x] if he belongs to a cycle.
- Or 1 + solution( sends[x] ) in the other case. (sends[x] is the martian x sends an email to.
Problem C and D: I plan to explain these later in big posts because they are interesting.
An issue I tend to have in contests hosted at UVA is that sometimes I have no idea what the problem expects me to do. For problem C, I spent a lot of time wondering if the intended solution is O(n*n), O(n*n*log(n)) or o(n*n). The humongous number of submissions I made to this problem was actually to reverse engineer the sizes of test cases so I can estimate whether some solutions were faster or not than others. Part of my issues here is that I am apparently unable to use hash_set and unable to implement a fast enough hash table that is actually faster than the n*n*log(n) solution I came up with first.
One hour before the end of the (official) match, I had to go for lunch. I came back two hours after it ended, but continued trying to solve C. I finally did it with a very hackish solution that is sort of n*n*log(n) but does a very dirty trick, more details later.
Problem D is cool because it exploits two cliches (Interval trees and calculating sums of arithmetic series in O(1)) into a problem that is actually interesting.
Problem E
Opened this during the match as it seemed popular. I am still not sure about what is a valid path here. Tried asking for clarifications, but I would say that no one actually reads those emails. This was the last problem I tried seriously, but I started to try to solve it around this morning and ended up without time to finish debugging.
0 comments:
Post a Comment