Nezzar's blog

By Nezzar, history, 5 months ago, In English

Good morning/afternoon/evening, Codeforcers!

We (Nezzar, triple__a, Nanako) are very excited to present to you Codeforces Round #698 (Div. 1) and Codeforces Round #698 (Div. 2), which will take place in Jan/28/2021 17:35 (Moscow time).

There will be 6 tasks waiting for you to be solved in 135 minutes!

We would also want to thank:

Score distribution will be announced at $$$n$$$ $$$(0 \leq n < + \infty)$$$ minutes before round starts.

We hope you high performance with a lot of points earned during contest!

UPD1 $$$n$$$ is chosen to be $$$300$$$.

Score distribution is

Div. 2: 500-1000-1500-1500-2000-2500

Div. 1: 500-1000-1500-2250-2750-4000

UPD2 The contest is ended despite CodeForces under attack from DDoS midway. Thanks all for joining!

Here is the editorial: Editorial

UPD3

Congratulations to the winners!

Div 1:

  1. maroonrk
  2. panole
  3. tourist
  4. Miracle03
  5. boboniu (The only contestant who solved F during contest time!)

div 2:

  1. bahu
  2. yplane
  3. islingr
  4. chen__zexing
  5. ChuTian

People who were first to solve each task:

D2A: pj423

D2B: Zeyush

D2C: BelieveInYou

D2D/D1A: IgorI

D2E/D1B: SSRS_

D2F/D1C: Benq

D1D: Um_nik

D1E: tourist

D1F: boboniu

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

»
5 months ago, # |
  Vote: I like it +634 Vote: I do not like it

As an author...

»
5 months ago, # |
  Vote: I like it +115 Vote: I do not like it

As a 17:35 msk hater...

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

missing almost-copy-pasted-part lmao

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Setters and testers from Hong Kong :o

»
5 months ago, # |
  Vote: I like it +36 Vote: I do not like it

My first round after a long pause. Wish all participants good luck and easy problems

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope it remains rated.

»
5 months ago, # |
  Vote: I like it +72 Vote: I do not like it

Um contest tab shows 120 minutes but you said 135 minutes?

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

    Nice catch! The one in contest tab will be changed to 135 minutes.

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

      Please give me 100 points for successful hacking attempt in this round. Thanks.

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

How much delay this time?

»
5 months ago, # |
Rev. 2   Vote: I like it +168 Vote: I do not like it

A question regarding the constraints of n:

