Hi, Codeforces!

I am glad to invite you to take part in Codeforces Round #870 (Div. 2), which will take place on May/05/2023 17:35 (Moscow time). The round will be **rated for the participants with rating lower than 2100**. Participants from the first division are also welcomed to take part out of competition.

You will be given **2 hours** to solve **6 problems**. All the problems were authored and prepared by me. One of the problems is interactive, please read the guide of interactive problems before the contest.

I would also like to thank:

- Akulyat for excellent coordination and help improving the problems!
- arzhantsev64, InversionSpaces, Aleks5d, PO3OBAR_Bblnb, DanWallgun, Dominater069, AlperenT, Sert, sdl, Daryusz, fishy15 for testing the round and giving valuable feedback.
- Special thanks to Sert for finding a crucial bug in one of the problems!
- MikeMirzayanov for great Codeforces and Polygon platforms!

Scoring: $$$500-1000-1500-2000-2750-3250$$$.

Don't forget to read ALL the problems. I wish you good luck and high ratings!

I tried my best to create some good problems and clear short statements, so I hope you'll enjoy the round and find a problem you like :)

**UPD**: Editorial

**UPD:** Winners and First-to-solve

Div1 + Div2

Place | Participant |
---|---|

1 | A_G |

2 | Rubikun |

3 | kotatsugame |

4 | 244mhq |

5 | risujiroh |

Div2

Place | Participant |
---|---|

1 | Perfectt |

2 | Hovery |

3 | UmajiHidakata |

4 | ivatopuria |

5 | wrihapcod |

First-to-solve

Task | Participant |
---|---|

A | arvindf232 |

B | A_G |

C | ksun48 |

D | kaiboy |

E | wsyear |

F | triple__a |

div2 round witih more div1 testers. not good.

As a not tester and not participant and shin chan supremacist, gimme downvotes.

i confirm, this is indeed a fact

Contest with short statements. I hope we'll enjoy.

Looking forward towards a positive delta! Wish Every body good luck.

Div.2 round with "3250" point's problem, quite interesting.

As a participant, I will appreciate the work of authors and testers. Thank you for the contest!

I hope being able to write short code for short statements , cuz short statement do not mean short code or being easy. However short statements is always good , good luck to everyone ! Thanks for authors )

Ha felt like forever since the last contest.

Excited to take part in this contest.

Short statements -----> Good contest o(*^ w ^*)o

Good luck everyone!

hope that i find some notes bcz i usually cant understand any problem in div2(●◡●)

The author asked us to read all problems. we will do. Good luck everyone!

No tester comment? Bad round.

No 'As a tester' comment, interesting

surprising

!Good round

okwedook Orz

hoping for easy A this time ;)

Don't hope for easy A. Hope for surviving hard A's. Hope for becoming strong.

buddy if there will no easy A then the number of people participating in contest will be less (people just leave just by seeing A)eventually affecting the ranking

Yeah. That's also a valid point. But I don't care tbh.

Welcome to pupils mate

I was planning for that. Now I will be rated for tomorrow's contest. Hahaha. I will see you guys on Div4. I will try to solve all problems within 1 hour 30 min.

Well, all I can say is best of luck tomorrow :)

Hmm. Same to you brother.

jinxed lol, A was too hard

At least I solved it and learned from it. that's what matters to me.

I survived it lol.

Good Luck or everyone

thanks for this "....to create some good problems and clear short statements"

Wish i could do will in this Round

All the best for all participants

Good luck for all of us

Let's See How It Goes

Looking forward to be sad like him

