BLeh , why did they have to make today's warmup the 14:00 GMT one instead of last one? I had an exam during the warmup and it seems I didn't have time to solve or even open the interesting parts of the problem set.
The exam
So, at 10:00 AM GMT-4 (exactly the same time as the warm up's start time) I was supposed to solve an exam. This was so lame.
10:40 : Exam begins, professor didn't arrived at 10:30 even though the exam's schedule was 10:00 AM - 12:00 PM...
Lame, only two questions , the first one was very easy using predicate transformer semantics (zero loops, conditional statements or anything.
Second question: Even lamer. So we have to use Hoare-Floyd logic to verify a program which has ... no post-condition. Well I got used to this during the course since it seems that verifying a program also includes making the post-condition up. Anyway... the algorithm was simple, just product using successive sums. The difficulty was that it had a do...while loop, and during the course we were only introduced to while loops. But the professor was kind enough to include the do...while loop's rule ... but THE RULE WAS WRONG. It is just the first time I get into Hoare-Floyd logic, but even I know there is no way in hell that B could be part of the post-condition of (do C while B) since we need B to be false to end the loop... So, I just figured out the correct rule by myself, included an explanation why the given rule was wrong, and a sort of proof that mine works based on the fact that do..while can be converted to a while loop by copying the loop's contents to the section before the loop...
So either I got a good 100% or 50% if somehow we were supposed to use the wrong rule to prove it or 0% knowing my luck.
11:00 : I am finished. I should probably go back home to actually try the warmup II contest... But I don't know if I should go or wait for the official end time... Always confusing.
11:40 : Ok, some people are just giving him their tests and leaving. I better do as well.
12:20 : I am at home and ready to open the problems...
Problem D
So, I look at statistics and problem D is by far the one with the most solutions. Turns out it was excessively easy. I actually double checked the statement just in case there wasn't a cheap difficulty device like having to use bignums or something. Turns out there wasn't. I just solved it. I wonder how would people manage not to have at least 1 problem in this warmup...
Problem J
Apparently the second easiest problem, I first thought that it was another easy one since I thought that if light a can trigger light b the converse is true as well. But then I noticed that it probably isn't the case. I asked for clarification to be sure. But the response to the question never came to my inbox...
So, after inspecting the examples, I finally figured out that the graph is directed, this makes things a little harder. I quickly noticed that all nodes belonging to a cycle could be treated as the same node. So we can do a SCC algorithm and then treat the transformed DAG graph for a solution. Once we can assume the graph is a DAG, things are easy. Just notice that you will have to manually turn a light on if and only if there are no lights that can trigger it. This can be read as "count all the nodes in the DAG that have in-degree equal to 0".
Coding the solution was hard since I noticed I never actually implemented a SCC algorithm before. I had just blurry memories of CLRS' lesson about it, so I went to wikipedia. It recommended tarjan's algorithm and also included pseudo-code for it. I took some time convincing myself that the pseudo-code is actually correct.
1:00 PM : The time I finished coding the problem coincided with lunch time. So I submitted it and checked the result... WA!
Lunch
I spent the whole lunch hour wondering if maybe the algorithm I conceived was wrong or not. I ended up quite convinced that it should work.
Back to problem J - Today's blunder
14:00 PM (ish)- I had no choice but to inspect my solution. I created some test cases and noticed that it was failing many of the new ones. After a lot of manual debugging I finally noticed my mistake... I had something like:
for (int i=0; i<T; i++) {
cin >> N;
for (int j=0; j<N; j++) {
adj[i].clear();
...
}
It was supposed to be adj[j].clear() ... So, some ghost edges could remain and ruin everything... I just fixed this issue and got AC.
Problem B
14:40-ish . The next easiest problem was B. I quickly noticed it was just a dp/memoization one. So, I made a recurrence, but it allowed some cycles, so you had to solve the equation inside the recurrence to avoid the cycles (so that dp/memo worked). There is also the other problem of having to get a) the prime divisors of a number and b) The number of primes between 1 and a number. These both are easy using a sieve, I modified Eratosthenes' one so that it would store a number's lowest prime divisor in its array. If no prime divisor was found for a number use this number as the minimum divisor for the multiples that don't have such number yet.
I was having problems at first with the example cases. it turns out my recurrence was wrong. At the end I finally figured out:
f(x) = ( 1 + sum( f(y) for each y such that y is prime and x divides y) ) / ( (number of good y primes ) / (number of primes between 1 and x) )
I actually finished this problem very close to the end of the contest.
Final result: 77-th place . Hmnn, I never do well in world finals warmups...
Conclusion
I think that maybe if it wasn't for the time wasted in problem J due to not knowing enough about SCC and the lame mistake I could have solved another problem or at least have more fun from the contest. I need to practice AND study more theory.
Final thoughts
Why do blogs use HTML? instead of something like BBCode or whatever wikipedia uses? Since they have to be paranoid about XSS attacks, they don't let you use many tags and it can get confused by things like C++ code in which > and < are used... With bbcode, we wouldn't have so many problems...
No comments :
Post a Comment