### FairyWinx's blog

By FairyWinx, history, 5 weeks ago, translation,

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

(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:

• +466

 » 5 weeks ago, # |   +4 hope tasks would be fine!
•  » » 5 weeks ago, # ^ |   +152 same bro
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 Tasks were ultra fine
 » 5 weeks ago, # |   +61 The author of the round FairyWinx is the best anime girl!
•  » » 5 weeks ago, # ^ |   0 I Love Megumin.
 » 5 weeks ago, # | ← Rev. 2 →   0 Looking forward to participating this contest! (also great effort on the image not gonna lie)
 » 5 weeks ago, # |   -45 How to calculate Rating change?
 » 5 weeks ago, # |   -17 Scoring distribution is scary
 » 5 weeks ago, # |   +15 I sus that the problem statements have been altered by impostors.... Good luck to all Excited to participate
 » 5 weeks ago, # |   +1 TeaTime ORZ
 » 5 weeks ago, # |   -11 Among us is the best game!!!
 » 5 weeks ago, # |   +10 Nobody: Literally Nobody:Me: Yes, it's TeaTime round (❁´◡❁)
 » 5 weeks ago, # | ← Rev. 5 →   -9 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 →   +38 ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣶⣿⣿⣷⣶⣄⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣾⣿⣿⡿⢿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⡟⠁⣰⣿⣿⣿⡿⠿⠻⠿⣿⣿⣿⣿⣧⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⠏⠀⣴⣿⣿⣿⠉⠀⠀⠀⠀⠀⠈⢻⣿⣿⣇⠀⠀⠀ ⠀⠀⠀⠀⢀⣠⣼⣿⣿⡏⠀⢠⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⡀⠀⠀ ⠀⠀⠀⣰⣿⣿⣿⣿⣿⡇⠀⢸⣿⣿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⡇⠀⠀ ⠀⠀⢰⣿⣿⡿⣿⣿⣿⡇⠀⠘⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⢀⣸⣿⣿⣿⠁⠀⠀ ⠀⠀⣿⣿⣿⠁⣿⣿⣿⡇⠀⠀⠻⣿⣿⣿⣷⣶⣶⣶⣶⣶⣿⣿⣿⣿⠃⠀⠀⠀ ⠀⢰⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀ ⠀⢸⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠉⠛⠛⠛⠉⢉⣿⣿⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣇⠀⣿⣿⣿⠀⠀⠀⠀⠀⢀⣤⣤⣤⡀⠀⠀⢸⣿⣿⣿⣷⣦⠀⠀⠀ ⠀⠀⢻⣿⣿⣶⣿⣿⣿⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣦⡀⠀⠉⠉⠻⣿⣿⡇⠀⠀ ⠀⠀⠀⠛⠿⣿⣿⣿⣿⣷⣤⡀⠀⠀⠀⠀⠈⠹⣿⣿⣇⣀⠀⣠⣾⣿⣿⡇⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣦⣤⣤⣤⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠻⢿⣿⣿⣿⣿⣿⣿⠿⠋⠉⠛⠋⠉⠉⠁⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⠁⠀⠀⠀⠀⠀⠀
•  » » 5 weeks ago, # ^ |   +3 sUs
•  » » 5 weeks ago, # ^ |   +3 What is this by the way ?
•  » » » 5 weeks ago, # ^ |   0 SuS
 » 5 weeks ago, # |   +3 Why this blog is so sweet ^-^
 » 5 weeks ago, # |   0 I like it :)
 » 5 weeks ago, # |   +4 i am new to codeforces can i attempt division 2 or not i know c++ and little bit dsa
•  » » 5 weeks ago, # ^ |   +4 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 →   +3 first 3 problem is easy or hard bro ?
•  » » » » 5 weeks ago, # ^ |   +1 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, # ^ |   +2 still waiting for the day div. 2c will be easy and i regularly solve div.2ABC
•  » » » » » » 5 weeks ago, # ^ |   0 so do i,hopefully my rating will not fall
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -11 hard
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -7 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, # |   0
 » 5 weeks ago, # |   0 GREAT!
 » 5 weeks ago, # |   0 the crewmates are bumping onto each other like how my submission does when they encounter special test cases.
 » 5 weeks ago, # |   +5 Amogus themed Round! Will use the Amogus Trick to AK the round
•  » » 5 weeks ago, # ^ |   0 It's just cute picture(
•  » » » 5 weeks ago, # ^ |   +5 Oof. Still the amogus trick can do something XD
•  » » 5 weeks ago, # ^ |   0 what if the two in the pic were both imposters tho
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0
 » 5 weeks ago, # |   +3 Spoilerඞ
 » 5 weeks ago, # | ← Rev. 5 →   -17 Hope to perform best in this contest
•  » » 5 weeks ago, # ^ |   0 You will be soon just continue
 » 5 weeks ago, # | ← Rev. 2 →   +14 AmongUsForces
 » 5 weeks ago, # |   +1
•  » » 5 weeks ago, # ^ |   +8 2022 — memes on memes :)
•  » » 5 weeks ago, # ^ |   +6 2020 good times I created that era (my previous username was SupaHotFire)
 » 5 weeks ago, # |   +9 amogugus
 » 5 weeks ago, # | ← Rev. 2 →   -8 happy birthday power-star Pawan Kalyan
 » 5 weeks ago, # |   0 Hope that this one wouldn't be too hard...
 » 5 weeks ago, # |   0 Hey I'm new and I use java. Is their a problem because of the higher runtime?
•  » » 5 weeks ago, # ^ |   0 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, # ^ |   +5 ty bro
 » 5 weeks ago, # |   0 Hope Task would be Fine !!
 » 5 weeks ago, # |   0 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, # ^ |   0 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, # ^ |   0 Hi, thanks a lot for explaining. So, there's no hacking phase for this round, right?
•  » » » » 5 weeks ago, # ^ |   0 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, # ^ |   0 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, # ^ |   0 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, # ^ |   +16 Thx bro for the story
•  » » » 5 weeks ago, # ^ |   0 Hi, can you suggest any application to extract sample input and output for all problems in a contest, for VS Code?
•  » » » » 5 weeks ago, # ^ |   0
•  » » » » » 5 weeks ago, # ^ |   0 Okay. That sounds good. By the way, can we access problems without logging in? For example, if I developed my own sample extractor, I would want it to work without signing in.
 » 5 weeks ago, # |   0 Good luck
 » 5 weeks ago, # |   +1 Hope to become an Expert :')
•  » » 5 weeks ago, # ^ |   0 Good wish to you！
 » 5 weeks ago, # |   +1 Hoping to reach specialist.
 » 5 weeks ago, # |   +8 I just wrote this to make numbers of comments 69 :)
 » 5 weeks ago, # |   0 hello everyone best of luck
 » 5 weeks ago, # |   -25 By far the worst contest I've ever attended.
 » 5 weeks ago, # |   -11 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 →   -17 Very hard problems for div.2?◑﹏◐
 » 5 weeks ago, # |   -8 Div 1.5 :'(
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -14 Your profile lOOks attractive :)EmilyBloom
•  » » 5 weeks ago, # ^ |   +3 5555
 » 5 weeks ago, # |   -8 i mean why someone would do that in problem b thats pure evil