Again hard 'A' :(

Div √2

lol

Thanks for the toughest contest I have ever seen.

That definitely not the toughest. But yeah it was on the harder side for sure.

Yeah 10 WA on A and for sure it is not a tough contest.

I have seen harder A's than this. You just started in mid 2022. I am here since 2020. There was a contest in 2020, I don't remember both A and B were the 1500s and non-trival.

Who said it was not tough? Maybe your English is broken. Read my comment again sir.

I don't have much to fix anything broken but you might need as you missed the line where I mentioned "I have ever seen." So please save your time and stop replying anymore you LOSER..

In B, if 'x' can be infinitely large print 0. anything divided by infinity will give remainder 0. So why can't infinity be answer for each case?

let's suppose infinity be 9999999999999999999, then also 1 % infinity = 1, and not zero.

Yeah True! Trust Noone Even the contest.

Hardest A, A took me longer than B and C combined.

+1

Problem E — F ratings are different from the blog post. Neither that it matters to me. xD ... cos I solved none of it.

Toughest A or Easiest C?

Weirdest contestfor me.C and D are like leetcode mediums

exactly, Leetcode standard DP problem.

Umm, which problem are you referring to ? is it about problem D? How exaclty dp works here, please explain!

refer this

Great solution bro, i really didn't ever think of this problem this way, like when taken == 0 we add current_index and when taken == 2 we subtract current_index beacuse (a_l + l) + a_mid + (a_r — r) , so yeah after coming to the equation above the problem looks quite simple.

how to do B ?

if it is already palindrome then answer will be 0 because you can take mod with any infinite value and thus answer will be zero in this case.

Now check the pairs from start and end and store the absolute difference of these numbers in a vector or array. now print the GCD of all the values. Because gcd will give the same modulus to all pairs.

Spoiler15 4 1 21 abs(21-15)=6, abs(4-1) =3

gcd(3,6)=3

)

here you can refer my code

Codecool thanks

a ≡ b mod x if (a — b ) = multiply of x so for every i from 0 to n / 2 the value of x is a factor of arr[i] — arr[ n — i + 1 ] now you need a common factor between all (arr[i] — arr[ n — i + 1 ] ) values so take gcd

Where can I get the solution please

Editorial is uploaded- https://codeforces.com/blog/entry/115892

do you mind sending me code for A,B,C? can you do that or that will violent the rules?

The submission code is all public in fact. Just click on other's submission.

how to solve E?

Let's say there is an edge from $$$x$$$ to $$$y$$$ iff $$$a[i][x] < a[i][y]$$$ for all $$$1 \leq i \leq m$$$

Building the graph can take $$$O(mn^2)$$$ time, but we can optimize it with bitset $$$O(\frac{mn^2}{64})$$$.

The graph we have is DAG, so you can do dp.

Can you explain a bit more about how are you going to use bitset to optimize it?

For each show, sort the models by their ratings.

Now for each model $$$v$$$, we know all models $$$u$$$ (which form some prefix and can be kept in bitset) for whom there is no edge from $$$v$$$ to $$$u$$$. Delete those models from your adjacency list.

Mine gets OOM when allocating bitset<5001>[501][5001]. I guess we need sqrt-decomp here?

You dont need to store bitset of all shows, you can create bitset<5001> [5001] for each show separately

ooooooops! I think you are right. bitset<5001> [5001] is enough and I can do city-by-city.

