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?

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

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?

What about the T-shirts for the last challenge?

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.

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

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?

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".

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.

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

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.)

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?

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.

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.

terminelo profe

reduce the submission rate limits NOW or i riot

Will the tests really be completely different in the end or will some new tests get added?

I try to use Python Decimal library to calculate the more accurate results, but that seems different with the results calculated in checker. And Kahan will also lose precision during summation. Can I assume that we are not expected to calculate the most accurate answer, but the answer that matches the checker most?

For example, this self defined input: 5 -1.577492e-05 -2.576098e-05 3.994e-3 100000 -99999.3233. If we load them as double in python and sum through decimal, the result is 0.6806524640963445590490334732164390274533616321. But through checker the result is 0.68065246409969404339790344238281. There are several bits difference, which will lead to a big score downgrade in accuracy.

Queue is stuck. Both new solutions and the ones with ongoing testing aren't progressing at the moment

You are right, but we can't get verdicts as fast as before now.

So, can codeforces allocate only 10% to other submissions?

In this contest, you can never assume that you have achieved an absolute lead.

Dear problem managers, I would really appreciate if you would put some submission restriction.

the standing is on fire

Let’s send our North Korean homie Sung.An to world finals.

When can we see others solution?

Here is a graph showing ranking on the leaderboard vs. score, and how it changed between May 12 and just before the end of the contest, on May 23.

Here is an enlargement of the upper left corner.

I have provisional 6th place. My main idea for 5000+ points:

Build a binary tree, make sure to keep every block of 16 elements as one subtree. Greedily assign the fastest possible operation in every node (Half, Single, Double). Never decrease the type from child to parent. In random order, iterate leaves and greedily upgrade the operation type if it decreases the total error (this requires updating the path to the root, like in a segment tree). Now use meet in the middle: for each child of the root, consider $$$K \approx 10^5$$$ possibilities of what few changes we should make to slightly modify the result. Sort the possible results in two children of the root, use two pointers to find the best pair. Like in birthday paradox, this is actually like considering $$$K^2$$$ possibilities.

Improvements:

1. Make two phases of improvements: one from Half to Single, then from Single to Double. This way, each phase you need to get lucky with fewer bits.
2. The Half (fp16) type is very special because it always rounds towards 0. If all numbers are positive, you can't use this type because you almost always decrease the final sum. There are tests where almost all numbers are small and positive. You can use the few big (positive and negative) values to manipulate the sum. In particular, $$$60000 + 0.01 = 60000$$$ and $$$-60000 + 0.01 \approx -59970$$$. You can combine those two operations and again use something like meet in the middle.
3. Some greedy approaches like merging from smallest absolute value, or combining a positive with negative value if their absolute value is close.

I'm very afraid that the final tests will be so different that my algorithm (2) will be useless.

And I have no idea how the top 1-2 achieved their scores.

