FairyWinx's blog

By FairyWinx, history, 5 weeks ago, translation, In English

Приветствую, Кодефорсес ✿*∗˵╰༼✪ᗜ✪༽╯˵∗*✿

(Welcome, Codeforces on Russian)

TeaTime and I are happy to invite you to participate in Codeforces Round #818 (Div. 2). It will take place on Sep/02/2022 17:35 (Moscow time). The round will be rated for all participants with rating strictly lower than 2100. You will have 2 hours to solve 6 problems.

The standard place for thanks:

See you at the round🥰

Scoring distribution: 500 — 1000 — 1500 — 2000 — 2000 — 3000

UPD: Editorial!!! (Thanks to imachug for English translation)

UPD: Winners!

Div 2:

Div 1:

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

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

hope tasks would be fine!

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

The author of the round FairyWinx is the best anime girl!

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

Looking forward to participating this contest! (also great effort on the image not gonna lie)

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

How to calculate Rating change?

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

Scoring distribution is scary

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

I sus that the problem statements have been altered by impostors.... Good luck to all Excited to participate

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

TeaTime ORZ

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

Among us is the best game!!!

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

Nobody: Literally Nobody:

Me: Yes, it's TeaTime round (❁´◡`❁)

»
5 weeks ago, # |
Rev. 5   Vote: I like it -9 Vote: I do not like it

Can somebody please suggest how to make strong strong grip on mathmatics Problem ,I get stuck on easy mathmatics problems?

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

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣶⣿⣿⣷⣶⣄⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣾⣿⣿⡿⢿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⡟⠁⣰⣿⣿⣿⡿⠿⠻⠿⣿⣿⣿⣿⣧⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⠏⠀⣴⣿⣿⣿⠉⠀⠀⠀⠀⠀⠈⢻⣿⣿⣇⠀⠀⠀ ⠀⠀⠀⠀⢀⣠⣼⣿⣿⡏⠀⢠⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⡀⠀⠀ ⠀⠀⠀⣰⣿⣿⣿⣿⣿⡇⠀⢸⣿⣿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⡇⠀⠀ ⠀⠀⢰⣿⣿⡿⣿⣿⣿⡇⠀⠘⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⢀⣸⣿⣿⣿⠁⠀⠀ ⠀⠀⣿⣿⣿⠁⣿⣿⣿⡇⠀⠀⠻⣿⣿⣿⣷⣶⣶⣶⣶⣶⣿⣿⣿⣿⠃⠀⠀⠀ ⠀⢰⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀ ⠀⢸⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠉⠛⠛⠛⠉⢉⣿⣿⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣇⠀⣿⣿⣿⠀⠀⠀⠀⠀⢀⣤⣤⣤⡀⠀⠀⢸⣿⣿⣿⣷⣦⠀⠀⠀ ⠀⠀⢻⣿⣿⣶⣿⣿⣿⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣦⡀⠀⠉⠉⠻⣿⣿⡇⠀⠀ ⠀⠀⠀⠛⠿⣿⣿⣿⣿⣷⣤⡀⠀⠀⠀⠀⠈⠹⣿⣿⣇⣀⠀⣠⣾⣿⣿⡇⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣦⣤⣤⣤⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠻⢿⣿⣿⣿⣿⣿⣿⠿⠋⠉⠛⠋⠉⠉⠁⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⠁⠀⠀⠀⠀⠀⠀

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

Why this blog is so sweet ^-^

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

I like it :)

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

i am new to codeforces can i attempt division 2 or not i know c++ and little bit dsa

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

    You don't really even need dsa for most div2 problems. The first 3 problems usually just end up being something greedy. Best of luck.

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

      first 3 problem is easy or hard bro ?

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

        Not easy, more like just usually don't require much prerequisite knowledge. If you are new to competitive programming, it'll take some practice before the first 3 start being easy.

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

          still waiting for the day div. 2c will be easy and i regularly solve div.2ABC

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

        hard

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

    imo yes, even a complete beginner should still attempt Division 2 contests. It's a good experience in the contest environment, and it's still notable to be able to solve even just one problem. Just don't go in with high expectations for how many problems you solve; focus more on your practice and growth and not on how high (or low) you are in the standings. It's primarily through consistent practice that you improve, so I highly recommend participating in ALL contests! Even upsolving D1A after reading the editorial after thinking about it for 2 hours should be good.

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

GREAT!

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

the crewmates are bumping onto each other like how my submission does when they encounter special test cases.

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

Amogus themed Round! Will use the Amogus Trick to AK the round

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

Hope to perform best in this contest

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

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

    2022 — memes on memes :)

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

    2020 good times I created that era (my previous username was SupaHotFire)

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

amogugus

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

happy birthday power-star Pawan Kalyan

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

Hope that this one wouldn't be too hard...

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

Hey I'm new and I use java. Is their a problem because of the higher runtime?

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

    Not an issue bro, though it is a little slower than CPP, but still you can solve all the questions in java if you caught up the problems. You can check submissions, there are thousands of java users like you and at a good ranking. Best of luck.

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

Hope Task would be Fine !!

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

