Unsupported ICPC rules modification

[kunyavskiy]

Some contest control systems do not round the penalty for each problem to the minute but use some other penalty resolution.

The main option I have seen is to sum submission times with seconds resolution and round down to the minute at the end, but just using penalty as seconds also makes sense.

Also, some contests (e.g. Atcoder rounds) use last-submission time instead of sum-of-submissions.

I think it should be possible to specify these changes in the Contest object, a penlty_time is specified, not forced to be equal to 20 minutes.

So my proposal is, to add the following fields in the contest object:

1. problem_penalty_resolution it can be either an integer (in seconds or in milliseconds?) or enum (MINUTE, SECOND, etc).
2. total_penalty_resolution in a similar way
3. penalty_algorithm which is enum, whether sum or last, maybe some more options if someone comes up with them.

This change is easy to implement in CCS'es - they can just send objects correctly to them not making it configurable, if it was not. And reasonably easy to implement in scoreboard calculation.

Questions need to be accurate with:
We should decide if penalty_time is specified in minutes or in problem_penalty_resolution units. Both make sense to me.

[niemela]

Questions need to be accurate with:
We should decide if penalty_time is specified in minutes or in problem_penalty_resolution units. Both make sense to me.

Since #151, penalty_time is now specified as RELTIME. So, neither.

Also, some contests (e.g. Atcoder rounds) use last-submission time instead of sum-of-submissions.

I thought AtCoder used scoring problems? As such they would not have "penalty" in the sense we talk about here? Could you elaborate on what the exact rules are for AtCoder rounds?

So my proposal is, to add the following fields in the contest object:

1. problem_penalty_resolution it can be either an integer (in seconds or in milliseconds?) or enum (MINUTE, SECOND, etc).

Maybe contest_time_resolution would be more consistent with current terminology (See scoring section of CCS requirements)? An argument can also be made for penalty_time_resolution.

Most consistent with the changes in #151 would be to specify it as RELTIME. I think that would work.

I think we should require that penalty_time is an integer multiple of this. Thoughts on that?

2. total_penalty_resolution in a similar way

Why would you want this to be different?

3. penalty_algorithm which is enum, whether sum or last, maybe some more options if someone comes up with them.

I don't think this is the penalty algorithm, this is more like the score(board) algorithm, and there are a lot more than these two.

[nickygerritsen]

I like the idea about contest_time_resolution. DOMjudge allows you to score in seconds instead of minutes and we could handle it more officially with this. It makes sense to me that penalty_time needs to be an integer multiple of that value.

[niemela]

I like the idea about contest_time_resolution. DOMjudge allows you to score in seconds instead of minutes and we could handle it more officially with this. It makes sense to me that penalty_time needs to be an integer multiple of that value.

FTR, Kattis also has this setting (and no way to communicate it through the API).

[kunyavskiy]

I thought AtCoder used scoring problems? As such they would not have "penalty" in the sense we talk about here? Could you elaborate on what the exact rules are for AtCoder rounds?

They have both. They have scoring, but no sub-tasks. That's why collision of score is quite probable, so tie-breaker is needed. In fact, it's much closer to weighted ICPC rules, than to IOI.

[niemela]

They have both. They have scoring, but no sub-tasks. That's why collision of score is quite probable, so tie-breaker is needed. In fact, it's much closer to weighted ICPC rules, than to IOI.

Could you explain what the rules are? I could not find information on the AtCoder site.

A common tie-breaker for the kind of contests that you describe is "time of last score improvement" (sometimes called "time of last submission"), which is not really penalty, in the sense we use the term. Is that what they are using?

[kunyavskiy]

I can't find it on the website indeed, but I can explain myself.

They do the following:

• On each problem remove all submissions after the last score improvement (most problems have only possible 0 -> full improvement, but rarely there is an extra step in between).
• On each problem you get 5 minutes of penalty for every submission before last
• You have penalty for time of you last submission overall problems
• This penalty (as sum of last submission time + wrong attempts) is used as a tie-breaker

I wouldn't say that an essential part of the definition of penalty is "being the sum of time of submissions + something". I would say it's "being related to time" and "being tie-breaker in case of equal score, not affecting score calculation itself". Similar rules were also used in google code jam and are used now on meta hackercup, so I wouldn't say it is something marginal.

[niemela]

I can't find it on the website indeed, but I can explain myself.

They do the following:

• On each problem remove all submissions after the last score improvement (most problems have only possible 0 -> full improvement, but rarely there is an extra step in between).
• On each problem you get 5 minutes of penalty for every submission before last
• You have penalty for time of you last submission overall problems
• This penalty (as sum of last submission time + wrong attempts) is used as a tie-breaker

This sounds to me like the normal ICPC rules with 5 instead of 20 penalty minutes, and extended to score?

I wouldn't say that an essential part of the definition of penalty is "being the sum of time of submissions + something". I would say it's "being related to time" and "being tie-breaker in case of equal score, not affecting score calculation itself". Similar rules were also used in google code jam and are used now on meta hackercup, so I wouldn't say it is something marginal.

Riiight, I mostly agree, because the rules you have now described are pretty much the same as the ICPC rules, and so it is in fact penalty in the sense we use the word.

I still would not call this setting penalty_algorithm, I would say that this is the "scoring algorithm" (problem with that is "score" is a bit overloaded here), or the "scoreboard algorithm). Furthermore, I think we need quite a bit more than an enum with 2 possible values to cover even the most common contest formats (oh, maybe that's a better term?).

I do agree that it would be worthwhile to solve this though. Maybe we could start by collecting all the contest formats we know of, and find a good compromise of settings that allows us to cover as much as possible as simply as possible.

[kunyavskiy]

Well, it's slightly different, as it has max instead of sum. But very close.

Here are all versions of penalty calculations I have for live, that can be a good start of list.

https://github.com/icpc/live-v3/blob/main/src/cds/core/src/main/kotlin/org/icpclive/cds/scoreboard/PenaltyCalculator.kt

They are not specific to score/icpc, assuming all submissions before last improvement as wrong and last improvement as one counted for penalty.

[kunyavskiy]

As communication of penalty calculation rules I see the following dimensions:

• Precision: if the penalty is calculated in minutes or seconds. I see two options here.
  • It can be an enum of one of the possible values (minutes, seconds, milliseconds)
  • It can be a duration, multiple of which penalty should be. This option is a bit more universal, but allows some nonsense like "precision is 1 second 234 milliseconds".
• Submission time rounding: how each submission time is rounded. Looks like it should be enum of
  • Rounding down to multiple of precision
  • Rounding up to multiple of precision
  • Rounding to the nearest multiple of precision
  • No rounding for each submission, with one of the roundings above for total penalty. Maybe this should be a separate field.
• Penalty per wrong submission. Already exists as part of the contest object, maybe should be moved here
• Rules of merging penalties of separate problems into a single value. From the ones I've seen, there are the following options:
  • SUM - the default one, used in ICPC rules
  • MAX/LAST - time of last improvement
  • ZERO - time is not relevant at all, only wrong submissions are important.
  • DISABLED - no tiebreaker, places are just divided on sam score (as on typical IOI competitions)

It looks like it can be hard to understand which combination of the properties above is reasonable in general, so an object with several fields looks better, than the specific list of available rulesets.

If we decide to go that way, there are a lot of naming questions, but probably they are easier to discuss within MR, not within issue.

[niemela]

This was discussed at today's meeting.

Quick summary of most important things:

• We will try to add some kind of rules setting as a set of known rule-sets with predefined (per rule-set) parameters. Rather than adding the full set of parameters needed for "any" rule (that we want to support).
• scoreboard_type in /contests should maybe be folded into this rules object?
• penalty_time in /contests should maybe be folded into this rules object?
• penalty in /judgement-types should maybe be folded into this rules object?
• We will add some section describing "known rulesets", similar to our lists of known judgements, and known awards.
• @kunyavskiy and @niemela will continue working on this (although anybody is welcome)

[deboer-tim]

My last thoughts from the meeting:

• Most clients don't need to know how the score was calculated, they just need to know how to display a scoreboard. scoreboard_type basically just tells you which properties will exist on the scoreboard row and data objects, so it (or an equally simple grouping) should be kept.
• For clients that need to calculate score, to me it is just a specialization of the kind and I like continuing the pattern, i.e. scoring_rule X may define additional properties wherever they make sense, and defines how they're used to derive the scoreboard. e.g. 'icpc' says that penalty_time will exist and what the rounding and tiebreaker rules are; 'ioi' may need additional properties (or not) and have different rules.

To make this really explicit, I think it would be fine for someone to define a scoreboard_type named 'style-points' which means that scoreboard data objects will have a style property and rows will have score.total_style. The associated scoring_rule might say that every correct judgement will have an integer style value assigned by the judges and how they are summed to create the scoreboard. 😎

[deboer-tim]

I had to fix a scoreboard this week (it started showing REL_TIMEs 😀) and work on another (longer story), but it made me realize that even the 'ICPC scoreboard' is subjective. e.g. if you made penalty_time 2.5 minutes or didn't round submission times, you might want to see that on the scoreboard.

So, I still prefer the pattern where each scoreboard/scoring algorithm adds properties and I think there is some value in a hierarchy or relationship between them (e.g. 'pass-fail.icpc' vs 'pass-fail.tim' might share properties or at least be easy to implement one if you already support the other?). But I think the only real difference between the scoreboard_type and _kind in my previous comment is 'does the feed contain enough data to calculate the scoreboard yourself'? I'm not sure it's worth making this distinction in the spec, so a single property is likely enough.