#1: Accepted [984 ms, 0 MB, 0 points]
#2: Accepted [952 ms, 0 MB, 0 points]
#3: Accepted [968 ms, 0 MB, 47.14 points]
#4: Accepted [1015 ms, 0 MB, 47.14 points]
#5: Accepted [1030 ms, 0 MB, 47.14 points]
#6: Accepted [1046 ms, 0 MB, 47.14 points]
#7: Accepted [1077 ms, 0 MB, 47.14 points]
#8: Accepted [1030 ms, 0 MB, 81.65 points]
#9: Accepted [1921 ms, 3 MB, 81.65 points]
#10: Accepted [953 ms, 0 MB, 47.14 points]
#11: Accepted [3858 ms, 3 MB, 59.63 points]
#12: Accepted [4765 ms, 5 MB, 62.471 points]
#13: Accepted [4874 ms, 92 MB, 63.344 points]
#14: Accepted [5562 ms, 162 MB, 63.362 points]
#15: Accepted [7702 ms, 253 MB, 63.37 points]
#16: Accepted [4687 ms, 92 MB, 77.972 points]
#17: Accepted [5374 ms, 164 MB, 77.971 points]
#18: Accepted [7124 ms, 256 MB, 77.997 points]
#19: Accepted [4749 ms, 93 MB, 81.298 points]
#20: Accepted [5296 ms, 163 MB, 81.176 points]
#21: Accepted [7015 ms, 255 MB, 81.192 points]
#22: Accepted [4749 ms, 93 MB, 81.394 points]
#23: Accepted [5249 ms, 164 MB, 81.523 points]
#24: Accepted [7155 ms, 255 MB, 81.535 points]
#25: Accepted [4749 ms, 97 MB, 81.436 points]
#26: Accepted [5374 ms, 166 MB, 81.533 points]
#27: Accepted [7124 ms, 259 MB, 81.532 points]
#28: Accepted [4749 ms, 100 MB, 81.447 points]
#29: Accepted [5093 ms, 161 MB, 81.46 points]
#30: Accepted [7250 ms, 261 MB, 81.524 points]
#31: Accepted [4686 ms, 94 MB, 81.418 points]
#32: Accepted [2155 ms, 125 MB, 81.621 points]
#33: Accepted [2671 ms, 181 MB, 81.64 points]
#34: Accepted [3733 ms, 295 MB, 81.642 points]
#35: Accepted [2218 ms, 126 MB, 81.622 points]
#36: Accepted [2436 ms, 155 MB, 81.641 points]
#37: Accepted [3796 ms, 297 MB, 81.643 points]
#38: Accepted [2139 ms, 126 MB, 81.623 points]
#39: Accepted [2983 ms, 211 MB, 81.637 points]
#40: Accepted [3859 ms, 300 MB, 81.643 points]
#41: Accepted [2187 ms, 125 MB, 81.62 points]
#42: Accepted [4718 ms, 93 MB, 81.388 points]
#43: Accepted [3561 ms, 0 MB, 57.711 points]
#44: Accepted [5234 ms, 163 MB, 81.275 points]
#45: Accepted [7139 ms, 254 MB, 81.352 points]
#46: Accepted [4796 ms, 97 MB, 81.283 points]
#47: Accepted [5265 ms, 167 MB, 81.348 points]
#48: Accepted [7217 ms, 258 MB, 81.381 points]
#49: Accepted [4764 ms, 101 MB, 81.23 points]
#50: Accepted [5265 ms, 162 MB, 81.289 points]
#51: Accepted [7312 ms, 261 MB, 80.951 points]
#52: Accepted [4765 ms, 93 MB, 70.176 points]
#53: Accepted [5578 ms, 164 MB, 72.095 points]
#54: Accepted [8077 ms, 256 MB, 78.445 points]
#55: Accepted [4812 ms, 97 MB, 79.891 points]
#56: Accepted [5702 ms, 165 MB, 65.472 points]
#57: Accepted [7531 ms, 259 MB, 74.913 points]
#58: Accepted [5030 ms, 101 MB, 74.111 points]
#59: Accepted [6109 ms, 162 MB, 70.467 points]
#60: Accepted [7359 ms, 261 MB, 79.901 points]
#61: Accepted [4671 ms, 94 MB, 81.22 points]
#62: Accepted [4796 ms, 92 MB, 79.363 points]
#63: Accepted [5515 ms, 164 MB, 79.404 points]
#64: Accepted [7655 ms, 255 MB, 79.327 points]
#65: Accepted [4812 ms, 97 MB, 79.066 points]
#66: Accepted [5468 ms, 168 MB, 79.115 points]
#67: Accepted [7484 ms, 259 MB, 79.339 points]
#68: Accepted [4890 ms, 101 MB, 79.515 points]
#69: Accepted [5343 ms, 163 MB, 79.28 points]
#70: Accepted [7578 ms, 262 MB, 79.083 points]
#71: Accepted [4796 ms, 94 MB, 79.244 points]
#72: Accepted [4999 ms, 4 MB, 57.642 points]
#73: Accepted [4515 ms, 39 MB, 55.839 points]
#74: Accepted [2625 ms, 3 MB, 58.974 points]
#75: Accepted [3765 ms, 4 MB, 61.72 points]
#76: Accepted [3031 ms, 39 MB, 63.812 points]
#77: Accepted [4436 ms, 3 MB, 53.402 points]
#78: Accepted [3389 ms, 38 MB, 49.236 points]

