flamestorm's blog

By flamestorm, 3 weeks ago, In English

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, nskybytskyi, 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

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

Let's Go !

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

FINALLY! I CAN SAY IT TOO.

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

contest after a long time !!

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

hope my last rated div 4

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

Hoping for the best Div.4 Round!

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

    it was worst

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

      it wasn't

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

        yes it was

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

          but why, where's the reasoning? right now it looks like you're just disappointed that you solved only 2 problems

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

            because it was so boring to solve the first 2 that I started to fall asleep

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

              div4 a-c are always like that. interesting tasks start are e-h, but icpc rules force you to solve this easy tasks first

              but i do get your poing

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

                yesterday I solved C and D from that div.4 from first! But not in the contest :( >_<

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

This will be mine first unrated contest.

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

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

»
3 weeks ago, # |
  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!

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

Aiming to reach Pupil after this

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

It's going to be my first contest, wish me luck. Hope to solve atleast A and B.

»
3 weeks ago, # |
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

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

    Close your eyes,what do you see?

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

    In Codeforces, it is considered that you've not participated. So nothing happens.

    In some platforms like AtCoder and Leetcode, if you've registered, then they'll consider your participation with 0 problems solved and you'll lose your rating.

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

<begin-copy-pasted-part>

</begin-copy-pasted-part>

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

I am excited for this contest.

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

what is the mean of "trusted participants"?

  • »
    »
    3 weeks ago, # ^ |
      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.

    • »
      »
      »
      3 weeks ago, # ^ |
        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?

  • »
    »
    3 weeks ago, # ^ |
      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.

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

    This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the third 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 1900 or higher in the rating.

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

Wow, Div4 after a long time. The server is gonna cry handling such a huge participants. Haha

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

    IT ACTUALLY DID. THEY CREATED THREE INSTANCES OF THE CONTEST IN THREE DIFFERENT WEBSITES TO MAKE IT SMOOTH.

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

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

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

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

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

First unrated contest :)

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

Aiming to reach specialist this contest!

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

First unrated. :)

»
3 weeks ago, # |
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">

»
3 weeks ago, # |
  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!

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

    How can I become a tester too :(

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

      Befriend a setter or another tester.

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

        Wanna be my friend? ;)

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

        Even Yukana Nogami would want me to be a tester :(

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

That's awesome! It's exciting for Div 4 to get closer to becoming the closest to Pupil Coder!

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

My first official unrated contest :)

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

    Me too! Now I don't have to stress about negative delta... good luck not dropping to pupil haha.

»
3 weeks ago, # |
  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.

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

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

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

Why for me in the contestants page it is showing as official participant(No asterisk beside the handle name)?

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

Good luck to everyone! Hope everyone reaches their desired level.

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

But due to two ongoing contests, the online judge of CF is already very slow. Not sure how slow it will be in today's contest !!

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

    I hope it runs on a separate server or... we have to wait forever xd

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

Hope for short queue :)

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

Would I reach cyan? Superman asked.

»
3 weeks ago, # |
  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

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

Finally!

»
3 weeks ago, # |
Rev. 5   Vote: I like it +14 Vote: I do not like it

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

The queue is already so long.

Please don't hold div4 today.

»
3 weeks ago, # |
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

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

I hate D and E :sob:

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

In F were we supposed to use binary search to find squares or such . I was getting very close answers from it ?

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

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

  • »
    »
    3 weeks ago, # ^ |
      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.

»
3 weeks ago, # |
  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.

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

TF wrong with my code

Problem E

extremely frustrating actually.

  • »
    »
    3 weeks ago, # ^ |
      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

    • »
      »
      »
      3 weeks ago, # ^ |
        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?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          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.

  • »
    »
    3 weeks ago, # ^ |
      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.

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

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

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

    Your bound on r for the binary search is wrong, since you have an array of size k + 1 and it is only k.

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

      I am not using the binary search function i created, i was using lower_bound().

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

        check this submission

        I used the binary search function you made, and added a check for if d is exactly one of the points in a in order to not get out of bounds when d == n, and it passed. I'm not sure, but a lot of solutions seem to be getting WA on test 2 for using the inbuilt lower_bound() / upper_bound() functions, so I didn't use them.

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

          Thank you so much!!

          I actually doubted myself and went for lower_bound() should have used it, anyways something to take away always. :)

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

    try cout<<tot_t + dis/speed<<" ";

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

      It will result in double, I have to print Integers.

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

        No it will print an integer because dis in an integer

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

          You are free to use my code and check it on your own.

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

I absolutely hate using doubles :(

Very nice problems btw :)

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

    which problem requires double?

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

      I am also thinking the same.

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

      I used doubles in F (for sqrt), for finding suitable Y-coordinates.

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

        bro you can square the whole equation and there will be no need for double

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

