Nezzar's blog

Codeforces Round #698 (Div.1, Div.2)
By Nezzar, history, 4 years 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. Rewinding
  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

Comments Comments (231)
| Write comment?
»
4 years ago, # |
  Vote: I like it +634 Vote: I do not like it

As an author...

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

As a 17:35 msk hater...

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

missing almost-copy-pasted-part lmao

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

Setters and testers from Hong Kong :o

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

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

Hope it remains rated.

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

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

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

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

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

How much delay this time?

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

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

    Sure thing

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

      Infinite thanks

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

        Does this mean that:

        • $$$ thanks = + \infty $$$
        • $$$+\infty \le thanks \le +\infty $$$
        → Reply
  • »
    »
    4 years 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).

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

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

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

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

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

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

Long time no see (div1)

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

finally div1! ^_^

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +56 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    • as a tester
    → Reply
  • »
    »
    4 years 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.

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

I have noticed that there are no weekend contests?

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

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

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

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

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

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

    Thankyou for the contest :)

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

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

It would be interesting if n <= -135

→ Reply
»
4 years 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^__^

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

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

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

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

Codeforces Declares round unrated due to long queues.

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

    No problem, just extend the round by 30 mins

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

Notice the unusual solving time (135 mins).

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

Finally a div1 round!

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

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

Oh well...

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

→ Reply
  • »
    »
    4 years 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)}$$$?

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

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

135 minutes! It is interesting.

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

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

    long queues started even before the beginning of the contest

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

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

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

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

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

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

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

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

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

    u r right

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

I hope I can solve problem D in this contest.

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

Good luck!

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

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

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

Fortunately the wait for div1 + div2 is over

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

oh！Good luck！

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

    im the first upvote of your first comment :dab:

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

Hoping a good contest today without any queue issues :)

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

contest getting delayed in 1....

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

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

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

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

    Yes, the queue is very large. I hope it will be fixed soon.

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

YES_NO-forces :D

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

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

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

    The latest submission is considered.

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

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

Very nice problem set... thank you authors

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

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

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

How to solve C?

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

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

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

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

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

      to exclude 0 I think

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

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

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

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

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

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

    It is not atcoder no!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        why num>=10*d is always YES.

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

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

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

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

how to do D?

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Nezzar's favourite jumps
→ Reply
»
4 years 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

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

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

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

Any hints for D?

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

    → Reply
  • »
    »
    4 years 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)$$$.

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

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

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

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

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

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

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

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

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

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

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

    both segment tree and chtholly tree is ok

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

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

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

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

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

https://acm.timus.ru/problem.aspx?space=1&num=1578&locale=en

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

    deleted

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

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

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

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

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

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

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

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

Such an awful and terrible and unfair contest

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

    Why? Was there some issue in Div 2?

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

    I do not see how it was unfair.

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

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

Chinese contests are even more faulty than Chinese goods.

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

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

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

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

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

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

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

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

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

In div1 C, is the answer always possible?

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

As an

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

Welcome to MathForces

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

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

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

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

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

Thanks for contest! C was very nice to solve.

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

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

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

        For a, the sum shouldn't be:

        $$$(a - a) + (a - (-a)) + (b - a) + (a - (-b)) + (c - a) + (a - (-c)) = 2(a + b + c)$$$

        ?

        nvm its a > b > c not a < b < c

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Check out my explanation of problem C — solution

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

what is 10013th testcase in B??

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

}

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

Some tags

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

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

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

.

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

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

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

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

Can anyone explain the intuition or solution to problem D?

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

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

Love this contest <3

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

→ Reply