NemanjaSo2005's blog

By NemanjaSo2005, history, 11 months ago, In English

Hello, Codeforces!

Riblji_Keksic and I are glad to invite you to Codeforces Round 911 (Div. 2), which will start on Nov/26/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.

The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially.

All problems are invented and prepared by Riblji_Keksic and me.

Special thanks go to n0sk1ll and TimDee for their great work during the testing process of the round.

And of course, I would love to thank the people who made this round possible:

We hope that you will participate and enjoy the round!

Update 1: The score distribution is 500 — 1000 — 1250 — 2000 — 2250 — 3000

Update 2: Congratulations to the winners:

Div. 2:

  1. HimenoTowa

  2. vflower

  3. eloge

  4. azureglow

  5. Im_dik

  6. Gold_Record

  7. Haaland

  8. mban259

  9. hazzler

  10. 111445

All participants:

  1. fallleaves07

  2. turmax

  3. A_G

  4. ppavic

  5. minato

  6. Umi

  7. potato167

  8. Rubikun

  9. Sugar_fan

  10. emthrm

First solvers:

A. people_plus_plus in 0:01

B. A_G in 0:04

C. WLZ in 0:04

D. A_G in 0:12

E. Superposition in 0:17

F. turmax in 0:26

Update 3: Editorial

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

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

Codeforces Round 911 whats your emergency?

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

    My Rating is dead.

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

      Can you explain more, why is your rating dead?

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

    I got stuck o B, please help!!

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

      When you think of the parity of numbers, there are three distinct situations that can be easily proven.

      1) If all three numbers are either odd or even, then the answer will be 1 1 1.

      2) If two of the numbers are even and the other one is odd, then the answer will be the odd number.

      3) If two of the numbers are odd and the other one is even, then the answer will be the even number.

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

        Yeah thanks I already solve it, just joking

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

        for a = 1, b = 3, c = 7 can you tell stepwise how can I achieve all numbers as 1

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

          Erase 2 and 3 three times and write 1 each time. Then you have 4 1s, no 2s, and 4 3s. Now use the following procedure: erase 1 and 3, writing 2. Then erase 2 and 3, and write 1. This decreases the number of 3s by 2, and doesn't change the number of 1s. Do this twice, and you have 4 1s and nothing else.

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

            Ohk got it, I was stuck on the approach that I would need sufficient number of 1s beforehand to make number of 2s and 3s equal didn't consider the 1s which are generating. Thank you.

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

          1,3,7 notice that if the other two of the numbers are the same you can always get the answer for A 1 3 7 -> 2 2 6 > 3 1 5 > 2 2 4 > 3 1 3 > 2 2 2

          More generally, the strategy is to alternate increasing the the one we are picking and the minimum of the other 2 numbers until the third number decreases and reaches the other number. So if we are picking A and b < c, we alternate between A and B until b=c.

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

        thanks

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

      Since, 1^2^3 = 0, after any operation you cannot change the xor. So if xor != 0, then only xor can be achieved, it can be achieved by doing n-1 operations. Otherwise, all can be achieved by the following operations, let's say you want xor to be 1, then if 2 and 3 exists then do operation on them, otherwise do it on 1 and other existing number. This will ensure that at least one 1 exists in array after any operations.

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

    my laptop is on fire send the firefighters

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

    Just a small thing, sir!

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

Definitely a round I enjoyed testing! NemanjaSo2005 Riblji_Keksic orz

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

Canon round.

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

    become specialist in this one, canon event

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

      let's see who becomes specialist first

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

        challenge accepted!

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

        You won! 😅, wanna race to Expert now?

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

          Yes Let's race to expert next!!!

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

As a tester,the problemset is dramatic.Hope you enjoy it :)

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

Yet another Serbian round?

orz

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

Hope I can reach the specialist again in this round.

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

THE BESTEST IN THE WORLD EVER 100% SERBIAN ROUND

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

Back to back div2s every day let's go

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