Shouldn't it be $$$(0 \leq n < + \infty)$$$ instead of $$$(0 \leq n \leq + \infty)$$$?

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

    Sure thing

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

      Infinite thanks

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

        Does this mean that:

        • $$$ thanks = + \infty $$$
        • $$$+\infty \le thanks \le +\infty $$$
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it -43 Vote: I do not like it

          $$$-\infty \lt thanks \lt +\infty$$$ is finite. That leaves us with $$$thanks \in$$$ {$$$-\infty, +\infty$$$}.

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

    We can actually make the constraints better. Since we will anyways get the scoring distribution after this certain point of time the range of $$$n$$$ can be better written as $$$0 \le n \le f$$$ where $$$f$$$ is a finite number which I don't have the finiteness to calculate.(but it is finite).

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by Nezzar (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it +28 Vote: I do not like it

As a Japanese participant, I was amazed that there is another p*0523 near Japanese testers in the post...!

»
5 months ago, # |
  Vote: I like it +38 Vote: I do not like it

It's comforting to know that $$$n \ge 0$$$.

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

Thanks for the contest Nezzar, I am a beginner and I managed to solved three questions in the previous contest, really hyped, looking forward to this one too... Love you codeforces Family!!!

»
5 months ago, # |
  Vote: I like it +43 Vote: I do not like it

Long time no see (div1)

»
5 months ago, # |
  Vote: I like it +27 Vote: I do not like it

finally div1! ^_^

»
5 months ago, # |
Rev. 3   Vote: I like it +56 Vote: I do not like it

As a tester...
Hope this round will go smoothly!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    • as a tester
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Let's hope that MikeMirzayanov does not have any doctor's appointment scheduled for Thursday.

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I have noticed that there are no weekend contests?

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you triple__a, Nezzar and Nanako for preparing div.1 and div.2 contests.

»
5 months ago, # |
  Vote: I like it +206 Vote: I do not like it

Just going to say that I'm a huge fan of starting round announcements with a "Good Morning!"

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

I just hope this round goes smoothly. Last Div3 round could had been my best round but nevertheless lets keep our spirits high for this one. Until then lets keep upsolving and discussing.

»
5 months ago, # |
  Vote: I like it +149 Vote: I do not like it

As a co-author...

Maybe I don't really deserve this appellation... I think I'm more like a tester because triple_a and Nezzar come up with many ideas with great inspiration when I just come up with much less ideas (and finally none of mine is interesting enough to become a problem in this round lul).

triple_a and Nezzar is really respectable. They spend half a year preparing this round. Comparing with them, I think I just do something that's not worth much mentioning.

Hope you can have fun in this round!

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

    I am sure all of you work very hard and prepare such contests. Thank you for all the efforts you put!

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    I can understand you. Different coordinators have different review standards. Some coordinators are very strict, and they have a very low pass rate for the questions they review. This does not mean that your topic is not interesting enough, maybe it is just that the level of interestingness does not meet the standards of this coordinator. Different coordinators have different definitions of interesting, so your topic does not seem interesting enough for this coordinator, but another coordinator (possibly) will find your topic interesting. Then, even if your topic is not selected, I think your contribution is enough to make us thank you. Looking forward to solving the problem of your proposition, although my level is not high, I will try my best.(One more thing to say, if your dream is to be an excellent writer, don't be disappointed in yourself. I believe that one day, you can impress the coordinator with your interesting topic.)

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

    Thankyou for the contest :)

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

n can be equal to 0 as well, then scoring distribution may be known only when the contest starts? :(

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

It would be interesting if n <= -135

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

I hope there wont be delay like last contest. It sucks and then gets unrated.

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

And what are the chances that there will be no problems at this contest, it would simply be sad if the contest did not become a rating?(((

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

Another China round! Thank you very much for the selfless dedication of the authors and testers, so that we can have a different experience. Then, let me guess, after this round, another China round is coming soon? (maybe the global round)? Let me look forward to it^__^

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

As a tester, hopefully you also find the problems are interesting like I do! I enjoy testing the problem set even I test it after tiring work. Good luck all!

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

Why can't users with a $$$1900 \leq rating < 2100$$$ register for the Div. 2?

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    In every Div1 + Div2 round, Candidate Masters are considered Div1 participants.

»
5 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Codeforces Declares round unrated due to long queues.

Meanwhile Codechef
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    No problem, just extend the round by 30 mins

»
5 months ago, # |
  Vote: I like it -22 Vote: I do not like it

As a participant....

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Notice the unusual solving time (135 mins).

»
5 months ago, # |
  Vote: I like it +111 Vote: I do not like it

Finally a div1 round!

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

could've easily had a tighter bound for n(the total no. of mins before the round starts)

»
5 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Oh well...

17:35(UTC)=22:35(UTC+8)=less sleep

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

    Since when $$$17.35 \text{ (UTC)} = 22.35 \text{ (UTC+8)}$$$ :( ? Did you mean $$$17.35 \textbf{ (MSK)}$$$?

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Will there be a contest for fines or balls?

»
5 months ago, # |
Rev. 2   Vote: I like it -24 Vote: I do not like it

My question is in this solution 105544722 return me answer please

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

135 minutes! It is interesting.

»
5 months ago, # |
  Vote: I like it -21 Vote: I do not like it

We are hopefully waiting for a rated round.Unfortunately the last round (div-3) was unrated.We think "Codeforces Community" will be able to overcome those obstacles.Thank You.

»
5 months ago, # |
  Vote: I like it +56 Vote: I do not like it
queue<long> q;

Long queue or something IDK, but I hope it does not happen :D

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

    long queues started even before the beginning of the contest

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

Score distribution will be announced at n (0 ≤ n < +∞) minutes before round starts.

Does this mean it is possible it will not be included in blog before contest, rather we will be seeing the distribution in contest?

»
5 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Well DIv2 D = DIv1 A with this score distribution right!

»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Nezzar Please remove "!" from 300, it seems like you want to say 300 factorial :(

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I suggest holding a testing contest before today's contest to test the In queue, MikeMirzayanov!

»
5 months ago, # |
  Vote: I like it +32 Vote: I do not like it

$$$4000$$$ points for Div.1 F...That's gonna be tough.

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

    they said that it took half-year preparing it so they had put a lot of effort to make it. so I think why problem F gives 4000 points and I think div2 will have a subproblem.

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

    u r right

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

I hope I can solve problem D in this contest.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Good luck!

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Interesting score distribution for Problem C and D.. :)

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Fortunately the wait for div1 + div2 is over

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

Every Programming contests love 15+10 rather than 25. You can relate :)

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

oh!Good luck!

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

    im the first upvote of your first comment :dab:

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

Hoping a good contest today without any queue issues :)

»
5 months ago, # |
  Vote: I like it -21 Vote: I do not like it

contest getting delayed in 1....

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

This is the joke about the hard contest you are looking for

»
5 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I am facing queue issues on Problem B

Is there someone else also ?

Edit: Resolved

»
5 months ago, # |
  Vote: I like it +35 Vote: I do not like it

YES_NO-forces :D

»
5 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Whoever came up with the problems really overestimates the CF community.

Jokes aside, a tough one for sure.

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

Hello Community. I want to ask one question. I submitted B problem twice, both passed pretests. Which one will be considered ? My rank went from 2200 to 4400 . Please somebody tell me .

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

    The latest submission is considered.

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

      I submitted first at 44 minutes and second at 1hr 2 min. So, the solution with 1hr 2min will be considered?

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

First time solved first 2 problems within 10 min :) ...Thanks for this problem set

»
5 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Very nice problem set... thank you authors

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone help me with the 2nd one after the contest?

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

    remove k from the number(n) until there is a digit k in n or n<=0..if n<=0 and we didnt find a number consist of digit k print no...if found print yes

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve C?

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    suppose n = 3 , then suppose array a will be of form $$$a_1<a_2<a_3$$$ and their negative values also . Then array d in increasing order will be (note that every number in d will be repeated twice so we are only considering n numbers) say $$$d_1<d_2<d_3$$$ then $$$2*(a_1+a_2+a_3) = d_1$$$ , $$$4*a_2 + 2*a_3 = d_2$$$ , $$$6*a_3 = d_3$$$ .You can show this by using formula in question. Now you can find $$$a_3,a_2,a_1$$$ one after the other using the equations .

    Similar generalization for any n.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      2∗(a1+a2+a3)=d1 , 4∗a2+2∗a3=d2 , 6∗a3=d3 can you explain this more?? UPD: got it

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

i probably overkilled C, but was there a reason for why the numbers were distinct? it cost me a WA coz I didn't think they should be, probably why my solution was hard.

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

    Exactly, there was no need of them to be distinct.

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

      to exclude 0 I think

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      There is a need for the values to be distinct because if you consider the array a = [-1 1 3 -3 -3 -3], you get the consequent d array to be [12 16 24 12 12 12], and therefore, a lot of useful properties fundamental for the original problem wouldn't be there.

»
5 months ago, # |
  Vote: I like it +104 Vote: I do not like it

A big big dislike for Div2 C and D. Both are more christmas riddles than programming problems. I do not care any more for orginal ideas or the like. For me this kind of riddles are only boring. You need to find some wired observation, like walking blind in a labyrinth finding the exit.

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

    totally agree, id rather have repetitive algorithmic problems than these find the pattern after 100 examples problems.

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

    Ya I don't know who likes these problems if most of them diskikes this type of problems then these puzzles are made for whom a big question mark on the community?

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

      I like them, and I know some others who do. More math-minded people I think tend to enjoy them

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

    It is not atcoder no!

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

    I think div2D/1A was a great problem. It was refreshing to see Bezout's Theorem, and it was a cute observation.

    Div 1B on the other hand was just standard lazy seg-tree so that wasn't so exciting but it was cool still.

    How to solve Div1C?

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

      If such things are cute for you ;)

      I liked the segment tree, the update operation was not very intuitive for me, I think I never implemented that kind of update before.

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

    I don't have any ideas about D, but I think the observation for C was not hard to stumble upon. I would say C was more intuitive and easier for me than B.

    Basically, take some small arrays, then try writing the sum of absolute difference for them, the way it's defined — but don't calculate the value, instead just observe the terms themselves in the sum of absolute difference.

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

      Yes, and some hundred participants did like this. Some other thousends did not. So where is the point?

      It was easy for you, so it is a good problem?

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

        It was hard for you, so is it a bad problem?

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 2   Vote: I like it +2 Vote: I do not like it

        I think if one were to try out small arrays and try to observe from them, the observation itself is not a very obscure pattern.

        But yes, I get your point. I am not saying it was a great problem — but was one of the better problems compared to other Div2 contests these days.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For C i solved by using the definition of how array d is constructed (by getting n equations).So it wasn't puzzle for sure.

    In D i observed (don't know if correct) that we require at most 2 numbers to create k .

    In B , i had idea that after a point all numbers can be created by lucky numbers but was not able prove it and didn't solved it.

    So i can't say anything regarding D and B.

    Let's hope tomorrows Educational round will be a good one.

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

    I disagree with you . They were really beautiful problem with some really good observation . I couldn't solve D but you can see my solution to C which is I think really clean and nice .

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

    These day if you want to get good in codeforces contest then it appears practicing puzzles is more beneficial than studying algorithms to

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

    agreed. Solving C was not at all fun. it was just some boring observations.

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

    Well, here is how you could navigate a labyrinth even blind without any weird observations or luck: click

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B and in problem D do we needed to check if k can be formed by any two numbers in array ?

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

    for problem B, you can use lucky number multiple times. means for d= 7, ai = 52, 7+7+7+7+7+17 is allowed answer

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

      You can compute all lucky smaller than d * 10. If the current number is >= d * 10, print "Yes. Else if it is among the previously calculated numbers print "YES". Else print "NO"

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

        why num>=10*d is always YES.

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

          Because no matter how much you subtract 7 from the number you get to a number that starts with 7 (70, 71,.., 79)

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

      for d=7 and ai=34, shall we split like 17+17..

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

    In problem B, we need to observe that for every number greater than 10*d, it is always possible to get the sum, for number < 10*d we can brute force and check.

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

      and that observation I made by running a dp solution up to some small numbers for each digit. I saw that beyond 10*d everything was possible. I could not prove this and continued with this observation.

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

        the simple proof of this is lets say a number is >= 10 * d then 10 * d would be of form "d0" then the remaining n % d part can be added to this number and still you have a digit 'd' on the tens place.

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

    For B notice that the number N can be written as floor(N/d)*d + N%d. Now if floor(N/d)>=10 then the answer is always yes as you can always club the remainder with the number of form 10*d and now this number formed i.e. 10d+N%d will always contain digit d. If floor(N/d)<10 then bruteforce for all x such that x*d+N%d contains d where x<10. Code:

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

      Can't we just say if a number is in the form of 10*x+y*d it will be a lucky number

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

how to do D?

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please give a test-case for which my code fails for problem C? WA_CODE

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

    The result of formula should not repeat and should not be negative.

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Any hints for D?

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

    You can view the operation as taking a number in the array and adding the difference (with your choice of sign) between any two other numbers of the array to it. Note that you can repeat the operation as many times as you want.

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

    Assume we have set $$$(a_{1}, \dots a_{n})$$$ and $$$g=gcd(a_{2}-a_{1}, \dots , a_{n}-a_{n-1})$$$. Then the closure of operation $$$2x-y$$$ is set $$$(\dots a_{1}-g, a_{1}, a_{1}+g, a_{1}+2g, \dots)$$$.

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

      Could you explain what is closure, seems interesting!!!

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

        Assume we have a set $$$S$$$ and operation "bring some numbers $$$a, b, \dots$$$, and insert into $$$S$$$ some value $$$f(a, b, \dots)$$$". Let do operation while we can get number, which is not in $$$S$$$. The set we got is called closure of set above operation (I am not sure if I wrote it correctly in english). It is just definition.

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

          Ohh nice, got it thanks for explaining

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

am I the only one, who just misunderstood the B problem statement. also i didnt find in question that the repetition is allowed. thanks to the problem setter, making difficult to understand problem statement.

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

So Div1B/Div2E isn't segment tree or what?

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

    I solved it using segment tree, don't know if there's an easier solution

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

    Yes, it was segtree with: "set all values in a range to $$$x$$$ " and "find sum of a range".

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

    Yes, you consider the queries in reverse order, and then note that the starting string is uniquely determined by the conditions (if at a point you have exactly half the elements in a range to be 0 and the other half to be 1, then this is invalid, and the answer is NO, otherwise you can just set the whole range to the majority element of the range). If the array so found is the same as the given initial array, then the answer is YES, else it's NO.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Exactly did this but probably there is sum bug in my code :(

      not exactly, After doing this i tried to change the array so that is the wrong logic :(

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

        I personally did a sum-query for each element (in the form [l, r] = [i, i]) to retrieve the new array using these operations, so this might be useful if you can afford to take $$$O(n \log n)$$$ time for creating the final array.

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

    both segment tree and chtholly tree is ok

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Is there anyone who also got WA on pretest 7 in Problem C.

Very disappointing problem c :(

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

    me too :(

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

    I got too,but I resolved it during the contest. My bug was that the array formed after deleting the repeating numbers should be exactly of size n. Maybe check this.

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

    Assuming we did the same thing, i.e. creating the sorted positive half of array a, I was getting it when I was checking if the array is non-decreasing, it was resolved when I checked the array to be strictly increasing.

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

I am so happy! :D

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

In div 2D, If we can form any two consecutive numbers, we can form any number. Was this observation helpful?

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

    Very close, but no. The observation that works is that if you take the difference of all elements with the first element, and call the resulting array $$$b_1, \dots, b_{n - 1}$$$, then performing the operation corresponds to finding the sum/difference of a few of these elements, and you can find an operation where it corresponds to finding the sum/difference of any two elements of $$$b_i$$$. Hence, the gcd of all $$$b_i$$$'s is achievable, and this is necessary and sufficient.

»
5 months ago, # |
  Vote: I like it +67 Vote: I do not like it
  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it -78 Vote: I do not like it

    deleted

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      Problems have been repeated many times in the past, verbatim. While the organizers try to avoid this, this doesn't make the contest unrated.

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

    We are really sorry that D1C has been appeared before. None of the team know the existence of this problem and we come up the whole problem ourselves (the idea comes from the lore actually)

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

      it's ok , i am not blaming you, i know it;s impossible to remember all the problems

»
5 months ago, # |
Rev. 3   Vote: I like it +48 Vote: I do not like it

When you use double to get the distance of two points with fuction sqrt in div.1C:

qaq

upd: WHY IT CAN PASS THE SYSTEM TEST? Too weak tests >_<

Hack case:
»
5 months ago, # |
  Vote: I like it -37 Vote: I do not like it

As a low-ranking coder in this round, I hope I can get some upvotes.

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

Can someone help me with this and why this gives Wrong answer on pretest 2.

Div2 Q2

https://codeforces.com/contest/1478/submission/105752797

»
5 months ago, # |
  Vote: I like it +23 Vote: I do not like it

F looks beautiful, but I have no idea how to solve it :<. After solving some differential equation I managed to understand first sample, but that doesn't generalize at all to almost any other inputs xd

  • »
    »
    5 months ago, # ^ |
    Rev. 4   Vote: I like it +39 Vote: I do not like it

    This paper explains how to count the probability that the maximum part is <=k after picking n random points. Then we need to put those probabilities into an exponential generating function, it turns out to be a sum of O(len) terms of form koef*exp(alpha*x)*x^beta for alpha of form i/total_length and beta up to total_length, so there are O(total_length^2) possible terms up to koef. Then we need to multiply all those generating functions, which boboniu does in O(total_length^3) by just using the fact that each of the functions has only O(len) nonzero terms so we can multiply naively, but maybe some FFT was required? The system test will tell :)

    Getting all details right within the contest is insane, hats off to boboniu!

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

      The editorial says that we actually have only O(n*total_length) nonzero terms in the product, therefore the naive multiplication is O(n*total_length^2) which should be good.

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

Can D be solved using the concept of two sum?

»
5 months ago, # |
  Vote: I like it -59 Vote: I do not like it

Such an awful and terrible and unfair contest

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it -32 Vote: I do not like it

    i don't think so, it was not good for me too but it doesn't mean that the contest was bad.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it -24 Vote: I do not like it

    I agree with you

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

    Why? Was there some issue in Div 2?

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

    I do not see how it was unfair.

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it +15 Vote: I do not like it

    Having more math elements in a contest isn't unfair to anyone. As long as the everybody can login at the same time, and the problems are correct, there is never an unfair contest. There may be "unbalanced" contest sometimes, but not this one. It isn't the author's fault if the problems had troubled you.

»
5 months ago, # |
  Vote: I like it -119 Vote: I do not like it

Chinese contests are even more faulty than Chinese goods.

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

For everyone who got WA on test 2, Div1B/Div2E, try this case:

2 1

11

10

1 2

The correct output is "NO", and if your output is "YES", you probably forgot that strictly less than half of the interval can be changed (at least that was my bug)

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

4/6 problems in div2(BCDE) just required me to output yes/no! I was grateful for not asking me to construct a way or something lol

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

Thanks for strong pretests for A and B....i loved to solve those....But couldn't even understand C

»
5 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Please next time don't give us riddles like C or D, we all want programming problems!

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

    What was the problem? I think they were perfectly fine problems.

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

    I liked C. (altho I could not solve it) I think it was more interesting than B.

»
5 months ago, # |
  Vote: I like it -21 Vote: I do not like it

DIV 2 (A + B) VIDEO EDITORIAL LINK : https://www.youtube.com/watch?v=amNk203dAGQ

»
5 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

After countless attempts and failing on B, losing 150 points and going down to 1500 from 1770 in just 2 contests, I've found a solution to the extended version of B.

So in case anybody is curious, suppose that the question also asked for example numbers, not just a "YES" or "NO".

We can see that number X * d, can be expressed as sum of X d's, in form:

d d d .... d (X times)

In other case, we can take a look at the number's last digit (say P) ans find the minimum multiple of d which corresponds to the same last digit. So suppose we have input:

113 7

The output should look like:

7 7 7 7 7 7 7 7 57

And how do we get this? Simply, if the multiple that corresponds to our last digit is equal to X * d, then we can take d and print it (X — 1) times and finally print S — (X — 1) * d, where S is the starting number.

The only case when it is impossible to print a valid sequence is when the lowest multiple with the same last digit is greater than our current number.

I hope some of you found this interesting, as it can be made into a solution to the easier version of the problem.

EDIT: And this goes to prove why 25 isn't possible, 53 isn't possible, 46 isn't possible, etc.

»
5 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

4 of the first 5 problems of Div2 were YES/NO problems. Maybe author's crush is very straightforward. Accpet or Reject his proposal in YES/NO

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

In div1 C, is the answer always possible?

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

As an

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

Welcome to MathForces

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

Auto comment: topic has been updated by Nezzar (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Who else got screwed in that contest? Though problem set was nice.

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

Thanks for contest! C was very nice to solve.

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

    Can you explain the idea? I tried reverse the array A, but it seems the wrong.

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

      I will give you an example to think about the idea. Let's say we have 3 distinct numbers (we will use the positive numbers since it is easier to reason about) [a, b, c] where a > b > c.

      Calculating the sum of differences for a:

        = (a - a) + (a - (-a)) + (a - b) + (a - (-b)) + (a - c) + (a - (-c))
        = 0 + 2a + a - b + a + b + a - c + a + c
        = 2a + 2a + 2a = 6a
      

      In general, with [a_1, ... , a_n], where a_1 > a_2 > .. > a_n, then sum of differences for a_1 is as follows:

        = 2a_1 + a_1 * (n-1) - (a_2 + a_3 + ... a+n) + a_1 * (n-1) + (a_2 + a_3 + ... a_n)
        = 2a_1 + a_1 *(n-1) + a_1 * (n-1)
        = 2 * n * a_1
      

      From this, you can find the value of a_1. Next, the way I thought about it was to consider [a_2, ..., a_n] (i.e. disregard a_1). But one thing is sum of differences for a_2 would be subtracted by 2a_1. This is because there is a term in the original sum of differences for a_2 (which includes a_1):

      (|a_2 - a_1| + a_2 + a_1) = a_1 - a_2 + a_2 + a_1 = 2a_1
      

      since we are disregarding a_1, we should subtract it by 2a_1.

      After subtracting, just do the same method as before to find a_2, then just do it until a_n.

      Hope this helps bro. Took me awhile to figure out.

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

        I did exactly this, probably I just have a bug. Thx for replying.

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

I'd like to ask

After I had passed the questions in the contest

Again, I submit the approved code for this topic

Why is the second pass time calculated

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

I solved B with coin change dp, anyone who had done the same???

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

105770938 In B, why I am getting wrong at test case 2 ?

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

    d = 2, a = 21

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      My code give "NO" output

      What is the solution if "YES"

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

        when d = 2, 21 itself is a lucky number :)

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

        There's a $$$2$$$ in $$$21$$$ so it is itself a lucky number. So YES

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

        "21" itself has 2, you dont have to make any other combination

        also try a=63,d=5

        5+5+53

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

Auto comment: topic has been updated by Nezzar (previous revision, new revision, compare).

»
5 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

it seems they didn't put the most basic case on problem C 1 1 0 0

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In the problem Div2(B), What was the case for which most of the submissions got Wrong Answer on Test Case 2 in 10021th Token??

»
5 months ago, # |
Rev. 2   Vote: I like it -48 Vote: I do not like it

No shade on the writers, the problems were very cool and clever. These kind of ad-hoc, constructive problems help with developing quick thinking and problem solving skills. And they are great in a contest as long as there's diversification in the problems. Or atleast 2 out of 5 contests focus on DSA skills too.

Majority of participants are here to improve their DS&A skills (by majority I mean people who don't have high ratings and aren't seasoned programmers). I would love to solve some questions on tree algorithms, dp, binary search, dsu or any basic/advanced algorithm once in a while to develop those skills too. I understand this might not be the priority for some participants, but this would help us keep in touch with actual data structures and algorithms.

Here is a blog (Changes in Codeforces problem style over 2020) where this issue is very well put.

PS — Using an alternate ID. Please read before downvoting. Thanks

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Okay, let me repeat.

    1) If you want to solve standard problems on tree/dp/dsu/e. t.c, then you can find it in any archive, you do not need to solve it during a real contest if you want to practice this topics.

    2) If you want to solve a non-standard problem using any algorithm at a contest, this is fine, but

    2.1) Such problems are almost always more difficult than Div2D, because otherwise required algorithm is much harder than problem itself

    2.2) it is very difficult to come up with a high-quality problem on a well-known topic (atleast for me :D)

»
5 months ago, # |
  Vote: I like it -32 Vote: I do not like it

if my code wasn't optimized enough to pass the system test why did it pass pretests? Come on Codeforces, what's the problem??

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

    Dude what the heck are you saying lol

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

      cos this is a problem that occurs more often than not. Getting TLE after passing pretest...

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

    Answer is quite obvious. You can think in two ways. This is the extended icpc rule.And you can see tons of submissions in each minute. If they provide more test cases, then probably it will results in long queue. So they try to reduce test cases and increase strong pretests. Though sometimes test cases might weak.

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

      yeah but they should care about the optimization factor as u don't want to get TLE after passing pretests

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

        You should perhaps see the time complexity of your solution first and cross check with the constraints. Just my Opinion.

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

can anybody please tell me what was the 10001st token on test case 4 for which my answer is wrong after passing all the pretest very disappointing

»
5 months ago, # |
  Vote: I like it +62 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

https://codeforces.com/contest/1478/submission/105734232

Nice way to escape from MOSS. Putting useless for loops!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    Get a life bro,may u improve in future

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

Check out my explanation of problem C — solution

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

what is 10013th testcase in B??

»
5 months ago, # |
  Vote: I like it -57 Vote: I do not like it

can someone point out the error in my code for div2-C

include <bits/stdc++.h>

include

define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

define ll long long

define endl "\n"

define lb lower_bound

define ub upper_bound

define fo(i,a,b) for(i=a;i<b;i++)

define all(v) (v).begin(),(v).end()

define all1(v) (v).begin()+1,(v).end()

define sort0(v) sort(all(v))

define max3(a,b,c) max(max((a),(b)),(c))

define max4(a,b,c,d) max(max((a),(b)),max((c),(d)))

define min3(a,b,c) min(min((a),(b)),(c))

define min4(a,b,c,d) min(min((a),(b)),max((c),(d)))

define pb push_back

define ppb pop_back

define mp make_pair

define inf 9999999999999

const ll mod=1e9+7;

ll inv(ll i){if(i==1) return 1;return (mod-((mod/i)*inv(mod%i))%mod)%mod;}

ll gcd(ll a,ll b){ if (b==0) return a;return gcd(b,a%b);}

ll pwr(ll a, ll b) {a %= mod; ll res = 1;while (b > 0) {if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1;}return res;} using namespace std;

int main() { fio; long long t; cin>>t; while(t--){ ll n,res=0,i,sum=0,max=0; cin>>n;

    ll a[2*n];
    fo(i,0,2*n)
    {cin>>a[i];
    if(a[i]%2!=0 or a[i]==0)
    res=1;}
    if(res==1)
    cout<<"NO"<<endl;
    else
    {sort(a,a+2*n);
    if(a[2*n-2]!=a[2*n-1])
    cout<<"NO"<<endl;
    else
    {fo(i,0,2*n-2)
    {
        if(a[i]!=a[i+1])
        {res=1;break;}
        if((a[i+2]-a[i])%2*(i/2+1)!=0 or a[i+2]==a[i])
        {res=1;break;}
        sum=sum+(a[i+2]-a[i])/(2*(i/2+1));
        /*cout<<sum<<" ";*/
        max=max+sum;
        i++;
    }
    /*cout<<max<<endl;*/
    if(res==1)
    cout<<"NO"<<endl;
    else
    {  if((a[0]-2*max)%(2*n)==0 and(a[0]-2*max>0))
        cout<<"YES"<<endl;
        else
        cout<<"NO"<<endl;
    }}}
}

return 0;

}

»
5 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Some tags

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

105785851 Why does this brute force sol work for div2 B? Shouldn't this get TLE?

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

    I think the constraint of number of test cases is saving the sol from getting TLE.

    1<=t<=9

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

Nice problem set. Enjoyed it. Also its my first time being pupil <3

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

.

»
5 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Oh god I just realized that tourist must be in second or first place to win some rating. That's scary...

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

Hard Div 2C:-)

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

Can somebody tell me how they got their idea of solving B, I found B really non intuitive.

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

    I just think that d < 10 so no matter what d and a you are working with, just minus d from a will give you a number with the digit in the tens (hundreds, thousands,...) place is d.

»
5 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can anyone explain the intuition or solution to problem D?

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

In the problem c , I dont know whats the tc , it'll be very helpful if someone figure outs the error ,by the way , the error that is being displayed by judge is in tc 11 (which is obviously is not visible due to its length) The code is here

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

Love this contest <3

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

Problem A: Can anyone say where did I get wrong? My code: https://codeforces.com/contest/1478/my

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

Why rating of contest has been rolled back temporary. Last time also it happened.

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

for D2F(D1C), it is quite easy, easier than D2D/D2E, why it is placed in the last problem, and get so much score? my solution is, firstly generate a random permutation as initialization, then brute force search an valid permutation based on this initialization permutation. the solution is very simple and source code is very short. if i know this i will definitly finish D2F earlier than D2D/D2E.