When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

flamestorm's blog

By flamestorm, 21 month(s) ago, In English

Hi Codeforces!

ScarletS and I are glad to invite you to Codeforces Round 803 (Div. 2) which will be held on Jun/28/2022 17:35 (Moscow time). The round will be rated for participants with rating lower than 2100. The theme of the round will be déjà vu! (Wait, wasn't that already a theme before?)

Thanks to the people who made this round possible:

Thanks to NEAR for supporting this round, details can be found in this post.

You will have 135 minutes to work on (and solve!) 7 problems. At most one of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round!

The scoring distribution is $$$250-500-1000-1500-2000-2500-3250$$$.

Good luck, and see you on the scoreboard!

UPD: Editorial is out!

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

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +56 Vote: I do not like it

déjà vu ? I've just been in this place before...

»
21 month(s) ago, # |
  Vote: I like it +199 Vote: I do not like it

As a problemsetter, each upvote on this comment equals one time I'll roast saarang

»
21 month(s) ago, # |
  Vote: I like it -7 Vote: I do not like it

I just hope I can perform incredibly and get a Candidate Master...

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do I feel like I've seen this theme before...

»
21 month(s) ago, # |
  Vote: I like it +77 Vote: I do not like it

As a tester, I’ve been told I get free internet points if I comment

»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

As a tester, I can tell you this round is fire! yall should try it :)

»
21 month(s) ago, # |
  Vote: I like it +32 Vote: I do not like it

As a tester I can tell problemsetters and coordinators have tried their best to keep the problemset as good as possible.
I Hope you guys enjoy it.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

"déjà vu", hmmm, something familiar

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Teach me the ways flame :orz:

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

As a tester, I can assure you really good quality problems. The contest in worth spending time. All the setters and testers have put a lot of work and effort. Good luck everyone !!

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Hoping I don't feel déjà vu while seeing my rating changes after this contest

»
21 month(s) ago, # |
  Vote: I like it +24 Vote: I do not like it

On the contest page, duration is shown as 2hrs. Please correct it. flamestorm

»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

Why are there at most 1 interactive problem and not 998244352

»
21 month(s) ago, # |
  Vote: I like it +178 Vote: I do not like it

Déjà vu theme is a very convenient excuse in case if some of the problems turn out to be well known

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +100 Vote: I do not like it

    We did this intentionally, as it is well-known that all problems are well-known in China

»
21 month(s) ago, # |
  Vote: I like it -18 Vote: I do not like it

Score distribution is 250 for problem A, means problem A's difficulty level below 800?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    It's probably gonna be easy, but I don't think it will be rated less than 800. I haven't seen any problems rated below that even if they are very easy

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think E will be interactive

upd.: happily, it wasn't

»
21 month(s) ago, # |
  Vote: I like it +37 Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

As a tester, I can snitch that the discord server icon is a picture of an anime girl.

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Excited!

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck everyone :)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

thank god speedforces

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

This is my first time,I'm scard

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -33 Vote: I do not like it

this round is much intresting

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

:)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Until you become pupil.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      That's funny because I stopped using python for contests after I got out of pupil.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got to orange in Python but even I gave in eventually

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Finally my exam is over. Hopefully I will able to solve 2 problem in this contest.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

it's morbing time

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to attempt D question?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +50 Vote: I do not like it
    1. Read the problem.
    2. Think hard.
    3. Write down the solution.
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

whyl i can't register?

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

yet, another speedforces round?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I shocked for a sec after seeing 4th problem :)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Took me a long time to debug, though got the approach early.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i didn't attempted *_*, but after seeing so many submissions it's seems easy .

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem A is a very greedy !!

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Does not have any idea on F. Expect fast editorial.

»
21 month(s) ago, # |
  Vote: I like it +34 Vote: I do not like it

Problem A was a great scam :3

