March 2013 contest feedback

I had a very strange bug with factorial computation which I did not manage to identify. At first, I just did naive calculation with break condition if answer became zero. The code was timing out and I finally found out this was due to factorial function (forcing RTE inside). This is the code (without taking the absolute value and sign of x, etc.):

  int ret = 1;

for(int i = 1; i <= x && ret != 0; i++) {
ret *= i;
if (i > 50) throw 13;
}

For the full code, see fact function at for example http://www.codechef.com/viewsolution/1891077

Can anyone explain why this happened at all?

As for ZENCALC, I believe without tricky division it would have been uninteresting. Can’t say exactly the same about negating -2^31, but it was a funny bug to make and fix.

@gojira: that was I was afraid of - that factorial for some numbers won’t have short circle… In other words I’m afraid that if I’ll calculate 35! as described in statement it won’t be 0, but I have to test it first…

@betlista if n! = 0 for some n than for all larger n it is also 0.

@gojira I have no ideas why we reach throw here.

@anton_lunyov: mathematically it’s clear to me, but with residue thing I was afraid that it will be “randomly jumping” in [-2^31, 2^31) interval without cycle, but yes I didn’t try to implement it - very similar mistake as in RDF problem - I spent 4 days optimizing the formula

RDF(n,k) = 1/n * RDF(n-1, k) + 1/n * RDF(n-1, k-1)

because I knew it would be too much memory to remember all the values (for n and k up to 10^5)…

@gojira: see this http://ideone.com/5ovykD , maybe some C++ guy will describe it clearly…

@betlista: you probably didn’t realize why if (n!)=0 then all larger factorials are also zero. Since (n+1)!=n!*(n+1), once n! becomes zero you have all further factorials equal to 0 multiplied by something, which is mathematically zero and its 32-bit residue is also obviously zero.

@betlista: the link leads to 404 for me.

@gojira my bad, markdown added ‘,’ to URL, it’s fixed

@betlista I didn’t notice that, sorry. That’s really interesting, probably a yet another compiler bug. My Visual Studio does not make the same bug.

I’m sorry to hear that I now exactly how you feel, especially with RDF problem. Just two hint before editorials come up. Values for K+1 are lower than those for K, so according to allowed error you can print 0 for some Ks… In fact connected components problem is very similar (in implementation) to minimal spanning tree problem (my favorite graph problem, probably because I used it once to solve TC hard problem in division 2).

Betlista, thank you for your comment! And YES, I thought about that too since RDF(N,N) = 0… Still I got lost pretty fast and was, as I said, a very humbling contest… I hope I can really take some valuable insights and actually learn new things with the upcoming editorials :wink:

As for the FIRESC problem, that was based on disjoint set data structure. And I was unaware of that during the contest, but without much knowledge of graph implementation was able to get AC using hashing and stacking. There’s always a best way to approach a problem, but then there are other ways too. :wink:

2 Likes

So, your tester is part of your submitted code…

I solved it similarly, but I defined interface in java and set implementation in my testing only.

I had problems with flushing I guess, so I left C++ and moved to Java. I’m wondering how to write two programs that one writes to others stdin…

Not needed actually, at least for this problem. You can virtually get input from a function as if you were getting from another program!

I solved FIRESC thanks to one of the past contests problems. My point is if you keep practicing you will eventually know a lot of helpful algorithms and will gain experience.

I learned a lot here in codechef and I’m glad to say that I grew up a lot here, looking back I can see how much I have improved, in this contest I could solve 5 problems and believe it or not in the first contest I participated I couldn’t solve even 1. I know there is a long way to go but what would be the fun of achieving something without any effort, right ?

My only advice is keep practicing, never give up.

1 Like

I really don’t know what you have against me, but FYI I thought it was one of the best Codechef problems I’ve seen.

Thank you very much @Bugkiller, I will definitely look into these videos when I have more time to spare :smiley:

Altough atm univ is a bit more important and different things are required there…

I have nothing against you. But all my previous tries to add some tricky corner case to the problem met a strong critic from you.

@gojira: Could it be that, on the systems where your code was run, an int was larger than 32 bits ? (e.g. they had 64 bit ints) This could explain why your code reached i above 50 (as the result did not become 0 at i=34). I know this seems unlikely, but maybe it’s possible. I tried to test this behavior by submitting a simple code at several practice problems, but sizeof(int) was always 4 – but maybe there’s a different set of machines used during contests ?