As a tester, the problems are exciting!

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

It is the first time for that guy to prepare a contest, I am a little worried ...

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

    You can talk when you become master.

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

      It is the first time for that guy to prepare a contest, I am a little worried ...

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

        It is the first time for that guy to prepare a contest, I am a little worried ...

        Jokes aside, yes, it is the first contest for both of us. We don't have much experience, so round will definitely have some flaws. But please provide us feedback after the contest so that we can improve in the future.

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

          My comment was directed towards TimDee, bullying someone based on rating.

          I hope everything goes well with the round. Don't worry about it.

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

            Yeah, I got that. The point of my comment was to say that even I am a bit nervous about the round, but yeah, hopefully everything will go good.

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

              haahah

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

              Your contest was awesome. Problem C was a great introduction for me (an absolute beginner) to DFS. I learned something new today. Your effort is greatly appreciated, thank you!

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

      Does being master guarantee being a good problem setter?

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

    When did Nemanja or I gain the reputation of being "that guy"?

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

Good luck for everyone! ;)

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

As a tester, NemanjaSo2005 Riblji_Keksic orz for preparing amazing problemset!

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

I love this contest marathon we've ended up having! ;)

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

as an arab, I cant wait for this round

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

I wish...this round became a better one (enjoyable) than previous all..!

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

3 rounds in 3 days wrooom!!!

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

    Contestants with aot profile pictures have +200% chance to have positive delta on the rounds I author.

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

Another serb round???

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

Good luck everyone ^_^

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

911 R.I.P

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

A 911 contest on 26/11 ? The numbers are too heavy to be considered a coincidence

»
11 months ago, # |
  Vote: I like it +7 Vote: I do not like it
Division 1 participants can participate :
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to reach pupil today

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

30000 score problem, nice!

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

    Yeah, it is actually NP hard, so if you solve it you prove P=NP.

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

am i seeing it correctly, or the score distribution for problem F really is 30,000(bang).

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

NemanjaSo2005 best problem setter!!

»
11 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Fun fact : $$$\text{E + F} > \text{A + B + C + D}$$$.

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

Can someone tell me whats the job of testers, if you need to correct the problem statement, text case explanation by a big margin in contest time? This is disgusting.

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

    We made just small changes to make problem more understandable. If you knew what problem A was originally you would understand what testers are for.

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

Keksic left on seen ......

Me: Us bro us

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

If I knew more algorithms/ theory about Number theory could have got D, the main idea is so obvious

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

    In which way exactly it is obvious for you if you do not know the theory? Can you please explain the "obvious main idea?"

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

      GCD convolution. A similar problem was asked a few time ago: https://codeforces.net/contest/1884/problem/D

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

        Sure, the trick involved is similar. Note that the problem (and solution) isn't similar, you can't call two problems using same trick or algorithm or data structure similar. (By the same logic, every binary search problem is simillr?) Also note that problem doesn't require you to brainlessly find number of pairs having GCD equal to i, also maybe look up the author solution and see that it's different as well (but yes, problem can be reduced to 1884D trick, that's how I solved it during testing, still that knowledge only helped me to know how to find number of pairs with fixed gcd, not to solve the problem.)

        In sfarsit, vreau sa spun ca Nila Ucsepop m-a dezamagit cu faptul ca nu a luat aur la Stelele Matematicii.

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

          Is there any specific name of this trick ? I want to learn , just curious.

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

            Not sure about exact name, but it's one of ways to do PIE here so read about it.

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

              Actually I found nothing on google about PIE.. Is there any full form of PIE.

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

                Inclusion-Exclusion Principle

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

queueueuueueueueueueforces

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

SpeedForces

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

QUEUE!!! ANY TIME EXTENDED?

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

I will keep trying to solve div2 problems :) I hope one day I will overcome the obstacles

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

Problem B is a nice application of the classical puzzle:

