flamestorm's blog

By flamestorm, 9 days 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

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

Let's Go !

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

FINALLY! I CAN SAY IT TOO.

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

contest after a long time !!

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

hope my last rated div 4

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

Hoping for the best Div.4 Round!

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

    it was worst

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

      it wasn't

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

        yes it was

        • »
          »
          »
          »
          »
          8 days 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

          • »
            »
            »
            »
            »
            »
            8 days 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

            • »
              »
              »
              »
              »
              »
              »
              8 days 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

              • »
                »
                »
                »
                »
                »
                »
                »
                6 days 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 :( >_<

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

                  that's cool!

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

This will be mine first unrated contest.

»
9 days 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)

»
9 days 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!

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

Aiming to reach Pupil after this

»
9 days 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.

»
9 days 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

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

    Close your eyes,what do you see?

  • »
    »
    9 days 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.

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

<begin-copy-pasted-part>

</begin-copy-pasted-part>

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

I am excited for this contest.

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

what is the mean of "trusted participants"?

  • »
    »
    9 days 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.

    • »
      »
      »
      7 days 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?

  • »
    »
    9 days 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.

  • »
    »
    7 days 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.

»
9 days 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

  • »
    »
    8 days 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.

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

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

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

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

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

First unrated contest :)

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

Aiming to reach specialist this contest!

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

First unrated. :)

»
9 days 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">

»
9 days 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!

»
9 days 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!

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

My first official unrated contest :)

  • »
    »
    9 days 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.

»
9 days 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.

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

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

»
9 days 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)?

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

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

»
9 days 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 !!

  • »
    »
    9 days 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

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

Hope for short queue :)

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

Would I reach cyan? Superman asked.

»
9 days 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

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

Finally!

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

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

The queue is already so long.

Please don't hold div4 today.

»
8 days 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

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

I hate D and E :sob:

»
8 days 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 ?

»
8 days 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 ????

  • »
    »
    8 days 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.

»
8 days 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.

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

TF wrong with my code

Problem E

extremely frustrating actually.

  • »
    »
    8 days 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

    • »
      »
      »
      8 days 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?

      • »
        »
        »
        »
        8 days 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.

  • »
    »
    8 days 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.

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

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

  • »
    »
    8 days 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.

    • »
      »
      »
      8 days 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().

      • »
        »
        »
        »
        8 days 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.

        • »
          »
          »
          »
          »
          8 days 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. :)

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

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

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

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

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

        No it will print an integer because dis in an integer

        • »
          »
          »
          »
          »
          8 days 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.

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

I absolutely hate using doubles :(

Very nice problems btw :)

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

    which problem requires double?

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

      I am also thinking the same.

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

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

      • »
        »
        »
        »
        8 days 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

»
8 days 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

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

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

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

Problem E sucked the living soul out of me.

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

is H 2-sat?

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

    It is.

  • »
    »
    8 days 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

    • »
      »
      »
      8 days 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

      • »
        »
        »
        »
        8 days 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$$$).

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

tough H

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

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

  • »
    »
    8 days 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.

    • »
      »
      »
      8 days 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 :)

  • »
    »
    8 days 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.

    • »
      »
      »
      8 days 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 :)

  • »
    »
    8 days 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$$$.

    • »
      »
      »
      8 days 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 :)

  • »
    »
    8 days 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";
    
    • »
      »
      »
      8 days 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 :)

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

what's the solution for problem H ?

  • »
    »
    8 days 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.

»
8 days 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?

  • »
    »
    8 days 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

  • »
    »
    8 days 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 .

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

Mehnn, this was a horrible ahhh contest for me.

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

See your grandpa without long long

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

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

»
8 days 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?

»
8 days 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://mirror.codeforces.com/contest/1971/submission/260428874

»
8 days 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

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

.___.

»
8 days 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.

»
8 days 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??

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

What is the idea in problems G and F

  • »
    »
    8 days 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.

  • »
    »
    8 days 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://mirror.codeforces.com/contest/1971/submission/260443847

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

"YEAH , this totally makes sense" T-T

https://imgur.com/a/dtdO5DN

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

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

»
8 days 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

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

    Use generators.

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

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

      • »
        »
        »
        »
        8 days 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.

        • »
          »
          »
          »
          »
          8 days 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

          • »
            »
            »
            »
            »
            »
            8 days 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.

»
8 days 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

»
8 days 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

»
8 days 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?

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

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

    • »
      »
      »
      8 days 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.

»
8 days 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://mirror.codeforces.com/contest/1971/submission/260435081

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

    What do you mean by "precision issues"?

    • »
      »
      »
      8 days 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

      • »
        »
        »
        »
        8 days 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

      • »
        »
        »
        »
        8 days 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

        • »
          »
          »
          »
          »
          8 days 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!

          • »
            »
            »
            »
            »
            »
            8 days 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++).

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

What is wrong with my E solution? 260398566

  • »
    »
    8 days 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.

    • »
      »
      »
      8 days 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 ?

      • »
        »
        »
        »
        8 days 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.

        • »
          »
          »
          »
          »
          8 days 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 ?

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

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

      • »
        »
        »
        »
        8 days 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

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

          which part are you talking about?

          • »
            »
            »
            »
            »
            »
            8 days 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

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it
»
8 days 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

»
8 days 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

  • »
    »
    8 days 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

    • »
      »
      »
      8 days 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

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

        G was easier then F

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

          Yes, but I'm talking about cf rating distribution

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

            ohh sure.. but i still didnt understand F

»
8 days 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://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.

  • »
    »
    8 days 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.

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

    don't smash your laptop :v

»
8 days 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

»
8 days 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.

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

why this submission got wa on t21

260348605

»
8 days 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.

  • »
    »
    8 days 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]));

    • »
      »
      »
      8 days 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??

      • »
        »
        »
        »
        8 days 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.

»
8 days 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?

»
8 days 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.

»
8 days 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?

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

div 4

»
8 days 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.

  • »
    »
    8 days 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!"

»
8 days 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

»
8 days 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.

  • »
    »
    8 days 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 .

»
8 days 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...

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

1

»
8 days 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 ?

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

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

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

Wish didnt see the "rounded down" in E.

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

why the rating is not update till now!!

»
7 days 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

:)

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

    Multiply all numerators first then divide.

    • »
      »
      »
      7 days 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?

      • »
        »
        »
        »
        7 days 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.

  • »
    »
    7 days 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 .

    • »
      »
      »
      7 days 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 ?

      • »
        »
        »
        »
        7 days 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

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

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

  • »
    »
    7 days 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.

»
7 days 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

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days 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)

  • »
    »
    7 days 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.

»
7 days 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:(

  • »
    »
    7 days 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 :|

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

so when the rank and rating get updated?

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

amount of FST on E is quite frightening

»
7 days 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?

  • »
    »
    7 days 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.

»
7 days 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???

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

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

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

Aiming to reach Pupil.

»
5 days 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)

  • »
    »
    5 days 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

»
5 days 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.

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

i actually love the problems this time :)

»
5 days 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.

»
4 days 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