flamestorm's blog

By flamestorm, 2 years ago, In English

Hi, Codeforces!

mesanu, SlavicG and I are very excited to invite you to Codeforces Round 944 (Div. 4)! It starts on 10.05.2024 17:35 (Московское время).

<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!

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

| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

FINALLY! I CAN SAY IT TOO.

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

hope my last rated div 4

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

Hoping for the best Div.4 Round!

»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

This will be mine first unrated contest.

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

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

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

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

»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Aiming to reach Pupil after this

»
2 years ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

<begin-copy-pasted-part>

</begin-copy-pasted-part>

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

what is the mean of "trusted participants"?

  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    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 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Do you have any idea why am I not being shown on the trusted participants' standings?

  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    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 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

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

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

»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

First unrated contest :)

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

Aiming to reach specialist this contest!

»
2 years ago, hide # |
Rev. 4  
Vote: I like it 0 Vote: I do not like it

html:

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

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

»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

My first official unrated contest :)

»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

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

»
2 years ago, hide # |
Rev. 5  
Vote: I like it +14 Vote: I do not like it

every div4)
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The queue is already so long.

Please don't hold div4 today.

»
2 years ago, hide # |
Rev. 3  
Vote: I like it -11 Vote: I do not like it

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

»
2 years ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

I hate D and E :sob:

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

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

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

    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 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, hide # |
Rev. 3  
Vote: I like it -8 Vote: I do not like it

TF wrong with my code

Problem E

extremely frustrating actually.

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

    try with long long. i use long double it gave WA 7 after changing it long long i got AC

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

      it worked for me although what's the diff b/w using long double and long long?

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

        i always fear of accuracy issue using non integers and that's i why never use them until it's extremely necessary, and i think there is some accuracy error in using double here. may be some experienced person can tell the actual issue.

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

    Your code may work slowly because you are using doubles although you don't need to, can you provide your full submission? based on your submission history you don't seem to have participated in this contest, quite weird.

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

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

»
2 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

I absolutely hate using doubles :(

Very nice problems btw :)

»
2 years ago, hide # |
Rev. 2  
Vote: I like it +10 Vote: I do not like it

is H 2-sat?

  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    It is.

  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    if it's, someone please give us the idea and the source code if it's available

    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      You can have at most one negative number in a column.

      Let's say X, Y, Z are the three elements in a column.

      In 2-sat terms, if X is negative, Y and Z must be positive. If Y is negative, X and Z must be positive. If Z is negative, X and Y must be positive.

      Submission: 260360108

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

        Slightly simpler: Just add the three clauses $$$X \lor Y$$$, $$$Y \lor Z$$$, $$$Z \lor X$$$, where $$$X$$$, $$$Y$$$, and $$$Z$$$ are the "actual" values of the variables (if $$$X$$$ is negative, then we take $$$\lnot X$$$ instead of $$$X$$$).

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

tough H

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

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

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

    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 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    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 years ago, hide # ^ |
       
      Vote: I like it +8 Vote: I do not like it

      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 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it +8 Vote: I do not like it

    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 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

what's the solution for problem H ?

  • »
    »
    2 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it +8 Vote: I do not like it

    Consider each column. Since there’s only 3 rows, you must have at least two $$$1$$$ in the same column. From this, you can see that if there exists a $$$-1$$$ in a column, then you must force the other two to be $$$1$$$. You can build 2-SAT clauses with this thought. Then you can solve 2-sat using any $$$O(n)/O(n^2)$$$ SCC algorithm.

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

See your grandpa without long long

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

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

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

What is the idea in problems G and F

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

    F: Binary search. Try to fix x = 1, 2, 3, 4, ... then find the range of corresponding y.

    G: Group all elements which have the same bit in their binary representation when divided by 4, then sort them.

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

    G: Since $$$a_i \oplus a_j \lt 4$$$ so there only $$$4$$$ values ($$$0, 1, 2, 3$$$). Let's call those values $$$c$$$. You can actually use dsu to merge $$$a_i$$$ and $$$c \oplus a_i$$$. But because these value is up to $$$10^9$$$. You can use a map to save $$$c \oplus a_i$$$'s index and merge their indices instead.

    Here is my implementation: https://codeforces.me/contest/1971/submission/260443847

»
2 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Testcase can not be longer than 256 KB

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

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

    Use generators.

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

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

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

        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 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it
          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 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            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 years ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

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 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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://codeforces.me/contest/1971/submission/260435081

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

    What do you mean by "precision issues"?

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

      I am working with the floating point numbers directly. Perhaps in the way I store them, or divide them, there is a problem

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

        Well, you don't need floating point numbers in this problem. Also, almost everytime you should avoid using them

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

          Lesson learned :')

          I just worked with speed = distance / time, since that's what I'm familiar with. Also didn't think Python would have a serious issue with it.

          But yeah. Going forward, I will try to minimize floats, divisions, and the like. Thank you!

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

            You can use distance // time (floor division). Usually, floating point numbers are a recipe for disaster, so only use them if you really need to. If possible, stick to integer arithmetic, and if you really need to, use double or long double instead (in C++).

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

What is wrong with my E solution? 260398566

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

    Hi Sayan, your solution is suffering from floating point errors. For example, if an answer is 6 exactly, your solution may produce 5.9999999999998, and therefore floor'ed to 5.

    Replace printing floor(ans) with floor(ans + 1e-6) makes your solution AC.

»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

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

https://codeforces.me/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 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    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 years ago, hide # |
Rev. 4  
Vote: I like it 0 Vote: I do not like it

why this submission got wa on t21

260348605

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

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 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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 years ago, hide # ^ |
    Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    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 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

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

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

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

Weak test cases for problem 'E'. Precision error was a nightmare.

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

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 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

amount of FST on E is quite frightening

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

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