Hi, I am new to Codeforces. I've participated in 6 rounds so far. The last round I participated in was Codeforces Round #817 (Div. 4). There was a small rating change. I want to know on what basis the ratings are updated after the contest. I also came across hacking where participants can see others' submissions and provide test cases where their code fails (if any). For Codeforces Round #817, it was mentioned that the hacking phase lasts for 12 hours. Post contest, this is usually the time I sleep. I wanted to know if there's any specific reason for exactly 12 hours provided for hacking. I am new to Codeforces blog too, so apologies if this information is already available anywhere else.

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

    Hacking phase only exists in educational, div3 and div4 rounds. I don't know if there is any reason for hacking being 12 hours, but I suggest you focus on solving the problems, which is the most important part, so don't feel bad for not being in hacking phase. Personally I've never cared about it. I think you can't even get points yourself, you can only make others lose their ranks.

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

      Hi, thanks a lot for explaining. So, there's no hacking phase for this round, right?

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

        Yes, that's right, speaking about proper hacking phase after the round. You can still hack during any round after locking the problem.

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

    Your ratings are updated based on the problems you solve in the contest and the average rating of others who could solve those problems. (Use CF-Predictor to get expected updated ratings before they are finally updated on codeforces).

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

      Okay. How about Div 2 and Div 1 contests? Div 1 Contests are rated for everyone, right? Why is only one leaderboard used then?

      Like, in CodeChef, each division has its own leaderboard. It allows comparing our performance with that of participants belonging to the same division.

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

    Thx bro for the story

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

Good luck

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

Hope to become an Expert :')

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

Hoping to reach specialist.

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

I just wrote this to make numbers of comments 69 :)

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

hello everyone best of luck

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

By far the worst contest I've ever attended.

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

This was the bad contest that I have ever attended!. I hope this contest should be hosted for only Div.1 users.

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

Very hard problems for div.2?◑﹏◐

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

Div 1.5 :'(

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

i mean why someone would do that in problem b thats pure evil

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

    IMHO B was easier than A

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

      not really even after i got an idea i stucked in implementing it then it got rte we can discuss further after the contest end if u want but i see its harder than a im sure

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

        well, almost everytime, B is easier than it looks.

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

          maybe you are right

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

            I was about to check the B but I was stuck with A in my head, I said I'll keep trying to solve A but nah... That input is literally evil for real.

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

              for me A was a little easy maybe because i solved alot of stuff like this ( not in this account for sure) and i got the idea with trying small samples and reasoning the thing is b was a hell for me i tried in it many random ideas and never worked even i got an idea that i thought it supposed to work and after alot of time trying implementing it volia rte then wa 2 i don't say the problem is hard/bad if i didn't solve it but really this is one of the hardest b problems i encountered ( maybe im totaly wrong but that is my opinion)

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

I Hate U Madoka ._.

»
5 weeks ago, # |
Rev. 4   Vote: I like it -9 Vote: I do not like it

Приветствую, Кодефорсес ✿*∗˵╰༼✪ᗜ✪༽╯˵∗*✿

after i have saw this i knew that the contest will be hard :( Edit : I love the Math :)

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

Thanks for the good contest, tasks are really interesting. But can you answer one question, please? Why tasks A B and D are pure maths without any competitive programming at all? I like ad-hocs, but this is too much.

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

    Because they are beautiful in my opinion)

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

      I agree, they are beautiful, liked them (only B is very well-known) :)

      A and B is normal thing to have pure maths, but not D, especially with such A and B.

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

        I can see why A and E could be considered pure math, D has some math component but is not just math. But what is math about problem B? It's just about rotating diagonals.

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

          I was solving such a problem during the math contest in 5th school grade.

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

            Well sure, but it still doesn't make the problem a math problem, unless there's some math concept involved in it.

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

      you should probably think more about ppl who have more ability in CP than maths

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

    Are you giving the contest from your alt account ?? Wind_Eagle

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

Problem A and B, Pure evil :(

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

Mathforces !

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

Feel REALLY grateful to the authors as I got AK for the first time.

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

This was my first contest. Problems were too difficult for me

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

    Usually, problems are way more easy in Div 2. It's just bad timing for you. Keep practicing, you will rock soon ;)

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

F is very classical, I don't like it :(

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

D is a good problem (In fact I don't think it is a pure Maths problem,you can realize the answer easily if you think about the problem in another way).

And I think E is much easier than D...(Just my opinion)

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

How to solve D?

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

    Let's construct a full-binary tree, some edges will have a weigth of 1, the others will have 0, depending on whether the player wins or not. Then we'll notice that if we sum up all the weights on the way to the root, the player can possibly win the tournament only and if only it is at least n — k. Then we can code every path in a row of n 0s and 1s, where 0 means going to left node and 1 means going to right node (it doesn't matter if we say that every left edge is losing and every right is winning). So we need to have at least n — k ones. That means we can calculate the answer as the sum of C(n, i), where i is in the range [n — k, n]

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

I was first surprised by the appearing of 'Madoka' in the titles, thinking 'some interesting background stories are gonna show up'. But now I'm a bit disappointed, as none of the statements have strong connections between the character or the anime itself, and the only common point is the name 'Madoka'...

But anyway, in spite of that, I would like to appreciate how clear and short the statements are.

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

    Hi, could you please explain, how you thought about problem C. I mean i've seen some solutions now, and see that its based on the final array B, and wheather it can be reached. But how did you prove that?

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

      Here's how I thought about it:

      If $$$a_i > b_i$$$, this is obviously impossible to achieve.

      If $$$a_i == b_i$$$, this index is fine, no changes needed.

      If $$$a_i < b_i$$$, then $$$a_i$$$ needs to increase (to $$$b_i$$$). This can only be achieved if $$$a_{i + 1}$$$ eventually becomes $$$b_i - 1$$$ at some point. This requires $$$b_{i + 1} \geq b_i - 1$$$ (otherwise you wouldn't want to increase $$$a_{i + 1}$$$ to $$$b_i - 1$$$).

      This gives us two necessary conditions:

      1. $$$a_i \leq b_i$$$ for all $$$i$$$
      2. for each $$$i$$$ such that $$$a_i < b_i$$$, we must have $$$b_i \leq b_{i + 1} + 1$$$

      As for why they're sufficient, this isn't a formal proof, but here's my intuition. The smallest element in $$$a$$$ is always eligible for an increase. If this element is already at its target value, then the element before it is either at its target value or it is below its target value and also eligible for an increase (condition #2). If it's at its target value, we can check the element before it and so on. This backwards scan guarantees that, if the two necessary conditions are fulfilled, then either all elements are at the target, or there will exist some element that is able to increase and is below its target value. This property is preserved after incrementing this element, so as slow as this process may be, eventually every element will reach its target, allowing us to efficiently answer YES without having to actually perform these operations.

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

    2nd Div 2 winner: Akemi-Homura

    I can see why...

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

So how exactly are we supposed to compute $$$\sum_{i = 0}^k {n \choose i}$$$ in modulo $$$10^9 + 7$$$? I get that we can reduce the problem to have $$$k$$$ below half of $$$n$$$, but the division by $$$k!$$$ under a modulo operation blocked me from completing D...

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

    There is a way to make division into multiplication under modulo called seeking invers.

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

    You can observe that when k > n, the answer is just 2^n. Thus, k is bounded above by 10^5. Now you can just compute each term in constant time (compute each n choose i from n choose i — 1)

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

      Yeah, I realized the $$$2^n$$$, but I still don't see how we can compute $$$n \choose i$$$ from $$$n \choose i - 1$$$ when there is a modulo operator involved, since the computation of $$$n \choose i - 1$$$ involves a division with $$$i - 1$$$

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

        $$${ n \choose m } = \frac{n!}{m! \times (n-m)!}$$$

        And $$$\frac{x}{y} \bmod p$$$ equals to $$$x \times y^{p-2} \bmod p$$$

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

          Thank you so much! I looked it up and learned about Fermat's Little Theorem, which finally allowed me to get an Accepted submission. Although, I couldn't solve this problem during the contest, I think I learned more from this experience than any of the other contests I did in the last few months. I used to feel like the modulo answers blocked division, but now I learned how wrong I was. Thank you!

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

    Can someone explain problem D?

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

      The minimum winner that Madoka can guarantee is equal to the number of possible winners if the sponsors are allowed to make $$$k$$$ changes. If there are $$$r$$$ possible winners, then Madoka would rearrange them to be labeled $$$1$$$ to $$$r$$$, so that regardless of how the sponsors make their changes, the winner will be at most $$$r$$$.

      Consider the path of the winner from the root to the bottom level as a binary sequence of left and right turns. There are $$$n$$$ edges in total, so the binary sequence has length $$$n$$$. The sponsors can change up to $$$k$$$ of the elements. Each distinct sequence leads to a unique participant. Therefore, the number of possible winners is $$$\sum_{i = 0}^{\min(n, k)} {n \choose i}$$$. Calculating this modulo $$$10^9 + 7$$$ is where I got stuck...

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

        Why $$$min(n,k)$$$ and why $$${n \choose i}$$$ ?

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

          Here's an example: suppose $$$n = 5$$$, and Madoka decided that it will always be the left contestant that wins. Then we can describe the path from the root (champion) to the leaf (bottom level) as LLLLL. This leads to one possible victor. Treat the order of the participants at the bottom as fixed (Madoka can optimize the initial setup, but it doesn't change once she makes her decision).

          The sponsors can make up to $$$k$$$ changes. If they change the outcome of the final match only, then the path becomes RLLLL (you can also think of it as LLLLR, but it doesn't affect the conclusion). Or maybe they leave the final match as L and change the semi-finals to R, so the path becomes LRLLL. Or maybe they make the would-be champion lose on their first round, so the sequence is LLLLR. Every distinct sequence leads to a different leaf at the bottom, i.e., a different champion.

          So now the question is, if you can flip at most $$$k$$$ elements of this sequence, how many possible distinct strings can you produce? If you flip exactly $$$i$$$ elements, for $$$i \leq n$$$, then you need to choose which $$$i$$$ elements out of $$$n$$$ they will flip, of which there are $$$n \choose i$$$ possibilities. Even if $$$k > n$$$, the sequence has length $$$n$$$, so it doesn't matter if you can make more than $$$n$$$ changes (the champion victory path only relies on the outcome of $$$n$$$ matches). In fact, $$$k \geq n$$$ results in an answer of $$$2^n$$$ since every possible sequence of length $$$n$$$ can be achieved (allowing every contestant to have the possibility of being the champion).

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

I think E is a bit standard?

D is cool though :)

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

    Can you give me a hint for E?

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

I solved $$$B$$$ and $$$C$$$ and still can't figure out A !

I found a solution but it got MLE, any hints?

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

    think about number which can make pair with number x(only 2 * x and 3 * x are suitable)

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

    The eqn can be written as (a*b)/(gcd(a,b))^2 <=3

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

      how do you solve this then?

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

        after this, it is clear that gcd(a,b) has to be as big as possible and it can at max min(a,b)

        So. we have to maximize gcd which means a,b should not be coprime hence should me multiples

        after that, I observed that for any a and 2*a the equation yields 2 and for any a and 3*a, it yields 3

        so we have to consider a,a*2 and a*3.

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

      please explain how u approach after getting this inequality

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

    Okay

    let's gcd of a and b equal D

    Then a=D*X and b=D*Y where gcd of X and Y equal 1.

    a*b/gcd(a,b)=lcm(a,b)

    XYD=lcm(a,b) XYD/D=XY

    SO you need to find pairs of numbers like x,x/3

    x/3,x

    x/2,x

    x,x/2

    x,x

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

Solved E in 15 mins, couldn't solve D((

And again i have 1-4 points left to become CM (4th time already)

Life is sad

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

    Knew how to solve D as soon as I started drawing out examples. Spent the last 1 hour on E and still couldn't do it...

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

    I can't get it, for me D was much easier than E, as for me E seems almost impossible, while D is acceptable. Any hints for E maybe?

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

      I kept thinking there must be a way to iterate to get $$$O(n \sqrt{n})$$$. Try to do some manipulations on the formula in order to be able to iterate over $$$c$$$ and over the value of some gcd expression, such that the value of this gcd expression is the same for some tuples, and you should count them and just multiply. That was my reasoning, I hope it gives you an idea.

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

      Hint 1

      Hint 2

      Hint 3

      Hint 4

      hope this helps))

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

Well, that's like mathforces :(

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

I think A is so hard for D2A, was there easier solution?

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

    n + 2*(n/2 + n/3)

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

    n + (n // 2) * 2 + (n // 3) * 2

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it
    int n;
    cin>>n;
    int x=n/3;
    int y=n/2;
    int z=n/1;
    int f1=x;
    int f2=y-x;
    int f3=z-y;
    cout<<(f1*5 + f2 * 3 + f3)<<endl;
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the prime decomposition of $$$A$$$ and $$$B$$$ there shouldn't be any different power of primes $$$> 3$$$. Also there can either be one more 2 OR one more 3 but not both. Hence either same number $$$(N)$$$ or pair $$$(x, 2x)$$$ $$$(2(N/2))$$$ or pair $$$(x, 3x)$$$ $$$(2(N/3))$$$ and we multiply by 2 to account for ordered pairs

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

    Yes, you may have pairs as follows:-

    • $$${(x, x), x \le n}$$$
    • $$${(x, 2 * x), x \le n /2}$$$
    • $$${(2 * x, x), x \le n / 2}$$$
    • $$${(x, 3 * x), x \le n / 3}$$$
    • $$${(3 * x, x), x \le n / 3}$$$

    So no of pairs = no of pairs of each above types = n + n / 2 + n / 2 + n / 3 + n / 3.

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

Can Problem E be solved in $$$O(n \log n)$$$?

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

    you could probably do it using sieveing the phi function, but $$$O(n\ln n\sqrt n)$$$ is easier to implement.

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

    How did you solve it?

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

    Yep)

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

    Mangooste solve in testing in $$$O(nlog)$$$

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

    jianlgy's solution is $$$O(n \log n)$$$

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

      Okay, I'm sorry, it's not completely $$$O(n \log n)$$$ because of std::lcm, but you can precompute them (there are only n pairs he needs)

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

Some contests (like this one!!), just ends up giving u loads of depression and self-doubt !! wasn't even able to solve A !!! feels like sh*t !!

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

    Yeah we've all been there, but try to rationalise — it's one problem. It was tough for Div 2A. It doesn't undo all the problems you can solve and have solved.

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

For C firstly I make all elements of array a which are smaller than smallest element of array b equal to smallest element of b now i got one element where a[i]=b[i] now i just traversed backward and check for for all other a[i]'s

isnt my approach for C correct ??

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

question about problem C: how did this massive lump of spaghetti pass the systests? I can't prove my solution. 170616890

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

    Your solution fails for a few cases, one of which includes this:

    1
    5
    1 2 3 4 5
    15 15 15 15 15
    

    It should output "YES", whereas your solution is returning "NO".

    "YES" because:

    1 2 3 4 5 changes to 5 5 5 5 5,

    and then to 6 6 6 6 6,

    and so on until 15 15 15 15 15.

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

      oh so it actually was a massive lump of spaghetti which doesn't even work properly. damn.

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

This A is way too hard and math-heavy for a decent Div2A and it can be seen as "guess from the samples" (especially considering the answer for $$$1\,000\,000\,000$$$ being provided).

Please don't do such Div2As, because you are scaring newcomers and biasing the rating changes for greens and grays (i. e. lots of contestants don't submit anything if Div2A is too hard, so they are skewing ratings).

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

    agree

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

    Kinda right, but in actuality it turned out to be relatively easy to solve.

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

    sampleforces

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

    Maybe, CF should adopt Atcoder style registration: Rating will drop even if you don't submit anything.

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

