March 2013 contest feedback

Hm, it seems it was quite difficult, but I achieved my goal on CodeChef - to solve all the problem that solved more than 99 contestants, and there are only 5 such problems…

I’m wating for editorials, because I have no idea f.e. how to calculate factorial (quickly) for Peaceful Calculator, also I know that to calculate graph diameter we need perform Dijkstra 2 times, but how to do that for Q (up to 10^5) queries?

Yes, and I like mines problem a lot. I had some problems to get accepted for C (http://www.codechef.com/MARCH13/status/MINESWPR,betlista ), but I had no problem with Java. I’m interested also in tips how did you test it…

And what about you?

8 Likes

34! and all further factorials are 0 modulo 2^32.

Also x = -2^31 is really evil number:
-x = x when computed in 32-bit signed integer type.
So many contestants were trapped by the following bug in the factorial calculation

int fact32(int a) {
    if(abs(a) > 100) return 0; // BUG HERE!!!
    // else do naive calculation
}

I expect many negative feedback about this (especially from @triplem :))

But I see now that we should left ZENCALC as it is without tricky division, factorials and exponentiation. Somehow we agreed with the problem-setter that simple modeling of evaluation process will make the problem SIMPLE :slight_smile:
Sorry about that.

But I am fine with the level of difficulty of other problems.
I don’t know know why we have so small AC-rate for SUBTREE and LECOINS.
It should be higher.

BTW. Dijkstra is an overkill in diameter problem. You just need two DFS-s.
And if you have LCA in hand, you can find distance between any two vertexes in O(log N) time.
So you can find diameter of the SUBTREE in two simple loops in O(K * log N) time.
Calculation of minimum common edge is a bit trickier but is not too far from finding the diameter.

4 Likes

Well,

As for me, this contest was actually one of the worst contests in terms of being able to do something about the problems…

I solved both APPROX and TOTR in the 1st day of the contest…

Then, I started thinking on FIRESC as it was the 3rd problem which had the most submissions:

I knew that it had to do with Graphs algorithms which is a topic where I still need to improve very much. In fact, the only graphs algorithms I know WELL (as in understand them fully and being able to implement it), are Shortest Path algorithm and very recently Floyd-Warshall to compute all-pairs shortest path ( I learnt this one by solving HOMEDEL after reading editorial, during MARCH13, in order to see if something came up to my mind, but no luck :frowning: ).

I searched trough the web about graphs algorithms read A LOT of PDF’s on a topic called “Connected Components” and its relationship with DFS, even found some algorithms on Sedgewick about a data structure called Union-Find, but I got lost in all the theory…

Result: I couldn’t implement anything about all that I’ve read and only got more demotivated afterwards…

After that (about 2/3 days on it) I decided to read about RDF, because it involved Expected Values, and there were several reasons for me to do so:

  1. I knew it involved DP which is a topic I also need to improve a lot;

  2. I could actually do something about this problem, compute some values by hand and try to find a pattern;

However, things also went really bad here:

I managed to deduce closed formulas for RDF(N,2) and RDF(N,3), but then failed to find a recurrence relationship between them…

Then, a few days before contest ended, I attempted once again, but this time I used the definition of Expected Value…

I managed to get some relationships for K=1 and 2, but once again got stuck on it and finally gave up…

So, as for me, this contest showed me that I still need A LOT of work to get the feel about some of the Discrete Maths used on these contests and also maybe I need to make better use from the editorials…

Other than that, all I have to say is that all problems were very well written and I enjoyed solving the ones I could :slight_smile:

Looking forward to enlightment and tips from editorials,

Bruno Oliveira

PS: If anyone has any advices or tips, feel free to share them here :slight_smile:

4 Likes

To betlista

Mines problem is really interesting. What is more interesting is “How to test it!”

Let me explain the way i used to test my program. And i am surprised my local tester generated almost the same score as the judge for most of my submissions

Generate own mines field

Choose n randomly between 30 and 50

choose p randomly between 0 and 2 inclusive

declare an array map[][], which holds the complete data about mine field.

loop over whole array and for each cell choose a random number between 0 and 9 inclusive

If this number is less than p, place a mine, else dont!

Once placing mines is done. Calculate the number of mines. This is m. Then calculate k as per generation rules mentioned.

For all elements in map[][] which dose not contain a mine, count the number of mines adjacent and store them in map[][] itself. So map[][] contains ‘M’ or a value between 0 and 8

So we are done with test data generation.

How to query?

when ever you want information about a cell. The tester returns map[][] value. I.e, ‘M’ if a mine is there or the count. Note that tester is just a function with in the program!

Neutralize

say you want to neutralize map[i][j].

Then if map[i][j] do not contain mine, do nothing.

If it contains a mine. reduce mine count of all adjacent cells by 1. Then count number of mines adjacent to current cell and update map[i][j].

Check if my program is working correct!

We have counters for neutralize calls and query calls. We check that these are less than k and n*n respectively. Also check that map[][] is not left with any mines at last.

Done :slight_smile:

This way when i run program locally , I loop over 100 times. Each time generate a map and solve it. Finally display the score. It worked perfect! score difference between online judge and my local score is less than 0.2.

Implementation - Here

Functions related to testing - generate(), localget(), localnut(), check(), main(), get(), nut()

Rest are logical functions.

P.S: Every time the data is generated randomly so how can you check which of two methods to solve is better? For this purpose i generated 100 testcases and stored to a file. I read from file and test for efficiency of score.

P.S: My program depends on 2 flags, SUBMIT, If its 0 it works in local mode. FROMFILE, 1 To get test data from file, else generate random data

2 Likes

@kuruma >> If I am allowed to give a suggestion, although I know that you are learning graph algorithms in your course, but I would like to tell that if you want to learn graph algorithms from other efficient source, do check the NPTEL videos by IIT Delhi, by Prof. Naveen Garg. He explains really well, and he formats the proofs so well that it seems like daily conversation. Just go through some video lectures, and you will never find graph algorithms tough. For example, http://youtu.be/CIm6RzdoPCI teaches you DFS! Very interesting and valuable. Good Luck!

1 Like

My opinion is that the March 2013 contest was harder than the usual Codechef long contests. It seems that there were more HARD problems than in other such contests (I was expecting 1 or 2 HARD problems, and instead we got 3 HARD problems, with 2 tricky MEDIUM problems - ZENCALC and SUBTREE : although SUBTREE may also be considered borderline HARD, I guess). This made the contest more stressful than usual for me :slight_smile: (because I wanted to solve all the problems) and also left me with less time than usual to focus on the CHALLENGE problem (which is one of the things I like best in these contests).

Anyway, on the other hand, I am also nicely impressed with the difficulty of the problems. It is not easy to come up with HARD problems which are tough to crack in a 10-day interval (many problems in other contests are HARD also because the length of the contest is shorter, but HARD problems in a 10-day contest need to be harder than hard problems in short contests).

Still, if I had to choose, I would prefer slightly easier contests in the months to come :slight_smile:

4 Likes

“March 2013 contest” doesn’t seem to be the right subject line for your question :wink:

I not sure if I made it better, but I changed it to “March 2013 contest feedback” :wink:

1 Like

Heh,

34! and all further factorials are 0 modulo 2^32.

and I couldn’t see it? Probably I’m blind :smiley:

1 Like

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).