Pa_sha's blog

Codeforces Round 891 (Div. 3)
By Pa_sha, 17 months ago, In English

Hello Codeforces!

We are pleased to invite you all to participate in Codeforces Round 891 (Div. 3), which will start on 07.08.2023 17:35 (Московское время).

The format of the event will be like any Div. 3 rounds:

  • 6-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.

We encourage participants with a rating of 1600+ not to create new accounts but to participate unofficially.

Only trusted participants of the third 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 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.

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

Problems have been created and written by our team: FBI, Skillful_Wanderer, SashaT9 and Pa_sha.

We would like to thank

Good luck!

UPD: There was an error on problem F. We fixed the tests and rejudged solutions . We apologize for that. It only affected a few people whose solutions passes all tests now. Also some hacks were already added to the tests and broke some of solutions.

UPD2: Editorial

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

Comments Comments (250)
| Write comment?
»
17 months ago, # |
  Vote: I like it +78 Vote: I do not like it

As a developer who happened to be the leader of the team, I would say you just these two words. Good luck!

→ Reply
»
17 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I hope the contest will be good, in advance I congratulate you on becoming the authors of the contest on cf

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks! Hope you will like our contest

    → Reply
»
17 months ago, # |
  Vote: I like it +38 Vote: I do not like it

As a coordinator the guys have prepared an interesting competition for you!

→ Reply
»
17 months ago, # |
  Vote: I like it +52 Vote: I do not like it

As a tester, I hope div3 users will enjoy this contest from well-prepared problems.

→ Reply
»
17 months ago, # |
  Vote: I like it +26 Vote: I do not like it

As a first-time tester, this is the best contest I’ve tested :) I hope you’ll like the problems!!

→ Reply
»
17 months ago, # |
  Vote: I like it +17 Vote: I do not like it

We know hacks do not give additional points, they just take away points .,.

→ Reply
»
17 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Hoping it will be a great round of Div.3. Best of luck to all contestants!

→ Reply
»
17 months ago, # |
  Vote: I like it +27 Vote: I do not like it

As a coach of these guys, I am delighted to see their first performance as problem setters at Codeforces, as well as to see positive feedback from the testers. I do believe that problems are well-prepared and fascinating. Also, I hope that everyone (including Grothendieck, the mathematician after whom we called our team) will enjoy the contest.

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it

As a tester, I can assure you that the problems are of high quality, and you will definitely enjoy solving them. Please, read all the statements. Even if you find yourself stuck on a problem — try to solve the next one.

Good luck! May the skill be with you.

→ Reply
»
17 months ago, # |
  Vote: I like it +11 Vote: I do not like it

As a first-time tester, all the problems are fun and well-prepared. I hope you will enjoy the contest and earn a positive delta! Good luck!

→ Reply
»
17 months ago, # |
  Vote: I like it +11 Vote: I do not like it

First Unrated Div3 :)

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Congrats!,But even though Div3 is unrated for everybody 1599+, everyone is welcome to participate)

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

SashaT9 orz

→ Reply
»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Tomorrow : Problem A : dp on a tree ):

→ Reply
»
17 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Ukranian Contest!

→ Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hoping to become cyan in this round.

→ Reply
»
17 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Good Luck everyone!!!

→ Reply
»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Wish everyone can enjoy the Div.3 round, let's gooooooooo!

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ukrain rocks!!!

→ Reply
»
17 months ago, # |
  Vote: I like it +7 Vote: I do not like it

I will solve at least five problems.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope a good round, although i will be unrated.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope that I can get back to expert.

→ Reply
»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I wish good luck to the participants and no problems during the round to the developers! I am also very glad that now more and more different teams are preparing div-3 rounds! ✨

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope everyone rating increse after div 3 , good luck everyone !

→ Reply
»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Currently, There's a variety in teams who prepare DIV 3. Interesting UwU

→ Reply
»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope to become expert

→ Reply
»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope to be Specialist this round.

→ Reply
»
17 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I really like it when I see the problem setters of the contest have solved thousands of problems, when their rating graphs has lots of ups and down, because they know the struggles of people who have practiced a lot and lot but still face problems during contest. And they set problem keeping these things in mind.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become expert!