A shop sells 1 chocolate at $1. you can exchange 3 wrappers for 1 chocolate. if you have $15, how many chocolates can you get?

Problem C is a gentle introduction to Tree DP (although arguably you could remove the DP array and deal directly with DFS return value instead).

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

    How is b related to that puzzle?

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

      If you have $$$(x, \ y, \ target)$$$, assuming $$$x \leq y$$$, then you could first convert it to $$$(0, \ y - x, \ target + x)$$$. Then, for each $$$(y - x)/2$$$ chocolate of the middle kind, you utilize one chocolate from the end to convert it to $$$(1, \ y - x - 1, \ target + x - 1)$$$.

      Hence, we need at least $$$(y - x)/2$$$ chocolates of the third kind for this to be possible.

      The catch (in this problem, as well as in the puzzle) is that you don't have to directly check $$$(y - x)/2 > target + x$$$, since chocolates/wrappers are generated on the fly, so you could utilize the generated ones as well.

      Submission

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

        For this question it is always possible if the other 2 have the same parity. The logic for that is you can keep going back and forth until the other 2 are the same value.

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

D is too hard for me :(

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

This is almost the same as B

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

How to solve D?

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

Why my this solution for problem C is giving TLE — https://ideone.com/uV3iX5

can someone pls help

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

    Per-leaf approaches can die vs. trees shaped like long-handled brooms. Your early-out will only work if the earlier answers are better than the ones that come afterwards. Otherwise, it's possible to get stuck traversing the treetrunk/broomhandle repeatedly as you improve your overall answer for each leaf.

    To avoid this, you can use the return/post portion of a dfs, or you can do a full topological sort. Basically you want to avoid repeatedly processing vertices, but you also want to make sure a vertex is processed after all of its children.

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

      Thanks for your reply. Means the only approach that will work is dfs? Or in my approach can any optimisation be done to pass?

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

        I said 'can' not 'have to' -- but the options I listed fit the problem pretty well.

        If you really want to start with only the leaves, you'd still have to track whether or not all children have been processed yet, maybe punting a current node to the back of the queue if not... which leads to an opportunity for sadness: even if you shuffle the queue order, a tree shaped like a wide comb with short teeth will mean you're going to have a lot of vertices getting punted as they wait for the ones on the end to get processed...

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

How to solve D?

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

    How to optimise O(n^2) solution is the better question

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

      I also tried my luck with that O(n^2) solution even though I was sure it would get a TLE.

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

i liked problem C and was very satisfied by solving it.

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

How to solve B?

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

    i got stuck on this for a whole hour lol ;-;

    Bassically, first get the mod 2 of them, if they are all equal the answer is "1 1 1", else, the answer is the number with a different mod of the other two.

    sorry for bad english.

    why this works? i don't now, proved by AC

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

      Note that 1 1 2 -> 1 3 -> 2. So you can always decrease the number of 1/2/3s by two.

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

      If you can't prove this solution then what was your intuition behind it

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

        1 1 2 2 2 3 3 3 3 this 1 and three will cancel out each other which in turn will also increase count of two so now it will be
        2 2 2 2 2 3 3 if now i will cancel 2 and 3 then it will become 2 2 2 2 3 1 now cancel 3 and 1 2 is your answer

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

    Let the total sum of all 3 numbers be X. Now if we exclude 1st number i.e X-a1. if this number modulo 2 is 0, we can remove pairs i.e two numbers from the other 2 numbers and we can get all numbers with color a1. Similarly check for other 2 numbers

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

    B was kind of tricky for me at start but the approach that i come up with while giving contest was let a,b,c be the no.'s if any two of them have diff%2==0 then other one will be marked as 1 if all three are having even diff then all will be marked as 1

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

    i don't know if it an intended solution but u can solve it with dp: https://codeforces.net/contest/1900/submission/234459457

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

    I used a method using even/odd. I solved some test cases of my own and found out that when theres 2 evens the one that is odd is the only one that can be the result any way u solve. same if theres 2 odds. also found that it can never result in 2 of them being 1's.. and the last scenario that remains is that if all are even or odd. then its ( 1 , 1 , 1 )

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

    input -> a(1) b(2) c(3)

    //consider a

    if (abs(b-c)%2 == 0) print 1 else print 0

    //consider b

    if (abs(a-c)%2 == 0) print 1 else print 0

    //consider c

    if (abs(a-b)%2 == 0) print 1 else print 0

    because we can tranfrom all of other two numbers to the number we consider -example we consider A

    1.we operate B and C to A(tranfrom B,C to A) the remaining of this operate is abs(B-C)

    2.we operate a remaining with A and operate again with a remaining then we get A (this operation need two remainings and we can do this until we run out the remaining)

    3.so if the remaining of abs(B-C) is even,array will not have a remaining.

    sry for bad english

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

    BEST EXPLAINATION EVER :P

    Let's solve for digit $$$1$$$.

    If there is atleast one $$$2$$$ on the board, u can use that to delete one $$$3$$$ and add an extra $$$1$$$ on the board. Using this extra $$$1$$$ and one more $$$3$$$, we can create the lost $$$2$$$ back on the board.

    So, if u see the pattern, we can use one digit of some type (in this case digit $$$2$$$) to reduce the other type (in this case digit $$$3$$$) by $$$2$$$ in each step, so all it remains is the remainder with $$$2$$$ i.e., $$$c \% 2$$$

    Similarly if there is atleast one $$$3$$$ on the board, use it to reduce the $$$2$$$ to $$$b \% 2$$$.

    Now, that both have been reduced to their remainder with $$$2$$$, it is only possible to completely erase them if both are either $$$0$$$ or $$$1$$$ i.e., $$$b\%2==c\%2$$$.

    Similarly, you can do for digit $$$2$$$ and digit $$$3$$$ as well. Here is my code.

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

    no of 1 = a no of 2 = b no of 3 = c

    if you want to remove 2s and 3s completely you have to make b = c. This is only possible if |b-c| is even. Ex: let a = 25, b = 9, c= 19. Apply operation to 2s and 3s Five times. You would get a = 20, b = 14, c = 14. Apply operation on 2s and 3s 14 times and you will be left with only 1s. Check this with |a-c| and |a-b|.

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

Could someone please tell why I'm getting TLE? 234480936

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

    Isn't my solution at most works in O(2 * (10 ^ 7))? Shouldn't it fit in the time limit?

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

      Seems like the solution is OK, but implementation is brr...Maybe i am not correct, but "vector < vector <vector < int > > >b(100001);", " while (pow(j, 2) <= a[i])" can make your program slow.

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

        How can 3d vector and squaring slow the program? I mean like why?

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

          easily! I am pretty sure, that if you change pow to "while (i * i < j)" it become faster.

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

I wonder what is the solution for D... There are a couple of thoughts on factorization, but nothing seems to fit in time limits.

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

B > C ;)

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

