Приветствую, Кодефорсес ✿*∗˵╰༼✪ᗜ✪༽╯˵∗*✿
(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:
- To our cute coordinator Artyom123.
- KAN, geranazavr555, MikeMirzayanov for being able to me conduct this round on this platform.
- Our valiant army of testers: Mangooste, teraqqq, SomethingNew, 74TrAkToR, Igorbunov, Vladithur, Dart-Xeyter, Alexdat2000, vsinitsynav, Renedyn, _DAC_, talant, NewLul, satyam343, I_love_geom, Aris, PUFL.
- Igorbunov for the idea of one of the tasks.
- You for your participation.
See you at the round🥰
Scoring distribution: 500 — 1000 — 1500 — 2000 — 2000 — 3000
UPD: Editorial!!! (Thanks to purplesyringa for English translation)
UPD: Winners!
Div 2:
Div 1:
hope tasks would be fine!
same bro
Tasks were ultra fine
The author of the round FairyWinx is the best anime girl!
I_love_geom — у понравился раунд? Если да, то это очень опасно.
Раунд будет замечательным!
Теперь никто участвовать не будет(
Я ведь не говорил, что мне он понравился, просто раунд очень хороший.
Не врешь?)
Looking forward to participating this contest! (also great effort on the image not gonna lie)
Scoring distribution is scary
I sus that the problem statements have been altered by impostors.... Good luck to all Excited to participate
TeaTime ORZ
Among us is the best game!!!
Nobody: Literally Nobody:
Me: Yes, it's TeaTime round (❁´◡`❁)
Can somebody please suggest how to make strong strong grip on mathmatics Problem ,I get stuck on easy mathmatics problems?
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣶⣿⣿⣷⣶⣄⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣾⣿⣿⡿⢿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⡟⠁⣰⣿⣿⣿⡿⠿⠻⠿⣿⣿⣿⣿⣧⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⠏⠀⣴⣿⣿⣿⠉⠀⠀⠀⠀⠀⠈⢻⣿⣿⣇⠀⠀⠀ ⠀⠀⠀⠀⢀⣠⣼⣿⣿⡏⠀⢠⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⡀⠀⠀ ⠀⠀⠀⣰⣿⣿⣿⣿⣿⡇⠀⢸⣿⣿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⡇⠀⠀ ⠀⠀⢰⣿⣿⡿⣿⣿⣿⡇⠀⠘⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⢀⣸⣿⣿⣿⠁⠀⠀ ⠀⠀⣿⣿⣿⠁⣿⣿⣿⡇⠀⠀⠻⣿⣿⣿⣷⣶⣶⣶⣶⣶⣿⣿⣿⣿⠃⠀⠀⠀ ⠀⢰⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀ ⠀⢸⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠉⠛⠛⠛⠉⢉⣿⣿⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣇⠀⣿⣿⣿⠀⠀⠀⠀⠀⢀⣤⣤⣤⡀⠀⠀⢸⣿⣿⣿⣷⣦⠀⠀⠀ ⠀⠀⢻⣿⣿⣶⣿⣿⣿⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣦⡀⠀⠉⠉⠻⣿⣿⡇⠀⠀ ⠀⠀⠀⠛⠿⣿⣿⣿⣿⣷⣤⡀⠀⠀⠀⠀⠈⠹⣿⣿⣇⣀⠀⣠⣾⣿⣿⡇⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣦⣤⣤⣤⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠻⢿⣿⣿⣿⣿⣿⣿⠿⠋⠉⠛⠋⠉⠉⠁⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⠁⠀⠀⠀⠀⠀⠀
Опять раунд от русских школьников...
Ты не прав, уже высших школьников
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣴⣶⣿⣿⣷⣶⣄⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣾⣿⣿⡿⢿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⡟⠁⣰⣿⣿⣿⡿⠿⠻⠿⣿⣿⣿⣿⣧⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⠏⠀⣴⣿⣿⣿⠉⠀⠀⠀⠀⠀⠈⢻⣿⣿⣇⠀⠀⠀ ⠀⠀⠀⠀⢀⣠⣼⣿⣿⡏⠀⢠⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⡀⠀⠀ ⠀⠀⠀⣰⣿⣿⣿⣿⣿⡇⠀⢸⣿⣿⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⡇⠀⠀ ⠀⠀⢰⣿⣿⡿⣿⣿⣿⡇⠀⠘⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⢀⣸⣿⣿⣿⠁⠀⠀ ⠀⠀⣿⣿⣿⠁⣿⣿⣿⡇⠀⠀⠻⣿⣿⣿⣷⣶⣶⣶⣶⣶⣿⣿⣿⣿⠃⠀⠀⠀ ⠀⢰⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀ ⠀⢸⣿⣿⡇⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠉⠛⠛⠛⠉⢉⣿⣿⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣇⠀⣿⣿⣿⠀⠀⠀⠀⠀⢀⣤⣤⣤⡀⠀⠀⢸⣿⣿⣿⣷⣦⠀⠀⠀ ⠀⠀⢻⣿⣿⣶⣿⣿⣿⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣦⡀⠀⠉⠉⠻⣿⣿⡇⠀⠀ ⠀⠀⠀⠛⠿⣿⣿⣿⣿⣷⣤⡀⠀⠀⠀⠀⠈⠹⣿⣿⣇⣀⠀⣠⣾⣿⣿⡇⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣦⣤⣤⣤⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠻⢿⣿⣿⣿⣿⣿⣿⠿⠋⠉⠛⠋⠉⠉⠁⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⠁⠀⠀⠀⠀⠀⠀
sUs
What is this by the way ?
SuS
Why this blog is so sweet ^-^
i am new to codeforces can i attempt division 2 or not i know c++ and little bit dsa
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.
first 3 problem is easy or hard bro ?
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.
still waiting for the day div. 2c will be easy and i regularly solve div.2ABC
so do i,hopefully my rating will not fall
hard
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.
the crewmates are bumping onto each other like how my submission does when they encounter special test cases.
Amogus themed Round! Will use the Amogus Trick to AK the round
It's just cute picture(
Oof. Still the amogus trick can do something XD
what if the two in the pic were both imposters tho
The comment is hidden because of too negative feedback,click
to view it
ඞ
2022 — memes on memes :)
2020 good times I created that era (my previous username was SupaHotFire)
amogugus
Hey I'm new and I use java. Is their a problem because of the higher runtime?
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.
ty bro
Hope Task would be Fine !!
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.
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.
Hi, thanks a lot for explaining. So, there's no hacking phase for this round, right?
Yes, that's right, speaking about proper hacking phase after the round. You can still hack during any round after locking the problem.
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).
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.
Thx bro for the story
Hi, can you suggest any application to extract sample input and output for all problems in a contest, for VS Code?
competetive companion https://chrome.google.com/webstore/detail/competitive-companion/cjnmckjndlpiamhfimnnjmnckgghkjbl
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.
Good luck
Hope to become an Expert :')
Good wish to you！
Hoping to reach specialist.
I just wrote this to make numbers of comments 69 :)
By far the worst contest I've ever attended.
By far the worst contest I've ever attended.
Div 1.5 :'(
5555
i mean why someone would do that in problem b thats pure evil
IMHO B was easier than A
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
well, almost everytime, B is easier than it looks.
Am I the only one who solved C but counldn't solve B lol
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.
Because they are beautiful in my opinion)
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.
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.
I was solving such a problem during the math contest in 5th school grade.
Well sure, but it still doesn't make the problem a math problem, unless there's some math concept involved in it.
you should probably think more about ppl who have more ability in CP than maths
Are you giving the contest from your alt account ?? Wind_Eagle
I'm just reading and trying to solve the problems without submitting :)
no he registered unofficially and just looked at it I think
Feel REALLY grateful to the authors as I got AK for the first time.
This was my first contest. Problems were too difficult for me
Usually, problems are way more easy in Div 2. It's just bad timing for you. Keep practicing, you will rock soon ;)
F is very classical, I don't like it :(
D and E are very classical too.
D is classical? Do you have any problems that are similar to it?
(I thought it was pretty unique lol)
Yeah, I took my solution for recent contest https://codeforces.me/contest/1696/problem/E and literally changed input parsing and 1 line
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)
Same
How to solve D?
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]
Great explanation, thanks.
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.
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?
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:
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.
2nd Div 2 winner: Akemi-Homura
I can see why...
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...
There is a way to make division into multiplication under modulo called seeking invers.
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)
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$$$
$$${ n \choose m } = \frac{n!}{m! \times (n-m)!}$$$
And $$$\frac{x}{y} \bmod p$$$ equals to $$$x \times y^{p-2} \bmod p$$$
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!
Can someone explain problem D?
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...
Why $$$min(n,k)$$$ and why $$${n \choose i}$$$ ?
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).
I think E is a bit standard?
D is cool though :)
Can you give me a hint for E?
You 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.
Euler's totient function
I solved $$$B$$$ and $$$C$$$ and still can't figure out A !
I found a solution but it got MLE, any hints?
think about number which can make pair with number x(only 2 * x and 3 * x are suitable)
The eqn can be written as (a*b)/(gcd(a,b))^2 <=3
please explain how u approach after getting this inequality
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
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
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...
We're all different))
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?
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.
$$$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$$$.
hope this helps))
Thank you
You are welcome
Well, that's like mathforces :(
I think A is so hard for D2A, was there easier solution?
n + 2*(n/2 + n/3)
n + (n // 2) * 2 + (n // 3) * 2
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
Yes, you may have pairs as follows:-
So no of pairs = no of pairs of each above types = n + n / 2 + n / 2 + n / 3 + n / 3.
For C I was first making all elements of a which are less than minimum of b equal = minimum of b. than i got one element where a[i]=b[i] now i just check for its prev a[i] and so on
isnt my approach for c is correct ?? or is there something else which i missed
Can Problem E be solved in $$$O(n \log n)$$$?
you could probably do it using sieveing the phi function, but $$$O(n\ln n\sqrt n)$$$ is easier to implement.
How did you solve it?
I mistyped the index, sorry
Yep)
Mangooste solve in testing in $$$O(nlog)$$$
jianlgy's solution is $$$O(n \log n)$$$
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)
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 !!
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.
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 ??
Consider the case
53 4 1 4 14 4 2 4 2Thanks 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.me/contest/1717/submission/170638678 Accepted Solution : https://codeforces.me/contest/1717/submission/170649100
Video Solution for Problem C
question about problem C: how did this massive lump of spaghetti pass the systests? I can't prove my solution. 170616890
Your solution fails for a few cases, one of which includes this:
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.
oh so it actually was a massive lump of spaghetti which doesn't even work properly. damn.
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).
agree
Kinda right, but in actuality it turned out to be relatively easy to solve.
sampleforces
Maybe, CF should adopt Atcoder style registration: Rating will drop even if you don't submit anything.
8000 решивших А, о чём-то и говорит)
I submitted B twice which are almost similar beacuse of my second my first submission is skipped.
It's the fastest system test of div.2 as far as I know.It just took about 15min .
Am I not mistaken? The system testing was fast as fuck, wasn't it?
But system tests of contests I've taken usually took me about 1 hour , so I feel that's so fast today.
I got suck in problem A for twenty minutes. The hardest D2A I've ever met!
Me too :'(
for 1 hour.then i picked up pen and paper and did it.
I think so , this problem A isn't as easy as before .
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.
To add values to the answer is cyclic, I noticed this with bruteforce than it was cake
This prolly was the fastest system testing I have ever seen, wow
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
How to understand D's statement?
For problem B for 1st testcase why is this answer wrong ?
3rd column in 3rd case is completely empty, I can pick 1*k vertical segment without X in it.
Thanks. I passed now.
'cause you got
Which leaves the rightmost column empty so it doesn't satisfy the requirement.
honestly, D statement is a bit hard to read and understand
Yep. But it's fun to solve. The most elegant task out of A-D in my opinion.
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,
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.
regardless means that we need to minimise the maximum of all possible outcomes
Good to see some coding questions in a maths contest!
The system test is so fast.Good job!
Why task C solved in O(n) on pypy3 has TL? https://codeforces.me/contest/1717/submission/170628126
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.me/contest/1717/submission/170651067
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.me/contest/1717/submission/170648846
https://codeforces.me/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".
Same here.
Maths-forces
Can someone tell me what's wrong with my submission? (for B) https://codeforces.me/contest/1717/submission/170645855
My logic:
I 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..X
X..X..
.X..X.
..X..X
next 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..X
Then I print the matrix accordingly and repeated it if necessary Ans for above problem:
..X..X
X..X..
.X..X.
..X..X
X..X..
.X..X.
Would be really grateful if you could post a counter test case, thanks!
EDIT: Figured it out, ty
Your code fails at multitest test cases. Try
2 10 10 1 1 8 2 1 1
Can someone please explain to me, how they thought about problem C and how you arrived at the observations?
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.
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.
sorry but isn't that B, not C
Oh oops I mixed up the problems.
Any hint for D?
Think about Pascal's triangle
suppose 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).
can someone tell me the idea of b?
enumerate 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?
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.me/contest/1717/submission/170632638
If 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?
what would be the best way to fill 'X' to satisfy both row and col.
so, 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.
Now, you may have filled the 'X's in the following way for the 3rd sample.
So now? what to do with cell $$$(r, c).$$$
Try making diagonals with $$$(r, c).$$$ 170650164
guys for problem C why is the expected output for A= 1 1 2 3 3 and B = 4 4 4 4 4 yes? From what I understood you can only get A to become 4 4 4 4 3 and not 4 4 4 4 4.
We can increase the last element by one, because it's not larger than the first element. Read the problem statement carefully.
Am I the only one who solved C but couldn't solve B?
Make A easy please, people will give up the contest quickly if they can't solve A..
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
Any idea why A solution is (n + n / 2 * 2 + n / 3 * 2 ) ?
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.
Try to write the TLE solution with nested loop and then observe the equation.
Really, It is a pure math problem!◑﹏◐
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.
D was a great one. Too bad, I was late for a minute
When will our ratings get updated?
soon(tm)
A is too complex for Div2 i think too much math
feels so lucky when ur solution passes system testing so close to TL.
Your solution meanwhile...
Should have added this test case for problem C: 1 2 1 1 1000000000 1000000000
Because this test is missing, some TLE solutions will pass all the test cases. For example this one: https://codeforces.me/contest/1717/submission/170655104
big fan of this round :)
Should have added this test case for problem C:
Because this test case is not there some TLE solution will get accepted like this one: https://codeforces.me/contest/1717/submission/170655104
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)
Problem D's harder than E.
Same for me, I don't understand how 1000+ people solved D.
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.
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!
Problem E is harder than D.
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.
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$$$.
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:
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:
We can simply code it and get AC: 170655872.
Amazing
The problem with this approach is that it takes more than 2 minutes.
Amazing!
Did you try it on problem E?
Given the delay with the editorial I am sure this will help the newbies. Thank you!
This is nice. If you observe a bit of basic math, you can simplify it further for integer n.
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.
I worked out the relation during contest:
170601961
You're too good. orz
wtf
a new OEIS lol
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!
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.
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
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.
should i continue with my strategy or there need a change?? thanks for ur kindness. regards
Yeah doing problems is the way
Thanks brother I am very grateful to you, keeping your suggestion in mind, Hope almighty bless you. Take love
Easily the worst contest I've seen so far, and that's not just me being salty because of the rating drop.
Care to elaborate? (asking in good faith)
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.
I agree. B is harder than usual, which uses a common trick(but it shouldn't appear on Div.2 B)
There are some problems with problem E statement.
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
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,
We can also write a and b using g like this:
Now let's transform the left-hand side of the given inequality using these variables:
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):
There are n / 2 possible pais such that (x, y) = (1, 2):
There are n / 3 possible pairs such that (x, y) = (1, 3):
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:
Shouldn't the exact formula be $$$n + 2*\lfloor\frac{n}{2}\rfloor + 2*\lfloor\frac{n}{3}\rfloor$$$?
Div1 contest.
How do you ever speak about a competition having Div.1 difficulty when you have never even experienced Div.1?
When editorial will be available?
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.
wait. Did anyone actually notice that this round had quite a lot of testers from the SIS? Was it just me?
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.
Why don't you ask your mentor about this competition? He/She would know better about this competition's difficulty after actually seeing it.
I struggled too. A is too hard for div1A
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?
include<bits/stdc++.h>
using namespace std; typedef long long int ll; int main() { int t; cin>>t; while(t--){ int n; cin>>n; ll ans=0; for(int i=1;i<=n;i++) { if(i*3<=n) ans+=3+2; else if(i*2<=n) ans+=2+1; else ans+=1; } cout<<ans<<endl; } return 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
Because there are $$$t \leq 10^4$$$ testcases and that with $$$n \leq 10^8$$$ multiplies to up to $$$10^{12}$$$.
there are 10^4 testcases, so your code performs around 1e4 * 1e8 = 1e12 operations...
Can somebody help me out on this.. this is showing WA on 10397th token ... Currently not able to figure out my mistake..
My submission
Take a look at Ticket 16146 from CF Stress for a counter example.
Thanks a lot <3.....
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?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).
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.
Number 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.
Dang, that's a nice way of thinking about it. Better than the nonexistent editorial lol
amogus
E is easier than D
Can anyone post a solution for E?
You can check out the official text editorial or this video editorial at 29:25.
Found a interesting solution to A
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)Auto comment: topic has been updated by FairyWinx (previous revision, new revision, compare).
thanks for the round :DDD i had a lot of fun upsolving
rubbish main test on problem F.
I see some accepted submissions failing on certain inputs for problem B. For example, the solution 170686656 fails for
The output is
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.
N has to be divisible by K. It's mentioned in the problem statement
Okay. I overlooked it and missed so many details.
Problem D video editorial with code!
This was a wonderful contest and i learnt a lot from it.
Thanks for this round which makes my pupil dream comes true.