Invitation to CodeChef April Long Challenge 2018!

general
,
11

One of the high-scoring solutions to CHEFPAR worked by reverse-engineering some of the parameters for the hidden problems and individually optimising different random seeds for each hidden problem. This was done by making use of the fact that you get told if your program aborts on a hidden problem, so some hidden information leaks back. The program would not work so well (or might not run at all) on a new random problem instance.

I don’t know if this is allowed or not, but I don’t think it is a desirable feature (and I wouldn’t use this method) as it seems to be against the spirit of the competition, in my opinion anyway. I suggest that the challenge problems be adjusted in future to reduce the effectiveness of this method. One thing that could be done is reduce the number of submissions allowed, since 200 is rather a lot: 50 should be plenty since you can try your method offline on test data. (Maybe even less than 50 is better.)

Another problem is that there are potentially even larger information leaks from the non-hidden problem instances (four instances in this case), because you get to see about 20 digits of output and there is execution time and memory usage that can be manipulated. Perhaps it would be a good idea to exclude the non-hidden problem instances entirely from the final judgement (in this case judging on 16 instances rather than 20). At least, that would fix this subproblem (information leak from non-hidden problem).

I suppose the nuclear option is not to give any information back at all (even TLE, RE etc) about what your program did on the hidden instances. I would personally be in favour of this, though I realise this could lead to disappointments if none of your submitted solutions run properly on the hidden set of instances.

1 Like
13

Suggestion for how to prevent reverse-engineering of challenge problems.

Taken from the thread on CHEFPAR and reverse-engineering instance parameters. In my opinion it is better if the competition is to find the program that works best on a random problem instance, rather than being a competition to reverse-engineer the hidden (or visible) instances. I think that would make CodeChef a more attractive environment to compete in (it is already very good, by the way - I hope this suggestion might help make it a bit better).

Definitions: by “feedback-instances” I mean those which contribute to your provisional rank, and for which you get back a score (four of these in the CHEFPAR contest, one for each type). By “hidden instances” I mean those for which you don’t get a score back during the contest (sixteen of these in the CHEFPAR contest, four for each type).

As far as I can make out, there are two competing needs:

(i) It is nice if people can be confident during the competition that their program will work (not abort, time-out etc) on hidden instances, so they need some kind of feedback during the competition that it works on hidden instances. It’s also nice if people feel able to try out lots of solutions over the 10 days.

(ii) It is good (in my opinion, anyway) if you can’t use the information from the result code (AC, TLE etc) to reverse-engineer parameters of the hidden instances. It’s also good if you can’t use the result information (score, time, memory usage) from the feedback-instances to reverse-engineer their parameters.

I think you can satisfy both of these needs by the following modifications to the rules:

(i) You are still allowed to submit a lot of answers (say 200), but in only (say) 20 of these will you get result code feedback from the hidden instances. 200 should be plenty to try out lots of ideas, and 20 should be plenty to make sure your program (that you already know runs successfully on feedback-instances) doesn’t crash on hidden instances. The user would get to choose which (up to 20) submissions count for the extra result code information. (The displayed time and memory usage would be taken from the feedback-instances, so you can’t get extra information about the hidden instances that way.)

(ii) feedback-instances are excluded entirely from the final score (after competition ends). In the case of the April 2018 challenge, that would mean you would be judged on 16 hidden instances rather than 20 = 4 + 16 instances. The reason for this is that it is very easy to leak information back from the feedback-instances, much easier than from the hidden instances. For example in CHEFPAR, during the competition you got back a 16-digit final score: you could encode information in some of these digits, so you get back much more than 1 bit of information per submission.

I think these changes would keep most of the necessary feedback so that users know their code is working and preserve the fun of seeing a live scoreboard, but would mostly prevent the problem being “hacked”.

1 Like
15

@aryanc403- Why? Thanks mate for the compliments!

We intend to do that as a regular practice to be honest, but problem setters are really busy at times. Like, some are having end-semester exams &etc. Even I have those, but comparatively I am a bit free right now, so I am trying to resolve as much as I can :slight_smile:

This time, I also tried to answer as many comments as I can xD. Just to assist setters. You wont believe, but we had over 150 comments for weightnum alone, all saying one thing “Why is W upto 300?”

Well, there is only 1 @vijju123 in entire world. And I have the motto that “If its me, things should change for good :slight_smile: .” I tried my best to act on lines I expect the panel to act- eg- answering all comments, even if its a trivial “Comment denied” or “Asking for hints isnt allowed.” Its really important in my opinion, that, setting panel should respond to comments else there hangs a feeling of “Aloofness”. Like, in CF rounds, all queries get answered, even if it takes 5-10minutes. If it happens there, why not here?

Though, I must agree on other side too, answering comments is tiring. For AVGPR and WEIGHNUM, there were like, 10 new comments every hour. Dont believe me? See the tab below-

Click to view