What is wrong with my sol to E , here is my submission: 260421810

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

    use multiplay instead of division don't calculate the speed first

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

Problem E sucked the living soul out of me.

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

is H 2-sat?

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

    It is.

  • »
    »
    3 weeks ago, # ^ |
      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

    • »
      »
      »
      3 weeks ago, # ^ |
        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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          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$$$).

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

tough H

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

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

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

    First you need to divide the string into subsegments of 0s and 1s let this number of subsegments be "m" and then try to see if a subsegment of the form "0000...1111" is possible.This can be done by checking if a 0 segment occurs before a 1 segment.If yes the answer is min(1,m-1) otherwise, the answer is m. My Submission.

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

      Thanks for sharing the code. I am not used to C++ code so it felt a bit daunting but i understood the approach :)

  • »
    »
    3 weeks ago, # ^ |
      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.

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

      Yes, I was thinking the same way in contest but went too deep in thinking it.

      Now implemented THIS and it works.

      Thank you for sharing :)

  • »
    »
    3 weeks ago, # ^ |
    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$$$.

    • »
      »
      »
      3 weeks ago, # ^ |
        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 :)

  • »
    »
    3 weeks ago, # ^ |
    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";
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for sharing, many solutions have used the same formula. Tough luck I couldn't think of it during the contest.

      Will try harder next time :)

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

what's the solution for problem H ?

  • »
    »
    3 weeks ago, # ^ |
    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.

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

Can someone please explain, in a clear way, how to round down the answer to the nearest integer in E?

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

    just make a normal division with integers. C++ division is floor for integers so no need to do somehting else

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

    just calculate everything with long double and floor the answer at the end .

    I also didn't get it during the contest .

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

Mehnn, this was a horrible ahhh contest for me.

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

See your grandpa without long long

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

Question E:Round up==floor,It's hilarious,

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

Why is it that the question of question E is reluctant to explain that the answer needs to be rounded down, but it is biased to say rounding?

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

what is wrong with this submission for E WA test 7 I used floor https://codeforces.com/contest/1971/submission/260428874

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

why was my submission for E failing when I was calculating the speed in long double ?

260353980

please go through once

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

.___.

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

Vote for making the contest unrated. For first 30 mins, I was merely able to access the website. It was slow AF. Images in the questions were also not getting loaded.

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

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

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

What is the idea in problems G and F

  • »
    »
    3 weeks ago, # ^ |
    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.

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

    G: Since $$$a_i \oplus a_j < 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.com/contest/1971/submission/260443847

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

"YEAH , this totally makes sense" T-T

https://imgur.com/a/dtdO5DN

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

    Precedence. First you do * and then / in the AC line.

»
3 weeks ago, # |
  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

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

    Use generators.

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

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          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.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            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

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              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.

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

              Got it, Maybe next time... Thanks

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

my code was right but when i wrote same code with difference that i stored ans and than printed my code gets wrong what is wrong TLE code 260349567- NEW wrong code:-> 260433835

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

I had D wrong and i have no idea why, when I checked my submission and what was wrong with it, it said that line 20 differs and instead of 3 i had 2 but when i checked the line 20 input it was 0101 and u can reach this by moving 0 infront or behind 2nd zero or by moving 1 infront or behind 2nd 1. Can any1 explai to me why was i wrong. This is my code btw

import math from collections import deque t = int(input()) for _ in range(t): b = list(input()) r = 1 for x in range(len(b)): if b[x] == '0' and x != 0: if b[x-1] == '1': r += 1 print(r)

Thx

»
3 weeks ago, # |
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?

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

    What if we just hardcode the right answers for all possible r?

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

      well, I think this source code will exceed 64kB, the limit of codeforces.

»
3 weeks ago, # |
  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.com/contest/1971/submission/260435081

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

    What do you mean by "precision issues"?

    • »
      »
      »
      3 weeks ago, # ^ |
        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

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

        I was just able to solve it. Yes, it was float stuff.

        For each interval [a[i], a[i+1]], I was keeping track of the speed of crossing the interval. Then, in my binary search function, I made use of this speed to find the time taken to reach the query point in the interval. That was enough, it seems, to mess everything up.

        I solved it by replacing the calculations involving "speed" (for example, time_taken_to_reach_query_point = (q — a[i]) / "speed") with the (distance / time), and then did regular arithmetic with the fractions. This passes the testcases

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          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

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            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!

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              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++).

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

