## HELP WITH NCPC

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### And for the problems

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.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### hmm

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Just solved K. A really nice problem!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

### Re: hmm

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.

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### Re: hmm

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

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:

### what the heck!!!

- - - CUT CUT CUT - - -
Last edited by the LA-Z-BOy on Wed Feb 02, 2005 7:14 pm, edited 1 time in total.
Istiaque Ahmed [the LA-Z-BOy]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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.

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm