#### Hello, Codeforces!

The ICPC Challenge World Finals in Luxor is approaching for some of you, and we are delighted to provide an additional exciting opportunity to compete open to all!

We are happy to invite you to the 2023 Post World Finals Online ICPC Challenge, powered by Huawei starting on **May 6, 2024 at 15:00 UTC and ending on May 20, 2024 at 14:59 UTC.**

In this Challenge, you will have a unique chance:

to compete with top programmers globally

to solve 1 exciting problem prepared by Huawei

to win amazing prizes from Huawei!

**It is an individual competition.**

**2023 Post World Finals Online ICPC Challenge powered by Huawei**:

Start: May 6, 2024 15:00 UTC

Finish: May 20, 2024 14:59 UTC

We hope you'll enjoy this complex Challenge!

#### Problem

We are glad to propose to you an exciting challenge **“Accuracy-preserving summation algorithm”**, which is prepared by Huawei Computing Product Line.

With this challenge, we focus on summation algorithms of floating point numbers in different precisions with the goal to use the lowest possible precision without losing too much of the accuracy of the end result. This problem arises in high-performance computing as lower precision can be computed faster. At the same time it also loses accuracy faster and can even lose it completely. Finding the right balance between fast low precision calculations and higher precision intermediate summations is a challenging task on modern architectures, and you would have an opportunity to try addressing this challenge

#### Prizes from Huawei

Rank | Prize | |

Grand Prize (Rank 1) | € 12 000 EUR + a travel trip to the 48th Annual ICPC World Finals in a guest role | |

First Prize (Rank 2-10) | € 8,000 EUR | |

Second Prize (Rank 11-30) | € 3,000 EUR | |

Third Prize (Rank 31-60): | € 800 EUR | |

TOP 200 Participants | Souvenir T-shirt | |

* If the allocated Huawei Challenge prize cannot be delivered to your region for any reason it may be replaced by another prize (if no legal restrictions), at the discretion of the Sponsor. | ||

#### Challenge Rules and Conditions

By participating in this Challenge, you agree to the Challenge Rules and Conditions of Participation

**Good luck, we hope this will be fun!**

Why was this postponed in the first place?

I remembered about a summation problem long ago, but it got wiped out of CF and I can't find it. Now it has came back with a different name.

Is it rated?

No

I think it's rated because carrot extension column called** (just now )** is founded in standing table

Should I be registered somewhere else from CF, or CF registration for the event is sufficient to be eligible for the prizes?

According to para. 8 of the challenge rules, "only participants who entered a valid ICPC username (email address) during registration are eligible for recognition as a Challenge winner", which means (if I remember correctly) that you need your codeforces email to match your icpc.global email. It should be possible to register there even if you are not icpc-eligible (e.g. not a student).

You can probably avoid this as long as possible and only do this after the contest ends if you are among the winners, though.

so we should have an account on ICPC website?

Yes, I think so.

You can participate no matter you have an account or not. If you don't have, then you'll be invited to create one after this contest.

Best of luck for all the participant.

Hello this contest has been such a great pleasure to complete! Thank you to all the writers and editors and testers of this :) such a great contest.

How many tasks are there in this contest?

only 1

thanks

What about the T-shirts for the last challenge?

I never got mine. Did anyone?

What should I learn to reach the level that I can solve that kind of problems?

it is rated?

Have to say, I haven't spent as much money since I was born as 12000 EUR.

Can I participate in other rated contests during the two-week challenge?

When will i receive my T-shirt I got last round?

What is the perfect score?

There's a lot of minor details about the scoring process that are missing from the statement. Do you plan to release a local scorer to clarify some of them? Thank you

The testing queue is so long, i need to wait 10 minutes to get the results.

DelayForces:( I have been waiting for judging for 25 minutes, but it is still "In queue" now.

For some reason this is happening to random submissions :(

Maybe the next time we will have to write an evaluator for codeforces :)

Or write a program to predict(guess) a proper time to submit to avoid being inq

Can someone explain which order codeforces judges? I sent submission 1 hour ago. Still in queue while recent ones have been already judged.

I just noticed the grader is extremely fast, can we expect the same performace for the hidden tests?

How hard is to reach 3000points? Like how long would a code for those scores be?

Can we see other's solutions after contest is over?

Time limit is "10s", for just adding 1000000 double numbers?. I am so confused: what is the point of solving this? Spending 10s CPU time and generate a not-reusable "program" just for a specific input. Am I missing something important? Really do not understand the "real" problem behind this "abstraction".

Not only that, they don't reveal many details which are very important and you have to guess them. If you want your "real" problem solved, you don't hide any details, you provide local tester and a few tests (or test generation method).

I second this

Maybe you could think that because I'm in the lead, I've understood the task statement.

I assure you : it's not the case. I have no idea how to add two fp16 numbers in the "right" way, by which I mean the one used in the evaluator. Especially subnormal fp16.

I would like to thank the organizers for the latest announcement.

Still have no idea how they cast fp64 to fp32 or sum fp32.

Two doubles -> Two floats -> Two doubles -> Sum

Oohhh thanks a lot! And they do not cast the sum to float? Anyway I will try when I will have access to a computer

The standings changes so fast!

Organizers aren't answering questions in the contest system so I will ask here:

1) In order to compute the perfect sum $$$S_e$$$, do we read input values as fp64 (

`double`

) or something more precise?2) What happens when we convert fp16 infinity back to fp64? Does it become infinity or e.g. the max fp16 value?

pinging @ICPCNews

1)

Note that the actual binary64 value is not always exactly equal to the given decimal value. Instead,the actual given valueis the closest number representable in binary64. When reading the input, most programming languages will do the conversion for you automatically.Based on this statement, it is enough to just read input value into double without any extra actions.

2)

When the algorithm performs an addition in type T, the two arguments are converted into type T, and the result is also of type T....The addition of two fp16 happens in fp64, but the result is immediately converted to fp16.If I understand correctly: double a, double b -> half a, half b -> double a, double b -> double sum -> half sum

This doesn't answer my doubts :(

1) I'm asking about the definition of $$$S_e$$$, which organizers calculate

"as precisely as [they] can". Is it the sum of input values, each rounded to binary64 first? Or is it the precise sum of input values, only at the end rounded to binary 64?2) What happens when we convert fp16

infinityback to fp64?1) I also struggle with understanding $$$S_e$$$, but if "

the actual given value is the closest number representable in binary64", I suppose that $$$S_e$$$ is computed based on the "given values".2) Based on my submissions, fp16 infinity converts into fp64 infinity. And it would be weird if infinity converts into some non-infinity value.

My best guess is the following: the expected sum S_e is the exact sum of input values converted to binary64. The tester has a bug, and does not calculate the sum correctly for 3 of the 76 test cases.

2) Shouldn't it be the same what happens when we convert float's infinity to double?

For 1), I have a simple algorithm that computes $$$S_e$$$. It may not give the theoretical $$$S_e$$$, but it seems to give the same $$$S_e$$$ as the evaluator. It may be that "as precisely as we can" != "as precisely as possible". I'm not sure I'm allowed to reveal more details.

I have no idea for 2).

"... I'm not sure I'm allowed to reveal more details..."Once the contest comes to an end, feel free to reveal all the details (procedure, source code, etc.) :). I'm eager to see a good solution in action.

The fifth Huawei-CF optimization challenge was on the midway... Participants were still guessing evaluation details...

I also asked questions, but organizers aren't answering the questions...

The announcement says "When a value is fp64 or fp32, we just use the native data types." , but I don't think this is very clear. This is because IEEE 754 allows several different rounding algorithms, as explained in https://en.wikipedia.org/wiki/IEEE_754#Rounding_rules , and is dependent on languages or compilers. (Python users may be in trouble because it doesn't support fp32 calculation in build-in functions.)

It seems to be consistent with C++

`double`

and`float`

.In my humble opinion, these recent announcements are not entirely fair to those individuals in top positions, as they were clever enough to unravel the hidden aspects of the contest unaided. Now, they may face additional competition for the top spots. While such adjustments might be acceptable in a 'just for fun' contest, they seem unjustified here, especially considering the significant monetary stakes involved.

Fear not, top performers! I pose no threat to you! I currently reside at the bottom of the leaderboard and intend to stay there for the duration of the competition. :)

Good luck!

Come on... releasing the checker and some tests after 10 days of the competition? +Extension

I did most of the work in the first week, and planned to do very little this week. Good luck with that plan now, right?

We know that not every solution is the best solution, because there are a thousand Hamlets for a thousand readers.

The current release plan is probably the one that best meets most candidate's needs. I apologize for the impact on you.

The contest is still on, who knows what the final result will be?

Why?

"Next, we calculate the expected sum as precisely as we can"

"//'Exact' answer based on Kahan summation"

Or, the Kahan is shown but the expected sum is really exact while testing?

Hope it is.

Expected sum is not always exact. It is calculated by Kahan summation as in the published checker implementation.

My clar few days ago:

Q. In scoring, "Next, we calculate the expected sum S_e as precisely as we can" Is this mean S_e is the exact sum (after converting the inputs into binary64)?

A. The intent is that it is the closest possible binary64 value to the actual (infinite precision) sum.

... then, finding the exact sum with Kahan's algorithm is contradict with this answer, but will the checker fixed?

Is the checker numerically stable? Will it always add the same numbers to the same value?

I locally got a situation where printing extra stuff in the checker changes the sum that it computes. Maybe that's allowed in C++.

I also created a test where

`s{a,b,c} != s{s{a,b},c}`

, but I don't understand float->double->float casting enough to say if this is incorrect.The checker seems deterministic, why would the order of operations change?

Could you share this situation or describe how to reproduce it? I don't think it should be legal in this code in standard C++, at least with IEEE 754-compliant FP arithmetic.

Could you share this test? float->double->float roundtrip should be lossless.

Edit: The example yosupo provided answers all my questions; "GNU G++17 7.3.0" doesn't strictly adhere to IEEE 754.

This code prints

`1.00000000020000001655`

under "GNU G++17 7.3.0", and prints`1.00000000000000000000`

under "GNU G++20 13.2". In addition to that, if we add a printf like`printf("value: %.20lf\n", nums.top()); currResultSingle += static_cast<float>(nums.top());`

, the result changes to`1.00000000000000000000`

under "GNU G++17 7.3.0".Interesting. I was aware of this issue a while ago, but lately couldn't reproduce it so discarded the knowledge as no longer relevant in practice. Thank you!

ezthanks