OJ Board

Since there is a lot of discussion about the problemset I feel saying some word myself.

First of all the Problemsetters made the problems deliberately easy so as to prevent the fate of ICPC2004. Only seven teams solved at least two and teams upto 65 solved one. Clearly, this seems to indicate that the Skill level of BUET Sphinx is same as that of some team solving 50 to 100 in OJ. But in reality there is certainly a huge gap between them. The main reason for this there was a problem of skill level 2 and then a jump to level 6. Therefore in NCPC the problemsetters tried to provide a set that is well distributed.

In my opinion they actually have done a good job, since the number of solved of each problem decreased at a steady rate.

As for the problems, I would like to give my views as a contestant:

Problem A: Very good introductory problem, no he hos, solve it and submit it.

Problem B: Well, i think this is the only odd one out. I must agree such one line code problem should not come in NCPC/ICPC contests. However, the answer was not directly visible so it required some analysis. The better and the experienced like Nasa, solved it on the spot, while less abled like me took longer and novices couldn't derive the formula.

Problem C: Another quality one from K. Zaman. Very easy to understand, requires some intuition to derive the solution and filled with traps which can be uncovered by the experienced.

Problem D: Easy geometry/trigonometry problem. In the contest, our team was the first to solve this and I think we used the most efficient method also. Many people used Binary_Search and others derived long and erroneous formula requiring 20+ lines of code. If one chooses to take the harder way, you are bound to be stuck and waste time.

Problem E: Trivial graph problem.

Problem F: If you find the right track this problem is very easy. A trivial minimum value( Calculas) problem. I think more teams could have solved it, but most probably they were interested in solving one of the harder ones, and did not have enough time after wasting precious time on solving easy problems like C and D.

Problem G: Very interesting problem, but haven't solved it yet.

Problem H: As mentioned earlier, a very painful to code problem.

Problem I: Haven't read it yet.

Problem J: This was the deceiver, on first reading many must have thought that this is a trivial BFS/DFS problem. But the difficulty level was realized only after reading posts regarding the problem.

As for the final words, it is true that problems B,D,F requires only knowledge of Math, but Math isn't much seperated from CS. The contests are regarding solving problems and Mathematics is the language while Computers are only tools. It is true that if problems B and F were replaced by some Graph/DP problem, there would be some change in Ranklist, but if one is totally unable to solve a problem while others can, then they don't have much right to complain.

aha just solved G - (A Different Task)...

little bit of study on the tower of hanoi problem made life a lot easier but really its a verrrry nice problem...

so now all 11 problems solved and nothing more left for me from ncpc'04... goodbye 2004. i won't make any further postings here. the end.

2 more tasks for me: I and K.

Problem I looks quite interesting, but I can only get an O(n^2 log n) algorithm, which I think can never pass the time limit... Could someone who's solved this write a few lines here?

Problem K, hmmm, is that just simple maths? Haven't read the problem description in details yet...

Actually problemK is a more original problem than I.

To solve problem I just find readings related to "Ham Sandwich Cut". Although very good programmers (like Derek Kisman) can solve it with only common sense and a few minutes thought .

Although I is a direct implementation of a known algorithm still I found it interesting because it was uncommon in contest world before this problem (I guess).

Just solved K. A really nice problem!

shahriar_manzoor wrote:To solve problem I just find readings related to "Ham Sandwich Cut".

I recognized Problem I as a Ham Sandwich application, but since the only Ham Sandwich Theorems I've seen are existence theorems, it didn't help me much (I even tried thinking through the only proof I've seen to see if it would yield an algorithm, but it didn't). In the end, common sense turned out to be the key.



Regarding the discussion of the rest of the problemset:
I thought the problemset was nice (I particularly liked problems C, I and J), and there were no technical issues with it, but I think it had two flaws (both of which have already been pointed out in this thread, and neither of them being end-of-the-world-serious).

First, I think having the problems sorted in order of difficulty is always a bad idea - and it's almost no work at all to fix it.

Second, I think the difficulty of the problemset was askew. In particular, the amount of medium-difficulty problems (to which I count G and H, and possibly F) was too small, especially in comparison to the amount of easy and very easy problems. I am, however, aware that the problems available to choose from are a big factor, and that it sometimes is impossible to combine these into a well-balanced problemset.

But of course, that's only my opinion, and you're free to ignore it.

Per wrote: I recognized Problem I as a Ham Sandwich application, but since the only Ham Sandwich Theorems I've seen are existence theorems, it didn't help me much (I even tried thinking through the only proof I've seen to see if it would yield an algorithm, but it didn't). In the end, common sense turned out to be the key.

Well then Kisman is not the only great problem solver of the world

Per wrote:
First, I think having the problems sorted in order of difficulty is always a bad idea - and it's almost no work at all to fix it.

Actually sorting them is a work. And the main reason for doing so was to boost up the novice teams. Because as a judge I have seen novice teams submitting problems as difficult problem J and I and because the sample matches. But surely sorting the problems is not a standard idea.

Per wrote: Second, I think the difficulty of the problemset was askew. In particular, the amount of medium-difficulty problems (to which I count G and H, and possibly F) was too small, especially in comparison to the amount of easy and very easy problems. I am, however, aware that the problems available to choose from are a big factor, and that it sometimes is impossible to combine these into a well-balanced problemset.

Actually, if it was not our NCPC, the problemset could have been made more standard for the World. For example, if Problem K, the "Champions League" and another DP problem were there instead of three easy ones it would have been a better problemset according to me and some others but we just wanted to be good buy even for once

- - - CUT CUT CUT - - -

Hi the LA-Z-BOy,
First of all please accept my heartiest apology.

Actually I did not attack you at all. It was just a very silly post, playing a detective game. As you have seen it did not get popular.

Believe me when I say it, I actually gave clue to your Teams name out of respect and not for any personal allegation. I feel that your team is much more capable of what was appearent by your contest result. But ofcourse I shouldn't have been too presumptous about it. I am totally disgraced.

There is nothing between us that will cause me to attack you, so if you took it the wrong way, then all I can say is "sorry for my mistake."

And of course that post will be edited, and I am sorry again.

dear shamim,
Some of my favorites of this site [ Shahriar Manzoor, Kamruzzaman ] were involved in this topic, thats why I did take it too seriously as I should have. Now that I know that it was just a misunderstanding, It's okay to me now.
It shouldn't have happened though, if you were a bit more careful.
Thanks for editing the wrong post.
Greets.