March 2013 contest feedback

@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 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

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.

2 Likes

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

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 ?

I really don’t want to derail another thread, so this will be only my only further reply on the topic, but I have never and will never critique anyone for deliberately adding tricky corner cases. That’s what programming contests are all about. The previous issues were unrelated: a) solutions/editorials which tell you to solve the problem, you must use unsigned variables, which rules out languages like Java entirely, and b) when the problem author did not expect or handle all corner cases properly, which you admitted yourself for ANDOOR. Had they been intended, I would have had no problems

I should mention that I am not the author of ANDOOR.
I would think 1000 times before posting such problem.
Because of many issues with other problems I had no time to consider it properly, hence such crap

So I am not the only one with such feelings. :D. Except that I took almost 6 approaches and 6-7 days to solve the FIRESC after approx and TOTR which were tip of the iceberg…
I never thought of any algorithm to solve FIRESC but feeling ashamed now that It was something I learnt in second year of Engineering…

1 Like

Dude, a topper at Codechef is expecting easier problems. Not expected! Just kidding bro, all the best.

1 Like