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!

Click for positive deltaAs a tester, I recommend listening to Taylor Swift while participating in this round.

based

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

FactThink 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

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.

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:

How to solve D? used BFS for each N, but got TLE.

I also used queue. Maybe you have some other issues.

https://mirror.codeforces.com/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:y<=15) and find if any integer x satisfies the equation.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:

SpoilerCan 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://mirror.codeforces.com/contest/1829/submission/204812242

I am very glad that my idea (see https://mirror.codeforces.com/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 ithttps://codeforcer.blogspot.com/2023/05/love%20story.html

why do we need tutorial of A? Everyone can do it with ease.

You are very talentedbtw, 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://mirror.codeforces.com/contest/1829/submission/204844540

You cannot clear the $$$1000 \times 1000$$$ arrays

`matr`

or`vis`

completely 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 though`memset`

is 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

`matr`

and`vis`

to $$$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://mirror.codeforces.com/contest/1829/submission/204766645

H: https://mirror.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 lifeThank 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 1The 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 acceptedThat 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

a good day to be a swiftie on codeforces

https://mirror.codeforces.com/contest/1829/submission/204906135 https://mirror.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.

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

Spoiler## 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