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!
Contest with short statements are always good.So,I hope we'll enjoy this div 4 and wish for the positive results.
The round was amazing. I especially liked problem F with a graph.
Enough?
As a tester, I recommend listening to Taylor Swift while participating in this round.
based
Nah , hamo el tekha wins
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
Gheez, smooth round..nice problemset but I think F was way easier than E
excited for it
so trash contest xD
Damn excited for this round. Hope I will become master after this round
You can only participate unofficially.
That was the joke
r/whoosh
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
in queue
I am very excited for another Division 4 Round; hoping to stay as a stable Pupil!
Good luck to all other participants and thanks for making the round!
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
Thanks to everyone
Just +20 to get to pupil. Hope i will do it tomorrow
for me just 48.I wish you all the best
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.
Good Luck for everyone I hope to be pupil
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.
Hope I would get a +ve Delta and become the pupil in this round.
As usual I liked the cat in Vladosiya's profile.(´◡`)
thank you very much!!
Finally div 4...
Thanks
Are you ready for it?
HELL YEAH FIXIOEKEK
I am a beginner. How difficult is Div4?
Give a glance to the previous div.4 contests.
That type of contest is the best for you at the moment. Cuz you feel more confident and find some extra power to continue).
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?
Hope everybody solve all problems!
After the total disaster of yesterday div2 contest, I hope to do better today. But I am not sure I Will have time...
The legand says that i am in queue from the last div 4
As a participant, hope to reach cyan.
I also hope to reach cyan again!
There was no queue today..thanks
Let's hope to get +13 today. I am really bored of the gray color
half hrs left i'm feeling nervous :)
Hope to surpass 700 rating mark today, still lot of ground to cover !!
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!!
MikeMirzayanov Orz.Awesome job done by Codeforces handling this much much load so smoothly.
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.
Nice problems. i liked G and H more
Solution of Blank Space — 871B Question with code and explanation of it
https://codeforcer.blogspot.com/2023/05/bla.html
Solution of Mr. Perfectly Fine — 871C Question with code and explanation of it
https://codeforcer.blogspot.com/2023/05/perfectly%20fine.html
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 think you have to create array with 2/3n and 1/3n and check if it's match m, but haven't solve it by myself
I also used queue. Maybe you have some other issues.
https://codeforces.com/contest/1829/submission/204858374
what would be the difference compared to your code using queue?
dont use fill for a large value.
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?
https://codeforces.com/contest/1829/submission/204886257
Seems like there is no need for tracking whether visited or not. Thank you for the helpful feedback!
u can use brute force to solve m*(3^x)*(1.5^y)=n
Instead of using
visitedarray fort1andt2, try once withcur.(i.e., After polling an element from the queue, if that element is already visited, skip to next turn. Otherwise visit the element.)
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.
Hey, thanks vgtcross! But I already did solve it right after you said those two were different constraints I have to think about. That helped me immediately notice that the only possible edge case I have to think about is that the center node and the intermediate nodes can have an equal count of degrees. But thanks all the same...you've been helpful.
can anyone help me with prove the complexity of my code on D? thanks: https://codeforces.com/contest/1829/submission/204812242
Nice contest !!
I am very glad that my idea (see https://codeforces.com/blog/entry/114062#comment-1014185) worked and there was no queue today!
very great sir
Yes, Thank You
Any tips on how to avoid
Runtime erroron problems likeProblem E: The Lakes?maybe you too took m as n.
Stack frames + the visited array are using too much memory, probably. Since it worked without the visited array.
Great Contest.
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?
yeah... but only after the contest though cause i didn't read the announcement beforehand :'), sorry...
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.
Yup, that's what I meant. Thanks :)
Can somebody explain me why this solution got TLE?
https://codeforces.com/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"
so glad that we finally have the first div.4 contest that runs smoothly
This was a really nice contest! I particularly enjoyed G and H. (D was also nice.)
I bashed E with DSU ;)
I did with dfs :)
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....)
The best round ever, i like the problems of dfs and bfs, Thank you.
I've TLE in G because of not answering each query in O(1), when handling it with a "calm mind" after the round it passed so sad :( (
Finally, solved all.
How to solve H for 1 <= a[i] <= 1e9 ?
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.
Can someone explain G in more detail or how the code is working? Thanks!!
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.
this is so iconic
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 - Вечная зима) ^_^
Congrats !!
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.com/contest/1829/submission/204766645
H: https://codeforces.com/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.com/contest/1829/submission/204906135 https://codeforces.com/contest/1829/submission/204781971
I have viewed the hack log and wonder why some people wrote these code that looks like a backdoor.
I also. I think its planned...
When will I gain a rate?
This contest was also unrated for me even though it should have been rated?
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
Can anyone tell me why I got -40 even though I solved A and B ?
hey when will the rating get updated??
Are you blind?
What happened? Did E get canceled?
After how much time the rating was updated
Failed system test on D :( My submission
First time, solve 6 problems, thanks and appreciate, T.T
This was my second contest, My rating after first contest(which was of div2) was 548. Still this round was unrated for me, why? Can anyone plz tell me, I am new to this site.
same happened with me too....however this was my first on codeforces
Have patience, rating will be updated soon!
Me when I solve A and B: :DDDDDDDDDDDDDDDDDDD
Me when I'm stuck on C: ;(((((((((((((((( ;(((((((((
Keep doing good work guys. We are grateful for those contest <3
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!
As a tester, this is surprisingly not that bad for a Div. 4
https://randomgenerate.io/
Why am I not rated？
nice contest
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
I think this round is good.
Problems in this contest are good. I enjoyed.
superb problems
I and kissan share same snippet template as we are friends and he teached me about competitive programming and question A the logic of is basic and simple and we have same logic for this question. This was unintentional and a coincidence. I request you to please remove plagiarism from this 204763906. And you can check rest submissions are unidentical. mesanu , flamestorm , SlavicG
Hello!
Today, just 5 minutes ago I received the following message Attention!
Your solution 204781248 for the problem 1829D significantly coincides with solutions Charizard2021/204781248, abhi.kr.2100/204797637. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
This is from the most recent Div 4 and it is problem D, and I do not know who this person is. My code is quite simple. The last line where I am printing YES or NO, is a new thing that I just learned. I have never used it before since one line printing is new to me. The other parts of the code is simple logic that is used in the editorial as well. I am unsure why I am flagged in this case, this must be a coincidence. The logic is very simple and the editorial uses the exact same idea. I wanted to make my code look concise, that's why in the recursion there is the ||. I am sure many people used the same method. None of the other submissions match with this person either. mesanu flamestorm SlavicG MikeMirzayanov
Thanks!
Nice probelems
Hmm does anyone know why this fails on test case 6 for problem E? Cannot seem to figure it out. Seems quite straightforward but am I missing something?
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