Блог пользователя flamestorm

Автор flamestorm, 2 года назад, По-английски

Hi, Codeforces!

mesanu, SlavicG and I are very excited to invite you to Codeforces Round 944 (Div. 4)! It starts on May/10/2024 17:35 (Moscow time).

<begin-copy-pasted-part>

The format of the event will be identical to Div. 3 rounds:

  • 5-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

<end-copy-pasted-part>

Thanks a lot to the testers: Dominater069, nika-skybytska, ScarletS, Gheal, BucketPotato, JustJie, htetgm, Vladosiya!

We suggest reading all of the problems and hope you will find them interesting. Good luck!

UPD: Editorial is out!

  • Проголосовать: нравится
  • +161
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
 
Проголосовать: нравится +20 Проголосовать: не нравится

FINALLY! I CAN SAY IT TOO.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

hope my last rated div 4

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Hoping for the best Div.4 Round!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

This will be mine first unrated contest.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

hoping i can get pupil rank after this contest (and flamestorm orz btw)

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I wish all trusted participants good luck and to learn something new from this contest!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Aiming to reach Pupil after this

»
2 года назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

What happens if I register to a contest and didn't show

»
2 года назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

<begin-copy-pasted-part>

</begin-copy-pasted-part>

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

what is the mean of "trusted participants"?

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    To qualify as a trusted participant of the fourth division, you must: take part in at least five rated rounds (and solve at least one problem in each of them), do not have a point of 1400 or higher in the rating.

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    Only trusted participants are included in the official standings table, and their performance will be used for rating calculations for all rated participants. Therefore, if you are not a trusted participant, your performance will not be used for rating calculations in the round.

    This can prevent certain users, such as those with alternative accounts, from disrupting the round since they are not trusted participants.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

NO Green Tester !!!!!!!!!!!!!!!! flamestorm

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Letssz goo finally a great round that is coming! Nicee!!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

First unrated contest :)

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Aiming to reach specialist this contest!

»
2 года назад, скрыть # |
Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

html:

<copy-pasted-part>
</copy-pasted-part>

Also: where's <img src="photo/writer-and-tester">

»
2 года назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

As a tester, I hope all of you guys have fun and the trusted participants would get the dubs!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

My first official unrated contest :)

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

wishing good luck to all participants. i can't participate due to an exam tomorrow sadly.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Me[being happy] who kept my rating for this round!!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

It's my first Div4 contest hopefully I will done more than 3 problems InshaAllah

»
2 года назад, скрыть # |
Rev. 5  
Проголосовать: нравится +14 Проголосовать: не нравится

every div4)
»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

The queue is already so long.

Please don't hold div4 today.

»
2 года назад, скрыть # |
Rev. 3  
Проголосовать: нравится -11 Проголосовать: не нравится

At the beginning, there was a long queue, but fortunately after some minutes, it fixed

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

wasted so much time in problem D corner case . how to Solve F ????

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Find the least value of x which satisfies the condition for some y(using binary search) then check while incrementing x check if it is a lattice point or not, if it is, ans+=4 as (all 4 quarants), else move to next value of y.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I created video editorial for G: XOUR. Here's the code associated with the video.

»
2 года назад, скрыть # |
Rev. 3  
Проголосовать: нравится -8 Проголосовать: не нравится

TF wrong with my code

Problem E

extremely frustrating actually.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me why my submission is wrong for problem E.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

I absolutely hate using doubles :(

Very nice problems btw :)

»
2 года назад, скрыть # |
Rev. 2  
Проголосовать: нравится +10 Проголосовать: не нравится

is H 2-sat?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

tough H

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Couldn't solve D. Can someone please explain how to approach it?

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Count the number of positions i where s[i] != s[i+1]. Reduce the answer by 1 if there exists at least one position where s[i] equals 0 and s[i+1] equals 1.

  • »
    »
    2 года назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    count how many $$$groups$$$ of consecutive zeros and ones are present, this can be done by checking $$$s[i] != [i+1]$$$.

    Then you have 3 cases:

    • case 1 : you have more than 2 groups, the answer is always $$$groups-1$$$ ( you can always merge two groups together )

    • case 2 : you have exactly to groups, either the two groups are in the correct order, so the answer is $$$1$$$, or they are in reverse order, so the answer is $$$2$$$.

    • case 3 : you have exactly one group, so the answer is $$$1$$$.

    • »
      »
      »
      2 года назад, скрыть # ^ |
       
      Проголосовать: нравится +8 Проголосовать: не нравится

      CASE 1 got me bad.

      I was trying to think of scenarios where a group like 00..11.. could be used to combine two individual groups of 00... and 11... Now writing this comment, its obvious it should be groups-1

      Thank you for sharing the approach :)

  • »
    »
    2 года назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится +8 Проголосовать: не нравится

    There are many ways to solve this problem, and some of them are quite overthought. One can observe that the answer is $$$max(1, numberOfTransitionsFrom0to1) + numberOfTransitionsFrom1to0$$$. Code:

    string s; cin >> s;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < s.size()-1; i++) {
        if (s[i] == '1' and s[i+1] == '0') cnt1++;
        if (s[i] == '0' and s[i+1] == '1') cnt2++;
    }
    cout << max(1, cnt2) + cnt1 << "\n";
    