•  » » 5 weeks ago, # ^ |   +11 IMHO B was easier than A
•  » » » 5 weeks ago, # ^ |   -12 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, # ^ |   +3 well, almost everytime, B is easier than it looks.
•  » » » » » 5 weeks ago, # ^ |   0 maybe you are right
•  » » » » » » 5 weeks ago, # ^ |   0 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, # ^ |   0 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, # |   -41 I Hate U Madoka ._.
 » 5 weeks ago, # | ← Rev. 4 →   -9 Приветствую, Кодефорсес ✿*∗˵╰༼✪ᗜ✪༽╯˵∗*✿after i have saw this i knew that the contest will be hard :( Edit : I love the Math :)
 » 5 weeks ago, # |   +54 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 →   +37 Because they are beautiful in my opinion)
•  » » » 5 weeks ago, # ^ |   0 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, # ^ |   +18 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, # ^ |   -8 I was solving such a problem during the math contest in 5th school grade.
•  » » » » » » 5 weeks ago, # ^ |   +8 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, # ^ |   -20 you should probably think more about ppl who have more ability in CP than maths
•  » » 5 weeks ago, # ^ |   -11 Are you giving the contest from your alt account ?? Wind_Eagle
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 I'm just reading and trying to solve the problems without submitting :)
•  » » » » 5 weeks ago, # ^ |   -10 I think you are come in category of red coders . :). Wind_Eagle
•  » » » 5 weeks ago, # ^ |   0 no he registered unofficially and just looked at it I think
 » 5 weeks ago, # |   -7 Problem A and B, Pure evil :(
•  » » 5 weeks ago, # ^ |   0 LOOL
 » 5 weeks ago, # |   -13 Mathforces !
 » 5 weeks ago, # |   +3 Feel REALLY grateful to the authors as I got AK for the first time.
 » 5 weeks ago, # |   0 This was my first contest. Problems were too difficult for me
•  » » 5 weeks ago, # ^ |   +8 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, # |   +37 F is very classical, I don't like it :(
•  » » 5 weeks ago, # ^ |   +10 D and E are very classical too.
•  » » » 5 weeks ago, # ^ |   +6 D is classical? Do you have any problems that are similar to it? (I thought it was pretty unique lol)
•  » » » » 5 weeks ago, # ^ |   -22 Yeah, I took my solution for recent contest https://codeforces.com/contest/1696/problem/E and literally changed input parsing and 1 line
 » 5 weeks ago, # |   +31 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, # ^ |   0 Same
 » 5 weeks ago, # |   +2 How to solve D?
•  » » 5 weeks ago, # ^ |   +12 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, # ^ |   +3 Great explanation, thanks.
 » 5 weeks ago, # | ← Rev. 2 →   +14 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, # ^ |   0 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 →   0 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: $a_i \leq b_i$ for all $i$ 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 →   +5 2nd Div 2 winner: Akemi-HomuraI can see why...
 » 5 weeks ago, # |   0 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 →   +10 There is a way to make division into multiplication under modulo called seeking invers.
•  » » 5 weeks ago, # ^ |   0 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, # ^ |   0 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, # ^ |   +30 ${ 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, # ^ |   +28 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, # ^ |   +1 Can someone explain problem D?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 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, # ^ |   0 Why $min(n,k)$ and why ${n \choose i}$ ?
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 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 →   +4 I think E is a bit standard?D is cool though :)
•  » » 5 weeks ago, # ^ |   0 Can you give me a hint for E?
•  » » » 5 weeks ago, # ^ |   0 SpoilerYou can enumerate "c" mentioned in the statement, and see what will happen to gcd(a,b) when a+b is a fixed value n-c.
•  » » » 5 weeks ago, # ^ |   0 SpoilerEuler's totient function
 » 5 weeks ago, # |   0 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, # ^ |   0 think about number which can make pair with number x(only 2 * x and 3 * x are suitable)
•  » » 5 weeks ago, # ^ |   0 The eqn can be written as (a*b)/(gcd(a,b))^2 <=3
•  » » » 5 weeks ago, # ^ |   0 how do you solve this then?
•  » » » » 5 weeks ago, # ^ |   0 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 multiplesafter that, I observed that for any a and 2*a the equation yields 2 and for any a and 3*a, it yields 3so we have to consider a,a*2 and a*3.
•  » » » 5 weeks ago, # ^ |   0 please explain how u approach after getting this inequality
•  » » 5 weeks ago, # ^ |   0 Okaylet's gcd of a and b equal DThen 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=XYSO you need to find pairs of numbers like x,x/3 x/3,xx/2,xx,x/2x,x
 » 5 weeks ago, # |   +8 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, # ^ |   +9 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, # ^ |   +15 We're all different))
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +13 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 →   +5 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$c \cdot \frac{\gcd (a, n-c)}{\gcd(\gcd (a, n-c), c)}$ And be careful not to count cases where some variable is $0$.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +5 Hint 1 Calculate the answer for each c:a+b = n-c, so there aren't a lot of variants of gcd(b,c), since gcd(b,c) is a divisor of n-k Hint 2 if gcd (a,b) = x, then a/x and b/x don't have common divisors, and their sum is (n-c)/x, so for certain number s below 1e5 (since n-c<=1e5) we need to find all pairs of a1+b1=s and gcd(a1,b1)=1Hint 3 Try to find just the opposite: all pairs of a1+b1=s and gcd(a1,b1)>1Hint 4 Can you calculate this for every s <=1e5 with dp?hope this helps))
•  » » » » 5 weeks ago, # ^ |   0 Thank you
•  » » » » » 5 weeks ago, # ^ |   0 You are welcome
 » 5 weeks ago, # |   +3 Well, that's like mathforces :(
 » 5 weeks ago, # |   +23 I think A is so hard for D2A, was there easier solution? my submission#include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); vector> ab={ {1,1}, {1,2}, {1,3}, {2,1}, {3,1} }; int t; cin >> t; while(t>0){ t--; int n,res=0; cin >> n; for(auto &nx : ab){ res+=n/(max(nx.first,nx.second)); } cout << res << "\n"; } return 0; } 
