flamestorm's blog

Codeforces Round #803 (Div. 2)
By flamestorm, 6 weeks 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

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

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

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 5   Vote: I like it +16 Vote: I do not like it

    (Higher on the street)

    And I know it's my time to go

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -52 Vote: I do not like it

      which one are you talking about lmao this is the best

      Olivia Rodrigo — deja vu

      Car rides to Malibu
      Strawberry ice cream
      One spoon for two
      And trading jackets
      Laughing 'bout how small it looks on you
      (Ha-ha-ha-ha, ha-ha-ha-ha, ha-ha-ha-ha)
      Watching reruns of Glee
      Being annoying
      Singing in harmony
      I bet she's bragging
      To all her friends, saying you're so unique, hmm
      So when you gonna tell her
      That we did that, too?
      She thinks it's special
      But it's all reused
      That was our place, I found it first
      I made the jokes you tell to her when she's with you
      Do you get déjà vu when she's with you?
      Do you get déjà vu? (Ah), hmm
      Do you get déjà vu, huh?
      Do you call her
      Almost say my name?
      'Cause let's be honest
      We kinda do sound the same
      Another actress
      I hate to think that I was just your type
      I'll bet that she knows Billy Joel
      'Cause you played her "Uptown Girl"
      You're singing it together
      Now I bet you even tell her
      How you love her
      In between the chorus and the verse (ooh) (I love you)
      So when you gonna tell her
      That we did that, too?
      She thinks it's special
      But it's all reused
      That was the show we talked about
      Played you the song she's singing now when she's with you
      Do you get déjà vu when she's with you?
      Do you get déjà vu? Oh
      Do you get déjà vu?
      Strawberry ice cream in Malibu
      Don't act like we didn't do that shit, too
      You're trading jackets like we used to do
      (Yeah, everything is all reused)
      Play her piano, but she doesn't know (oh, oh)
      That I was the one who taught you Billy Joel (oh)
      A different girl now, but there's nothing new
      (I know you get déjà vu)

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

      Calling you, and the search is a mystery

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

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

    nice photo

    → Reply
»
6 weeks 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
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

Teach me the ways flame :orz:

→ Reply
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please tell me how to be a tester for contests

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

their will be no perfect rating in this round

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

Why are there at most 1 interactive problem and not 998244352

→ Reply
»
6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

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

Excited!

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

Good luck everyone :)

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

there will be no perfect rating in this round

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My idea

You should start with B

GOOD LUCK

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Mysterious score distribution!!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thank god speedforces

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

This is my first time,I'm scard

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

this round is much intresting

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's polygon?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I will try to make at least 3 problems today :)

→ Reply
»
6 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Python is the best programming language in the world!

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

    Until you become pupil.

    → Reply
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C is interactive ?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will have to flush the output buffer for the interactive problem

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I really love 250 problems in the contest :)) thanks for that :))

→ Reply
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hope i am lucky this time.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

it's morbing time

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to attempt D question?

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

Looking forward to a great contest

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

whyl i can't register?

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

yet, another speedforces round?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

YESSS, I will be newbie again!!!

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

Problem A is a very greedy !!

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

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

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

Problem A was a great scam :3

→ Reply
»
6 weeks 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
  • »
    »
    6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
    • »
      »
      »
      6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +65 Vote: I do not like it

I hate this round

→ Reply
»
6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
        • »
          »
          »
          »
          »
          6 weeks 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
          • »
            »
            »
            »
            »
            »
            6 weeks 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
            • »
              »
              »
              »
              »
              »
              »
              6 weeks 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
              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks ago, # ^ |
                  Vote: I like it -10 Vote: I do not like it

                thats great, wish you progress :)

                → Reply
      • »
        »
        »
        »
        6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

-500 incoming

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C?

→ Reply
  • »
    »
    6 weeks 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
  • »
    »
    6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What in the name of lord was the third question. GODDAMNIT!!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome question but got stuck in C ..Anyone can explain me plzz ?

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

    for n<=4 brute force and for n>4 if number of zeroes>=(n-1) its a yes else if number of zeroes=n-2 and rest 2 numbers add to zero then yes, else no!

    → Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it -6 Vote: I do not like it

ConstructiveForces

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C is pretty strange :)

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

    Yea should pass, why not

    → Reply
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      His/her brute force will catch it though :)

      → Reply
      • »
        »
        »
        »
        6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

wandering here after solving a,b,c :P

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

    how to solve c

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

      sort the array & see if last three are positive or first three are negative , if anyone above is true then answer is NO . else both the cases are failed means there is zero in between repeatingly so take first three element & last three element & apply brute force

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    Hint

    → Reply
    • »
      »
      »
      6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