→ Reply
»
17 months ago, # |
  Vote: I like it +17 Vote: I do not like it

A div 3 prepared by Ukrainian and Russian, I love this.

→ Reply
»
17 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Hope to become at least Specialist in this round . ;(

→ Reply
»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

안녕, i am a (beta) tester

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully i will be pupil again. Good Luck guys!

→ Reply
»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Wow, so the writers are all from Ukraine!

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck!

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping it will be a great round of Div.3. Best of luck to all contestants!

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope to get close to 1600 or above.

→ Reply
»
17 months ago, # |
  Vote: I like it -9 Vote: I do not like it

John Cena wishes you luck

→ Reply
»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope that the statement is clear and short

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Speedforces!!

Speedcoding is a different kind of fun...

→ Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

idk but i feel like this contest might have been a little bit hard :)

→ Reply
»
17 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I see a lot of negative comments, and I don't know why, as the statements were pretty clear and problems seemed fine, just like in the last 2 contests.

→ Reply
»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

G is absolutely beautiful!

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Didn't solve but seems pretty elegant to me as well!

    → Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Is it 2^(number of pairs u-v where dist(u,v) < S) ??? I couldn't think of a concrete solution

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      No, the main idea is based on Kruskal's algorithm. If you know Kruskal's then you'll recall that it adds edges in increasing order of weight, but if an edge creates a cycle, then it skips it. Now if you apply Kruskal's to the given tree (add edges in order of weight), you'll be able to deduce some of the edges that need to have larger weights than the current edge. (bad explanation, ik, but it should get the main idea across.)

      → Reply
    • »
      »
      »
      17 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I believe that if any of the edge has a weight s initially, then it's 0.

      Otherwise, it's a combinatorics problem — You can try to insert every possible edge with every possible combination with every weight in range of [max weight in the given tree+1, S].

      P.S: 0 if w_i==s is wrong. An edge can be added without changing the MST.

      → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      80 is a possible output as shown in testcases; so unlikely

      → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    kind of standard actually, ive seen this exact thing before (counting how many pairs of nodes each edge is maximum of)

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      It's div3, so perhaps standard problems are excusable.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it -22 Vote: I do not like it

        i disagree, all rated contests should have non-standard problems. Either way, i was talking about why i dont find it beautiful or even good.

        → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint: for each pair of x and y, there is only one set of numbers which satisfies a + b = x and a * b = y

    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If ai is part of a pair then ai+(y/ai)=x, which gives a quadratic equation. Solve it and you get the values of ai and aj. The rest is simple combinatorics. Be careful of the case when the quadratic equation has zero or one solutions.

    → Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 5   Vote: I like it +1 Vote: I do not like it

    For every $$$(x,y)$$$ the is at most one unordered pair of integers $$$(a,b)$$$ such that $$$a+b = x$$$ and $$$ab = y$$$. You can find $$$a$$$ and $$$b$$$ via quadratic quation.

    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can store the frequency distribution of a_i in a map and then just try to solve the quadratic. If roots are equal, answer is n choose 2 where n is frequency of the root otherwise, it is n1*n2

    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solved it 5 minutes after contest sadge. The answer is pretty simple, just notice that you can rewrite your two equations as two quadratic equations and then apply the quadratic formula.

    a_i + a_j = x means that a_i = x — a_j. And if you insert this in a_i * a_j = y you get a_j*(x-a_j) = y which can be written as a_j ² — a_j x + y. And the same for a_i.

    Then quadratic equation gives you two possible solutions x — sqrt(x*x — 4*y) and x + sqrt(x*x — 4*y). So you just see how many of these elements are in your array to make an answer out of and you get your answer :)

    https://codeforces.net/contest/1857/submission/217739412

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro i saw your code what is (x+thing)%2 in that can you please explain

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry for the non-descriptive name, but thing is just the square root of the discriminant. You can see that in the quadratic formula the answer is (-b +/- thing)/2a. Which is (x +/- thing)/2 (which you see in the code)

        The reason we have (x + thing)%2 in our code, is just because we are working with integers and not floating point numbers. If (x+thing) was an odd number, then the quadratic formula would've given us a non-integer as an answer, which we know we can't have, so we exclude those cases.

        → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G ?

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 4   Vote: I like it +6 Vote: I do not like it

    Consider Kruskal algorithm performed on input tree. On each step we're connecting 2 components via edge with weight $$$w$$$. The other edges connecting these two components must either have higher weight or just not exist, so we multiply our answer by $$$(S-w+1)^{S_1S_2-1}$$$, where $$$S_1$$$ means size of first component and $$$S_2$$$ size of the second one.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I mean, problem G is much more than that, isn´t it?

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        No, it's the whole solution.

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Actually my code for problem G is almost identical as yours but I mean, the reasoning to solve the problem is more than that in my opinion.

          → Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