I didn't achieve good scores, but look at the spreadsheet I used to analyze my solutions! (this was the first time I used such simple technique as "visualize my results")

I want to share the testcase data I extracted using memory allocation I learnt from last ICPC challenge. It shows some distribution or feature of each testcase. The value is not accurate since I use square root or log10 for those large values, but you can know the rough magnitude. Here ld is long double, d is double, s is single, h is half. Also log is the log10 and error is the accuracy error calculated from score.

Are the standings final? I don’t believe the final tests have been run, but the scoreboard says final standings.

There is a bug in mingw-w64 implementation of scanf, which is used by the checker (Codeforces testing system is run on Windows). If you're using any method of input other than scanf and it's relatives, you'll sometimes get different last bit when reading numbers compared to what the checker sees. This results in a difference in the final sum between you and the checker if this bit is high enough. In this problem 1 bit of difference means you'll get half the points for the test. The probability of the bug is 1/4096 for numbers that are not representable exactly by long double (most decimals, e.g. 0.1, 0.12, 0.123,..). In my tests the probability was around 1/4300. I found this bug, because my sum and checker's sum were different in last bit on some of my random tests.

P.S. Apparently the bug only works if the number is written with less than 17 digits of precision. Otherwise we get 0 in first extra long double mantissa bit and everything is A-OK. So the bug is absent in all numbers from tests #16 and #10, because they have 19 digits of precision. But if there are long tests like #5 (with 7 digits of precision), there will be problems

P.P.S. Don't blame me for not telling everyone during contest. I wasn't aware of it until the last day.

Example: godbolt

#include <cstdio>

int main() {
    double val          =  1337.1337221 ;
    const char *str_val = "1337.1337221";
    
    double scanned;
    sscanf(str_val, "%lf", &scanned);
    if (scanned != val) {
        printf("⛔ %s ( %.13la != %.13la )\n", str_val, scanned, val);
    } else {
        printf("✅ %s\n", str_val);
    }
}

If you're using mingw-w64 (like Codeforces does), this will give you ⛔.

#include <cstdio>

