Nezzar's blog

By Nezzar, history, 5 weeks 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 28.01.2021 17:35 (Московское время).

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 weeks ago, # |
  Vote: I like it +634 Vote: I do not like it

As an author...

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

As a 17:35 msk hater...

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

missing almost-copy-pasted-part lmao

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

Setters and testers from Hong Kong :o

»
5 weeks 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 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope it remains rated.

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

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

  • »
    »
    5 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

How much delay this time?

»
5 weeks 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 weeks ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Sure thing

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

      Infinite thanks

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

        Does this mean that:

        • $$$ thanks = + \infty $$$
        • $$$+\infty \le thanks \le +\infty $$$
        • »
          »
          »
          »
          »
          5 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

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

»
5 weeks 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 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

Long time no see (div1)

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

finally div1! ^_^

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

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    • as a tester
  • »
    »
    5 weeks 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 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

I have noticed that there are no weekend contests?

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

    Thankyou for the contest :)

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

It would be interesting if n <= -135

»
5 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

Codeforces Declares round unrated due to long queues.

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

    No problem, just extend the round by 30 mins

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

As a participant....

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

Notice the unusual solving time (135 mins).

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

Finally a div1 round!

»
5 weeks 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 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

Oh well...

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

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

Will there be a contest for fines or balls?

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

135 minutes! It is interesting.

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

    long queues started even before the beginning of the contest

»
5 weeks 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 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

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

»
5 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

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

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

    u r right

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

I hope I can solve problem D in this contest.

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

Good luck!

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

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

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

Fortunately the wait for div1 + div2 is over

»
5 weeks 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 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

oh!Good luck!

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

    im the first upvote of your first comment :dab:

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

Hoping a good contest today without any queue issues :)

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

contest getting delayed in 1....

»
5 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

YES_NO-forces :D

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

    The latest submission is considered.

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

Very nice problem set... thank you authors

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

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

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

How to solve C?

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

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

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

      to exclude 0 I think

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

    It is not atcoder no!

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

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

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

        why num>=10*d is always YES.

        • »
          »
          »
          »
          »
          4 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

how to do D?

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

Any hints for D?

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

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

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

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

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

    both segment tree and chtholly tree is ok

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

    me too :(

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

I am so happy! :D

»
5 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +67 Vote: I do not like it
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -78 Vote: I do not like it

    deleted

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

Can D be solved using the concept of two sum?

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

Such an awful and terrible and unfair contest

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

    I agree with you

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

    Why? Was there some issue in Div 2?

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

    I do not see how it was unfair.

  • »
    »
    5 weeks 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 weeks ago, # |
  Vote: I like it -119 Vote: I do not like it

Chinese contests are even more faulty than Chinese goods.

»
5 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

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

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

In div1 C, is the answer always possible?

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

As an

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

Welcome to MathForces

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

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

Thanks for contest! C was very nice to solve.

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

    d = 2, a = 21

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

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

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

    Dude what the heck are you saying lol

    • »
      »
      »
      5 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    Get a life bro,may u improve in future

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

Check out my explanation of problem C — solution

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

what is 10013th testcase in B??

»
5 weeks 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 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

Some tags

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

.

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

Hard Div 2C:-)

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

Love this contest <3

»
5 weeks 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

»
4 weeks 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.

»
4 weeks 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.