»
21 month(s) ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Wanna problem C hint after the contest :(

seem like its hard for me :(

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    i am hard stuck at C for the entire round. Need to learn how to move on to D.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When you have more than 2 negative or more than 2 positive integers, the answer is NO (think why). Now you can save min(cnt0, 3) zeros and check the condition on array of size less than 10.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same thing, my logic was, answer is YES if there are >= n-2 zeroes (for n-2 case, sum of non zero ones should be zero). Other than that, only for n=3 and 4 answer is possible otherwise no. Can you give a counter example for this logic?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think that only for n = 3 and n = 4 the answer is possible.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        -2 -2 -2 you can check this by yourself in submission details.

»
21 month(s) ago, # |
  Vote: I like it +65 Vote: I do not like it

I hate this round

»
21 month(s) ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

What I did during the round. 1% of the time solving A and B - 99% of the time trying to figure out why C kept on failing.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

What was the idea behind D? I know it's a binary search, but non of my ideas on how to exclude segments were correct.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably it has to do something with a number of numbers that are in range (l, r) for a particular segment, but I couldn't elaborate this idea.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Query on segments like [1, x].
    Let miss be count of integers between 1 and x, such that they are not present in query result.
    For even and odd segment lengths, think about what should be the parity of miss if answer <= x and if answer > x

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Explain it further, please, I have so many thoughts on D now and can hardly imagine anything :)

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My solution:

        after each ask count numbers that potentially could be 'x'

        let it be cnt

        if cnt is odd => 'x' is in our half, otherwise — in second half

        continue binary search until l != r

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If you don't mind — link your solution, please. So I'll exactly see what is what.

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            Here it is: 162142911

            but it is a bit messy so:

            Solution
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah, I see, thanks a lot. Was just a few steps away from observing that

              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) ago, # ^ |
                  Vote: I like it -10 Vote: I do not like it

                thats great, wish you progress :)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Appreciate that!

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        binary search in [l, r], set k = (l + r) / 2, then check [l, k], if \sum_{i=l}^{k}[l<=a_i<=k] is odd(number of exchanges in [l, k] modulo 2 equal 1), answer will in [l, k], otherwise [k + 1, r]

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

-500 incoming

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    If 3 positive or 3 negative, answer is not possible.

    Otherwise, brute force.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I put that logic...still failed..can i show you the code now that the contest has ended?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hint:Notice that the number of non-zero numbers must be very small.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    3sum-closed array has at most 2 negative numbers, and at most 2 positive numbers. Then reduce zeros to some small value, so we can iterate all i, j, k and check all sums.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

C is pretty strange :)

I hope it will pass
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yea should pass, why not

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Umm... we can never have more than 2 positive/negative integers?? So if the count of odd or neg numbers is >2 then the answer will be "NO"

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      His/her brute force will catch it though :)

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, I mean ofc it will pass, I was just mentioning why his solution passed (^^ゞ

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know C++ but it looks like he's applying Brute force only if size of array is less than 100 or else he is printing NO ig

»
21 month(s) ago, # |
  Vote: I like it +12 Vote: I do not like it

Harder Div2, I thought I was accidentally solving some D1Bs and D1Cs during the contest...

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

wandering here after solving a,b,c :P

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Hint

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u point mistake in my code. Dude I did the same thing but showling TLE

»
21 month(s) ago, # |
  Vote: I like it +27 Vote: I do not like it

How to solve E lol

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it +24 Vote: I do not like it

    Hi! It's my first time for me solving E, i'm very happy, so lemme write my solution;)

    Let's notice that if we are given a certain permutation b we can only change a to b when for each element a[i] if j is the position we should move a[i] to, b[j] <= a[i] + s:

    If the condition is not true (for example for a[i], if a[i] should be on j-th place) — then we can't move a[i] to its needed place, because if we can, then we do it on move <=i therefore other element we swap (a[j]) has a difference with a[i] no more than s, but a[j] > a[i] + s (contradiction)

    If the condition is true for each a[i], notice that we can consequently move a[i] to its needed position on a[i]-th move (legally).

    So let's find all permutations which suit the condition:

    Firstly, for each a[i] if b[i] is already not -1, then b[i] must be no more than a[i] + s (condition 1), otherwise answer is 0 (same reasons as in 2nd paragraph)

    Assume 1st condition is true: lets say that we have c[1] < c[2] < ... < c[x] — elements of array a, under theis indexes in array B stand -1s. And we have d[1] < d[2] ... < d[x] — elements we have to insert in B on places of -1s.

    After substracting s from each d[i], a suitable permutation will be when for every d[j] standing under element Y from A, y>=d[j]. (same reasons as in 2nd paragraph)

    So for each d[i] we can find under how much elements of C it can stand (when I say stand under, i mean that they have same index, it's just my visualisation that array B stands under array A) using binary search Let's notice that if b[j] > b[i], on every position we can put b[j], we can also put b[i]. So let's choose a suitable permutation consequently choosing a place for d[1], then for d[2], and so on. if we can place d[i] onto z places, then if we already placed first i-1 elements of D, then we can choose a place for d[i] by z-(i-1) variants.

    Let's notice that if we can put d[i] on z<i places, then we can place first i elements of D on z<i places (contradiction, so answer is 0) (condition 2)

    In the other case, if d[i] can be put on e[i] places, answer is (e[1]-0) * (e[2] — 1) * ... * (e[i] — (i-1)) * ... * (e[n] — (n-1)) (mod 998244353).

    Sorry for my bad english, of if you didn't understand something) i hope you will understand me))

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With your explanation and code,I get it eventually :) Thank you so much!!

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        You are welcome! I'm glad somebody understood me;))

»
21 month(s) ago, # |
  Vote: I like it +25 Vote: I do not like it

interactive = binary search