How to solve E lol

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

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

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

interactive = binary search

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

wow took me an hour and a half just to solve A lol

→ Reply
»
6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey could you please help me find the failing test case in 162156403 for yesterday's C problem.

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

      E — reversing an array using impicit treap

      come again?

      → Reply
  • »
    »
    6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem C I tried to observe only one pattern sum of all numbers must be zero. I couldn't further break it down.

→ Reply
»
6 weeks 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
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

whats wrong in this code? https://codeforces.com/contest/1698/submission/162151736 in problem c.

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

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

→ Reply
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So do I

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

    -3a -a a a

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

More tricky than interesting... shortcuts on A, B, C made my completely moronic solve-of-something-trivial-that-isn't-the-problem for D seem way too plausible. Even had the usual binary search thought and how the constraints fit... but was already locked in on the stupid. OH well.

A smarter me would retire until end of daylight savings... even if I successfully carve out time, I still rush in anticipation of getting interrupted... results have been less than comical.

→ Reply
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Run your program with and without it and you will see

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

      I wish I could run but the wait for the system test is killing me.

      → Reply
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Understood it now. I thought adding "fflush(stdout)" will flush the output but it didn't. Is it because of "\n"?

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

        because they are not the same stream. use cout.flush() instead or remove the iosbasesync with stdio null line... this line is responsible for temporal aligning of c and cpp buffers

        for ref. https://stackoverflow.com/a/41777103/

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

the problem statements robbed me (" _ ")

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

    You can print any of the elements

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

    I think it can be any element

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

      WHY???!!!

      → Reply
      • »
        »
        »
        »
        6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As xor of whole array is zero, you can pick any element to be the xor of rest other elements. So it can be any element, not just element 0

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

    it is not the first element.. it is any element lol

    say XOR of n-1 is $$$a$$$, then XOR'ing the XOR of n-1 elements with $$$a$$$ means $$$a\oplus a=0$$$. Now, when you are given n elements, you can literally pick any element say "k" and the XOR sum of the remaining n-1 elements is guaranteed to be "k" because $$$x\oplus y=0$$$ iff $$$x=y$$$

    → Reply
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve b TT

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

    If k==1, then you can increase alternate elements to any height except 1st and last element. So answer = (n-2 + 1)/2

    else: if k>1 then if you apply operation on any range, then it would not be useful as it will also increase the count of adjcent element. So the answer is the tall piles without any operation.

    → Reply
»
6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate a lil?

    → Reply
    • »
      »
      »
      6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    there is a hint in the editorial, but imo it kinda sucks.

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Hint 1
    Hint 2
    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why I should use Bsearch in problem D? TIA

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

    First of all notice the constraints. n is upto 10^4 and maximum no. of operations is 15. Observing this, it is clear that the solution has to be in log(n) and hence binary search is the best approach (as far as I thought of it).

    → Reply
»
6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right, I did not read the statement well, thank you.

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

    See the announcement during the round.

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

      You are right, I did not read the statement well, thanks

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

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

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

    I did, but announcement wasn't for me, i knew that it should be true for every i,j,k index

    → Reply
»
6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this contest is unratted in my profile ?

→ Reply
»
6 weeks ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

my solution for problem d is giving different output's on my pc and on online compiler (https://codeforces.com/contest/1698/submission/162170632)

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

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

→ Reply
»
6 weeks 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

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The round teach me to be more carefully,i must be stronger after some trainings

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

So many people got many wrong answers to problem C. The main issue with everyone was that they thought, they could solve it by just observing some test cases. I, myself got 6 WA in C. Hope I will do better in upcoming rounds.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C made me feel so dumb with 10 wa

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

预警糖

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

it's so hard being a rookie.

→ Reply
»
6 weeks 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
»
5 weeks 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

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

Codeforces Global Round 21(Question C)

Can anyone please please help me...like where I'm wrong in this code? 162330458

I have been trying to resolve it. But it's been two days and I am not able to find any clue, any help. Please help!

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

deja. Vu? Hmm something familiar!

→ Reply
»
5 weeks 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
  • »
    »
    5 weeks 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
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, my contest has been skipped for code similarity at 1698B - Rising Sand. After I got the message i looked at the other guy's code and i saw that they are similar 162137682 162082266, but it was an easy problem with straightforward solution. I demand to get back my contest result back. flamestorm ScarletS MikeMirzayanov errorgorn

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is it rated?

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

→ Reply