»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

what's the solution for problem H ?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

See your grandpa without long long

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I tried to hack this submission, but it showed "Unexpected verdict". What happened??

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What is the idea in problems G and F

»
2 года назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Testcase can not be longer than 256 KB

Why this restriction as long as my testcase is valid ? Do it a mb atleast

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Use generators.

    • »
      »
      »
      2 года назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      So output.txt file generated with my code is bad ?

      • »
        »
        »
        »
        2 года назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        When you submit a hack, you can upload a generator (a program that prints the input) instead of the input data itself. This way you can submit a hack that has bigger input data.

        • »
          »
          »
          »
          »
          2 года назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          Spoiler

          I used new line at end of input, Still some sort of error >> Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin, line 1)]. First time trying it so might be something silly

          • »
            »
            »
            »
            »
            »
            2 года назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

            You must format the input data so that it exactly matches the format given in the problem statements, including newlines and spaces. Also, you must not print trailing spaces at the end of the line (each line must end with a non-space character).

            It might be a good idea to start with smaller input data, so you can check your input locally.

»
2 года назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

if problem F removes this statement "The sum of r over all test cases does not exceed 1e5". Does anyone have a solution that can pass it?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Anyone using Python to solve E? I can't get this to pass for some reason :( WA on T2. I think it might be precision issues, but I refuse to believe Python suffers from them as well, at least not on a Div 4. E

https://mirror.codeforces.com/contest/1971/submission/260435081

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What is wrong with my E solution? 260398566

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

is H red problem? I do think it's orange at least just by looking # of solve

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Wrong answer on test 35, whats wrong here? I have tried adding 1e-6 too.

https://mirror.codeforces.com/contest/1971/submission/260462886

Ambiguous questions like this should not be a part of div 4 contests for beginners. I spent 90 mins on this problem with multiple wrong answers, I was very close to smashing my laptop at the end.

  • »
    »
    2 года назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    never use floating point, instead simplify your computation in single fraction (numerator)/(denominator) consists of only integer operator. for example a / (b / c) = (a * c) / b

    I had exact same issue and it completely ruined contest experience.

»
2 года назад, скрыть # |
Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

why this submission got wa on t21

260348605

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

In Problem E ,I submitted the following code : My Submission

but it gives wrong answer on test case : 1 6 1 1 6 45 2

the expected output is 15 but my code's output is 14

When i debug my code, i found that whole error occurs in the line long long ans=floorl(time); bcoz the value of time before was 15 but after taking floorl it became 14.I don't understand why this is happening on my system and also on online judge.Is this a bug of C++ 20?? or i have done something wrong in my code.I have also used fixed<<setprecision(0) to avoid printing of answer in scientific notation like 1e9 instead of 1000000000 . But it does not affect my answer but floorl does. Kindly help me out and explain this unexpected behaviour of floorl which can be used for long double numbers as per documentation.

»
2 года назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Problem F reminded me of my Computer Graphics course, where we discussed how to draw a circle efficiently on the screen. (It involves avoiding FP computation and replacing multiplication with addition.)

So my solution works as follows. Let point P start at $$$(0, r)$$$. For every step, checks if $$$P$$$ falls in the range. Then, P moves to the right 1 unit, and if $$$|OP| \ge r+1$$$, revert the previous move and move P down 1 unit instead. Repeat until you reach $$$(r, 0)$$$, and multiply the answer by 4.

Code

This algorithm works because the width is 1. The reason why CG introduced this algorithm is that it never requires calculating the $$$|OP|^2$$$ by performing 2 multiplications, but you can instead calculate the increment of $$$|OP|^2$$$ in O(1) additions for each iteration.

  • »
    »
    2 года назад, скрыть # ^ |
    Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    It's interesting that we competitive programmers work on the level of big-O, avoid letting the constant factor determine what solutions get AC instead of TLE. But CG course together with Parallel Distributive Computation (another course this semester) show us a big optimization on the constant will determine who's SOTA in practice, and I feel those engineers "One clock cycle (or I-O bandwidth, network communication, warp utilization in GPUs...)matters!"

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Hey! Check out my video solutions for the contest. I've covered Problem A-G. https://youtu.be/WBECy_7Ux0I

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problem E has to be (div.0 — E), not (div.4 — E) because of precision errors...

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Hi, can someone explain why my solution for E doesn't work. I used doubles carefully but still got WA on test case 12.

Thanks.

260363341

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Not careful enough:(

    Perhaps add a really tiny eps can work, like 1e-11(the value of a correct eps is totally arbitrary and hard to calculate). But it's better to use integer types and not to use double or even long double.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Number of ACs in problem E has nearly halved after the main test:(

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

amount of FST on E is quite frightening

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why are submssions after the contest in queue for such a long time???