not saying it was a bad contest at all, but problem D was very similar to problem 645F(https://codeforces.net/contest/645/problem/F) such that it was the case of k=2 for that problem.

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

    I just read it and it doesn't seem in any way similar, unless I don't know actual solution. However, i don't think that comparing the trick used in solution/solution itself is best way to describe similarity of two problems.

    Still, I may miss something, so could you please elaborate about what exactly they're similar in? =)

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

      say you have the solution of the problem for k=2.

      you can solve D like this:

      n=1 q=n-1, k=2 sort the array and give the elements of it in each query. the sum of all querys except the last one is the answer.

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

        Hm, right, it makes sense. Though i still don't agree that "solution to this problem can also solve this problem" makes those two similar (sometimes it can, but here it's not the case, since problems ask for different things (I mean, 645F should be heavily simplifies to arrive to today's D, like, limit K to 2, sort array, do queries adding sorted array elements ...))

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

          Anyway, thanks for your problemsetting I really enjoyed your contest.

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

            (I wasn't setter, I was tester, but still thanks for feedback :D) so I ping NemanjaSo2005 for good contest

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

Cool problems, Thanks!!

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

Is answer in D smaller than long long max?

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

    Yes, I think N choose 3 < long long max

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

    $$$\binom{80\,000}{3}\cdot100\,000\approx8.5\cdot10^{18}$$$

    $$$2^{63}-1\approx9.2\cdot10^{18}$$$

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

      Yeah, that makes sence, Thank you. I was too nervous during contest and didn't come up with this

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

Is $$$E$$$ following? Build condensation of graph (find strongly connected components and make them 1 vertice, the graph becomes acyclic). And then just dp on DAG to find path with greatest number of vertices (sum not the vertices in condensation, but for each vertice in condensation number of original vertices in it). (Why do we have to minimize some cost then? It doesn't change the problem)

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

    I thought of this too. There can be multiple longest paths in a DAG

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

    This method is correct, at least I have temporarily passed it

    1->2 1->3 2->4 3->4 There are two logest paths in a DAG 1->2->4 and 1->3->4

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

    The graph may not necessarily be connected, therefore there might be multiple paths with the same longest length but different weights.

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

    Yes. Then you can store dp as pair {length, sum} and update it as the statement requires it.

    Кстати, стоимость просят минимизировать т.к. у тебя может быть более одного множества вершин формирующих путь максимальной длины и соответственно на этом и строится задача, хотя ограничение довольно искусственное, но без него задача была бы слишком стандартной наверное)

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

      It is still very standard

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

        After you observe that you must condensate the graph, yes. It's not too trivial to arrive to that observation.

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

Any hints for F?

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

    i think its something along the lines of:

    • figuring out that at most O(logn) operations will be done on an array A
    • do the operations on the whole array and memorize the array after every query, lets call A_k array A after k operations
    • to solve queries [L,R], if you consider just the elements of A_1 in [L,R], lets call the array of those elements B, you can see at most 2 elements(one from the front and one from the back) should be added to B
    • then you can just simulate the queries(smartly) only looking at the left and right boundaries and maintaining the left and right boundary in A_k that corresponds to the array that is left after simulating k operations on the array in interval [L,R] in A

    UPD: you will also have to add O(logn) elements to the front and the back of the array that you are maintaining in the query while simulating the operations(because some elements from the begining and the end of your query interval could have been deleted by the rest of your array)

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

Is D mobius?

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

    I saw someone solve it with mobius, although i know nothing about it. Do I really need to know mobius to reach expert, I solved ABC in 19 minutes?

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

      Not really it's rare, i would recommend focusing on more common topics first

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

    I solved it without mobius (hopefully :)

    Hint: iterate over all possible GCDs

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

I'm willing to bet money that problem A was inspired by Minecraft.

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

Minecraft water logic in A, nice

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

I enjoyed thinking about problems ABCD,Thanks you for the contest. by the way any hints for optimizing (n ^ 2) solution of problem D

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

Please tell me what topics I need to solve problems like D and E (also to become expert: in general) thankyou so much :3

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

    problem D was a combination of number theory(gcd), combinatorics and inclusion-exclusion principle

    problem E was a combination of graph theory(for SCC compression) and simple DP on DAG(to calculate maximum length of a path and its smallest value)

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

Was too rusty on my Möbius reduction to solve D in time sadly :c. ABC were good, as well as E, which wasn't straight up untouchable while still proving hard!

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

    Did you end up solving it using mobius?

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

      what is mobius?

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

      In the end no, but it simplifies down to calculating this: (then subtract a thing, divide by 2 and multiply by $$$n$$$, more or less)

      $$$\Sigma^n_{i=1} \Sigma^n_{j=1} \gcd(a_i, a_j)$$$

      Which should be very similar to the last example in this blog post, but for gcd instead of lca. I couldn't wrap my head around those last transitions though.

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

        can you explain more please i did get to o(n ^ 2) solution but i can't understand how can i optimize it using mobius

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

          I doubt I can really explain it better than the blog post I linked. There is this function $$$\mu$$$ which is multiplicative and you can use the linear sieve to calculate its values quickly, and it has this interesting property which... yeah I'll just refer to the blog post.

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

        There is (n-j) term here i think for instead of multiplying by n

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

          The first thing is you sort the array in descending order. Then if I'm not mistaken: \begin{equation} \Sigma^n_{i=1} \Sigma^n_{j=i+1} \Sigma^n_{k=j+1} f(a_i,a_j,a_k) \end{equation} \begin{equation} = \Sigma^n_{i=1} \Sigma^n_{j=i+1} \Sigma^n_{k=j+1} \gcd(a_j,a_k) \end{equation} \begin{equation} = n \cdot \Sigma^n_{j=2} \Sigma^n_{k=j+1} \gcd(a_i, a_j) \end{equation} \begin{equation} = n \cdot \frac{\Sigma^n_{j=2} \Sigma^n_{k=2} \gcd(a_i, a_j) — \Sigma^n_{i=2} \gcd(a_i,a_i)}{2} \end{equation}

          Sike, I am mistaken. You are right, line two $$$\ne$$$ line three.

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

    Do you really need that for D?

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

      Judging by the comments here no, some people solved the problem without it

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

Problem A is basically minecraft infinite water source.

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

please quickly upload the editorial, so that I can understand problem D

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

    Calculating the sum of (gcd) of the two smallest numbers in all three-member subsets of a given set.

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

      thank you for the reply, but I meant that I want to understand the solution. My bad :(

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

D is very interestring problem... i like it

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

freaking hard D

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

    Problem D is pretty like to this 1884D - Counting Rhyme problem. There we should use a trick with inclusion-exclusion in dp for calculating all pairs of integers, that have fixed gcd. But these two problems are different from classical problem and we should modificate this dp.

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

      The inclusion-exclusion principle is relatively hard for D. It took me roughly an 1.5 hour to come up with it because I forgot this idea.

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

        Unluck :(

        I was stucked on problem B :)))))))

        May be you didn't solve too many problems with different tricks(I automatically recognized this trick when I have seen the problem)

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

    I am waiting for system testing to end so that I can try my D solution I solved it like 1 min after contest, and couldn't send it. :(

    And it gave me TLE

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