RIP my rating. That first problem was brutal and then I struggled on the second after :(

1826B - Lunatic Never Content copied from https://codeforces.com/gym/102035/problem/I

SpoilerSolution of this problem : https://blog.csdn.net/qq_40306845/article/details/86136563

How to optimize in Problem E

use bitset

Could you please explain further?

You sort the ratings of each city, for each city you start with a bitset full of zeroes, then you go from right to left updating the bitset and the adjacency list of the model you currently are updates g[model] &= city

## include <bits/stdc++.h>

using namespace std;

## define int long long int

int32_t main() { int t; cin>>t; while(t--) { int n; cin>>n; int a[n]; for(int i=0;i<n;i++)cin>>a[i]; vectorv; for(int i=0;i<((n+1)/2);i++) { int k= abs(a[i]-a[n-i-1]); if(k==0)v.push_back(-1); else v.push_back(k); }

}

I am getting WA at 4 testcase please help me asap

So apparently every single one of the testers saw A and solved it and though that it's a good idea to put something like that in the contest?

A looks cool isnt it?

Honestly, it's absolutely disgusting :/

Pupil Logic.

You literally dropped to pupil 2 days ago bro, what are you on about xD

wait for today will become cyan again(i am quite confident).

Oh well in that case you're a big boy !

The more experienced you become, the better you realize no problem is bad, it's you who is not capable enough to tackle it.

And yes no problem is disgusting sir. You are seriously denying all the efforts the author has put into making that problem. Believe me, I am working as a problem setter intern and it's not a cup of cake to come up with unique ideas, write test cases, handle exceptions, and handle wrong code. Authors should be praised more. At least they deserve constructive criticism.

Thank you senpai

actually, A was a different task when i tested, and probably a harder one.

I feel both are fine for div2A though....

Difficulty jump from D to E is too much. Up till task D it feels like div 3

I think it's quite balanced for div2

Brutal Div2A

Any hints for C and D

A lot of testcases with big n, m should hint to you to think of a math solution. if m == 1, we can just print("YES"), otherwise,

Notice that if n can divide any number from 2 to m, the worst strategy is to always choose the number of boxes that divide n, that way it will repeat forever. If not, you can never choose suitable boxes as they will all not divide with n.

Therefore, we can just check if the prime divisors of n are all > m, if so, we print "YES" else print "NO"

For C, do casework for m and n.

For D, try to write the answer function in a different way.

Is D can be solved using ternary search ?

Isnt it f(len) = max1+max2+max3+len for all length a convex function

I tried during contest but couldnt do. Can somebody let me know whether i am correct or not

I think it's max1+max2+max3**-**len. Not plus the length.

Ya thats what I meant , but later i realized it is not necesarily convex

C: how to make a tie? when it's possile to tie?

D: Look from middle to both left/right sides.

great contest! thanks

Codeforces Round 657 vibes

Can someone tell where can I find some similar problem to practice :(

Codeforces problemset section

F is an absolute joke. Just query y=0, x=0, y=240x

Very cool problem

And just after that you got TLE on the same test. Really cool.

Problem A is very hard for me and i can't even solve A in the contest...

What is the proof of C ?

Refer to my comment above

can anyone please give hints for problem E.

C is more easier than A,,,Hardest A ever...

Was D a dp problem ?

Hope to become specialist this time.Well it's less complicated than DP.

Hint: look from middle.

Yes it is dp problem.

Till index i, suppose u have taken 2 values, what is the best you can do, => dp[i][2]

and suppose till index i, u have taken one value, what is the best you can do => dp[i][1]

fill in the DP from above state.

I solved i5 using DP, let dp[i][j] be the max sum that can be made using the first i light where we have picked j lights till now. j can be 1,2 or 3. Code

As a newbie, I started doubting myself when I was unable to solve A, but looks like it is really a tough problem. Now waiting for someone to post it's solution.

Enumerate possible answers and verify them one by one.

Bonus: you can do better than pure brutal-force. Although it's not needed given the data scale.

We can brute force on the number of liars. lets call this number x. We go from x = 0 to n

So lets check, is 0 liars possible? 1 liar possible? is 2 liars possible? and so on. We run through the array, checking if arr[i] > x, that person is lying for that value of x, because they are saying that there are at least arr[i] liars. We increase the liar count

Now, if the liar count == our projected value of liars x, we print x. Otherwise, we cannot determine the liars, so we print -1.

https://codeforces.com/contest/1826/submission/204635985

thanks for such a simple solution. I often do this mistake of over optimizing the first problems of contests instead of trying out bruteforce :(

I kinda made that mistake as well, I kept trying to see a pattern and how to best determine the number of liars and so on.

This is a good learning point for me as well, because next time if I cannot think of the optimal solution for A I will just bruteforce it if the constraints are good

Yea this A was a complete shitshow. Since it's been solved by less than 5000 people, I think this problem A takes the reward for the hardest A since America was discovered.

after spending more than hour and 3 Wa the solution is very easy , you can just brute force all possible number of liars from i = 0 to i = n and count every one who said that there is a bigger number of liars as a liar(cnt++) if the counter of liars == i then thats your answer

Problem B is from past contests.

Problem Link: https://codeforces.com/gym/102035/problem/I

Did anyone have the same problem as me in C? I figured it out pretty quickly and tried using a sieve to implement it. Kept on getting TLE on 4. preset tho...

I looked at your submission and you found primes up to $$$10^6$$$ when you only need to find primes up to $$$10^3$$$.

This is because you only need to find the lowest prime factor, and the lowest prime factor of a number $$$n$$$ is at most $$$\sqrt{n}$$$

As a result, in the worst case, you need to check every single prime up to $$$10^6$$$ for each test case. And there are roughly $$$8\times 10^4$$$ primes that you need to check in that case. Given that there are $$$10^5$$$ testcases, this is far too slow.

but i got WA while i found primes upto 1000 and got AC upto 1010 why this happened can you explain or i made mistake somewhere ?

Yay, Pupil!!!

For me, A was quite impossible, I think I had a decent idea, but couldn't implement it. Spent at least forty-five minutes attempting it just to get nowhere. Similar to the last contest, A was really difficult to understand resulting in A being difficult for me and I ended up spending >15 minutes re-reading it over and over. Although, both B and C were far easier, all A, B, and C seemed to be fairly tricky.

Anyways, thanks for the contest, the problems were really enjoyable. I need to think about A more!

congrats :)

A: Brute force for all possible numbers of liars from 0 to n.

B: To make a[1]%x==a[n]%x we must have x is a divisor of abs(a[1]-a[n]). So the answer is the gcd of abs(a[i]-a[n+1-i]) for 1<=i<=n/2.

C: If m is a divisor of n, m can remain the same after voting, otherwise m must be decreased. So if m < the minimal prime factor of n, m will be decreased to 1.

D: Let the indexes of sights we pick are i, j, k from left to right, then definately we will let L=i, R=k. So we just need to find the minimum of b[i]+b[j]+b[k]-(k-i)=(b[i]+i) + (b[k]-k) + b[j], where i<j<k. We can do this by pre-calculating the prefix-maximum of (b[i]+i) and the suffix-maximum of (b[k]-k).

E: If model u can be ordered before model v, for all i we have r[i][u]<r[i][v]. So we can build a DAG (directed acyclic graph) in O(m*n^2), and we can solve the problem by toposort and dp. Naive approach will get TLE and we can optimize this solution to O(m*n^2/w) by bitset, which could pass the pretest (and hopefully system test).

PS: Is there any O(m*n) solution of E? I think there must be something faster than O(m*n^2) but I can't come up with it.

What I tried was, first sort all people by the first city. Now we have permutation [0,1,...N]. I sort this permutation by every city, while ensuring that inversions are always created and never destroyed. This is because for some person X > person Y, this should hold in every city. So inversion created in any one city always stays. After sorting by every city we can simply take LIS. But I didn't get AC

I mis-implement the biset so it OOM for me... rather than solve the OOM issue, I chose to sqrt-decomp it but failed to finish before deadline. With sqrt-decomp it should get O(mnlogn, n^2, m*n*sqrt(n))~=O(m*n*sqrt(n)).

It may seem obvious, but in problem A you can get non-brut force solution if you sort all numbers in non-ascending order and without loss of generality assume that liars told the first k numbers, and try to find maximum possible k.

Problem B was exanctly this problem

Is there any solution for problem E that is faster than O(n^2*m/w), like O(mn+n^2) ? I tried to find a O(m*n) solution to compute all pairs of i,j that j can go after i, but failed.

B was google-able, solved it after finding this which is the first link when you google "largest number that gives same modulo for 2 numbers"

Or just google- "a mod m = b mod m". https://stackoverflow.com/questions/27387033/given-a-and-b-find-m-such-that-a-mod-m-b-mod-m

870A — Trust Nobody with Explanationhttps://codeforcer.blogspot.com/2023/05/trust-nobody-870a-solution-in-cpp.html

I hate E

You can solve problem 1826E - Walk the Runway in $$$O\left(n^2 \times m\right)$$$ in C++ without bitsets. Based on naive $$$O\left(n^2 \times m\right)$$$ approach, you need to apply next optimizations one-by-one for getting

`1872 ms`

.Optimization 1$$$2.500.000$$$ numbers in input is a lot. Use fast input of chars with symbolic reading (google C++ getchar unlocked).

Optimization 2Reduce size of 2D array

`r`

in $$$2$$$ times. Since $$$r_{ij} \le 500$$$, you can use`uint16_t`

. It will allow you to hit L1, L2 and L3 cache better.Optimization 3Use cache-friendly order of data access. In original naive approach you need to compare $$$r_{1i} \lt r_{1j}, r_{2i} \lt r_{2j}, ..., r_{ni} \lt r_{nj}$$$, if you will decide to pick two persons $$$ij\text{ }\left(i < j\right)$$$ and placed them nearly. Instead of it, you can transpose array

`r`

and compare $$$r_{i1} \lt r_{j1}, r_{i2} \lt r_{j2}, ..., r_{in} \lt r_{jn}$$$. Now, all of the elements will be placed in memory one-by-one and memory access will be cache-friendly.Optimization 4Allow GCC to use SIMD instructions. Enable

`Ofast`

,`unroll-loops`

,`avx`

,`avx2`

and`fma`

and use keyword`__restrict`

for pointing that memory for arrays are not overlapped.Accepted 1872 ms submission

Optimization 5 for getting 1200 ms

good luck whoever is participating.

The problem C is copied from https://codeforces.com/gym/433264/problem/F

really？ OAO

Yes, I did the problem last month.

Can you please take a screenshot or something? cuz I am not in that group.

can problem B be solved using binary search ?

can anyone tell what is wrong in my solution for problem b

as we have to find max x the value of mod will always be between min and max of the array and if we take x greater than the Max element of the array then it will return same array itself so our domain of x is restricted to min and max of the array and now we can apply binary search and the checker function will check if the array that we have formed is pallindrome or not

but

3

100 1 1000000000

this Tc is giving wrong output

can anybody tell what is wrong in my logic part ?

https://codeforces.com/contest/1826/submission/204660439

I'm stupid and had to do a bunch of random tests for B to find out the set of possible answers for a mod x = b mod x are the factors of abs(a-b). From there, I didn't realize that it's literally just equivalent to GCD XD

Got TLE 8 on that sadge

same

It says it's rated but when I open my account it's viewed as unrated what's going on? (this is my first contest in a long time so idk how these work.)

For E), I had the following DP recurrence:

and I think it runs in

Never would have thought to use bitsets though, I was trying to optimize it to either

because it looked suspiciously similar to longest increasing sequence.

10134 — 6367 = 3767 participants (37.2%) can't solve a single problem!

In problem D, I made this 204647760 during the contest and after about 20 minutes I realized that it can be hacked with a test case like this:

`1`

`100000`

`1 1 2 3 4 5 6 7 .....`

The reason is that I use -1 to check if I visited a state in dp or not and the above test produces -1 a lot which mean the dp will recompute states which was computed before, so I made another submission to avoid this mistake.

But after the contest, I submitted the first solution again and it passed the tests of the problem with about 46 ms , I think that this test should be added to main tests!

I liked the contest, it was nice. But E is so bad

My E solution with bitset took 2800 ms :(

I found a tricky way to exclude those pairs without ordering fast: if a[i]<b[i] for evety i, then sum(a)<sum(b), min(a)<min(b), max(a)<max(b). Problem E, a 592 ms solution without using bitsets.

Problem B was written in GYM before:

B- https://codeforces.com/problemset/gymProblem/102035/I

Good job bro !

Ratings updated preliminary, it will be recalculated after removing the cheaters.

Problem B was written in GYM before:

B- https://codeforces.com/problemset/gymProblem/102035/I

problem A so bad statement

Can D be done using ternary search https://codeforces.com/contest/1826/submission/204648453 Or binary search https://codeforces.com/contest/1826/submission/204631760

good contest, problems were quite interesting, i am able to prove my solutions of a b and c!

Problem A.. Uff..

Has anyone come up with a dp solution for problem d？

My code can pass the example on my computer but failed when testing. Can somebody help me ? My code

I can't solve some problem during contest, but after contest I had solve.

All problems are Good. I loved it.