What is wrong with my E solution? 260398566

  • »
    »
    3 weeks ago, # ^ |
      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.

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

      whats the idea behind taking 1e-6 only ? why not 1e-7 or 1e-5 ?

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

        It's arbitrary. To prevent getting hacked I would suggest you use a more tiny value.

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

          this value depends on the test cases right ? like 1e-6 might work on some test case but might fail if there is a test case that depends on more than 6 floating point right ?

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

      thanks! that worked. Here I was scratching my head finding logical errors :(

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

        you can use multiplay instead of division also a/(b/c) -> ac/b

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

          which part are you talking about?

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

            you are calculating the speed first alone right ? and then you do distance/speed

            you can avoid that by multiplying the denominator of the speed with the distance

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

I wrote this code for problem F During the contest.. But now I really have no idea way it works !!!!!!

void calculate() {
    int r;
    cin >> r;
    int ans = 2;
    for(int x = -1*r; x <= r; x++) {
        ans += ((int)sqrt((r+1)*(r+1)-x*x-1)-(int)sqrt(r*r-x*x-1))*2;
    }   
    cout << ans << endl;
}

There is a case when r*r-x*x-1 becomes negative and then sqrt(negative) !!

I didn't notice that during the contest but I am really surprised to see it works!

the second thing is why the answer is 2 ? when I wrote this weird solution I noticed that it got the right answer — 2 so I added 2 to the answer

Very weird

»
3 weeks ago, # |
  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

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

    I got to orange by solving all other problems in under 50 minutes. So probably high orange — low red(2300/2400).

    A — 800 (700 if was available)

    B — 800

    C — 800

    D — 900

    E — 1200

    F — 1500

    G — 1500

    H — 2300

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

      My predictions for problems are: A 800 B 800 C 800 D 1000 E 1500 F 1600 G 1600 H 2100

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

        G was easier then F

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

          Yes, but I'm talking about cf rating distribution

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

            ohh sure.. but i still didnt understand F

»
3 weeks ago, # |
  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.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.

  • »
    »
    3 weeks ago, # ^ |
    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.

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

    don't smash your laptop :v

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

My code for problem F doesn't do it correctly for r = 100000. Is this an edge/special case or do I just need broader range to store the integer

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

i want to share something in this contest my friend found some similarities on second problem solution. we both used to learn algorithms from the same mentor hence there is very large possibility that we both have same approach. since he is in his hometown so we have no contact right now,but he texted me that my code is similar to his so to clearify the doubt i am writing this. again it is very simple string problem and lot of people shares the same approach of finding the first different element and swapping it may common in lot of candidates.

thanks.

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

why this submission got wa on t21

260348605

»
3 weeks ago, # |
  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.

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

    multiply all numerators first then divide.

    long double time=b[ind-1]+((dis-a[ind-1] * (b[ind]-b[ind-1]))/(a[ind]-a[ind-1]));

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

      ok,but i don't get the logic behind it.Why not this way works??

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

        (distdif/timedif) this operation itself is having some precision error.

        when it is multiplied by some constant the error increases.

        to avoid multiplication of error. multiply numerators which is error free operation, then divide.

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

I am below 1400, why am I considered unrated or the ratings aren't updated yet?

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

How long does it take to update the ratting normally? As I attended for the very first time, I am very much curious.

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

I got hacked on the question 'E' but the same test used in hacking is giving me correct answer on my machine. How can I tell this to codeforces or justify my point?

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

div 4

»
3 weeks ago, # |
  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.

  • »
    »
    3 weeks ago, # ^ |
    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!"

»
3 weeks ago, # |
  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

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

E was such an easy problem but precision errors spoiled it. I literally kept getting a wrong answer on test 7 and it just wouldnt work. Now even after some changes when it worked and got accepted, my solution got hacked. Now i am genuinely pissed.

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

    Before the system testing my rank was at 3000 (I didn't solve E), but now i'm at 500 .

    Precision error really got everyone .

»
3 weeks ago, # |
  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...

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

1

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

Is it me ? Or the system testing is taking way longer than usual ?

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

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

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

Wish didnt see the "rounded down" in E.

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

why the rating is not update till now!!

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

could someone please tell me what the wrong with my solutions in question E

i do not understand what wrong with it

:)

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

    Multiply all numerators first then divide.

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

      thanks it worked

      but why divide then multiply make precision error but Multiply all numerators first then divide not?

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

        (distdif/timedif) this operation itself is having some precision error.

        when it is multiplied by some constant the error increases.

        to avoid multiplication of error. multiply numerators which is error free operation, then divide.

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

    I'm not sure but try changing (...) * (double)(d - a[index]) to (double)(d - a[index]) * ...

    make sure to remove the parentheses like i did.

    The reason why is that in your submission the code will do the division first than multiply the result .But that leads to precision error .

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

      i try it and i worked

      thanks

      but how precision error happen in my first code and not in the second code ?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        think of it as doing the operation on the numbers from left to right .

        I will give an example with addition .

        what would 1.1 + 2.2 == 3.3 be from the compiler's perspective (True or False).

        short answer is False even tho when you cout them .Both equal 3.3

        I will give you another example but it's not very accurate .

        Let's take multiplication and division now.

        6*1/6 and 1/6*6

        the compiler will see this

        (1/6)*6 = 0.16666(infinitly) * 6 = 0.9666666... round down to 0 .

        (6*1)/6 = 6/6 = 1.0 round down to 1 .

        when i said 0.666(infinitly) i lied the compiler makes it equal 0.66666667

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

Can someone tell why the rating is not updated of this contest!!

  • »
    »
    3 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    The system testing is at 98% right now . it should be done in an hour.

»
3 weeks ago, # |
  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

  • »
    »
    3 weeks ago, # ^ |
      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.

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

      Ohh, thank you. Won't forget that (especially after failing system tests cuz of it :p)

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

    change double to long double . I tested it on some cases and worked fine.

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

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

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

    Problem E has successfully planted the fear of floating point numbers in my mind :|

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

so when the rank and rating get updated?

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

amount of FST on E is quite frightening

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

My Ranking in standing list is 3590 while at my contest list it's 4688 (which effect my rating changes) why?

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

    This was either due to unofficial participants, or due to participants who were skipped after system testing, or due to those who were hacked within 24 hours after the contest. So don't worry , be happy.

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

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

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

I can't believe I'll be green soon!

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

Aiming to reach Pupil.

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

1971E - Find the Car For this question here is my solution. I feel it is correct in logic. What you guys feel about the mistake in my code. It is showing WA on Testcase 23.

// Shanmukh
#include <bits/stdc++.h>
#define ll long long int
#define pub push_back
#define endl '\n'
#define fastio() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ss second
#define ff first
#define mod 1000000007
using namespace std;
void solve() 
{
  ll n,k,q,d;
  cin>>n>>k>>q;
  vector<ll> a(k+1),b(k+1);
  a[0]=0;
  b[0]=0;
  for(ll i=1;i<=k;i++)
  {
    cin>>a[i];
  }
  for(ll i=1;i<=k;i++)
  {
    cin>>b[i];
  }
  for(ll i=0;i<q;i++)
  {
    cin>>d;
    //ind is first index where a[index] is less than or equal to d.
    ll ind = upper_bound(a.begin(),a.end(),d)-a.begin()-1;
    double req=0;
    req=req+b[ind];
    double further = d - a[ind]; //further distance from the just visited toll gate
    if(further!=0) req=req+((further/(a[ind+1]-a[ind]))*(b[ind+1]-b[ind]));
    if(req>=(ll)req) cout<<(ll)(req)<<" ";
    else cout<<(ll)(req)-1<<" ";   //Cases to consider(like 25.99 may become 26 when typecasted)
  }
  cout<<endl;
}
int main()
{
  fastio()
  ll t;
  t=1;
  cin>>t;   //commenting if t = 1;
  while(t--)
  {
    solve();
  }
}

I guess there is some discussion carried on previously in the comments section(Just seen)

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

    Okay, I guess it was due to precision error in double arithmetic. It got accepted just now when I multiplied the numerators first as a whole and then carried on division(which indeed seems to be convincing) Thankyou

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

Who got pupil in the contest congratulations and best of luck for their future.

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

i actually love the problems this time :)