B was a little unclear for me. also hard.

→ Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for the round. I solved until problem E. Problems up to E were fine for me, except for problem B.

→ Reply
»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Missed F by 30 seconds. F

→ Reply
»
17 months ago, # |
  Vote: I like it +37 Vote: I do not like it

I feel like Problem B was too hard for D3B.

→ Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What's the test 24 on pG:(

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Exit for the type of frequent

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm, I've no idea. Could you please explain? I guessed my modulo had some problems at first, but it seems not.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In most solutions, there is an exit for the type in exponentiation

        → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Doing modulo on the exponent is wrong (I was doing this too and it's worked for many past problems as I guess the exponents never got that high).

        → Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it -9 Vote: I do not like it

    On line 44 in submission 217723319, int x=fpow((s-c+1)%mod,(siz[a]*siz[b]-1)%mod); should be changed to int x=fpow((s-c+1)%mod,(siz[a]*siz[b]-1)%(mod-1)); because of Fermat's little theorem.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I learned that before but I forgot it in the contest:< U're so genius:D btw,I think I heard ur chinese name before. :)

      → Reply
»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

very easy with problem F, but i wasted time for B, and D, E , F is more easy than D or E.

→ Reply
»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

B = C >> F for me, solved in in 7 minutes but for the next hour couldn't solve and implement B and C correctly. Feels so bad ;(

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes me too,F took me 10 minutes but B is 30 mins

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Need to work more on constructive and greedy problems, literally they are of the types either you get the idea early or you can be stuck for the entire contest getting no idea

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes, i think it is so easy to me when start, but some complex case torture me.

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          best words to describe xD, there is always some complex case there to torture us in these problems ☠️☠️

          → Reply
»
17 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Problem statement of B is the ultimate example of "How not to write a problem statement".

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved C using this. Can it be optimized further? 217736885

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What does "Unexpected verdict" mean in hacking?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

guys when does results will come

→ Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Appreciate it :) I really enjoyed the round.
I wish I could notice earlier the fact that
the description of problem B was actually describing normal round operation, but still I had lessons learned.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B was an unclear statement take me a lot of time to understand!

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Same here.
    I rather chose to infer from examples

    → Reply
»
17 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Good contest. Enjoyed. But F, it was just like: "Hey! do you know quadratic equations?"

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

rename this contest to Div.2 ):

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    i think it was quite easy, especially if we check the solutions stat other div. 3 contest.

    → Reply
»
17 months ago, # |
  Vote: I like it +22 Vote: I do not like it

What the hell was B? very bad problem statement!

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

solved E, F but unable to solve D :v. Wasting time for thinking about graph and reverse graph :v

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    I was lucky enough to consider transpose the equation au−av ≥ bu−bv into au−bu ≥ av−bv.
    Then the problem turns into finding maximum values in the new array c = a - b

    → Reply
»
17 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Why does this code give WA in problem G? Can you help me please to find a mistake in the code? https://codeforces.net/contest/1857/submission/217742367

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Solutions for problems A, B, C, D and E were on youtube during the contest again. Can't codeforces contact Youtuble to delay codeforces related videos when there is a contest? + Why do people even cheat? Why are they getting from cheating?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