»
21 month(s) ago, # |
  Vote: I like it +39 Vote: I do not like it

I learned three lessons from this contest

Read the problems carefully !

Read the problems carefully !

Read the problems carefully !

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I misread the problem C, I thought one fulfilling pair was enough.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Me too. I misread problem C until the problem setter made the announcement. And, I misread problem E again. I solved problem E immediately after the contest.

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Ok I need to know, what was déjà vu in this contest?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think that the problems had classic prototypes like:

    A — xoring to find the unique number

    C — 2Sum or 3Sum problem

    F — reversing an array via Implicit Treap

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not sure though whether knowing about these prototypes can help you solve today's problems faster :)

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      E — reversing an array using impicit treap

      come again?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    3-SUM was reference to recent div4, PermutationForces was reference to one of recent problems too (don't remember the contest), pretty much sure all other problem names you could've meet before.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

a is 3SUM-closed if for all integers..... anyone missed the all integer part like me.. That's created the problem more hard :'( even is that possible with the same constraints ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What else would it be? For even one such $$$i, j, k$$$?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how u find there have at least one i,j,k as if a[i]+a[j]+a[k] also exist in array. ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one hour is wasted on that thing, I really gotta read the problem statement carefully the next time.

»
21 month(s) ago, # |
  Vote: I like it +64 Vote: I do not like it

I solve F while using only 2n operations. And I don't have any idea why the limit is n^2.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's very sad that your rating is 2100, not 2099

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -39 Vote: I do not like it

      I actually use sjcsjcsjc for Div1 contest.

      2100 isn't my real rating lol.

      (Sorry for violating the rules :( )

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        ded after looking at ur real rating.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I waste too much time because of misreading the statement of E so that I didn't have time thinking about G.

    Anyway, the problems are very impressive and a bit more difficult than normal Div2. Really like this contest.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It would be nice if someone could look at my submission for the interactive problem (Java). It was my first interactive problem and I think I did something wrong with the queries / flushing, my submission didn't do anything (my testing did work, think the solution was correct). 162145333

»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

I liked problem D. Thanks to the authors for the contest.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good problem..but number of queries was a direct hint to binary search..If number of queries were hidden,it would have been a even better problem.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      If they hid number of queries, one would just get WA without knowing why?

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For C, there can be atmost 4 non-zero numbers(say m), for the given condition to satisfy.

For, m=4, there can be only 2 forms of numbers — a,-a,b,-b and 3a,a,-a,-a. Can there be any other kind of arrangement?

Thanks in advance :')

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Failed systest because I didn't see the 3a, a, -a, -a case. :(

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      :'(

      I was taking different cases for proving that there isn't any arrangement of 5 numbers possible and stumbled upon this case. Although, I skipped its implementation and applied a general implementation for n=4. Implementing different cases separately wasn't necessary

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yea I didn't include the m=4 option at first and WA'd, then by messing around, found the -b, -a, a, b case and just submitted it and passed pretests so I didn't bother looking at it again.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So do I

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    -3a -a a a

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

Why does the presence of this line give idleness limit exceeded?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Run your program with and without it and you will see

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It shouldn't, however if you defined "endl" as "\n" it will because \n does not flush the stream and you were explicitly asked to flush your streams.

    however, if you remove that def, the streams are flushed automatically https://stackoverflow.com/a/31165481/

»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

the problem statements robbed me (" _ ")

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

As a tester, I'm very glad to participate this contest,which tell me i am lacking for training

»
21 month(s) ago, # |
Rev. 4   Vote: I like it +19 Vote: I do not like it

Problem D:

Binary Search: Bro.

Interactive Problem: Yea, bro.

Binary Search: Close your eyes, bro.

Interactive Problem: Ok, bro.

Binary Search: What do you see, bro?

Interactive Problem: I see you, bro.

Binary Search: Broo!!

Interactive Problem: Bro.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

For A why is it always first element? Although I used brute force after long time by seeing the constraints

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    You can print any of the elements

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think it can be any element

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      WHY???!!!

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Let the xor of original array = $$$x$$$. After adding $$$x$$$, xor of the new array = $$$0$$$. Therefore for all inputs the xor of the array equals $$$0$$$.

        So, now you want to find any $$$x$$$ such that $$$x$$$ = [xor of the rest of the array]. This is true for any $$$x$$$ present in the array because $$$x$$$ xor the rest of the array is $$$0$$$. Hope that helps.

»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

I feel this was a perfect contest. Also problem A feels like a troll problem.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I spent even more time on B or C than D...

And I get many "WA 2"s

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For anyone wondering why they got TLE on test 13 of problem C, I suggest reading this and noting that A[0] = 107897 — commiserations if this is you and you've never heard of this phenomenon before; I guess you won't make that mistake again.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate a lil?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't know specifically what's changed from GCC 17 to GCC 20, but I can make an educated guess. From the blog I quote:

      It turns out the right prime depends on the compiler version: for gcc 6 or earlier, 126271 does the job, and for gcc 7 or later, 107897 will work. Run the code below in Custom Invocation and see what output you get.

      I suspect that the hash function for unordered map / unordered set has changed from GCC 17 to GCC 20, and now in order to hack it a different prime is required.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

I love problem D and E, they're quite nice. I enjoy the feeling of finding an interesting conclusion and solve the problem without a long code. However, I think B is not so good because of the weak samples. A k=1 sample can really help a lot. Anyway, love this round very much!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

My code for 3rd problem got accepted in C++20 but shows tle for the same code in c++17 I lost nearly 18 points due to this. What should I do?

»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Any hint for E? Spent more than an hour. Don't wanna ruin it by directly reading the solution.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Hint 1
    Hint 2
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why the testcase: n = 6 ar = [1,2,3,4,5,6] the answer is NO in the problem C? if 1 + 2 + 3 == 6

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because (for example) 4 + 5 + 6 = 15, and 15 is not in the array.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    See the announcement during the round.

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

If problem C change the statement from "all (i,j,k) pairs must satisfy" to "one (i,j,k) is enough". What is the most optimal time complexity? Can this problems solve by O(n), O(nlgn) or O(n^2)?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    It's possible to solve it in $$$\mathcal{O}(n ^ 2 \log n)$$$ with std::map or $$$\mathcal{O}(n ^ 2)$$$ with std::unordered_map.

    Iterate from the end. In the map $$$cnt$$$ for each possible $$$s$$$ store the number of pairs $$$(j, k)$$$ such that $$$j < k$$$, $$$a_j + a_k = s$$$ and $$$j > i$$$ where $$$i$$$ is the current position. Then, bruteforce $$$l$$$. If $$$cnt_{a_l - a_i} > 0$$$, print YES. If we haven't found such pair print NO.

    UPD1.

    Code

    UPD2. You can use bitset of size $$$2 \cdot 10^9$$$ instead of unordered_map and get better constant factor.

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Has anyone solved C just after the announcement during the contest?

»
21 month(s) ago, # |
  Vote: I like it -41 Vote: I do not like it

the third problems was wrong and how it impossible with 2e5 and t <= 1000 ??

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you notice in last line of input format: "It is guaranteed that the sum of n across all test cases does not exceed 2*10^5" Its common in codeforces

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      did you check testcases in problem C? there is t equal to 1, if t will be 1000 and each n will be equal 2e5 i sure that all solutions will be TLE)))

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        If t will be 1000 and all n be equal 2e5 then sum of n over all test cases will be 2e8 which is not possible due to constraints