I submitted B twice which are almost similar beacuse of my second my first submission is skipped.

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

Damm Questions were quite tough!

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

It's the fastest system test of div.2 as far as I know.It just took about 15min .

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

Am I not mistaken? The system testing was fast as fuck, wasn't it?

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

    But system tests of contests I've taken usually took me about 1 hour , so I feel that's so fast today.

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

I got suck in problem A for twenty minutes. The hardest D2A I've ever met!

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

    Me too :'(

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

    for 1 hour.then i picked up pen and paper and did it.

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

    I think so , this problem A isn't as easy as before .

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

    Yeah that surprised me a little bit. Managed to figure it out by realizing it was equivalent to a/gcd * b/gcd <= 3 and then I did some casework.

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

      To add values to the answer is cyclic, I noticed this with bruteforce than it was cake

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

    Yeah it's hard to find the solution and i used 40 minutes to solve it:(

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

This prolly was the fastest system testing I have ever seen, wow

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

My solution should not pass But It is passing . Weak Tests I must say 170648782 1 4 1 1 1 1 40000000 40000000 40000000 40000000

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

How to understand D's statement?

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

For problem B for 1st testcase why is this answer wrong ?

X..
X..
.X.
XX
XX
.X..X.
X..X..
X..X..
.X..X.
X..X..
X..X..
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    3rd column in 3rd case is completely empty, I can pick 1*k vertical segment without X in it.

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

    'cause you got

    X..
    X..
    .X.
    

    Which leaves the rightmost column empty so it doesn't satisfy the requirement.

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