»
2 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

I recently received a message stating that my code is very similar to [user:cindy34]'s code. I would like to appeal against this.

I can easily tell that this is a 2-SAT problem, but I forgot how to write 2-SAT for a while, so I used a code I used on the website of Luogu (China) before. The code is visible in this link. It is not visible if you don't have a Luogu account or you didn't get AC on this problem, but I'm sure someone can see that. To be honest, I think it's normal to have a similar coding style with 2-SAT problem. Just add virtual node and connect edge and run a Tarjan algorithm, I think there can't be too much difference before one's 2-SAT code and another.

I have added a link to the click card of my Codeforces account on this user's Luogu personal page, which proves that the user of this account is me. If it's not visible, then this page may be a choice.

This is my first time to take part in a Codeforces competition and I don't want to make it end up like this.

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

MikeMirzayanov 260410803 flamestorm

I got a plagiarism warning for my submission of 260410803 to the problem 1971G - XOUR . I would like to add that I did not use any online ide/compiler. I did not share my solution with anyone else, nor did I copy from any human. I did use chatgpt which is an AI for help. Since the condition A[i] ^ A[j] < 4 was given in the question, I gave the whole question to chatgpt along with some ideas. It did manage to give me the solution which got accepted. So I believe that the same happened with many other users whose code is similar to mine, they also might have used chatgpt. In the code of conduct also, I did not find any specific mention of AI that it is prohibited. Dominater069