In problem C, why my code is TLE when I use dfs by recursion, and I AC when I use dfs by Stack ?

Code TLE: https://codeforces.net/contest/1900/submission/234465423

Code AC: https://codeforces.net/contest/1900/submission/234469294

Besides: My other Code use O(nlog(n)) but it's TLE : https://codeforces.net/contest/1900/submission/234458841

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

Feedback: In my opinion, B and C were a little too easy, and D was a little too hard. Maybe not, but the jump in difficulty from C to D was really huge for sure. Either: 1) make B,C harder or 2) make D easier (or a little bit of both). Other than that, that was a great contest, especially given that it's your guys' first time setting, good job!

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

Thanks for the authors for this round ! Here is my advice about the problems (uncorrelated to my performance)

A
B
C
D
E

Congratulation to the authors though, the problems were still of good quality and I appreciate the fact that AB were not left behind !!

Looking forward to another round of yours :))

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

    Can you please explain your solution to D or maybe add comments in your code?

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

    can you tell me why this solution won't work:

    https://codeforces.net/contest/1900/submission/234481346

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

    Expain your DP on D

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

      First I considered the easier problem of finding the sum of $$$gcd(a_i,a_j)$$$.

      Let $$$dp[d]$$$ be the number of pairs having their gcd equals to $$$d$$$. Once you know all rhe $$$dp[d]$$$, the answer is just $$$\displaystyle\sum_d dp[d] \cdot d$$$.

      Let $$$M$$$ be the maximal value of $$$a_i$$$ (here $$$M = 10^5$$$). Notice $$$dp[M]$$$ is the number of pairs of elements that are divisible by $$$M$$$.

      Let's compute $$$dp[d]$$$ Assume $$$dp[k]$$$ is known for all $$$k > d$$$. We know $$$dp[d]$$$ is at most the number of pairs of elements that are both divisible by $$$d$$$. However, among these pairs, we need to remove the ones whose gcd is not $$$d$$$. Such pairs will have gcd $$$2 \cdot d$$$ or $$$3 \cdot d$$$ etc.

      You can use the exact same approach to solve the problem (except you are counting triplets so you should sort the array first to know how many elements are larger)

      Code 234513315

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

        Thank you, I'll study this method.

        My solution during round was working with complexity $$$O(M \cdot uv)$$$ where $$$u$$$ is $$$M^{\frac{1}{3}}$$$ and $$$v$$$ unknown for me, but it gladly AC.

        Your solution is working $$$O(M \cdot M^{\frac{1}{3}})$$$ I guess.

