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;

intfix(intm,intd){

//before,after,orequaltofebruary29?

if(m<1){

return0;

}

if(m==1&&d<29){

return0;

}

if(m==1){

return1;

}

return2;}

//howmanyleapyearsinyearsx:(0<=x<year)?intbefore(intyear){

//x:numberofmultiplesof4

intx=(year-1)/4;

//y:numberofmultiplesof100

inty=(year-1)/100;

//z:numberofmultiplesof400

intz=(year-1)/400;

returnx-y+z;

}

intsolve(strings1,intd1,inty1,strings2,intd2,inty2){

intm1=monthid[s1];

intm2=monthid[s2];

intx1=fix(m1,d1);

intx2=fix(m2,d2);

if(x1>1){

y1++;

}

y2++;

if(x2<1){

y2--;

}

if(y1>=y2){

return0;

}

//cout<<"["<<x1<<";"<<x2<<endl;

//cout<<"{"<<y2<<":"<<before(y2)<<";;"<<y1<<":"<<before(y1)<<endl;

returnbefore(y2)-before(y1);

}

voidinit(){

constchar*s[12]={"January","February","March","April","May",

"June","July","August","September","October","November",

"December"};

for(inti=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.

## 1 comment :

sample code for the remaining problems?

Post a Comment