int main() {
    double scanned;
    
#define test(val) \
    sscanf(#val, "%lf", &scanned); \
    if (scanned != val) { \
        printf("⛔ %-12s ( %.13la != %.13la )\n", #val, scanned, val); \
    } else { \
        printf("✅ %s\n", #val); \
    }
    
    test(12.34514011)
    test(1.23458561)
    test(.123456428)
    test(.0123456789) // ok
    
    test(1e126)
    test(2e126)
    test(3e126) // ok
    test(4e126)
    test(5e125)
    
    test(1337.1337221)
    test(1337.1337671)
    test(1337.1337) // ok

    test(666.124212)
    test(666.6642291)
    test(666.) // ok
    
    test(96.69e+109)
    test(60.09e-190)
    test(420.420e261)
    test(420.691789)
    test(69.420) // nice
}

Fun fact: there is no bug if you #include <stdio.h> instead of <cstdio>, but only if there are no other C++ headers included before it. The solution to this mystery lies in the depths of libstdc++ config/os/mingw32-w64/os_defines.h:l51

I used some very funny ideas:

Suppose we want to compute the exact sum $$$S_e$$$ with a mantissa of 52 bits. Then I first search for two input values $$$x$$$ and $$$y$$$ such that summing them in double precision gives a number with a mantissa that has the same bits as the 29 last bits of $$$S_e$$$. As in most cases $$$N^2 » 2^{29}$$$, $$$x$$$ and $$$y$$$ can be easily found in $$$\mathcal{O}(N \log N)$$$.

Now I can build a tree with the $$$N-2$$$ remaining values. My only condition for building this tree is $$$\texttt{float(T) + (x+y)} = S_e$$$, such that I just have to compute the sum of the remaining values with a precision of 23 bits instead of 52 bits. That way it's easier to use float summations.

But we can also repeat this process if $$$T$$$ can be cast to fp16. It's possible to search for two input values $$$z$$$ and $$$w$$$ such that $$$z+w$$$ has the same bits as the last $$$13$$$ bits of $$$float(T)$$$. That way I can compute a tree $$$T'$$$ with the $$$N-4$$$ remaining values such that $$$\texttt{float(fp16(T') + (z+w))} = \texttt{float(T)}$$$ That way I can compute $$$T'$$$ with a 10 bits precision and make it easier to use fp16 summation.

In the end my tree looks like $$$\verb|{d: {s: {d: {h:T'}, {d: z, w}}}, {d: x, y}}|$$$

There was no need for custom janky fp16. Both Intel and AMD have F16C extension since SSE2 times (2011-2012), it's supported by GCC 12+ and Clang 15+ as _Float16 and since C++23 as std::float16_t.

For small test, I ran some simple SA where I randomly move nodes around (keeping block of 16) and changing the type. For most tests, I am trying something a bit smarter:

• First I check what accuracy is needed in term of power of 2 (it is the exponent of the final sum — 52).
• For each value of the input, I compute the error if we cast them to float32 and float16. For each bit above the threshold computed above, I pick two values such as the error of the cast has its most significant bit matching.
• For each pair of value, I want want that provides me the option to increase the error, and one that can decrease the error. If both have the same sign, I can cast one of them and keep the other one alone.
• I move those values at the end, sorted by most signficant bit (higher first)
• I compute my initial error which depends on how many of those value have been cast, and I try to generate a tree with an error as small as possible.
• Finally I compute the total error, and I switch the cast on and off in order to progressively reduce the error to 0.

I needed a special case for the least significant bit where I need one of the two values to not be rounded up.

To build the tree:

• I select an order (randomly permute block of 16 and randomly permute within a blockl),
• I keep the current error
• Each turn I merge two adjacent nodes and replace them by the result in my list. Which nodes I pick is determined by in priority using float16 cast, and among all the option pick the one that would reduce my error the most (and if it does not, keep me in range of what can be corrected).

This work well for most seed from 11 to 71 (one exception at 42 I think) and 75/76, and for the other my SA works decently.

One issue here is that cast 16 only goes down (in absolute value) so when the input is all positive, we can't really use them unless we start with number that are close to a float16 to start with. The max score will usually be 63 there. For most other cases it's possible to achieve 81.

#1: Accepted [9061 ms, 460 MB, 0 points]
#2: Accepted [9062 ms, 460 MB, 0 points]
#3: Accepted [9093 ms, 460 MB, 47.14 points]
#4: Accepted [9078 ms, 460 MB, 47.14 points]
#5: Accepted [9062 ms, 460 MB, 47.14 points]
#6: Accepted [9093 ms, 460 MB, 47.14 points]
#7: Accepted [9077 ms, 460 MB, 47.14 points]
#8: Accepted [9093 ms, 460 MB, 81.65 points]
#9: Accepted [9077 ms, 460 MB, 81.65 points]
#10: Accepted [9078 ms, 460 MB, 47.14 points]
#11: Accepted [6842 ms, 460 MB, 61.284 points]
#12: Accepted [6827 ms, 460 MB, 62.833 points]
#13: Accepted [6874 ms, 471 MB, 63.141 points]
#14: Accepted [7671 ms, 494 MB, 63.139 points]
#15: Accepted [7765 ms, 505 MB, 63.138 points]
#16: Accepted [7109 ms, 470 MB, 79.471 points]
#17: Accepted [7374 ms, 488 MB, 79.386 points]
#18: Accepted [7077 ms, 500 MB, 78.668 points]
#19: Accepted [7000 ms, 471 MB, 81.595 points]
#20: Accepted [7218 ms, 488 MB, 81.599 points]
#21: Accepted [7562 ms, 499 MB, 81.591 points]
#22: Accepted [6968 ms, 470 MB, 81.611 points]
#23: Accepted [7577 ms, 488 MB, 81.631 points]
#24: Accepted [7280 ms, 499 MB, 81.636 points]
#25: Accepted [6890 ms, 470 MB, 81.614 points]
#26: Accepted [7577 ms, 488 MB, 81.635 points]
#27: Accepted [7952 ms, 500 MB, 81.638 points]
#28: Accepted [6921 ms, 471 MB, 81.615 points]
#29: Accepted [7343 ms, 488 MB, 81.633 points]
#30: Accepted [7343 ms, 500 MB, 81.638 points]
#31: Accepted [6983 ms, 470 MB, 81.616 points]
#32: Accepted [7280 ms, 471 MB, 81.604 points]
#33: Accepted [7249 ms, 494 MB, 81.604 points]
#34: Accepted [8015 ms, 500 MB, 79.35 points]
#35: Accepted [7171 ms, 472 MB, 81.594 points]
#36: Accepted [7171 ms, 494 MB, 81.62 points]
#37: Accepted [8234 ms, 500 MB, 81.627 points]
#38: Accepted [6968 ms, 472 MB, 81.531 points]
#39: Accepted [7749 ms, 489 MB, 81.59 points]
#40: Accepted [8406 ms, 500 MB, 81.627 points]
#41: Accepted [7155 ms, 472 MB, 81.216 points]
#42: Accepted [7030 ms, 470 MB, 81.614 points]
#43: Accepted [9077 ms, 460 MB, 57.711 points]
#44: Accepted [7124 ms, 488 MB, 81.635 points]
#45: Accepted [7296 ms, 499 MB, 81.641 points]
#46: Accepted [6890 ms, 470 MB, 81.617 points]
#47: Accepted [6984 ms, 488 MB, 81.635 points]
#48: Accepted [7874 ms, 500 MB, 81.64 points]
#49: Accepted [6890 ms, 471 MB, 81.618 points]
#50: Accepted [7124 ms, 488 MB, 81.635 points]
#51: Accepted [7218 ms, 500 MB, 81.641 points]
#52: Accepted [6937 ms, 470 MB, 80.228 points]
#53: Accepted [7624 ms, 494 MB, 81.5 points]
#54: Accepted [6968 ms, 505 MB, 81.598 points]
#55: Accepted [7062 ms, 472 MB, 81.615 points]
#56: Accepted [7328 ms, 490 MB, 63.234 points]
#57: Accepted [7031 ms, 500 MB, 81.584 points]
#58: Accepted [6905 ms, 471 MB, 81.571 points]
#59: Accepted [7671 ms, 488 MB, 81.597 points]
#60: Accepted [7453 ms, 500 MB, 81.626 points]
#61: Accepted [6999 ms, 470 MB, 81.61 points]
#62: Accepted [6952 ms, 470 MB, 80.919 points]
#63: Accepted [7514 ms, 494 MB, 80.842 points]
#64: Accepted [7202 ms, 499 MB, 80.876 points]
#65: Accepted [6937 ms, 472 MB, 80.855 points]
#66: Accepted [7530 ms, 494 MB, 80.941 points]
#67: Accepted [7421 ms, 500 MB, 80.865 points]
#68: Accepted [7234 ms, 472 MB, 80.752 points]
#69: Accepted [7686 ms, 488 MB, 80.959 points]
#70: Accepted [7218 ms, 500 MB, 81.018 points]
#71: Accepted [6984 ms, 471 MB, 80.903 points]
#72: Accepted [9093 ms, 460 MB, 56.599 points]
#73: Accepted [9140 ms, 462 MB, 49.905 points]
#74: Accepted [9078 ms, 460 MB, 67.463 points]
#75: Accepted [6874 ms, 460 MB, 73.534 points]
#76: Accepted [6890 ms, 465 MB, 74.169 points]
#77: Accepted [9077 ms, 460 MB, 49.55 points]
#78: Accepted [4906 ms, 471 MB, 46.998 points]

my best submission scored 5k+ points, but the last one was 4k+, can I contact someone to solve this problem?(

Is it still possible to register on the ICPC website? I don't know where to find the competition there.

When will the system test be conducted?

P/s: Nice contest, and there are quite a lot of simple but efficient solutions in the comments which really amaze me :).

I want the system to be able to test both the last commit and the highest scoring commit, so that people like me who scored low on the last commit will not lose the score they deserve.

It seems that the final judging is over and the tests are very similar. I guess that organizers used the same generator method, just with different seeds. Here are some statistics, assuming that nothing will change.

maxplus didn't lose many points and thus climbed to the first place, congrats. The top10 didn't change but the threshold dropped around 60-70 points. Three new people got into top30, and obviously three people dropped down.

When I execute my code on my self-generated random test with N = 10^6 and each number has the form A.BCDEFGHIJKLMNOPQRSTeX where -300 <= X <= 300, it takes over 9 seconds to finish (and I got more than 47.14 points which indicates perfect accuracy). However the same code run for less than 5 seconds on each test of the organizer. Does that mean the final system tests are still weak somehow?

Is there going to be any plagiarism tests before the prizes are distributed or should I lose hope as I placed 205 ;(

Hi, everyone! I've finished 9th this time. And this was by a margin the hardest contest for me so far.

I had a kind of unique approach from the start and faith in it until the very end. But I was struggling so hard to guess the correct way of calculating fp16 addition, so basically I started to optimize something only on 11th day, after the checker's code was published :)

Let me share the idea with you. First of all, I split the input array into two parts.

1. First part consists of 90-97.5% of elements. The main goal is to get the minimum W as possible, keeping an absolute error relatively low

2. Second part is the "compensator". Let's build a balanced tree. Leafs are elements, internal nodes are operations. All the internal operations are fp64, and only the lowest level of operations (between two leaves) might be fp32 or fp16. We can approximate desired error almost transparently by choosing between different type of operation on the lowest level (other operations on the path to the root of the tree are fp64, so we usually don't lose any precision there)

The main challenge is how to keep the absolute error in the first part relatively low. You can notice that rounding during fp16 addition always truncate the result towards zero. It's not a problem if array is balanced in terms of the number of positive and negative elemtents. So actually the main problem is how to use as much fp16 operations as possible if array is not balanced at all

Without loss of generality, let's consider that the array consists only of positive number.

Consider following approach:

• Split the array to some number of blocks of predetermined size (let's say blockSize = 16 to get rid of random memory access penalty)

• Sum up all the elements in each block constructing a balanced tree using as much fp16/fp32 operations as possible. We almost don't care about resulting error right there

• Sum up all the blocks one by one choosing between fp32 and fp64. We should pick fp32 only if rounding helps to lower the error. The "compensated" amount of each step is the rounding error, which clearly depends on magnitude of addendums. But this is a good news since all the elements are positive, partial sum will increase after each step, so we would compensate bigger amount closer to the end of blocks summation process

This approach allows us to get a relatively low resulting error (which most probably might be compensated by the second part) even if all the elements have the same sign. In worst case scenario we have to skip some worst (in terms of increasing error) fp16 operations during blocks sum calculation

the ones who does not have positive contribution can not make a comment with image ****

thank you

Just so you just realize how useless and impractical this task is:

If you round numbers in fp16 you never reduce the error => using replacing fp64 with fp16 you only increase the answer.

Is it logical that fp32 should also not reduce the answer? Yes.... but a bunch of bugs in the author checker changes the problem dramatically.

As it should be: We use fp64 to somehow reduce the answer, then use fp16, fp32 to increase it. And the task is to gnaw the scores, because it is really hard to do it (even ~55 on a random test). Butooooooooooooooooooooooooooo, we have a different task. We have fp64, which can calculate the answer very slightly inaccurately. We have fp16, which only increases. And there's fp32, which doesn't know how to behave at all.

And as if a task in which we would have to think about rounding and how it works is even slightly meaningful. But a task where we???????? where we can make random changes in the response thanks to incorrect authoring code is a task that can never be applied anywhere.

I was expecting a problem to minimize the error, but it turned out to be a problem to cancel the error knowing the accurate answer. Still a fun problem, but it seems not as useful in practice as advertised (they said "addressing this challenge", not "a problem inspired by this challenge"). It would be surprising to me if the organizer could use any of the algorithms in this contest on their chips.