»
11 months ago, # |
  Vote: I like it +7 Vote: I do not like it
»
11 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Thanks for the contest!

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

Solving Backwards D-C-B-A, hope I will reach CM one day, By the way very nice problem D, and glad that I solved it in the contest itself.

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

    Can you please explain your approach for Problem D?

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

      Sort the array,

      Now for every element ai push the index i in map of the factors of ai. After completing this step for all elements, for each key in map you will get the indexes where the elements present are divisible by this particular key.

      Now gcd will be some number inside our keys in map.

      Iterate from highest keys to lowest keys , as answer for any key will also depend upon the answer for multiples of that key.

      => Remember map[i][j] represents and index b/w 0-n , such that element at that index is divisible by i, formally a[map[i][j]]%i=0

      Particularly, dp[i] += i*j*(n-map[i][j]-1)

      (because for jth element in map[i], you can select any 1 element from 0 to j-1 , jth element and any 1 among n-1-map[i][j], as these 3 numbers will give you a valid tuples (ap1,ap2,ap3) whose gcd = gcd(ap1,ap2) = i.

      Also you have to subtract the contribution of multiples of i, as if i divides 2 numbers then it doesn't necessarily mean i will be the gcd of these 2 numbers.

      Hence, dp[i] -= dp[i*j]/j for all j

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

        This is fucking amazing. Thank you for this. Edit: I paraphrased above answer a bit with better formatting.

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

        Thanks a lot. Just one more thing: In the last line, "$$$dp(i) -= dp(i*j)/j$$$ for all j," j is in range 2 to $$$\frac{\text{highestKey}}{i}$$$, right?

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

          Yeah because after that , all the states will be zero.

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

          And actually for higher keys we will subtract for the factors of that higher key, and will add for them afterwardss when our loop will arrive eventually to them.

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

            Yeah. I felt that the problem was a bit difficult to be Div2D.

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

    Shouldn't have solved backwards, you're sacrificing a lot of free delta from A and B

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

      I know, but I want to get myself accustomed to solve D in live contest, as after solving A,B,C either there isn't much time left for me or my brain becomes fucked up to think for D calmly.

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

      damn bro, how are you improving so fast!! ;)

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