honestly, D statement is a bit hard to read and understand

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

    Yep. But it's fun to solve. The most elegant task out of A-D in my opinion.

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

    It's not just hard to read, it's awful and ambiguous. You have to guess things which is not clearly stated in the statements. It's not stated that after sponsor changed outcome for other matches left still win if left was winning before. Also,

    Print the minimum possible number of the winner in the tournament, which Madoka can get regardless of changes in sponsors.

    In example if sponsor changes outcome of finals, Madoka would get number 2, which is obviously less than 3, and isn't it smaller? If sponsor decide to always do this for this tournament, Madoka can't get 3 regardless, because winner is 2.

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

      regardless means that we need to minimise the maximum of all possible outcomes

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

Good to see some coding questions in a maths contest!

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

The system test is so fast.Good job!

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

Why task C solved in O(n) on pypy3 has TL? https://codeforces.com/contest/1717/submission/170628126

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

During the contest I used pypy3 in problem C, and got TLE in the system test. (And I tried to resubmit, this time it got AC within 997ms.)

However the same code got AC using python3 within less than 600ms. This makes me really troubled.

Here are the url of the two submissions. The first one is pypy3, and the second is python3.

https://codeforces.com/contest/1717/submission/170648846

https://codeforces.com/contest/1717/submission/170648671

This is a profound lesson, which tells me that the I/O function of pypy3 is slower than python3.

Besides, I think the tip of "Almost always, if you send a solution on PyPy, it works much faster" when submitting python3 should be updated. At least it should be modified to "most time" instead of "almost always".

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

Maths-forces

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

Can someone tell me what's wrong with my submission? (for B) https://codeforces.com/contest/1717/submission/170645855

My logic:

Spoiler

Would be really grateful if you could post a counter test case, thanks!

EDIT: Figured it out, ty

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

    Your code fails at multitest test cases. Try

    2 10 10 1 1 8 2 1 1

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

      I figured out what's wrong I think it had something to do with the construction implementation of the matrix. I changed the approach and got AC.

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

Can someone please explain to me, how they thought about problem C and how you arrived at the observations?

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

    Let me try:

    Let prev be the previous element and cur be the current element. Since we can only increment the previous element under the given conditions, it means that the prev-1<=cur OR a[i-1]==b[i-1] where i is index of current element and i-1 = prev. Also, elements can't be decreased, so all b[i]>=a[i] for all i. This gives a conclusion that if (b[i-1]-1>b[i] OR b[i]<a[i]) AND a[i]!=b[i], b can't be obtained from a.

    I hope this makes sense.

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

    Try solve an easier version of C: Print a configuration with minimum X that satisfies that there's at least one X for every subarray of size (1,k). The obvious answer is that there will be exactly n/k evenly spaced Xs on each row.

    Now try solving the whole problem: There should be at least one X for every subarray of size (1,k) and (k,1). Again, notice there's exactly n/k evenly spaced X on each column, then the idea becomes obvious that you need to shift the X position of some rows until it satisfies both condition.

    This is how I found the solution during the contest.

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