»
21 month(s) ago, # |
  Vote: I like it -27 Vote: I do not like it

worst contest i have ever entered because the third problem's solution not logical

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why do you think the solution is wrong / not logical?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, what a great round! I really enjoyed the problems, especially E))

It's my first time solving div2 E (and getting a master performance)! I'm so happy I spent my time on it, trying to think of the solution, which in fact is really beautiful

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Really a great contest. Statements are obvious and clear. Thanks all writers and testers.

»
21 month(s) ago, # |
  Vote: I like it +38 Vote: I do not like it

To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretests for C are so weak. How can this code pass pretests ?

def solve(n,arr):
    
    arr.sort()
    
    if len(set(arr)) == 1 and arr[0] == 0:
        return True
    
    if n == 3 and sum(arr) in arr:
        return True
    
    if n == 4 and arr[0] == -arr[3] and arr[1] == -arr[2]:
        return True
    
    if arr[:-1] == [0]*(n-1) or arr[1:] == [0]*(n-1):
        return True
    
    if arr[1:-1] == [0]*(n-2) and arr[0] == -arr[-1]:
        return True

    return False
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

As a beginner, i'm glad to take more Contests

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Look at this guy's code. He is probably using his crush's name(Ayushi) as variable name. XD.

https://codeforces.com/contest/1698/submission/162129130

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

C made me feel so dumb with 10 wa

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

My rank after system testing increased by 1000. This is unbelievable and I'm so happy about that.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

problem E, why the same code in GNU C++17 got tle, in Clang++20 Diagnostics got ac??? ac: https://codeforces.com/contest/1698/submission/162327659 tle: https://codeforces.com/contest/1698/submission/162327699

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

deja. Vu? Hmm something familiar!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I have been using a template for this contest which I found from an open-source, a few days back, and I believe that many other people might be using that code template, and thus it might have been plagiarised, and I confirm that the code for this problem was done completely by me. Please look into this matter. If required I am also ready to share the template that I used. 162153992 1698C - 3SUM Closure

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    The skipped solutions have the same implementation as the problem was pretty straightforward in this case you can see hmm