FBI Why where is no such test in F that $$$x^2 - 4y$$$ is not a full square?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    that's for hacks

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Does that mean we should not add any tests? Let the paricipants add test themselves during hacks!

      No, that is not. I suppose all test were random.

      That is just poor testers' work

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        more than 1 mil test cases and no such as x^2 — 4 * y is not a full square? Odds say that it was intentional.

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What is not how this works, you can make 2mln random tests and you won't find correct test.

          → Reply
          • »
            »
            »
            »
            »
            »
            17 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Then tell me how it works

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              17 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              https://codeforces.net/problemset/problem/1743/D

              Solve this and you find out why random tests are bad

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                17 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Majority of tests on cf are random

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  No, they are not.

                  If they were random, 90% or more uncorrect solution would become accepted

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  What gives you that idea?

                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                17 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                you know,if the tests were actually random, you could have passed this problem by just randomly outputting 0 and 1 ))),

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I guess, that is that your F validator does, randomly validate tests

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  you know, the thing is that you don`t know how tests were generated and you will never know,so i think that it would be appropriate to stop trying to insult someone from the preparation team)

                  → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Many comments says that F had several problems with tests. So, it wasn't intentional, just bad work of testers, and probably by authors themselves, because test 7 was with zeroes in it, meanwhile it is prohibited by statement $$$(1 \le |x| \le 10^9)$$$.

          → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I simply forgot to check if 

    sqrt(x*x-4*y)*sqrt(x*x-4*y) == x*x-4*y

    And got accepted, now I hacked my solution ofc, but this is strange that this test wasn't added

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the problem statement in C is kind of easy to be misunderstood.

It's quite sad that I couldn't solve C despite solving (preliminarily) D E F.

→ Reply
»
17 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Mathforces

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can we solve problem C? what's the intuition behind and are there any similar problems?

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Math.
    Sort array b, then the minimum element shows up (n-1) times, next smaller value shows up (n-2) times, ... so on and the last value(largest one) can't be determined.
    So we can simply choose the maximum value for the last one, which is 10^9 in this problem.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah thanks, i just realized b was result of all possible pairs not subarrays, should have re read the statement. -_-

      → Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I really enjoyed the contest, and in my opinion B wasn't that bad like other comments say, but the implementation was tricky

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    B was really easy, C was tricky

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For a div3 C I think it's pretty good, if you figure out that the smallest element in array a will be present n-1 times in array b, then the rest is very easy (other than the implementation)

      → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The problem statement was kinda wacky and the implementation is way above D3B level.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody look into my solution for C: https://codeforces.net/contest/1857/submission/217718886 I am not able to find the mistake. Thanks.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you try to restore elements of a in sorted order.Then it will be easy.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys please give some hints to D, I's stuck there

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

None of the CF extensions are working. Not even CF Get Rating or CF Analytics. It shows codeforces API error. I just wanted to know my predicted delta. Anybody else with the same error?

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I my opinion hardness of Problem G sharply increased.

→ Reply
»
17 months ago, # |
← Rev. 3   Vote: I like it +61 Vote: I do not like it

Good contest overall problems was fun! However I noticed there is a bad test case on problem F. In the constraints, it stated that x and y had to have at least an absolute value of 1 or greater. However, test case 7 had queries where x = 0, causing my code to fail. :(((((((( I've noticed a lot of other people failed this case too, so ig i have the power to make this unrated :p

Submission: https://codeforces.net/contest/1857/submission/217663720

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

problem D hadn't pretest like: 

1 
2
-1000000000 -1000000000
1000000000 1000000000

is it good?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's 2 <= n in problem D.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah fixed, I mean it hadn't max test for a[i] — b[i]

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There was a test where array $$$a$$$ was $$$10^9$$$ and array $$$b$$$ was $$$-10^9$$$ (10 test case)

        → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it was for hacks)) Poorly, i think that -1e9 is minimum value)

    → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +38 Vote: I do not like it

Problem statement of F mentions $$$1<=|x|$$$ but testcase 7 has $$$ x = 0$$$ and $$$ y = -9$$$ as one of the queries.

This should not fail in my opinion if $$$x \neq 0$$$ was ensured.

Edit: incorrect link

→ Reply
»
17 months ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

F's pretests were really weak i forgot to check the most important condition whether the (-b + sqrt(D)) is divisibly by 2 or not :O. A lot of hacks incoming

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    I don't think it's possible for (x + sqrt(x^2 - 4y))to be odd. 4y is always even. If x is odd, x^2 must be odd. Then odd - even is odd. So sqrt must be odd. So, x + D is even.

    Similarly you can argue for the case where x is even.

    → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Just wanted to get some clarification, for the problem D of today's contest. I got this weird error in the following submissions (using java):

When I submitted equivalent code using long, it worked (using java): - https://codeforces.net/contest/1857/submission/217686813

Using int, cpp code worked though: - https://codeforces.net/contest/1857/submission/217741962

Anyone has any idea what might have happened? I would really appreciate the help. Thanks in advance.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The issue is caused by your compare function for pair. min(A[i] — B[i]) can be -2e9 and subtracting from another -2e9 overflows.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      One more doubt, though, does codeforces raise exception, for integer overflow also?

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        For C++, the answer is yes in practise and no during contest.

        → Reply
»
17 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Task C is complete constructive shit. I liked all the other tasks very much.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Lol, it is not even constructive

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, for this it was constructive, because it is necessary to stupidly come up with an array.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        The idea behind problem C was nice actually, not stupid.

        → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    In order to become a good competetive programmer, you need to be able to solve constructive problems ;)

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone suggest me some better approach in E? MY submission https://codeforces.net/contest/1857/submission/217726880

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    i think, the only optimization here can be not finding lower_bound(vb.begin(), vb.end(), va[i]), but using just i instead, because anyway you get 1 from segments like [a, a] and lower_bound adds logN to your complexity. The idea seems ok.

    Edit. I'm sorry for not noticing that, but this way you should use vb for iterating through the indices, not va. So, you don't actually need va except for reading the input :)

    → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

well i got RE for 7 times in D 217669362 (exit with 11:java.lang.IllegalArgumentException: Comparison method violates its general contract!) and solved in this version 217692889 ...never got exception like this before,can anyone tell me why?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why were all problems except G math-y?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

look at this guy's submission Stark663

I think he is a cheater

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    no,but he may be banned because he violated the rules that you are agreeing to before registering to any CF contest)

    → Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Video Editorial For problems A to F.

https://youtu.be/6s1vEnzK7vI

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    nice,but I don`t think that it is allowed to post this before the hacking stage is over)

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      And why is that so? Everybody is sharing their solutions anyway. Also there's no rule iirc that prohibits that.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        maybe you are right, thanks

        → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Now EveryOne's solutions are public So I guess That should be Allowed.

      → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I getting MLE at test case 4 in F? MY submission https://codeforces.net/contest/1857/submission/217743843 How can I optimize it?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Even if it didn't MLE, it would have probably been hacked (TLE) because you used unordered_map, see this blog for more details

    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not necessarily related to MLE, but I wonder what's C++ sqrt()'s behavior on negative input because x * x — 4 * y could be negative.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

