ICPCNews's blog

By ICPCNews, 7 weeks ago, In English

text

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

REGISTER

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!

  • Vote: I like it
  • +196
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

Why was this postponed in the first place?

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

Is it rated?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    No

  • »
    »
    3 days ago, # ^ |
      Vote: I like it -56 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      so we should have an account on ICPC website?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I think so.

      • »
        »
        »
        »
        13 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck for all the participant.

»
2 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

How many tasks are there in this contest?

»
13 days ago, # |
  Vote: I like it +18 Vote: I do not like it

What about the T-shirts for the last challenge?

»
13 days ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it -44 Vote: I do not like it

it is rated?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +37 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the perfect score?

»
12 days ago, # |
  Vote: I like it +88 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +27 Vote: I do not like it

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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For some reason this is happening to random submissions :(

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
11 days ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it -42 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

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

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I second this

»
9 days ago, # |
  Vote: I like it +102 Vote: I do not like it

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.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

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

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it +48 Vote: I do not like it

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

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The standings changes so fast!

»
6 days ago, # |
  Vote: I like it +69 Vote: I do not like it

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

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1) Note that the actual binary64 value is not always exactly equal to the given decimal value. Instead, the actual given value is 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

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      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 infinity back to fp64?

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        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.

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

»
6 days ago, # |
  Vote: I like it +46 Vote: I do not like it

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

»
5 days ago, # |
  Vote: I like it +30 Vote: I do not like it

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

  • »
    »
    5 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    It seems to be consistent with C++ double and float.

»
2 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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!

»
2 days ago, # |
  Vote: I like it +110 Vote: I do not like it

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?

  • »
    »
    37 hours ago, # ^ |
      Vote: I like it -40 Vote: I do not like it

    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?

»
2 days ago, # |
Rev. 2   Vote: I like it +38 Vote: I do not like it

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.

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

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

»
35 hours ago, # |
  Vote: I like it +13 Vote: I do not like it

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?

»
28 hours ago, # |
  Vote: I like it +67 Vote: I do not like it

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.

  • »
    »
    12 hours ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    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.

    • »
      »
      »
      8 hours ago, # ^ |
      Rev. 3   Vote: I like it +24 Vote: I do not like it
      #include <iostream>
      #include <stack>
      
      
      using namespace std;
      
      // Calculate the fp32 sum sequence like {s:1,2,3}
      double calculateFp32(stack<double>& nums) {
          float currResultSingle = 0;
          while (!nums.empty()) {
              currResultSingle += static_cast<float>(nums.top());
              nums.pop();
          }
          return static_cast<double>(currResultSingle);
      }
      
      int main() {
          stack<double> s({1.0e-10, 1.0e-10, 1.0e0});
          double answer = calculateFp32(s);
          printf("%.20lf\n", answer);
      }
      

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

      • »
        »
        »
        »
        7 hours ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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!

»
23 hours ago, # |
  Vote: I like it -14 Vote: I do not like it
ez
»
23 hours ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

thanks