Can someone who was able to solve E can explain why this won't work for E, or report any points i missed:

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

    You need to consider strongly connected components. Currently you are running a dp on a graph that has cycles (well sometimes you can use dp even when you have cycles)...

    If you are still not convinced, try thinking about why you think your solution is correct

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

For problem D,any particular reason we are not required to output the answer mod some prime. In the current form, the maximal answer can $$$nC3*max(a[i])$$$ which if not calculated carefully (finding the ncr part and then multiplying) can overflow.

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

      I agree with that. However if we are not careful and in the worst case where n= $$$ 8* 10^4$$$ with all array values as $$$ 10^5 $$$, if we are not careful and write the code as

      ans=ans+(i*freq*(freq-1)*(freq-2))/6ll;
      ans=ans+i*(freq*(freq-1)*(freq-2))/6ll;

      It can overflow. I know this is mostly my fault but still I feel that mod would have been a better option here

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

    I got FST in the last test case due to this... Also, it would have been cool if these overflow test cases were included as pre-tests.

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

I feel like problems today were more educational than usually, you just should know the main approach for problems like these and then they're easy, otherwise really hard to come up with

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

Nice contest. Problems were well designed and fun to solve. Thanks for the round NemanjaSo2005 Riblji_Keksic and all testers.

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

Yo it was a great contest!