•  » » 5 weeks ago, # ^ |   +6 n + 2*(n/2 + n/3)
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   +6 n + (n // 2) * 2 + (n // 3) * 2
•  » » 5 weeks ago, # ^ |   -10 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)<
•  » » 5 weeks ago, # ^ |   0 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, # ^ |   +3 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 →   +23 Can Problem E be solved in $O(n \log n)$?
•  » » 5 weeks ago, # ^ |   +15 you could probably do it using sieveing the phi function, but $O(n\ln n\sqrt n)$ is easier to implement.
•  » » 5 weeks ago, # ^ |   +15 How did you solve it?
•  » » » 5 weeks ago, # ^ |   0 I mistyped the index, sorry
•  » » 5 weeks ago, # ^ |   +8 Yep)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +28 Mangooste solve in testing in $O(nlog)$
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 jianlgy's solution is $O(n \log n)$
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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, # |   +1 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, # ^ |   +26 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, # |   0 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]'sisnt my approach for C correct ??
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Consider the case 5 3 4 1 4 1 4 4 2 4 2
•  » » » 5 weeks ago, # ^ |   0 Thanks for replying just see the test where it was failing it just that i had to put OR there but i had put AND Wrong Solution : https://codeforces.com/contest/1717/submission/170638678 Accepted Solution : https://codeforces.com/contest/1717/submission/170649100
•  » » 5 weeks ago, # ^ |   0 Video Solution for Problem C
 » 5 weeks ago, # |   0 question about problem C: how did this massive lump of spaghetti pass the systests? I can't prove my solution. 170616890
•  » » 5 weeks ago, # ^ |   0 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, # ^ |   +3 oh so it actually was a massive lump of spaghetti which doesn't even work properly. damn.
 » 5 weeks ago, # |   +96 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, # ^ |   0 agree
•  » » 5 weeks ago, # ^ |   0 Kinda right, but in actuality it turned out to be relatively easy to solve.
•  » » 5 weeks ago, # ^ |   +1 sampleforces
•  » » 5 weeks ago, # ^ |   +27 Maybe, CF should adopt Atcoder style registration: Rating will drop even if you don't submit anything.
 » 5 weeks ago, # |   0 I submitted B twice which are almost similar beacuse of my second my first submission is skipped.
 » 5 weeks ago, # |   0 Damm Questions were quite tough!
•  » » 5 weeks ago, # ^ |   0 yep for sure
 » 5 weeks ago, # |   +31 It's the fastest system test of div.2 as far as I know.It just took about 15min .
 » 5 weeks ago, # |   0 Am I not mistaken? The system testing was fast as fuck, wasn't it?
•  » » 5 weeks ago, # ^ |   0 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 →   +53 I got suck in problem A for twenty minutes. The hardest D2A I've ever met!
•  » » 5 weeks ago, # ^ |   +3 Me too :'(
•  » » 5 weeks ago, # ^ |   +3 for 1 hour.then i picked up pen and paper and did it.
•  » » 5 weeks ago, # ^ |   0 I think so , this problem A isn't as easy as before .
•  » » 5 weeks ago, # ^ |   0 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, # ^ |   0 To add values to the answer is cyclic, I noticed this with bruteforce than it was cake
•  » » 4 weeks ago, # ^ |   0 Yeah it's hard to find the solution and i used 40 minutes to solve it:(
 » 5 weeks ago, # | ← Rev. 2 →   0 This prolly was the fastest system testing I have ever seen, wow
 » 5 weeks ago, # |   +10 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, # |   +29 How to understand D's statement?
 » 5 weeks ago, # | ← Rev. 2 →   0 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 →   +1 3rd column in 3rd case is completely empty, I can pick 1*k vertical segment without X in it.
•  » » » 5 weeks ago, # ^ |   +1 Thanks. I passed now.
•  » » 5 weeks ago, # ^ |   0 'cause you got X.. X.. .X. Which leaves the rightmost column empty so it doesn't satisfy the requirement.
 » 5 weeks ago, # |   +41 honestly, D statement is a bit hard to read and understand
•  » » 5 weeks ago, # ^ |   +18 Yep. But it's fun to solve. The most elegant task out of A-D in my opinion.
•  » » 5 weeks ago, # ^ |   +34 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, # ^ |   -10 regardless means that we need to minimise the maximum of all possible outcomes
 » 5 weeks ago, # |   +36 Good to see some coding questions in a maths contest!
 » 5 weeks ago, # |   +17 The system test is so fast.Good job!
 » 5 weeks ago, # |   +1 Why task C solved in O(n) on pypy3 has TL? https://codeforces.com/contest/1717/submission/170628126
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +10 You should use sys.stdin.readline() and sys.stdout.write for fast python i/o when a problem has a lot of cases. https://codeforces.com/contest/1717/submission/170651067
 » 5 weeks ago, # |   +1 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/170648846https://codeforces.com/contest/1717/submission/170648671This 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, # ^ |   0 Same happened with me. The same code ran now but failed system tests.
•  » » 5 weeks ago, # ^ |   0 Same here.
 » 5 weeks ago, # |   0 Maths-forces
 » 5 weeks ago, # | ← Rev. 6 →   0 Can someone tell me what's wrong with my submission? (for B) https://codeforces.com/contest/1717/submission/170645855My logic: SpoilerI created a n*n matrix with diagonal Xs according to the value of K. for example for n=6, k=3, this matrix would be created:X..X...X..X...X..XX..X...X..X...X..Xnext I found the row which would satisfy the given c value for example for c= 4, this row will be selected X..X..Now for the row to come at the position of the given r, say r=2, I will calculate the row which I should start the matrix from which in this case would be:..X..XThen I print the matrix accordingly and repeated it if necessary Ans for above problem:..X..XX..X...X..X...X..XX..X...X..X.Would be really grateful if you could post a counter test case, thanks!EDIT: Figured it out, ty
•  » » 5 weeks ago, # ^ |   0 Your code fails at multitest test cases. Try2 10 10 1 1 8 2 1 1
•  » » » 5 weeks ago, # ^ |   0 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, # |   0 Can someone please explain to me, how they thought about problem C and how you arrived at the observations?
•  » » 5 weeks ago, # ^ |   0 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]
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +3 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, # ^ |   0 sorry but isn't that B, not C
•  » » » » 5 weeks ago, # ^ |   +3 Oh oops I mixed up the problems.
 » 5 weeks ago, # |   0 Any hint for D?
•  » » 5 weeks ago, # ^ |   -8 Think about Pascal's triangle
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 hintsuppose Madoka chose winner for finals to be the right. then, there is exists equivalent tournament with winner in finals from left: just swap two halfs (left subtree of finals, and right subtree of finals).
 » 5 weeks ago, # |   0 can someone tell me the idea of b?
•  » » 5 weeks ago, # ^ |   0 Hintenumerate all $r+c$ of the cells with an $\text{X}$ in the example outputs, and then look at the $r+c$ with the corresponding input. do you see a pattern?
•  » » » 5 weeks ago, # ^ |   0 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 meanhttps://codeforces.com/contest/1717/submission/170632638
•  » » » » 5 weeks ago, # ^ |   +3 Hint 2If we enumerate $r+c$ of the fifth test case's output, we see ${3,6,9,12}$ as the set of unique values. In the input, $r+c$ is $6$ and $k$ is $3$. Do you see a pattern now?
•  » » 5 weeks ago, # ^ |   0 Hint 1what would be the best way to fill 'X' to satisfy both row and col. Hint 2so, the answer is 'diagonal way'. so try filling as few 'X' as possible so that 2 'X's in a single column or row has k distance. Hint 3Now, you may have filled the 'X's in the following way for the 3rd sample. X..X.. .X..X. ..X..X X..X.. .X..X. ..X..X So now? what to do with cell $(r, c).$ Hint 4Try making diagonals with $(r, c).$ 170650164
 » 5 weeks ago, # |   0 Am I the only one who solved C but couldn't solve B?
 » 5 weeks ago, # |   +11 Make A easy please, people will give up the contest quickly if they can't solve A..
•  » » 5 weeks ago, # ^ |   0 Agreed, often I see A is tougher than usual.
 » 5 weeks ago, # |   +7 The problems were somehow interesting but most of them were math (very close to pure math).... It makes this round less than a good roundDid the testers give their opinion about this? I blame them too if they did not
 » 5 weeks ago, # |   0 Any idea why A solution is (n + n / 2 * 2 + n / 3 * 2 ) ?
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   0 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, # ^ |   +3 Try to write the TLE solution with nested loop and then observe the equation. Really, It is a pure math problem!◑﹏◐
•  » » 5 weeks ago, # ^ |   0 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 a3*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 →   0 D was a great one. Too bad, I was late for a minute
 » 5 weeks ago, # |   0 When will our ratings get updated?
•  » » 5 weeks ago, # ^ |   0 soon(tm)
 » 5 weeks ago, # |   +3 A is too complex for Div2 i think too much math
 » 5 weeks ago, # |   +3 feels so lucky when ur solution passes system testing so close to TL.
•  » » 5 weeks ago, # ^ |   +7 Indian meme :)Your solution meanwhile...
 » 5 weeks ago, # |   0 big fan of this round :)
 » 5 weeks ago, # |   +1 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, # |   +4 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, # |   +13 Problem D's harder than E.
•  » » 5 weeks ago, # ^ |   +5 Same for me, I don't understand how 1000+ people solved D.
•  » » » 5 weeks ago, # ^ |   0 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, # ^ |   0 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, # ^ |   +20 Problem E is harder than D.
•  » » » 5 weeks ago, # ^ |   +3 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, # ^ |   +19 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, # |   +86 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, # ^ |   0 Amazing!
•  » » 5 weeks ago, # ^ |   0 Amazing
•  » » 5 weeks ago, # ^ |   +4 The problem with this approach is that it takes more than 2 minutes.
•  » » 5 weeks ago, # ^ |   +3 Amazing!Did you try it on problem E?
•  » » 5 weeks ago, # ^ |   +19 Given the delay with the editorial I am sure this will help the newbies. Thank you!
•  » » 5 weeks ago, # ^ |   0 This is nice. If you observe a bit of basic math, you can simplify it further for integer n.
•  » » 5 weeks ago, # ^ |   0 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, # ^ |   +10 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, # ^ |   0 Yes i did that too
•  » » 5 weeks ago, # ^ |   0 You're too good. orz
•  » » 5 weeks ago, # ^ |   0 wtf
•  » » 5 weeks ago, # ^ |   0 a new OEIS lol
 » 5 weeks ago, # |   0 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, # ^ |   0 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, # ^ |   0 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, # ^ |   0 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, # ^ |   0 should i continue with my strategy or there need a change?? thanks for ur kindness. regards
•  » » » » » » 4 weeks ago, # ^ |   0 Yeah doing problems is the way
•  » » » » » » » 4 weeks ago, # ^ |   +3 Thanks brother I am very grateful to you, keeping your suggestion in mind, Hope almighty bless you. Take love
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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, # ^ |   0 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, # ^ |   0 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, # ^ |   0 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, # |   -18 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, # ^ |   0 Care to elaborate? (asking in good faith)
•  » » » 5 weeks ago, # ^ |   +4 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, # ^ |   0 I agree. B is harder than usual, which uses a common trick(but it shouldn't appear on Div.2 B)
 » 5 weeks ago, # |   +20 There are some problems with problem E statement.
 » 5 weeks ago, # |   +6 Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
 » 5 weeks ago, # |   0 Hard Contest :/
 » 5 weeks ago, # |   0 Can Anyone Explain Solution of Problem B I am not able to figure out it???
 » 5 weeks ago, # | ← Rev. 2 →   +4 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, # ^ |   0 Shouldn't the exact formula be $n + 2*\lfloor\frac{n}{2}\rfloor + 2*\lfloor\frac{n}{3}\rfloor$?
•  » » » 4 weeks ago, # ^ |   0 Yes, edited my comment, clarified that we are using only integer division.
 » 5 weeks ago, # |   -11 Div1 contest.
•  » » 5 weeks ago, # ^ |   0 How do you ever speak about a competition having Div.1 difficulty when you have never even experienced Div.1?
 » 5 weeks ago, # |   +8 When editorial will be available?
•  » » 5 weeks ago, # ^ |   0 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, # |   -13 wait. Did anyone actually notice that this round had quite a lot of testers from the SIS? Was it just me?
 » 5 weeks ago, # |   0 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, # ^ |   0 He was talking in general about Div2 contests.
•  » » 5 weeks ago, # ^ |   0 I struggled too. A is too hard for div1A
»
5 weeks ago, # |
Rev. 2   0

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, # ^ |   0 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, # ^ |   0 thanks
•  » » 5 weeks ago, # ^ |   0 Because there are $t \leq 10^4$ testcases and that with $n \leq 10^8$ multiplies to up to $10^{12}$.
•  » » » 5 weeks ago, # ^ |   0 Thanks
•  » » 5 weeks ago, # ^ |   0 there are 10^4 testcases, so your code performs around 1e4 * 1e8 = 1e12 operations...
 » 5 weeks ago, # |   0 Need help on this
 » 5 weeks ago, # |   0 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, # |   0 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, # ^ |   0 Take a look at Ticket 16146 from CF Stress for a counter example.
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot <3.....
 » 5 weeks ago, # |   0 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, # ^ |   +4 Comment here:Generally speaking, let's notice that we can simplify problem a bit by assuming that initially winner of each match is on the left, and Madoka controls only the permutation of numbers in the last layer (we can reduce any other case to this, by imagining that we "swap" appropiate left sub-trees with right subtrees). So the situation looks like that:Purple numbers on the picture mean how many changes sponsors have to make in order to make given participant a winner. Possible winners are nodes with purple numbers smaller or equal k, so given that Madoka controls the initial permutation of participants, the answer to task is number of nodes with purple numbers smaller or equal k in last layer. Now we have to count them. Let a[i][j] be number of purple numbers equal to j in i-th layer of our tree (counting from the top). It's easy (?) to see that a[i][j]=a[i-1][j-1]+a[i-1][j] (this conclusion comes directly from the picture). And this is formula for Pascal's triangle. Pascal's triangleNumber in the i-th row and j-th column of Pascal's triangle is C(i,j)=i!/(j!*(i-j)!). So to generate fast numbers in i-th row of Pascal's triangle you can use formula C(i,j)=C(i,j-1)/j*(i-j). That's the answer for your question. Sorry for no Latex.
•  » » » 5 weeks ago, # ^ |   0 Dang, that's a nice way of thinking about it. Better than the nonexistent editorial lol
•  » » » 4 weeks ago, # ^ |   0 Thanks, really helps!
 » 5 weeks ago, # |   +3 amogus
 » 5 weeks ago, # |   0 E is easier than D
 » 5 weeks ago, # |   +4 Can anyone post a solution for E?
•  » » 5 weeks ago, # ^ |   0 You can check out the official text editorial or this video editorial at 29:25.
 » 5 weeks ago, # | ← Rev. 2 →   +11 Found a interesting solution to A Here's the code#include #define all(x) (x).begin(), (x).end() #define sz(x) (x).size() #define MAX using namespace std; using ll = long long; #define int ll using pii = pair; int T,n; void solve(){ cin >> n; int lookup[] = {1, 3, 3, 3, 1, 5}; int sum = 16; int len = 6; int ans = (n/len)*sum; for(int i = 0; i < n%len; i++){ ans += lookup[i]; } cout << ans << "\n"; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> T; while(T--){ solve(); } } 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, # |   0 Auto comment: topic has been updated by FairyWinx (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 thanks for the round :DDD i had a lot of fun upsolving
 » 5 weeks ago, # |   0 rubbish main test on problem F.
 » 4 weeks ago, # | ← Rev. 2 →   0 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, # ^ |   0 N has to be divisible by K. It's mentioned in the problem statement
•  » » » 4 weeks ago, # ^ |   0 Okay. I overlooked it and missed so many details.
 » 4 weeks ago, # | ← Rev. 2 →   0 Problem D video editorial with code!
 » 4 weeks ago,