Challenge problem solved exactly in August Challenge .

august14
challenge
#1

This refers to the problem “Sereja and Shuffling” in the August Challenge 2014 currently underway .

5 people seem to have exactly solved the problem . On a careful consideration it seems an exact solution can be reached for most of the test cases .

The RAW score formula is (INIT - S) / INIT , where S has to minimized and can be at minimum zero . So the best raw score for a test file is 1 . So only taking into account scores for 4 test files ( out of 20 ) a score of 0.2 would be achieved at best which the top 5 contestants for the challenge problem have achieved .

The contest is only halfway , and it would be better if codechef admin’s add another challenge problem .

Also it is time to rethink the process by which challenge problems are accepted for inclusion in a LONG contest .

#2

Maybe it could be a good idea to take some insights from previously used and “successful” Challenge problems?

I mean, it’s not that those older problems couldn’t also be hacked… I guess everyone agrees that top competitors here have set the bar extremely high and setters’ need to get more and more creative with each passing contest in order to keep these top competitors motivated… So the problem of the contestants being absolutely amazing (I guess everyone knows ACRush, Gennady and I’m personally a fan of Mugurel Ionut) also makes this task a lot harder to manage.

Maybe if there were different scoring schemes for several batches of files that would be dependent on how a given test case was structured on those files would make the task of achieving an exact solution harder…

But maybe some of the top competitors can also give valuable tips to future setters on this matter, I believe.

Best,

Bruno

#3

Without the analysis of test case generation its not possible to submit it correctly. And Great programmers like ACRush, MugurelIonut can crack the test files easily by knowing the test generation scheme. But its very difficult for beginners to analyse this. I always solve the challenge problem with poor complexity then I try to optimize it but this time its more biased towards the test cases. And as this problem has high complexity naive approach and the range of input is really large.

#4

@kuruma : Thanks for the response . Topcoder also organizes marathon and there the problems can not be hacked in this way . I think its about :

  1. Formally proving the problem to be NP-Complete , PSPACE complete or EXP complete or large input size with high polynomial complexity .
  2. Good Test Case Generation : Random might not be best choice . Custom hand-tuned test cases may be required .

    I think in the current problem its the point 2 that has not been taken care of .

    The current problem is different from contestants hacking test data , I guess .
#5

@vineetpaliwal, I just try to help in the best way I can :slight_smile: I haven’t solved the problem…I face much greater difficulties in “easier” problems :’( But with the time and skillset I have right now, this is the best contribution I can give