»
11 months ago, # |
  Vote: I like it -15 Vote: I do not like it

There was a long queue in last 10-15 minutes. Then still it's considered as rated round. Disappointed :(

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

    There is no queue lol

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

      I submitted my last solution 11 minutes earlier of the deadline but still didn't get verdicts till the end

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

good contest

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

This game was very interesting, but at the beginning I treated question B as question A, thinking that question B was question A, which caused me to be stuck for 30 minutes. I finally finished writing question C before thinking about question B, so I think The difficulty of the first three questions in this game is A<C<B.

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

Please tell me how you think about problem D and what is the breakthrough point?

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

    +1

    How to improve number theory with dp?

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

    I didn't know how to solve it with dp, but I passed it during contest.

    Idea is following:

    let $$$x$$$ be divisor of $$$a[i]$$$ ($$$a[i] \mod{x} = 0$$$). Let's $$$q[v]$$$ is the number of such $$$a[j] (j < i)$$$ that $$$v$$$ is divisor of $$$a[j]$$$. Let's iterate over all divisors $$$x$$$ of $$$a[i]$$$ and sum over $$$q[x]$$$ is the answer.

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

orz

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

Task B's statment was too unclear for me

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

How did people_plus_plus solve a problem in 1 second???

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

Can someone Please explain why I am getting a TLE in this solution for problem C 234510811

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

I got message from the system that my solution of C is same as other coder. my code: https://codeforces.net/contest/1900/submission/234467535 other's code: https://codeforces.net/contest/1900/submission/234459009

i didnt copied anyone's code, the solution is very straightforward. Easy codes can look similar. Please remove this penalty

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

I got a message from the system that my solution of C coincides with another code:

my solution: https://codeforces.net/contest/1900/submission/234456967

other code: https://codeforces.net/contest/1900/submission/234468345

Just see the difference between the coding style between those two codes.

I have no idea how did this happen. I wrote a very simple solution just using BFS. i think it is normal that easy codes look similar to each other.

Please reconsider this and remove my penalty.

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

Hey @MikeMirzayanov i have received this System mail yesterday

Attention! Your solution 234440272 for the problem 1900C significantly coincides with solutions KatsuKimechi/234437376, anikethend1234/234440272. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I know violation of rules of contest is not good. But i fact i have not done any kind of such thing.But yesterday i notice that the guy you talking about had used my CP template and code before this contest also. He used my CP template i the same contest also(you can check my previously solved solutions for reference).I think I have not done any kind of voilation of rules. Please check into the matter once.

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

Does anyone have any idea why this dfs fails pretest 6?

Please refer to the solve() function. https://codeforces.net/contest/1900/submission/238214972

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

    probably it overflows or something

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

For C what is worong ``` ll ans = 1e8, n;string s; ll l[maxn], r[maxn];

void dfs(ll v, ll op = 0){ if (l[v] == -1 && r[v] == -1) ans = min(ans, op); if (l[v] != -1) dfs(l[v], op + (s[v] != 'L')); if (r[v] != -1) dfs(r[v], op + (s[v] != 'R')); }

void run(){ cin >> n >> s; for (int i = 0 ; i < n ; i ++){ cin >> l[i] >> r[i]; l[i]--;r[i]--; } dfs(0); cout << ans << nl; }

```