Now that SEP13 has come to an end, I guess I would like to share some thoughts about it and comment a bit about what I felt of the contest and also about some of the pre-requisites some problems had (I will also reply to an e-mail I received about this matter later today).
To begin with, my own performance was, again, really bad, as I only managed to solve 3 out of 10 problems (this time, I couldn’t even know enough to try a naive implementation for the challenge problem ).
The problems I managed to solve were, CAOS1, LEEXAMS and COOLGUYS.
Imho, this is, only by itself, bad on one hand, as 3 problems really is a very, very low mark and on other hand, frustrating because I left 2 problems with more AC submissions than LEEXAMS to do, and I couldn’t also do SPOONS, which was solved by many people as well (over 1000 AC submissions).
I’m not exactly sure what this means, but possibly (and this is what I’ve been suspecting all along) my background in Discrete Mathematics is not very strong and concepts like Combinatorics, Set manipulation, Pigeonhole principle, Probabilities are still all very “foggy concepts” to me, meaning that I know them and some theory behind them, but to identify them and work with them is a different story. I believe this to be valid for problems which usually don’t have any Pre-requisites, like CAOS2 and INTEG, where sometimes my mathematical thinking just seems to “get stuck” and I can’t usually deduce the ideas or insights which can lead to the necessary optimizations… On the other hand, I guess I have already understood the power of pre-computations and also the need to improve more on my logical thinking and less on coding concepts (at least, I think so).
With this being said, I shall write a small analysis about all the problems I solved and/or thought about during the contest, as hopefully, someone might have had similar experiences.
This was the Cakewalk problem and I simply used a brute force approach to solve it.
I used several while loops to calculate the values for all the CPC cells in a brute force manner, then realized the fact that P could be only 2 (as 2 is the smallest prime that exists) and coupling this with the cell being different than #, solved this problem to me.
This was the second problem I managed to solve and I have to say that I actually loved to solve this one
However, this proved to be a bit harder for me than I initially expected, mainly because I was having serious trouble initializing 2D C++ vectors (basically they are runtime resizeable arrays).
The main idea here was actually pretty easy for me to figure out as well!
Simply if N > 16 answer will always be 0, as there will always be repeated tickets!
Once we know this, we can simply to a brute force on smaller values of N.
The approach I took on this brute force was to use bitmasks to simulate all the possible combinations of the N tickets:
I use value 0 if I select ticket numbered Ai, which is selected with probability pi or I use value 1 if I select ticket numbered Bi.
It’s easy to see that for N tickets, the maximum number of configurations which we need to check is always lesser than or equal to 2N, so, I created vector with this dimensions and enumerated all possible arrangements.
I also maintained an auxiliary vector in which I stored the calculation of the probability of each one of the 2N arrangements.
Then it was clear for me that the answer would be the sum of the probabilities of the arrangements where there were no repeated elements, that is, there should be N distinct values on the arrangements that will be accounted in final answer.
For this I used a set and I summed the probabilities only when the size of this set was equal to N.
This approach was giving me TLE, but, after doing a pre-initialization of all vectors, it managed to pass the time limit and I got AC (Once again, power of pre-computation!)
This was the next problem I approached that I managed to solve, which involved some Number Theory (a subject which is not my strongest point, AT ALL).
I actually liked the concept of this problem and more specially, I was in awe with the Time Limit:
However, as I do on all problems, I decided to write some small examples on paper, to get the feel for what the problem was all about and I wrote 2 independent tables for N = 5 and N = 6.
After writing them (I wrote pairs on the form (A,B), with A varying in line and B varying in column) I circled all the relevant pairs (which were the pairs where A <= B and B%A=0, on other words, B must be a multiple of A) and understood two different things with two different analysis:
Looking at this in line, I arrived at the first, very slow solution of summing N/i with i going from 1 to N. Obviously, with N being equal to 109, this would time out even with all possible optimizations and it was with no surprise I got several TLE veredicts… (I thought about precomputing primes to factorize numbers in some way, but rapidly discarded this idea was it would be extremely slow with Sieve of Erathostenes and I couldn’t implement nor be sure about Sieve of Atkin’s performance boost…)
However, looking at this column-wise was a bit more encouraging… I could actually see clearly the divisors of each number circled in front of my eyes! And I knew an algorithm which ran in O(sqrt(N)) time to compute all divisors of N!!
Sadly, after using this “approach”, I got an horrible complexity of O(Nsqrt(N)) for solution, which was much worst than the previous O(N) algorithm which was already timing out…
It seemed like this problem would remain unsolved for me… But, motivated with a comment about the overall complexity being sqrt(N), I decided to do some research work and stumbled upon a very interesting paper, which presented the insight described in the editorial, which was the intended solution!
I was happy about my realization of the O(sqrt(N)) algorithm for divisors, leading me in the right search direction and I was at the same time a bit sad that I couldnt come up with such deduction on my own, but, nontheless, I still learned a lot from this problem!!
This was possibly the most frustrating problem for me, as I tried A LOT of approaches here, but all of them got TLE…
I only had the realizations that we needed only to apply operations to negative numbers (this was trivial) and also that we should use operation 1 while number of negative elements is greater than X and then we should use operation 2…
These were the only ideas I had that were valuable enough to be coded (I thought about sorting, but I couldn’t honestly see how it would help me on this, except probably about counting the number of elements which turned positive after say K applications of operation 1), but as this was giving me either WA or TLE, I actually got demotivated and eventually gave up on this problem…
Same goes for CAOS2, as I only had 2 ideas which I coded and a 3rd one which I didn’t even implemented…
I began by having a table of primes up to 500 pre-computed in my code, as I thought this would help with speed-up an eventual prime search…
Then I used STL’s lower_bound to find the number of primes in O(log2 N), but this was getting TLE…
I then understood later that the problem must lay in the calculation of my CPC cells values, for which I had the idea of somehow store the locations of ^ and use their positions to calculate values of L,R,T,B with only subtractions and not exhaustive searches (as I did for CAOS1), but, as I would also need to iterate over the table where these locations were stored, I thought that maybe this wouldn’t be such good idea after all and also gave up on it…
This was the last problem I looked at, only because it had many submissions and a friend of mine had got AC on it, but, maybe I couldnt understand statement very well and did nothing special about it besides converting N to base 2 and outputing the length of the binary string only as a stupid long shot (or not so stupid as I’ve seen values 64 appearing in comments several times, maybe it came to my mind it was a power of 2), and I obviously got WA and gave up on it… again…
These were the only problems I actually struggled about during contest time… Besides these ones I also understood that using Suffix Arrays was the way to go on TMP01, but obviously doing naive algorithm welcomed be with a shower of SIGBARTS, possibly due to memory restrictions and I also gave up on it as I understood it should be a very hard problem afterwards…
I only read other problems and I guess I didnt even opened some of them (like TWOROADS) for not having the time to even read them…
So, as you can see, I actually struggled pretty hard… and again failed
I hope someone else can share their thoughts as well and, as usual, provide some tips