flamestorm's blog

Codeforces Round #803 (Div. 2)
By flamestorm, 2 years ago, In English

Hi Codeforces!

ScarletS and I are glad to invite you to Codeforces Round 803 (Div. 2) which will be held on 28.06.2022 17:35 (Московское время). 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

Comments Comments (194)
| Write comment?
»
2 years ago, # |
  Vote: I like it +56 Vote: I do not like it

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

→ Reply
»
2 years 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

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

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

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

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

→ Reply
»
2 years 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

→ Reply
»
2 years 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 :)

→ Reply
»
2 years 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.

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

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

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

Teach me the ways flame :orz:

→ Reply
»
2 years 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 !!

→ Reply
»
2 years 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

→ Reply
»
2 years 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

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

Why are there at most 1 interactive problem and not 998244352

→ Reply
»
2 years 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

→ Reply
  • »
    »
    2 years 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

    → Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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

    → Reply
»
2 years 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

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

→ Reply
»
2 years 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.

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

Excited!

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

Good luck everyone :)

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

thank god speedforces

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

This is my first time,I'm scard

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -33 Vote: I do not like it

this round is much intresting

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

:)

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

    Until you become pupil.

    → Reply
    • »
      »
      »
      2 years 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.

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

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

        → Reply
»
2 years 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.

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

it's morbing time

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

How to attempt D question?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +50 Vote: I do not like it
    1. Read the problem.
    2. Think hard.
    3. Write down the solution.
    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

whyl i can't register?

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

yet, another speedforces round?

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

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

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

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

    → Reply
    • »
      »
      »
      2 years 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 .

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

Problem A is a very greedy !!

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

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

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

Problem A was a great scam :3

→ Reply
»
2 years 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 :(

→ Reply
  • »
    »
    2 years 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.

    → Reply
  • »
    »
    2 years 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.

    → Reply
    • »
      »
      »
      2 years 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?

      → Reply
      • »
        »
        »
        »
        2 years 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.

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

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

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

      lets say my array is [1, 2, 3, 6], will be the answer be yes or no ?

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

I hate this round

→ Reply
»
2 years 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.

→ Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years 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.

    → Reply
  • »
    »
    2 years 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

    → Reply
    • »
      »
      »
      2 years 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 :)

      → Reply
      • »
        »
        »
        »
        2 years 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

        → Reply
        • »
          »
          »
          »
          »
          2 years 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.

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

            Here it is: 162142911

            but it is a bit messy so:

            Solution
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years 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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it -10 Vote: I do not like it

                thats great, wish you progress :)

                → Reply
      • »
        »
        »
        »
        2 years 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]

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

-500 incoming

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

How to solve problem C?

→ Reply
  • »
    »
    2 years 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.

    → Reply
  • »
    »
    2 years 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.

    → Reply
  • »
    »
    2 years 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.

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

C is pretty strange :)

I hope it will pass
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yea should pass, why not

    → Reply
  • »
    »
    2 years 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"

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

      His/her brute force will catch it though :)

      → Reply
      • »
        »
        »
        »
        2 years 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 (^^ゞ

        → Reply
      • »
        »
        »
        »
        2 years 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

        → Reply
»
2 years 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...

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

wandering here after solving a,b,c :P

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

How to solve D?

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

    Hint

    → Reply
    • »
      »
      »
      2 years 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

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

How to solve E lol

→ Reply
  • »
    »
    2 years 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))

    → Reply
    • »
      »
      »
      2 years 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!!

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

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

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

interactive = binary search

→ Reply
»
2 years 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 !

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

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

    → Reply
    • »
      »
      »
      2 years 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.

      → Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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

    → Reply
    • »
      »
      »
      2 years 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 :)

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

      E — reversing an array using impicit treap

      come again?

      → Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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 ?

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

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

    → Reply
    • »
      »
      »
      2 years 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. ?

      → Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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.

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

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

    → Reply
    • »
      »
      »
      2 years 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 :( )

      → Reply
  • »
    »
    2 years 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.

    → Reply
»
2 years 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

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

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

→ Reply
  • »
    »
    2 years 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.

    → Reply
    • »
      »
      »
      2 years 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?

      → Reply
»
2 years 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 :')

→ Reply
  • »
    »
    2 years 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. :(

    → Reply
    • »
      »
      »
      2 years 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

      → Reply
      • »
        »
        »
        »
        2 years 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.

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

      So do I

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

    -3a -a a a

    → Reply
»
2 years 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?

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

    Run your program with and without it and you will see

    → Reply
  • »
    »
    2 years 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/

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

the problem statements robbed me (" _ ")

→ Reply
»
2 years 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

→ Reply
»
2 years 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.

→ Reply
»
2 years 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

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

    You can print any of the elements

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

    I think it can be any element

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

      WHY???!!!

      → Reply
      • »
        »
        »
        »
        2 years 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.

        → Reply
»
2 years 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.

→ Reply
»
2 years 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

→ Reply
»
2 years 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.

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

    Can you elaborate a lil?

    → Reply
    • »
      »
      »
      2 years 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.

      → Reply
»
2 years 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!

→ Reply
»
2 years 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?

→ Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Hint 1
    Hint 2
    → Reply
»
2 years 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

→ Reply
  • »
    »
    2 years 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.

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

    See the announcement during the round.

    → Reply
»
2 years 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)?

→ Reply
  • »
    »
    2 years 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.

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

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

→ Reply
»
2 years 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 ??

→ Reply
  • »
    »
    2 years 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

    → Reply
    • »
      »
      »
      2 years 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)))

      → Reply
      • »
        »
        »
        »
        2 years 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

        → Reply
»
2 years 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

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

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

    → Reply
»
2 years 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

→ Reply
»
2 years 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.

→ Reply
»
2 years 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!

→ Reply
»
2 years 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
→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
2 years 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.net/contest/1698/submission/162129130

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

C made me feel so dumb with 10 wa

→ Reply
»
2 years 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.

→ Reply
»
2 years 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.net/contest/1698/submission/162327659 tle: https://codeforces.net/contest/1698/submission/162327699

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

deja. Vu? Hmm something familiar!

→ Reply
»
2 years 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

→ Reply
  • »
    »
    2 years 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

    → Reply