Any hint for D?

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

    Think about Pascal's triangle

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

can someone tell me the idea of b?

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

      i see that its distributed on diagonals the number of Xs in every diagonal start increasing then it reaches a point where the diagonal contains the point r, c then it decrease is that what u meant? i tried to implement this idea but got wa2 don't know if this what do you mean

      https://codeforces.com/contest/1717/submission/170632638

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Hint 2
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    Hint 4
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only one who solved C but couldn't solve B?

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

Make A easy please, people will give up the contest quickly if they can't solve A..

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

    Agreed, often I see A is tougher than usual.

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

The problems were somehow interesting but most of them were math (very close to pure math).... It makes this round less than a good round

Did the testers give their opinion about this? I blame them too if they did not

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

Any idea why A solution is (n + n / 2 * 2 + n / 3 * 2 ) ?

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

    Without loss of generality we can assume for all pairs (a,b) that a <= b.

    if b is divisible by a, then gcd(a,b) == a ,lcm(a,b) == b (and vice versa). In this case, It's obvious that the only correct pairs are (b/3,b) (b/2,b) (b,b). The number of pairs are n/3, n/2 and n respectively. To count the pairs with a > b, just swap (b/3,b) and (b/2,b) to (b,b/3) and (b,b/2)

    Now let's try to prove that there's no pair in which a and b aren't divisible by each other. if b is not divisible by a, then gcd(a,b) <= a/2, lcm(a,b) >= b*2. We know this because a/2 is the largest possible divisor of a that isn't equal to a and b*2 is the smallest possible multiple of b that isn't equal to b. Obviously lcm(a,b) / gcd(a,b) >= (b*2) / (a/2) >= 4 because a <= b.

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

    Try to write the TLE solution with nested loop and then observe the equation.
    Really, It is a pure math problem!◑﹏◐

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

    Let me try:

    There are n (a,b) pairs where a=b. Their gcd of (a, a)=a and lcm of (a, a)=a. a/a=1<=3; So there are at least n pairs under the given conditions.

    Let a<b(a=b case already covered above). LCM of (a, b) will not be less than b, while GCD of (a, b) won't be more than a. It means that for any number x where x>3*a, LCM/GCD>3. The same goes for 2.

    so for every a, there exists b=2a and b=3a which are valid pairs(b=a already covered above). To make sure b=2a doesn't overflow(b can't be more than n), we take floor of n/2 and multiply it by 2. Multiplication by 2 is caused by the fact that pairs can be inversed. AKA pair (a, b) is different from pair (b, a). The same logic goes for pairs where b=3a.

    I hope this makes sense and helps you some.

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

D was a great one. Too bad, I was late for a minute

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

When will our ratings get updated?

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

A is too complex for Div2 i think too much math

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

feels so lucky when ur solution passes system testing so close to TL.

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

big fan of this round :)

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

Should have added this test case for problem C:

1
2
1 1
1000000000 1000000000

Because this test case is not there some TLE solution will get accepted like this one: https://codeforces.com/contest/1717/submission/170655104

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

Damn it, I was too slow to AC A-E and upsolved F 30min after contest without help... Great contest, A and E were cool number theory equation-shuffling (although this A might be a bit hard for A?), F was a standard flow problem with a classic trick, it was really interesting to boil problem D down to its core, and it practically solves itself when you get to the core. B/C I can’t really give feedback because I kind of just guessed them without any proof or intuition but they were interesting enough to keep me thinking for a solid bit. Banger contest overall.

(I’m totally not biased because this was my first div2 contest that I could AC all problems by myself, what are you talking about)

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

Problem D's harder than E.

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

    Same for me, I don't understand how 1000+ people solved D.

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

      Well, it's most likely because people always attempt D before E, and if they can't solve D they usually won't attempt E.

      Another reason I can think of is that D and E are fundamentally different and require very different skill and experience.

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

        Yes, you are right.

        I think if I didn't know that this is Div.2 D and that 1000+ people solved it, I would think that this is 2400 problem. But solution is so beautiful!

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

    Problem E is harder than D.

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

      For me D is harder because of my logic :v. In problem E it's like: iterate over c and gcd(a, b) = gcd(a, a + b) & the number of divisors of n consecutive number is not that big so use some trick with euler totient function. In problem D, it's more of a adhoc problem (the number of leaves that has k black edge on the path to the root is the same for every binary tree with the same size) and for me it's kind of hard to guess it out.

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

      Okay, okay, guess what, both of you could be correct. Yall should refer to the scoring, and you will see that both have a score of $$$2000$$$.

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

Due to some difficulty of the problem A, I explain the solution which do not require brains at all.

The problem A can be solved without any thinking. All you need to do is use Wolfram Mathematica:

GetPairs[n_] := Module[{ans = 0, i, j},
   For[i = 1, i <= n, i++,
    For[j = 1, j <= n, j++,
      If[LCM[i, j]/GCD[i, j] <= 3, ans += 1]
      ];
    ];
   Return[ans];
   ];