made video explaining A&B&C&D:

https://youtu.be/elQ4jmUfYqM

thought would be usefull for community

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It was contest with the most creative (also good) problems I have ever participated.

Although B may be difficult for many people, it can be in best problems for last contests. Also E and G were pretty good. But I think F was too mathematical, perhaps you could add another problem which more greedy or more algorithmic.

Thanks for the great contest, I love it :D

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how this code got hacked https://codeforces.net/contest/1857/submission/217662800

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't it like $$$O(len^2)$$$ for 99999..99999?

    → Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

TY for the contest <3

→ Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Please check this blog , Problem F constrains has (1 $$$\le$$$ $$$|x|$$$ $$$\le$$$ 10^9).

Meanwhile in test 7 many test cases have x = 0.

I don't know what should happen in this case, but please do something about it.

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I get it nvm

→ Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

open upsolving please

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If I hacked someone, but it was unsuccessful. Do I lose points?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know why my solution is failing for F: https://codeforces.net/contest/1857/submission/217724931 Can somebody help me?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you need to check again if temp*(x-temp)!=y

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks, it got AC

      → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I got AC by adding this. But I'm trouble in why is it necessary? I try to check sqrt(x * x - 4 * y) * sqrt(x * x - 4 * y) != x * x - 4 * y but got WA too. Thanks for your patience.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        According to Quadratic Formula,you need to assure that ai,aj are all Integers, so sqrt(x*x -4*y) should be an Integer too, or else you may get wrong answer,so having a check is nice

        → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I managed to solve up to E during the contest and F afterward. The problems were nice, they were from various topics and I enjoyed solving them.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the approach for E?

