You are not logged in. Please login at www.codechef.com to post your questions!

×

Should we have two challenge problems in Long Contest?

Hello

100 hours into the July Long Contest, Top 10 scores are >=9.95.

I think having two challenge problems will make it more interesting!

asked 08 Jul '14, 18:03

yash_15's gravatar image

5★yash_15
5181716
accept rate: 2%


No, I think having a hard problem would make the top places more distinct, and therefore the competition more interesting.

The hardest problem so far, SEAEQ, seemed pretty easy to me (I spent much more effort on GNUM), despite the fact that even though I asked for clarification of the sense-lacking "number of index", it hasn't been answered and I had to guess that it actually means "number of indices".

UPD: I'm not saying anything about the other problems in the contest (in particular, this doesn't mean that I don't want a challenge problem), just saying that there isn't a truly hard one. And of course, I mean a hard binary-scored problem.

link

answered 08 Jul '14, 21:15

xellos0's gravatar image

7★xellos0
5.9k54394
accept rate: 10%

edited 10 Jul '14, 02:03

@xellos0 : Yes I agree that one or two HARD problems keeps the contest very vibrant . I didn't support the idea of 2 challenge problems because in current contest there are lots of people with all 9 problems solved . That might have been the intention of the person who started the thread ( @yash_15 ) but not me . I supported the idea because of my respect for the challenge problem and what it takes to do well at them .

(09 Jul '14, 10:58) vineetpaliwal6★

I can understand your frustration that you stayed at top for considerable time, but then were done by some little bit more optimised solutions. But imagine the case when all top 50 people ending up with perfect 10. Then you people will make the short contest (24 hrs or even less) out of it!!

(09 Jul '14, 23:19) yash_155★
1

If there was a very hard binary-scored problem,

all top 50 people ending up with perfect 10

would be impossible.

(10 Jul '14, 02:00) xellos07★

@yash_15 : Yes that would be a good idea :) . I think challenge problems are the pinnacle of programming and need to be paid more attention , and will definitely lead to more learning for the participants .

link

answered 08 Jul '14, 18:15

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107171
accept rate: 12%

2

@vineetpaliwal, you alive? could you rip-off some money for your course project: http://discuss.codechef.com/questions/41771/online-course-by-vineet-paliwal :P

(08 Jul '14, 19:56) garakchy1★
5

The pinnacle of programming? Maybe, I don't know. The pinnacle of algorithmic programming? Definitely not - imagine taking away all known algorithms, how would algorithmic programming look then?

Besides, they're incredibly time-consuming (or luck-dependent, or giving lower scores, pick one), which is kind of ironic, that high efficiency of one's code causes low efficiency of problem solving.

(08 Jul '14, 23:57) xellos07★

@xellos0 : You said challenge problem is not pinnacle of algorithmic programming . I don't agree with it . Because NP Complete etc problems force you to think of other algorithmic approaches like APPROXIMATION ALGORITHMS and RANDOMIZED ALGORITHMS . Also if you think the world of known algorithms is taken away when doing challenge problems , I don't agree with that also . Because to solve a challenge problem often what is a good approach is to approximately match it to a known scenario by making some small invalid assumptions and then solve the reduced problem by an EXACT algorithm .
Also , I never said that you have only two challenge problems in LONG CONTEST . I never said anything about not having other 9 problems .

link

answered 09 Jul '14, 10:53

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107171
accept rate: 12%

edited 09 Jul '14, 10:54

3

No need to write in caps, we aren't fighting to the death :D

You have a point here, but that still doesn't entitle you to putting challenge problems above all exact ones, which the word "pinnacle" implies to me.

With challenge problems, we can ask "how much better can we solve this problem", and eventually arrive to something that's almost perfect, but not perfect. But then, there's a question of "is this the best we have?", that of exactness. I ask, would it be okay to completely disregard it? All the exact algorithms we have so far would exist, but there'd be something missing.

(10 Jul '14, 01:50) xellos07★
1

And I don't know about others, but I never cared much about theoretical complexities in challenge problems, because there's always a point where complexity only needs to be good enough and real runtime matters. These (possibly subtle) differences of "what'd happen if we used inputs that we can't produce IRL" can be interesting just as well as those of real runtime.

All in all, I'm not opposed to challenge problems, but opposed to opposing exact problems. These are not the same thing.

(10 Jul '14, 01:59) xellos07★
1

Also, I never said anything about long contests when responding to you, that was completely beside the point.

Practical note: Codechef threads don't sort answers by time, but by votes, so it's better to discuss in comments than answers (even though they're short), or this could end up like reading an n-logy of books in random order...

(10 Jul '14, 01:59) xellos07★

@xellos0 :

"No, I think having a hard problem would make the top places more distinct, and therefore the competition more interesting."

So a challenge problem for a medium problem should be acceptable. Hardest problem can be made even harder, but no matter how hard the problem they choose, I believe that some of us will be definitely able to solve it.

Simple Logic : They also provide the editorial and two working solutions at the end, meaning that he problem is solvable! And we have some really great people out here who just cant let the contest end with a problem remaining unsolved.

link

answered 09 Jul '14, 23:15

yash_15's gravatar image

5★yash_15
5181716
accept rate: 2%

1

See my UPD: I'm not saying anything about the challenge problem :D

(10 Jul '14, 02:03) xellos07★

But I was asking about challenge problems.

(14 Jul '14, 19:18) yash_155★

just a reminder: "The score that you will see during the contest will only be partial (obtained on 20% of the test data)." maybe this thing increases chances to differentiate top10 participants score in appropriate way? (sorry for my bad English)

link

answered 10 Jul '14, 02:20

bdzl's gravatar image

5★bdzl
1
accept rate: 0%

-6
Answer is hidden because of too many downvotes. Click here to view.

answered 09 Jul '14, 11:06

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107171
accept rate: 12%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,424
×858

question asked: 08 Jul '14, 18:03

question was seen: 2,538 times

last updated: 14 Jul '14, 19:18