Map[GetPairs, Range[1, 100]];
FindSequenceFunction[%, n];
FullSimplify[%, Assumptions -> And[n \[Element] Integers]]

In fact, we are looking for an answer in the form of a function that depends on $$$n$$$.

And the Wolfram Mathematica gives the answer:

$$$ n \mapsto \frac{1}{18} \left(48 n+9 (-1)^n+2 \sqrt{3} \sin \left(\frac{2 \pi n}{3}\right)-2 \sqrt{3} \sin \left(\frac{4 \pi n}{3}\right)+6 \cos \left(\frac{2 \pi n}{3}\right)+6 \cos \left(\frac{4 \pi n}{3}\right)-21\right). $$$

We can simply code it and get AC: 170655872.

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

    Amazing!

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

    Amazing

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

    The problem with this approach is that it takes more than 2 minutes.

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

    Amazing!

    Did you try it on problem E?

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

    Given the delay with the editorial I am sure this will help the newbies. Thank you!

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

    This is nice. If you observe a bit of basic math, you can simplify it further for integer n.

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

    Hereby I suggest another solution which also do not require brains.

    The solution is to use the Berlekamp-Massey algorithm, which is an algorithm that predicts the recurrence relation of an integer sequence with a linear recurrence, given its first few values. It requires a certain modulo, but considering that the answer is below $$$10^9 + 7$$$ for the biggest input possible, that would suffice. Now all that is left, is faith. Faith that it would have a good linear recurrence relation.

    Here(170662330)'s the submission that passed the tests with this method, and here is the Berlekamp-Massey template I used. Huge thanks to ko_osaga for the template.

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

      I worked out the relation during contest:

              ll rem = (n-1)%6;
              ll mul = (n-1)/6;
              switch (rem) {
                  case 0: x = 1; break;
                  case 1: x = 4; break;
                  case 2: x = 7; break;
                  case 3: x = 10; break;
                  case 4: x = 11; break;
                  case 5: x = 16; break;
              }
              ans = 16 * mul + x;
      

      170601961

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

    You're too good. orz

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

    wtf

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

    a new OEIS lol

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

everyone are doing it cout << (n) + (2 * (n / 2)) + (2 * (n / 3)) << endl;

i mean how they make this equation? where i am lackings? i cant even think with this way. i was supposed to make a series for few numbers and tried to construct a series which will satisfied all cases.

can anyone tell me how can i develop my mathematics skill, i cant imagine to construct something like this. feeling despondent!

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

    Let d = gcd(a,b), then a = dp, b = dq (p & q co-prime). Then lcm(a,b)=dpq, therefore lcm(a,b)/gcd(a,b)=pq. Only possible pairs are (1,1),(1,2),(2,1),(1,3),(3,1). For satisfying dp,dq<=n, the number of possible values of d are n,n/2,n/2,n/3,n/3 — hence the answer.

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

      brother i was unable to think in this way after seeing the solution it as always seem easy. but will you recommend me how should i practice or which mathematical stuff should i master on. currently im solving 1000-1400 rating problems ascending then i will decesending too. and doing same strategy after tagging number theory in cf. thanks a lot for ur time. regards

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

        Any number theory book would be enough. I can say always try to simplify things, the upper bound in LCM/GCD term gives the intuition of less types of pairs. Then you can just proceed by fixing a, say a = 15, and trying to find values of b that satisfy the condition, you'll easily see the pattern that way. In 1000-1400 you don't need anything advanced, just general problem solving skills which develop with time. If you get stuck just try examples from sample tests or make by yourself, that should be enough.

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

          should i continue with my strategy or there need a change?? thanks for ur kindness. regards

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

            Yeah doing problems is the way

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

              Thanks brother I am very grateful to you, keeping your suggestion in mind, Hope almighty bless you. Take love

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

    the answer is number of pairs in this form (n, n) (n, 2n), (n, 3n) thats when this equation comming from feel free to ask for further explanation you can prove why these pairs are the only pairs that satisfy the condition lcm / gcd <= 3 but lets say you are clueless just try to solve it for small samples like n = 6 or make a brute force solution and try to observe the pattern ps : and for sure (2n, n), (3n, n) thats why the second and the third part of equation are multiplied by 2

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

      thanks a lot for your explanation, i was unable to think with this way. i made some equation for cases like 5 6 7 8 9 10 and i found a series for odd and even numbers it took a lot of time from me. then i observed prime numbers are not satisfying my series .after that i started to think for making another a series for prime numbers but it was impossible to construct a series for that. i leave the question. for me your given strategy was unreachable for me.

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

        its not unreachable and is not the best stretagy too however, its easy to generate all the pairs that satisify the conditions and then observe the pattern ( this is also works with alot of problems) it took no time to write something like this : https://ideone.com/pn7Ean then starting to observe the pattern then formulating the equation will be the easy part. btw, in this problem it was sufficient for me to get the observation from the samples and by thinking about lcm/gcd = 1 , lcm / gcd = 2, lcm / gcd = 3 each part alone but the above method can help in such sutations too sory for bad english

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

    Try to think when LCM(a,b)/GCD(a,b) will become 1,2 or 3 separately ... Think about it. Then you will find this equation.

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

