Hey, hi Codeforces!
It's mesanu, flamestorm and me and we are very excited to invite you to Codeforces Round 871 (Div. 4)! It starts on May/06/2023 17:35 (Moscow time).
We worked swiftly to tailor the problems for this contest, so we hope you will enjoy them! We tried to make the statements short, epic and concise.
The format of the event will be identical to Div. 3 rounds:
- 5-8 tasks;
- ICPC rules with a penalty of 10 minutes for an incorrect submission;
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
- by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).
We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.
Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them),
- do not have a point of 1400 or higher in the rating.
Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.
Many thanks to all testers: RedstoneGamer22, tibinyte, sandry24, jampm, haochenkang, qwexd, Vladosiya, _Vanilla_, Phantom_Performer, ScarletS, NintsiChkhaidze, keta_tsimakuridze, Dominater069, Gheal, Bakry!
And thanks to Vladosiya for russian statement translations!
We suggest reading all of the problems and hope you will find them interesting!
Good Luck and have fun!!
Are you ready for it?
UPD: Editorial is out!
As a tester, problems are great!
As a tester, I recommend listening to Taylor Swift while participating in this round.
based
we are proud of you ya king :)
which song you recommend ?
I recommend listening to Forever Winter.
I think the problem titles have already answered your question :))
Can confirm, this piece of advice works.
queue
Think 5 mins
code 10 min
in queue 20 mins
WA on pretest 2
ffgfgffees
Gheez, smooth round..nice problemset but I think F was way easier than E
so trash contest xD
Damn excited for this round. Hope I will become master after this round
You can only participate unofficially.
google what is joke. Lol
Yup same here.
As a tester, I won't make clickbaiting claims and I won't beg for upvotes.
Yes Sir.
Ya slavicG div4 contest
New specialist (including me and 69 others) in div4 comments section,,,
I am really excited to participate in a Div4 contest on my birthday, and also hoping for positive delta!
Happy Birthday Enigma06
Happy Birthday Enigma06
Happy Birthday Sir. Keep grinding
Just +20 to get to pupil. Hope i will do it tomorrow
Seems like i will made pupil. delta prediction is +66 and i just need +20. I think this time it is great. I was able to solve 6/8 problem in less than 1h25min but G i had TL and solved it just at the end of contest unfortunately.
congratulations sir.
Thank you. You have also made specialist great job.
As a tester, this is surprisingly not that bad for a Div. 4
As a tester, I'm not sure I agree
I am seeing the same meme for the past 3 years on Codeforces. At least post something else.
Praying for +14 delta
Praying for +9 delta
Praying for +14 delta
Praying for +105 delta
It's my first "out of competition" contest after a great success on round #870 lol.
As usual I liked the cat in Vladosiya's profile.(´◡`)
Thanks
Are you ready for it?
HELL YEAH FIXIOEKEK
We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.
This part is amazing!)
Although I am unrated, I still want to participate. Is there anyone else who feels the same as me?
Hello everyone! Have a great round and a good mood.
cant guarantee for 2nd :)
My mood is decided by the queue. Hoping for the smooth contest.
Queue Forces!!!!
Wait, where did you see a queue?
Sorry My bad!! Today's response time is awesome!!
Very fast loading and queue for div4! Pretty nice, Good Job Codeforces team!
nice Taylor Swift round.
based participant
what's meaning of "taylor swift round" ?
The contest names are songs of taylor swift, I just realised this.
Good contest, quit after solving 2 problems.
Good contest, quit after speedforcing first 6 problems and being too dumb for G and H.
Taylor Swift Round 871！
Have you noticed the references in the announcement?
Today's contest was really fun and interesting. Appreciate the problem setters :)
Very good problems, especially H. Thanks to the authors for a cool contest.
Single people after reading problem A:
Любительский разбор всех задач.
Создадим строку
s=codeforces. Прочитаем строкуtи сравним её сsпоэлементно. Посчитаем количество несовпадений и выведем его.Решение на C++
Решим задачу двумя указателями. Прочитаем все элементы массива. Теперь выставим $$$i$$$ в первый элемент, $$$j$$$ сделаем равным $$$i$$$ и пока $$$a_i = a_j$$$ и не вышли за пределы массива, двигаем $$$j$$$ вправо. Таким образом, мы нашли полуинтервал $$$[i,j)$$$, состоящий только из одинаковых элементов, равных $$$a_i$$$. Если $$$a_i = 0$$$, то обновляем ответ за счёт $$$j-i$$$. Затем ставим $$$i$$$ в позицию $$$j$$$ и повторяем процесс, пока $$$i$$$ не выйдет за пределы массива.
Классическая идея, но на соревновании важно оптимально её реализовать (без багов и быстро). Я всегда использую описанную выше реализацию с двумя циклами по $$$i$$$ и по $$$j$$$.
Решение на C++
Мы либо учим
10и01, либо сразу учим11. Давайте посчитаем минимум среди всех книг с битмасками01,10и11. Тогда ответ этоmin(min01 + min10, min11).Решение на C++
Давайте сразу поделим оба числа на их наибольший общий делитель и будем работать уже с изменёнными числами $$$s$$$ и $$$t$$$. Хотим $$$s$$$ превратить в $$$t$$$.
Каждое действие это:
Найдём, сколько раз $$$s$$$ и $$$t$$$ делятся на $$$2$$$ и на $$$3$$$. Для этого можно написать функцию и вызвать её $$$4$$$ раза. В самой функции будем делить число до тех пор пока делится.
Теперь мы знаем $$$s_2, s_3, t_2, t_3$$$ — сколько раз данное число делится на $$$2$$$ и на $$$3$$$.
Мы не сможем получить ответ, если в $$$s$$$ и $$$t$$$ есть какие-то другие простые множители (например, множитель $$$5$$$). Давайте проверим это. Если не выполняется:
То ответа нет. Проверить можно возведением в степень.
Теперь мы будем делить на $$$3$$$, поэтому должно выполняться $$$s_3 \ge t_3$$$. Также мы будем умножать на $$$2$$$, поэтому должно выполняться $$$s_2 \le t_2$$$. Также мы не можем умножить на $$$2$$$ больше раз, чем поделить на $$$3$$$, поэтому должно выполняться $$$t_2-s_2 \le s_3 - t_3$$$. Если всё-всё-всё выполняется, то ответ YES, иначе NO.
Решение на C++
Давайте рассмотрим эту задачу как задачу на графы. Вершины графа — наши клетки на сетке. Ребра графа — переходы вверх, вниз, влево и вправо. На таком графе нам нужно найти компоненты связности. Для каждой компоненты найти сумму чисел в ней. Среди всех компонент найти максимальную сумму и вывести её.
Найти компоненты связности можно при помощи поиска в глубину или в ширину. Сумму для каждой компоненты можно поддерживать, зная номер этой компоненты, и при переходе в ненулевую вершину увеличивать эту сумму, а максимум можно вычислить потом, когда будут посчитаны все значения.
Решение на C++
Давайте найдём центр дерева. Центр — это середина диаметра. Диаметр ищется так:
Итого, величина диаметра, это расстояние от $$$s$$$ до $$$t$$$, которое равно $$$4$$$, а центр — это такая вершина $$$u$$$, у которой
distFromS[u] == 2 && distFromT[u] == 2.Нашли центр. Теперь $$$x$$$ — это размер списка смежности вершины $$$u$$$, а $$$y$$$ — размер списка смежности любого соседа вершины $$$u$$$, вычесть $$$1$$$ (вычитаем ребро в саму вершину $$$u$$$).
Решение на C++
Повернём треугольник на 45 градусов, получим что-то вроде такого (возведения в квадрат опущены):
Теперь надо считать сумму в прямоугольнике с правым нижним углом в $$$n$$$, а левым верхним в $$$1$$$. С этим и будем работать.
Оценим число строк и столбцов в нашей матрице. Если мы возьмём её фрагмент из $$$2000$$$ строк и $$$2000$$$ столбцов, то будет примерно $$$2$$$ миллиона элементов, и этого достаточно, чтобы удовлетворить ограничениям, итак, решить можно следующим образом:
Создаём матрицу $$$2000 \times 2000$$$, заполняя её змейкой по диагоналям. Это можно сделать в двойном цикле
for: во внешнем перебираем номер диагонали $$$1, 2, 3, ...$$$ — это сумма $$$r$$$ и $$$c$$$, а во внутреннем перебираем $$$c$$$ — столбец. Зная номер диагонали и столбец, находим строку $$$r$$$ однозначно. При этом мы можем перебирать очень грубо и даже те клетки, которые выходят за пределы карты, просто проверим это. Если клетка лежит в пределах таблицы, то заполняем её новым значением.Можно воспользоваться двумерными префикс-суммами:
sum[r][c] = sum[r-1][c] + sum[r][c-1] - sum[r-1][c-1]— предподсчитываем сумму в каждом прямоугольнике.Можно пробежаться по матрице и для каждого числа запомнить его строку и столбец.
Теперь мы готовы отвечать на наш первый запрос и все остальные запросы. Читаем число, вспоминаем, в каком столбце и строке оно лежало, достаём предподсчитанную сумму и выводим её.
Решение на C++
Заметим, что ограничения на $$$a_i$$$ довольно маленькие: всего $$$64$$$ варианта. Также побитовое И варьируется от $$$0$$$ до $$$63$$$ включительно. Давайте посчитаем ответ динамикой
dp[n][bitwise_and]— сколько подпоследовательностей на префиксе длины $$$n$$$ имеют побитовое И, равноеbitwise_and. Не будем хранить пустую подпоследовательность в динамике, так как она одна такая.Инициализация динамики:
dp[0][0...63] = 0— на префиксе длины $$$0$$$ нет подпоследовательностей.Переход: пусть смотрим префикс длины $$$i$$$. Последний элемент на этом префиксе это $$$a_i$$$. Давайте либо добавим его во все подпоследовательности префикса $$$(i-1)$$$, либо не будем добавлять. Для этого переберём, какое побитовое И было у последовательности на предыдущем префиксе, и обновим за счёт значения $$$a_i$$$. Также не забудем, что мы могли взять подпоследовательность с одним $$$a_i$$$, то есть, к пустой подпоследовательности добавить $$$a_i$$$.
Итого:
dp[i][0...63] = dp[i-1][0...63]— не добавляемa[i];dp[i][was & a[i]] += dp[i-1][was]для всехwasот $$$0$$$ до $$$63$$$ — добавляемa[i];dp[i][a[i]] += 1— одна подпоследовательность, состоящая лишь изa[i].Решение
How to solve D? used BFS for each N, but got TLE.
I also used queue. Maybe you have some other issues.
https://codeforces.net/contest/1829/submission/204858374
what would be the difference compared to your code using queue?
why array? Use a boolean.
I used array for tracking if it is visited already or not, to avoid pushing same number into the queue. How can I use only boolean to do that?
u can use brute force to solve m*(3^x)*(1.5^y)=n
Short Editorial :
what would be the actual rating of G and H according to you? I guess something around 1500 for G and maybe 1800 H
Seems about right. G-1500, H-1750
In problem F, if the values of both x and y are greater than 1, values of n & m should at least be 7 & 6 respectively, right? But the problem statement says that n can be 2 and m can be 1 [2≤n≤200; 1≤m≤min(1000,n(n−1)2)]...essentially meaning x can be 1 and y can be 0! I'm a bit confused about how to handle such cases of input as my solution got WA.
For an input to be valid, all constraints have to be fulfilled. These are the two different constraints you're thinking about:
It doesn't matter that constraint 1 allows cases like $$$n = 2$$$ or $$$m = 1$$$ since these are impossible according to constraint 2. As I said, all constraints have to be met for an input to be valid. Thus, these cases can never appear and you don't need to consider them in your code.
UPD: The reason you got WA is because there is an edge case you missed. Here is one test case where your code fails:
Can you see why this happens?
Hint: The edge case scenario is described in the editorial.
can anyone help me with prove the complexity of my code on D? thanks: https://codeforces.net/contest/1829/submission/204812242
I am very glad that my idea (see https://codeforces.net/blog/entry/114062#comment-1014185) worked and there was no queue today!
very great sir
In F , according to the constraints , if m = 1 , then how x and y could be both greater than 1 such that x*(y+1) = m = 1 ??
Since inputs are always valid, $$$m$$$ cannot equal 1. Even though the constraint $$$1 \le m \le \min(1000 , \frac{n(n−1)}{2})$$$ allows it, no valid snowflake graph can have only 1 edge. The constraint "It is guaranteed that this graph is a snowflake graph for some integers x and y both greater than 1" "overrides" the fact that $$$m = 1$$$ is allowed by the previous constraint.
ah ok , seems right m can't be a prime number , this thing confused me during the contest:(
Solution of A.Love Story — 871A Question with code and explanation of it
https://codeforcer.blogspot.com/2023/05/love%20story.html
why do we need tutorial of A? Everyone can do it with ease.
You are very talented btw, it was not for you. so kindly ignore it. instead of talking for the solution you can talk about approach too. btw the way thanks for commenting out.
TAYLOR SWIFT REFFERENCES!? AFTER HER SPEAK NOW TAYLOR’S VERSION ANNOUCEMENT!? I CANNOT-
(sorry for all caps i’m just a big swifty :>)
Did you notice the references in the announcement?
Finally Solved my first dp question in live contest. Despite Div 4, happiness nd motivation bcz of DP is overflowing :)
how did you reach Specialist without knowing Dynamic programming?
note the word live contest, he never said its his first dp solve, he said its first dp solve in live contest.
This is because other contests unlike div4 wont give a problem which is just knowing dp, but you need to make other harder observations on top of them.
Can somebody explain me why this solution got TLE?
https://codeforces.net/contest/1829/submission/204844540
You cannot clear the $$$1000 \times 1000$$$ arrays
matrorviscompletely every time if there are $$$10\ 000$$$ test cases since this would require $$$1000 \cdot 1000 \cdot 10\ 000 = 10^{10}$$$ operations which is not fast enough. Even thoughmemsetis fast, it's only a constant factor improvement over manual clearing. You should just clear the arrays manually in the required sections for each test case.UPD: You should also increase your arrays
matrandvisto $$$1002 \times 1002$$$ from $$$1001 \times 1001$$$ so that you have the exrta "buffer layer" on every side of the used area. 204881319Overall a great round. Well-balanced Problem Set. Although standard ideas were involved, but liked Problems G and H especially. Good educational problems for DP I would say.
Ya I totally agree, the problems were like "INTRODUCTION TO TREE,GRAPH,DP,etc"
This was a really nice contest! I particularly enjoyed G and H. (D was also nice.)
I bashed E with DSU ;)
Good contest! It makes me know that small mistakes will lead to fatal errors.(In details,I misused variables in for-loops for consecutive 3 problems and wasted plenty of time to fix them....)
Finally, solved all.
Hint for G. Hits Different ?
Precalculate max(max_i), and min(min_i) values of each row(i). You can calculate Sum(i^2) from i=a to b in O(1). First find row where N is(R). Each row(R, R-1, ... 0) you can calculate start and end numbers of can that falls(Using previous rows start and end number + max_i and min_i). And add SUM(Start, end number) to the answer.
E was exactly same as https://leetcode.com/contest/biweekly-contest-103/problems/maximum-number-of-fish-in-a-grid/
If someone copies my code from here is there any chance that my solution can get skipped?
Also this question is from latest biweekly contest on leet code. How can there be soo similar question again on CF.
How would someone would copy your code from there except you? i don't think so your solution will be skipped, coz i also copied my code from old submission
Solutions are visible in contest leaderboard
its a very standard problem, and every tester told the same in testing, however apparently, having standard problems in div4 is fine.
and for having those standard problems, beginners can reinforce their newly learnt concepts and algorithms too! so i don't think it's a big deal after all in my opinion
yes, sure, just make those contests unrated then. In my opinion, rated contests should not be having standard problems.
CSES exists, other tons of archives exists. Beginners can solve standard problems from there. They should not be getting rating for copy pasting codes to standard problems.
if they know all standard problems than they aren't Beginners at all :3
Disagree, a person can know 1000 standard problems and still unable to solve a div2A because they have not seen it before.
This type of person is what this div4 round encourage :(
Maybe i am wrong, but most other div4 rounds dont have classical problems atleast in hardest slot, and as mentioned above, E is literally a leetcode problem.
well, with your perspective a lgm can consider a certain problem standard which might still be out of your knowledge, also most of the problem in div2 that they solve might be of some similar concept which they would have already seen in the past, so that doesn't mean the problems like that shouldn't be created just because they felt it quite reused and standard. Hope i was able to say my point clearly
I think there is a big difference in making a standard problem, and having a problem be standard to someone. Today's E and H are examples of the former.
I cant find any examples of the former in recent div2 rounds, even if they need standard knowledge, they are not just that. You need to make some observations after that. Perhaps you can enlighten me to some problems i missed which are completely standard in div2(in recent times and preferably one of the easier ones not F or smth)
As for the lgm point, yes there are definitely such problems which an lgm would find standard and i still cant solve. I dont see whats wrong with that. The lgm(hopefully) and me would oppose putting such problems in a div1 round.
yeahh, actually i agree with you on that. overall i do think the later problems in the contest are less dificult compared to the other div 4s. nevertheless, the problems are still interesting and the contest is one of my favorites so far!!! :>
Its not about the difficulty. A slightly easier contest is fine. One cannot always have the correct difficulty.
However, i think all rated rounds should have original problems. bad problems are better than unoriginal ones.
I am curious, was the theme determined after the announcement of her new album or are they unrelated?
The announcement of her new album was determined based on the theme.
But in all seriousness... it was a coincidence she announced it on the same day :D We had the theme set for quite some time before it.
The collaboration I never knew I needed.
This contest has given me a very big motivation ( and hopefully a very big rating :) ). Thank you for the creators of this contest, I really liked problems, especially the problem H.
The contest was great
Cool contest, last 3 problems were interesting and at a good difficulty level for myself.
First time I can solve a graph problem (1829F - Forever Winter) ^_^
Congrats!
i don't know what makes you think it wasn't a graph problem just because a constructive math solution exists
Yep, I just saw some dfs based solutions. It's a graph problem indeed.
Is it legal for two or more people to participate using the same account?
I think this account c0nf11c7 is being used by two or more people in this contest.
Here are the clues that lead me to believe this:
Some of the code has strange symbols, while other code does not.
This is unusual, as we usually use the same template during the contest.
There is only an 11-second gap between problem C and H, and the templates of them are different.
C: https://codeforces.net/contest/1829/submission/204766645
H: https://codeforces.net/contest/1829/submission/204767094
If this is indeed cheating, please take action as soon as possible.
MikeMirzayanov should look for this.
Best Contest of my life
Thank you all
if i hack some people i'll gain extra elo ?
Hello, CF why I it give me TLE here 204890621 I replace if (n%3!=0) by if(n/3*2!=n-n/3)
you are resetting your dp array everytime which made it $$$O(1e7 * t)$$$.
Try using map to memoize.
Thank you, but why it did not give TLE on test 1 And my friend do the same thing but vector v(max(n, m), 0) but he get accepted
why it did not give TLE on test 1
The code only TLE's if there are too many test cases. Test 1 has only 11 test cases and resetting the array 11 times is fast enough. Resetting it 1000 times is not fast enough.
And my friend do the same thing but vector v(max(n, m), 0) but he get accepted
That sounds like it shoudn't pass the time limit (or I'm just stupid). Can you send a link to your friend's code?
Or I am the stupid
hello everyone, first of all I am sorry for bad English. Can someone tell me about the best place where I can reed about theories in c++?
Highly recommend GeeksforGeeks
Video Solution Of All Problems.
Link : https://youtu.be/axLtBF-td3o
Nice contest, btw in case someone is interested: This is a similar problem to C
a good day to be a swiftie on codeforces
https://codeforces.net/contest/1829/submission/204906135 https://codeforces.net/contest/1829/submission/204781971
I have viewed the hack log and wonder why some people wrote these code that looks like a backdoor.
When will I gain a rate?
The rating updates several hours after the end of the systems tests. Just wait little bit more
Minutes or hours?
Usually a few hours after. In rare cases, rating may be updated several days after contest. Such as this one
Failed system test on D :( My submission
I am a newbie with ~600 rating, then why is this contest showing to be unrated in my contest section!
The ratings are not updated yet, so It is normal for the results in your contest section to appear as Unrated. Let's wait until the rating is updated!
Great problems! Problem F is really impressive!
Expected to cross newbie level with this contest, but fine, it was a great contest with interesting problems
Swifties round :)
Can anyone tell me why I got -40 even though I solved A and B ?
The contest was Div.4 — it means the problems were easier, and you had to solve more problems than usual to get expected performance in the contest.
In this contest, you got performance of
321, it's lower than your rating, so unfortunately you received a negative rating change for that.Better luck next time! You can install the Carrot Extension to see the predicted rating changes.
Got it..Thanks
Nice probelems
I tried solving G with DP, but it is even failing on the first test case:
pragma GCC optimize("Ofast,unroll-loops")
pragma GCC target("avx,avx2,fma")
include <bits/stdc++.h>
using namespace std;
typedef long long ll; const ll MAX = 1e6 + 2; ll dp[MAX], n, x;
void solve() { cin >> n; dp[1] = 1; x = 1; for (ll i = 2; i <= n; i++) { if (x * (x + 1) / 2 < i) x++; if (i == x * (x + 1) / 2) dp[i] = dp[x * (x — 1) / 2] + i * i; else if (i == x * (x + 1) / 2 + 1) dp[i] = dp[x * (x — 1) / 2 + 1] + i * i; else dp[i] = -dp[i — 2 * (x — 1)] + dp[i — x] + dp[i — x + 1] + i * i; } cout << dp[n] << "\n"; }
int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) solve(); }
P.S: I'm sorry about the bad format of the code, I don't know how to make it look good.
bump