alt text

And that brings me to one of my key points. People, especially Div2, should NOT share ideone links etc. in comments, not ask for hints, or ask setter to debug his/her code. Thats simply outrageous. Because of that, we keep on missing some valid comments :frowning:

16

This is to inform you that all the Setter’s, Tester’s and Editorialist’s solutions are successfully linked to the editorials, except for CUTPLANT.(I am in talks over this delay for that editorial, we will look into that).

The editorialist solution is commented most (I think all :stuck_out_tongue: ) the time, so you can refer to that in case you have any further doubt. Hope you enjoyed the editorials as much as (or preferably more :p) than the problems. In case there is any further issue accessing solution of any other editorial, except CUTPLANT, do ping me here, we will look into that. With that, I would like to conclude the final announcement for this long with three magical words…

Click to view

PREPARE FOR COOKOFF

1 Like
17

Just chiming in to the lovely discussion of @alexthelemon and @algmyr.

As I see it, the essence of the CodeChef tie-break problems is to design an efficient algorithm that finds approximate solution to an NP-hard problem. You are given the time and memory budgets, and also - which may not happen in real life - a nicely defined domain of the possible input values. Since a lot of approximation algorithms carry a significant amount of randomization techniques, it is appropriate to ask how the fairness of the judging process can be assured.

20 test cases is definitely too low of a number to have a 95% confidence that one algorithm is better than another. Furthermore, the current practice of taking the best result out of (potentially) 200 solutions favors the algorithms with high volatility of the results - which is kind of gambling.

Definitely, the first step is the clear separation of the provisional tests from the hidden/final ones. The purpose of the provisional tests is to give you some kind of calibration of your solution to the CodeChef system resources, and to give a quick test run. The final score should be calculated from the hidden tests generated for the final scoring only. Maybe a hundred test cases to give a good spread of the potential input values, and to reduce the element of darn luck.

The second step (which is more laborious to implement) is to give a contestant the choice which solution he/she considers as a final solution. Not the last solution, but the actual choice to define the final solution. We can even go one step further - not a single solution but multiple solutions. But out of multiple solutions, not the maximum score but the average score. Some people may prefer to gamble and choose a single final solution, some people may want to mitigate the risk (the downside) and choose multiple solutions (CodeChef may limit the number of final solutions by, say, 10). This way the final score calculation can still proceed at reasonable pace (more test cases but less solutions to check) and the judging as a whole appears more fair.

18

Duration of APRIL18 will be extended by one day soon.

19

It really shouldn’t matter. GCJ was just for 27 hours.

20

Yes, but we extended APRIL18A from another reason - JADUGAR

1 Like
21

Div1 afaik. The page there says nothing about div2 top 20. It would be unfair for newly gone div1 guys if they’d get equal prize in div2. Would be undesirable.

22

Div1 got extension because the problem JADUGAR was split into two, and a new subproblem was added in the newer version, JADUGAR2. This did not affect div2 in any way.

However, if you want an extension as well, I can talk to @mgch regarding that- but I need a valid reason to do so.

23

I will consult contest admin @mgch over your concern.

24

The contest for Div2 is extended now. It will end on Tuesday with Div1.

25

They already are.

26

I already replied to your query. I will copy it here for documentation purposes :slight_smile: -

@aryanc403- Thats not correct, and wont help. One instance I can give is, that today itself, some guy submitted ≈60 submissions on PyPy, each of which took 20secs to get verdict.

A better solution which we suggested what “Limit number of submissions a user can make in X minutes to Y”- i.e. dont allow indefinite submissions for any problem.

28

loved the problems this time around :slight_smile:

29

Yes, I will forward this feedback to @admin for consideration. Dont worry about that :slight_smile:

30

Even I loved quite many of them. My favourite was CUTPLANT. AVGPR adn WEIGHTNUM had good concepts involved as well wheich I felt are good for beginners :slight_smile:

1 Like
31

Thank you :smiley:

I started this when I wrote ICPC editorials for Amritapuri- to put basically any content which I feel might be useful to some, but couldnt be put in formal section. (I got too many complaints of my editorials being too long and too explanative xD). Chef Vijju’s corner, or the unofficial part is a nice place for some light hearted humor, and other approaches and “what if” things. Glad you liked it :slight_smile: . (After all, I believe my editorials should stand out from rest, shouldn;t they? xD)

1 Like
32

We are aware of that. Just to reduce that they reduced it from 500 to 200. If any further reductions are needed, they will do so as well :). Do you think it is direly needed right now?

34

A simple way of helping the issue is to do something like what is done at the Yandex optimization track, just consider the LAST submission for the final score. This doesn’t give the incentive of submitting a lot of times to randomly get a good outcome (since you don’t know the full test suite). Rate limiting, while a decent idea, does not alleviate the issue that submitting a random algo a lot of times is beneficial. @admin @aryanc403 @vijju123

2 Likes