Easily the worst contest I've seen so far, and that's not just me being salty because of the rating drop.

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

    Care to elaborate? (asking in good faith)

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

      Bad ad-hoc A, cant guess or prove the solution easily for an A leading to most people leaving the contest without submitting to preserve rating, also frankly just a bad problem for a coding contest. I know CF is based on math and all but there should be some balance.

      B higher than the usual level of D2Bs (atleast I thought so personally). D2 A and Bs need to be solvable relatively easily and I personally felt like these problems werent a good example of that. C was a good problem at an appropriate level tho, but A and B being this way kinda ruined what would be coming anyway for most people at lower rating ranges.

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

        I agree. B is harder than usual, which uses a common trick(but it shouldn't appear on Div.2 B)

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

There are some problems with problem E statement.

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

Hard Contest :/

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

Can Anyone Explain Solution of Problem B I am not able to figure out it???

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

Trying to write an easy explanation of why the answer of A is $$$n + 2(n/2) + 2(n/3)$$$. Note that we are using only integer division here.

Suppose,

$$$g = gcd(a, b)$$$
$$$l = lcm(a, b) = ab / g$$$

We can also write a and b using g like this:

$$$a = gx$$$
$$$b = gy$$$

Now let's transform the left-hand side of the given inequality using these variables:

$$$l/g = ab/gg = gxgy/gg = xy$$$

Values of the pair (x, y) can be (1,1), (1,2) or (1,3). Otherwise, xy would be greater than 3.

There are n possible pairs such that (x, y) = (1, 1):

$$$(1, 1), (2, 2), (3, 3), ..., (n, n)$$$

There are n / 2 possible pais such that (x, y) = (1, 2):

$$$(1, 2), (2, 4), (3, 6), ..., (n/2, n)$$$

There are n / 3 possible pairs such that (x, y) = (1, 3):

$$$(1, 3), (2, 6), (3, 9), ..., (n/3, n)$$$

Each pair (a, b) that satisfies (x, y) = (1, 2) or (x, y) = (1, 3) will be counted twice because (a, b) and (b, a) are considered different pair when a is not equal to b.

Hence, the number of pair (a, b) that satisfy the given inequality is:

$$$n + 2(n/2) + 2(n/3)$$$
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Shouldn't the exact formula be $$$n + 2*\lfloor\frac{n}{2}\rfloor + 2*\lfloor\frac{n}{3}\rfloor$$$?

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

      Yes, edited my comment, clarified that we are using only integer division.

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

Div1 contest.

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

    How do you ever speak about a competition having Div.1 difficulty when you have never even experienced Div.1?

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

When editorial will be available?

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

    I have now translated the editorial into English, you can read it here. The delay was because the editorial was not available even in Russian back then, and translating it into English took me a bit more time than I expected because I haven't even read the problems before.

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

wait. Did anyone actually notice that this round had quite a lot of testers from the SIS? Was it just me?

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

This was my first Div2. During the contest, thought that CP is not my cup of tea. According to my mentor, I should be able to solve at least two questions in Div2 contests. Struggled a lot even in the first question.

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

    Why don't you ask your mentor about this competition? He/She would know better about this competition's difficulty after actually seeing it.

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

      He was talking in general about Div2 contests.

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

    I struggled too. A is too hard for div1A

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

Problem A I solved in O(N) but why did I get TLE on test case 2????

N<=10^8 will O(n) not work in 1 sec?

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

    time complexity of total code is O(n * t) , if you look closely its 10 ^ 12 order or so try to solve in O(1) time and space complexity

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

    Because there are $$$t \leq 10^4$$$ testcases and that with $$$n \leq 10^8$$$ multiplies to up to $$$10^{12}$$$.

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

    there are 10^4 testcases, so your code performs around 1e4 * 1e8 = 1e12 operations...

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

Need help on this

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

Hey ! I have stuck in this 1000-1150 rating for a really long time now. I just dont seem to move forward. It's become very tiring and irritating now. Can someone please suggest some tips and/or resources to get better :')

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

Can somebody help me out on this.. this is showing WA on 10397th token ... Currently not able to figure out my mistake..

My submission

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

How does one come up with the observation x *= (n-i)/(i+1) where x is to be added to answer at every iteration during the contest? Can you recommend some practice material?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Comment here:
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Dang, that's a nice way of thinking about it. Better than the nonexistent editorial lol

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

      Thanks, really helps!

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

amogus

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

E is easier than D

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

Can anyone post a solution for E?

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

Found a interesting solution to A

Here's the code

I was writing a brute force trying to find a rule and found that between two consecutive Ns the difference is 1, 3, 3, 1, 5 (in this order repeating)

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

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

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

thanks for the round :DDD i had a lot of fun upsolving

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

rubbish main test on problem F.

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

I see some accepted submissions failing on certain inputs for problem B. For example, the solution 170686656 fails for

1
5 4 3 3

The output is

.X...
..X..
..X..
...X.
X...X

I see two columns, column 2 and column 4, having a continuous block of 4 cells without an X.

What should be the conclusion? The tests were weak? Even my submission fails for this input.

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