Some thoughts about SEP13 and my frustration

[kuruma]

Hello @all,

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.

• CAOS1

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.

• LEEXAMS

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 A_i, which is selected with probability p_i or I use value 1 if I select ticket numbered B_i.

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 2^N, 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 2^N 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!)

• COOLGUYS

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:

3 seconds!!!

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:

1. 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 10⁹, 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…)

2. 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!!

• INTEG

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…

• CAOS2

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(log₂ 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…

• SPOONS

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

Best regards,

Bruno

[tyrant]

For me the best way to handle these “unknown” problems (without having any existing knowledge) is try to solve it by hand as many cases as possible. This method is very frustrated at time, but you will learn most out of it whether you solve it or not. Why?

• If you eventually solve it, you will feel extremely rewarded which is good!
• If you fail, you will remember it by heart after reading its editorial because the amount of time you spending drawing out those examples does count.
• Additionally, while struggling on formalizing these examples, you’re in fact practicing your thinking process. And guess what, the more you try to hold in your head, the better you will get latter.

Once you have enough examples in front of you, try to formalize them into an “ok” solution, then improve its running time by apply the best algorithm that you already knew. However, this step is no longer easy and you rarely can’t solve it by the brute-force method I mentioned above. Now your job is to do research to find the correct algorithm via:

• Google
• Research Paper
• Books
• Similar problems from previous contests (from Codechef, TopCoder, Codeforces…)

And if none of these works (very likely unfortunately), then at least you should be proud of yourself that you have tried your best. Or one more method that I often use to overcome these frustration is to solve other practice problems to boost my confidence & motivation back.

Last but not least, it’s time to solve those problems again with unlimited time + resource.

[tusharmakkar08]

Solving by hand method works best in most of the cases

[dtb]

Only thing I did not like was 6 problems with >1000 solvers and next one has <200 with nothing in between. Problem setters should realize that problems based on ‘knowledge’ ( like COOLGUYS, SPOONS) will be eventually solved by many (thanks to google) regardless of the difficulty (which is perfectly acceptable). So we have 6 adhoc problems followed by lazy propagating segment trees - surely many simpler but constructive problems could be added in between, no ?

[arnabbcs08]

Dont worry dude. I will give you my stats for the the past 4 months.

1. 1st month - 2 problems. That too struggled.
2. 2nd month - 4 problems. Struggled less.
3. 3rd month - 5 problems. Was just lazy to think that I had to code a O(n lg n) suffix array so left the 6th although I had an algo in mind.
4. 4th month(this month) - 7 problems. Though this time I was at my limit. The hard problems were really beyond my reach.
   So I can tell you the climb till solving medium level problems will be fast. You will have early success. And in 3 months you will be also able to do 7 problems. Now I have reduced it to a problem of solving the hard problems in Codechef. To which I have no answer.

[kudkudak]

I just have one comment about SEP13: there are tons of problems with long longs, not sure why. My SPOON solution was correct, but didn’t get accepted, after I have looked through accepted solution all they differ from mine was really strange I/O. Any suggestions was could I have done wrong? In case anyone feels like helping me http://www.codechef.com/viewsolution/2675885 It is basically the same thing like in the editorial.

[sobhagya]

@kudkudak Your array seems to be wrong. That’s why your solution not get accepted. And, it have nothing to do with strange I/O.

[sobhagya]

@all

First, about the contest, the most interesting contest i ever participated on codechef, the easy problems are really simple and not frustraing like in previous contests, unless you are looking in wrong direction which is proven by more than 1000 correct submissions for the 6 easy problem. The Medium section problem is really medium and it requires some thinking(deep thinking in my case) and knowledge base, which is also proven by less than 200 submissions for the MLCHEF problem. And, hard section problems are really tough only the topcoders are able to solve the problem. And last, the chalenge problem which i think is also a little bit on tougher side if compared with previous contests.

Positives: Different from the previous ones. More people able to solve the easy section problems. And hats off to the question setters for setting these intersting problems.

Negatives: Challenge problem is bit tough and gathers less attention. A big gap between hard, medium and easy problems.

@kuruma I know, its frustrating for you but don’t worry, follow @tyrant instructions. And, i always says solve more and more practice problems. That will help you gain confident and knowledge.

[kuruma]

Thanks @all for your answers!!

I guess that what @tyrant said is actually the best way to go, but, unfortunately, it’s still quite hard for me to do so as I am always busy with university and I can’t actually settle myself and sit down and carefully work throughout editorials and by writing my own solutions to unsolved problems… I might be able to do it like 1-2 months per year, if not less…

So, it’s up to me to use my time in the best possible way I guess!

Once again thank you all,

Bruno

[bugkiller]

@kuruma >> Bro, I understand your feelings but you know what, the longer you keep this inside that You have some kinda fear for Maths, the longer are you gonna be in trouble Trust me! Challenge it, practice harder, and harder!

Solve problems on PE and Mathalon and just tear your fear apart. Study concepts from books/turorials, from anywhere you find. But just thrash 'em all.

You can improve and boost your naive coding abilities greatly with Codeforces contests in addition to Codechef cook-offs. They are short and require fast thinking and coding.

More, later

[kuruma]

Thanks for your answer @bugkiller
And it’s not fear now (it was before ), now it’s just frustration for lacking some background… But over time and with training, I will get better
(I loved round 200 of Codeforces )

[junior94]

Exactly @bugkiller, instead of focusing on how bad your math backgrounds are you should focus on improving those weaknesses… Find ways around it, for example, whenever I see one of those problems I brute force their first values and try to see some kind of relation between them (this works surprisingly well when you can organize the data you’re studying)…

@kuruma dude I’m not a math genius either but you focus too much on that, as long as you keep fearing it and using it as an excuse you won’t be able to improve much… Everybody has a weakness, even the strong competitors as I could see this month but they won’t give them away and believe me they work really, really hard because they know hard work pays off.

Another advice, unless you’re worried about something in the problem statement don’t go to the comment section. Those comments can get to you, like a comment like this: “Easy one”. Then you’ll start to think of easy approaches to the problem and miss the big picture. Once again you’re focusing too much on how weak you think your math is. I for one know some of my weaknesses but I also know that I want to beat the crap out of those top coders… I’ll keep practicing until I can top their points. In this contest I realized I was seriously underestimating the amount of work those guys get into in order to get maximum scores and was being very lazy myself.

Once again find ways around your problems, programming is a beautiful thing, there are so many ways of solving so many things.

[kuruma]

It’s not using it as an excuse, it’s just the truth… I mean, at least, I’ve never heard about Sperner’s Theorem before this contest… So, if I’ve never heard about it, for as much as I tried to find a formula and keep wearing myself out with it, if I knew the theorem I’d have solved it immediately and that’s why the problem was an easy one… But as usual, I plan on improving on this and I also solved 5 problems once myself, so I know it’s possible

[tyrant]

I myself just graduated about 3 months ago, so I totally understand your point. However, here is the approach that I took while in school. Are you having fun while doing these contests? If the answer is “YES”, you definitely can find “the best algorithm” to beat the time problem Best of luck!

[tijoforyou]

@kuruma I had also never heard about Sperner’s Theorem before. I tried to find a solution (working by hand) for some small values of n. Then, i tried to find a reasoning that the idea indeed works, and then i tried the code, only to see AC. Only after the contest did I find out that this thing even had a theorem named after it. I thought this was another question, where you need your observation skills to come up with the answer.

[sobhagya]

Totally agree with @tijoforyou i had also never heard about Sperner’s Theorem before. Even, i also first time sovled segment tree problem with lazy propogation. Even, many things i don’t know or done before. But, never let them be my excuse. Stop, trying to be the perfectionist and solve the problems from what you have at that moment.