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 | NetSpeed1 |
| F | triple__a |
div2 round witih more div1 testers. not good.
As a not tester and not participant and shin chan supremacist, gimme downvotes.
Contest with short statements. I hope we'll enjoy.
Div.2 round with "3250" point's problem, quite interesting.
Ha felt like forever since the last contest.
Excited to take part in this contest.
No 'As a tester' comment, interesting
surprising
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 for all of us
Looking forward to be sad like him
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..
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 contest for 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
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.
15 4 1 21 abs(21-15)=6, abs(4-1) =3
gcd(3,6)=3
)
here you can refer my code
Where can I get the solution please
Editorial is uploaded- https://codeforces.me/blog/entry/115892
do you mind sending me code for A,B,C? can you do that or that will violent the rules?
how to solve E?
Let's say there is an edge from $$$x$$$ to $$$y$$$ iff $$$a[i][x] \lt 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.me/gym/102035/problem/I
Solution 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); }
int ans=-1; int cnt=0; for(auto x:v)if(x!=-1)cnt=1; if(cnt==0) { ans=0; cout<<ans<<endl; } else if(cnt!=0) { vector<int>v1; for(auto x:v)if(x!=-1)v1.push_back(x); int ans=v1[0]; for(int i=1;i<v1.size();i++)ans=__gcd(ans,v[i]); cout<<ans<<endl; } }}
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.
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
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.
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 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.me/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.me/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.
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 Explanation
https://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.$$$2.500.000$$$ numbers in input is a lot. Use fast input of chars with symbolic reading (google C++ getchar unlocked).
Reduce size of 2D array
rin $$$2$$$ times. Since $$$r_{ij} \le 500$$$, you can useuint16_t. It will allow you to hit L1, L2 and L3 cache better.Use 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 \lt j\right)$$$ and placed them nearly. Instead of it, you can transpose array
rand 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.Allow GCC to use SIMD instructions. Enable
Ofast,unroll-loops,avx,avx2andfmaand use keyword__restrictfor pointing that memory for arrays are not overlapped.Accepted 1872 ms submission
Optimization 5 for getting 1200 ms
The problem C is copied from https://codeforces.me/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.
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
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:
11000001 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.me/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.me/problemset/gymProblem/102035/I
Can D be done using ternary search https://codeforces.me/contest/1826/submission/204648453 Or binary search https://codeforces.me/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