I got TLE here : https://codeforces.net/contest/1857/submission/217725866

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code is O(n^2), read the editorial for O(n log n) solution

    → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Math tag for problems ×

Math tag for contest ✓

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The round was made unrated?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

G is beautiful

→ Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Had sys test finished?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It is writtent that tis contest is rated for everyone having rating less than 1900. But my rating haven't updated current rating :-806

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My F was hacked. Can someone tell what's the issue?

My Submission : 217815371

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You didn't check if the square root is an integer or not , as ai and aj must be integers.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wasn't this sufficient??

      ll t = sqrtl(x * x — 4 * y); return (t * t) == (x * x — 4 * y);

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i think you still need to check if the discriminant is negative or not

        → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Why have you taken a $$$MOD$$$ here?

    cout << (cnt1 * cnt2) % MOD1 << " ";
    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me find out why this submission for F is getting tle? 217653085

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WHY did code give TLE in system testing (PROBLEM -F)

#include <bits/stdc++.h>
        using namespace std;
        #define int  long long 
        const int N = 200000;
        int p=1e9+7;

    void solve()
        {
            int n;
            cin>>n;
             unordered_map<int,int>mp;
             for(int i=0;i<n;i++)
             {
                int a;
                cin>>a;
                mp[a]++;
             }
             int q;
             cin>>q;
             while(q--)
             {
                  int a,b;
                  cin>>a>>b;
                  int val=sqrtl(a*a-4*b);
                  int count=0;
                  if(val*val==a*a-4*b)
                  {
                    if((a+val)%2==0)
                    {
                     int num1=(a+val)/2;
                      int num2=a-num1;
                      if(num1==num2 )
                      {

                        count+=(mp[num1]*(mp[num1]-1))/2;
                      }
                      else 
                      count+=mp[num1]*mp[num2];
                    }
                    else if((a-val)%2==0)
                    {
                         int num1=(a-val)/2;
                      int num2=a-num1;
                      if(num1==num2)
                      {
                        count+=(mp[num1]*(mp[num1]-1))/2;
                      }
                      else 
                      count+=mp[num1]*mp[num2];
                    }
                  }
                  cout<<count<<" ";

             }
             cout<<endl;


        }

        signed main()
        {
            int t=1;
            cin>>t;    
            while(t--){
                solve();
            }
        }
→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try using map instead of hashing. Searching in a hashmap is O(n) worst case.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why F using unordered_map will TLE?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is causing TLE in problem E?

→ Reply
»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I see the system testing has stopped at 100% for a while xD.

Hmm, it's 20:00 in my timezone and I haven't eaten yet T.T

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating changes???

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nah,hot yet

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Why not?

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You know,I could start telling you some bs answers, but i literally have no idea, the system testing is not over yet,maybe that is the problem

        → Reply
»
17 months ago, # |
← Rev. 7   Vote: I like it +13 Vote: I do not like it

Why is the contest frozen for so long MikeMirzayanov FBI

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 12   Vote: I like it +3 Vote: I do not like it

    I noticed some (about 10) submissions have been "running on test 1" for hours. Though I don't know why they are like this, it might be the reason why the contest is still "system testing: 100%".

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Never expected such good performance by me in such div 3 contest

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By the way can someone suggest some problem around the problem G to practice

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is much much easier than problem B

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Honestly it depends on implementation skills, B is pretty easy to figure out but the implementation is difficult, while in C you need a bit more thinking with easier implementations

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B was good, but the test cases weren't exhaustive during contest, it didn't help with the fact that codeforces was down so had to use m1 lite version which didn't show my submission time and solution was accepted, although i should have written efficient code in the first place, but this kind of gave false positive until solutions were hacked :(

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hh, this kind of thing often occurs, but this pretest is still passable, at least most people's C, wa7 will realize the error later, 883's pretest is the weakest

    → Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice!!!Through this round of Div3, I became Pupil for the first time!

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I never understand the pointing system... I mean although i just solved one question how could i lose points for that??

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    One of the main reason your rating is decreasing after cobtwst is that you underperformed (your performance is below your rating).

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got a TLE because of umap on F QwQ

I was so close to AK :(

→ Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Fun round for sure! Really enjoyed D, E and F, even though had to re-solve them after the round. Good tasks for a begginer, since they did indeed give me some new approaches!

→ Reply