Hello Codeforces! Me and yud08 are excited to invite you to take part in Codeforces Round 982 (Div. 2), which starts on Oct/26/2024 17:35 (Moscow time). You will be given 5 problems and 2 hours to solve them. Two problems are divided into two subtasks.
This round will be rated for all participants whose rating is strictly below 2100.
The problems were authored by me and yud08, and prepared by me.
We would like to thank:
- abc864197532 and Vladithur for an amazing double coordination.
- Alexdat2000 for translating the statements to Russian.
- BurnedChicken for LGM testing.
- BucketPotato, Fysty, alvingogo, and WiwiHo for red testing.
- sammyuri, anango, jay_jayjay, amsraman, Intellegent, valeriu, erekle, and golions for orange testing.
- Beacon, iceylemon157, and LittlePants for purple testing.
- Jasonwei08, godgenji, Banis, temmieowo and Arthas for blue testing.
- t0rtik, lumid, and AG-88301 for cyan testing.
- vatzahellmen for green testing.
- MikeMirzayanov for the Polygon and Codeforces platforms.
We hope you enjoy the problems!
Score Distribution: $$$500 - 1000 - 1250 - (1250 + 1000) - (2000 + 1000)$$$
We actually wanted to continue the trend of posting photos of contest writers, but we could only find one photo containing both of us, which was a group photo that we took with some other UK informatics people! (I'm the one in the back of the picture who is wearing the MHC T-shirt and yud08 is the one whose head is popping out from the left side of the photo.)
UPD1: Congratulations to the winners of the contests:
Div 1:
Div 2:
Also, first solves! (if any of these are wrong please let me know)
- A: A_G in 00:00:45
- B: A_G in 00:03:01
- C: Alex239 in 00:05:09
- D1: 74TrAkToR in 00:09:21
- D2: 74TrAkToR in 00:18:51
- E1: jiangly in 00:38:36
- E2: jiangly in 01:01:08
UPD2: Editorial is available here
As a tester, this is my first "as a tester" comment.
Wait a minute, are you the guy who made Minecraft inside of Minecraft, and other cool stuff?
Edit: this is his youtube channel: Click me
Indeed
wow!
I was thinking to ask but I thought there was no way lmao
Since we all know real Codeforces rating is actually determined by
rating * contribution, as a writer, give me contribution.This means I have to decrease my rating for increase my real codeforces rating?
As a tester, the contest is very good and I like all the problems!
Also, orz myst-6
as a tester, i swear on skippity problem F can be solved by binary searching a segment tree and morphing the result into a dsu before finally getting the answer using a mixture of crt and fft (alternatively you can use a persistent 1729-dimensional convex hull trick on a sparse segment tree)
Also, orz myst-6
seems easy for a F
that's trivial, I can't believe this is appearing on a codeforces div2 round. What's happened to Codeforces???
Trivial
As a tester, do not miss the contest.
Love the photo! Who are the other mysterious coders in it? One of them has a blank screen. We need to know :)
I'm the blank screen
2022D1 - Asesino (Easy Version) Is there an impostor? How many queries do we need?
I'm the guy in the back
Are you the impostor? Also the guy in the back right looks very familiar!
As a tester, just put the contribution in the comment bro
BucketPotato orz
Another quick chance to re-perform after all these greedy pains and hacks on map... Hope to reach pupil again this time
Last year I made the same question and still don't know why to make a contest on Ieeextreme day T~T Ik maybe it's not on clist but most of coders know about ieeextreme and its date. Anyway, Thanks authors for a new round ^-^
After this contest, I will be pupil!
I am the camera
Whats (1250 + 1000). Can someone explain?
It's a problem with a subtask, subtask of a problem means it will be a similar problem but with harder constant or condition.
Another way to see it is 2250 problem being splited out into (1250 + 1000) for easier approach. Which aimed at weaker contestant to have a chance at solving (like me, the lower rating part).
Understood. Thanks
LongTrainDiv2
As a tester, I love the problems! ＼(＾▽＾)／
Also, orz myst-6
Hoping for the best Div.2 round. All the best to all contestants!
wtf these guys look too chad to be studying cs
As someone who knows at least half of them quite well, I can confirm that they are real skibidi rizzlers with true chad energy.
just put the code in the IDE lil bro
RAHHHHHHHH VIM IS THE TRUE CHAD EDITORRRRRRRRR RAHHHHHHHH WHAT THE F___ IS AN IDE????????
I'm not exactly sure what a skibidi rizzler is, but good for them I think.
certified macaquedev moment
certified myst-6 moment
As a tester, I can confirm that problems have statements
clashes with lc biweekly
should I give cf div 2 or leetcode biweekly?
Both
cf div1 >> cf div2 >> cf div3 >>>>>> leetcode
Hi I'm new to Codeforces and I'm trying to improve by reviewing code from past contests. However, I noticed that when I go to the past contests page, select a problem, and click on the accepted submission numbers, the source code isn't showing—it's marked as 'N/A' for all submissions. Is there something I'm missing, or are the codes generally kept private? Any tips on how I can view code submissions would be greatly appreciated!
this is a really good practice of keeping the photos of people preparing the contest, it gives good vibes + i personally feel that yes in today's AI world still there is human interaction which makes me happy.
Yes, I agree. I think it's nice to see the faces behind the screens.
wait a minute, I thought global round was going to take place
As a tester, I've purchased this contest for kids' enjoyment.
First CF after AFO.
CSP rp++ (CSP: a very important contest for Chinese OIers, just ended 30min ago)
Guys you giving LeetCode Biweekly or, Codeforces Div 2? Imma confused :(
Ofcourse Codeforces, Codeforces is like a lover, who gives you a lot of emotional pain, but still you want to be with her.
Yeah, I will try to give cf
Enjoy the contest, enjoy the problem, don't care about the score ！！！
hopefully i become newbie after this round
myst-6 fasrsi baladi?
Na
Is there gonna be a hacking phase?
No
It was not mentioned in the blog? so ig it wa a glitch
Hopefully I can become Pupil this Round And also, Good Luck everybody!
Sorry bro just rated you negative it happened by mistake
Good Index.
hope i become specialist after this round :)
why is contest registration closed before the start?
Oh, speedforces today!
dp forces
Any hints for E1? I feel like the nimber for each pile should only be revolving around $$$\text{popcnt}(x_i)$$$, but I hardly came up with anything...
Wasting 40min thinking about E1 while I could have been coding D2 should be one of the worst tactical decisions I've ever made XD
made a table of the SG, observe and guess, that's is.
so close to solve C but failed...
Oh! Because I wasn't familiar with discretization, I lost a lot of ratings in this round.꒰╬•᷅д•᷄╬꒱
How do you solve C ? I couldn't solve it no matter what
I used graphs
288149235
That's genius!
I used backtracking: https://mirror.codeforces.com/contest/2027/submission/288167004
How come mine TLEed ? https://mirror.codeforces.com/contest/2027/submission/288152899
The contest is over and now can not submit. But I think you need to memorization. Consider this if (dp[size] != 0) return dp[size]; before each call to f
I did that also but it TLE'd https://mirror.codeforces.com/contest/2027/submission/288154023
I think it's different. map::find() takes O(logn) while accessing value dp[size] takes O(1). absolutely find() is slower
dp[size] is TLE too. You could pre-prepare to reduce search range instead of iterating all a[i] at each time
I'm not sure what techniques i'm using, but i got kinda excited that it's the first time i sucessfully solved C. I'm gonna leave my solution here, hope it helps
https://mirror.codeforces.com/contest/2027/submission/288162730
Alright, so how to count the number of ways to achieve the result in D2? Struggled for an hour and still didn't get past TL8 (all other ideas just WA-ed).
Take the DP table used to solve D1 (one with states [elements removed][value of $$$k$$$]). In this table, I'm assuming you found the minimal cost for each state by doing the minimum of costs required when increasing $$$k$$$ by 1, and when removing a prefix, where removing the largest one doesn't hurt.
When increasing $$$k$$$ by 1, the number of optimal options assuming you do that is obviously just the number of optimal options for the state with $$$k$$$ greater by $$$1$$$.
However, when removing a prefix, it's possible that removing a smaller prefix would also lead to an optimal solution. However, what you can note is that as the number of removed elements increases, the minimal costs required to finish are non-increasing. So, what you can do is first find the optimal cost, then use binary search to find the smallest prefix you can remove if you want to achieve that cost, and then calculate the sum of numbers of options for each prefix between the largest one with this cost and the smallest one with this cost (doable with suffix sums).
Now, just compare the minimal costs obtained by increasing $$$k$$$ and by removing a prefix, if they're unequal, take the smaller one and the number of options for that operations, and if they're equal, take that cost and the sum of numbers of options for both of these operations.
How do you do C? I tried a graph solution but it was too slow.
288149235 its not too slow tho
288172503 see this why this gave me memory limit exceeded maybe because i used n in the nodes values?
i wrote the same thing graph solution with unordered_map and got TLE after the contest does anyone know why? 288157167
unordered_map has worse time complexities when comparing the worst case with normal maps , as there are hash collisions. So use maps instead
ok thank you!!
well you can see that its a directed acyclic graph, so we dont actually have to store the indices or whatever, but just store the edges, and then you can go over all the edges in decreasing order of starting node, and store whether you visited an index in a set
Deleted.
(bcz it's just bfs/dfs on DAG with a map to check visited. I'm bad)
i got so confused on B, worst performance in a while. i found C pretty cool, and D1 seems doable, but i just wasted too much time on B. nice round
I hate problems like B :(
I think B was kinda tricky. I just brute forced my way through the following code. It worked but the code was a mess.
hints for D1??
DP
You can use DP to solve it. An important observation is that you should always greedily remove as many objects as possible. Here are the techniques you need for it:
Prefix Sums and Binary Search
I did exactly that, what's wrong with my code? TLE on test case #8.
https://mirror.codeforces.com/contest/2027/submission/288173861
Got it thanks
How to solve A? Really do not understand why my solution was wrong.
you just have to add 2*(currmaxheight- ogmaxheight) to perimeter
and do the same for width
if currmaxheight and currmaxwidth exist then perimeter = currmaxheight*currmaxwidth
I did it, but you also need to sort data.288141087
probably not,288142926
Actually, I really do not understand where my solution fails.
here's a simple solution https://mirror.codeforces.com/contest/2027/submission/288121633 it's based on observation so I don't have any proof for it
ayoooooo,
it never thought of it
Fix bottom left corner at (0,0), then you just need to find max width and max height, then ans will be 2*(mw + mh)
Oh, yeah. That is much easier, than I did. Luckily I solved it quite quickly.
Awesome B. Cost me 1 hrs + 3 WAs. That B is fucking hard, C is much easier. I think D1 is easier than B, but I have no enough time to solve it.
Was your solution $$$O(n^2)$$$ (which passes, and IMO isn't hard to do), or something better (which probably is much harder than C)?
My sol is O(n^2). But I just can't get the idea during most of the time of the contest.
wtf was b's solution? I know im sleep deprived, but im felling dumb af
Say x is at index i then all the elements after index should be smaller than x. And for all the elements before index i, we only care about the elements before the maximum element upto index i, we will need to remove all those.
288132226
idk if I understand it well, but thats basicly what I did I kept searching for the max element on the vector, then I removed all the elements from the right of it
Then i searched again for the max element up to index of the last max and on and on
Then my answer was the number of max elements — the max element between the max elements it passed only test 1
alright so lets take an example
3 6 9 4 2 5 2
say i am checking for index, i = 5 (1 based indexing), so the idea is to make both the right side (i>5) and left side (i<5) suitable but i handled that sepertaely
for the right side, so the no of elements greater a[j] > a[i] such that j>i is simply 1, i.e., only 5( for j =6)
for the left side, the ideal way is to remove all the elements before the maximum upto i = 5. so the maximum upto i = 5 is 9 and no of elements before it is 2.
so total = 1 + 2 = 3, so if i had to make i = 5 as sort of the "center" of my arrangement then i need to remove 3 elemnts
Now i will run this algo for all i from 0 to n and keep on taking the min for it
oh damn i see it now
Since n is small, you can count for every index i, number of a[j]>a[i] such that j>i by brute force.
what u do with that number then ?
index with minimum count will be answer. For eg. a=[3 6 4 9 2 5 2] here cnt represent number of a[j]>a[i] such that j>i cnt=[4,1,2,0,1,0,0] now return min(i+cnt[i])
brute force the following for each i and pick the minimum:
i + # elements a[j] (j > i) such that a[j] > a[i]
I printed lots of pairs $$$(n,k)$$$ on problem E1 and try to guess answer, it takes me 2 hours, just for 1000 points?
As a newbie, I am just never able to solve B (crying emojis)
Don't cry for things out of control, you can start with some easier problems or exercise thinking skills. It's unnecessary to worry about how many problems you have solved but how many skills you have learnt.
damn.
Problems A, B and C were pretty good, but D1 is too easy. It is a really standard DP problem. Also speedforces.
All dp? Solved B, C, D1 with dp.
can you explain d1 approach?
$$$ dp_{i, j} = $$$ minimum cost to remove the prefix of $$$a$$$ up to $$$i$$$ with $$$k$$$ at $$$j$$$.
dp[ind][cur_k] => Minimum cost for the subarray a[ind:n] with current k value = cur_k
I have used prefix_sum + binary search to get the maximum prefix length we can discard from a[ind:n].
C is dp? I used sets to solve it
In fact, it's a DAG problem.
True
first time i got 3 pretest accepted on a div2. hoping that i can achieve 1200+
How to solve E1? My code is timing out when computing the SG function. Can someone help me?
I don't understand why B's constraints are low when a non-n^2 solution is not hard to do and fits a div2 B. (Yes, I am annoyed that I didn't look at the constraints, which is totally my fault).
I think that a better solution than $$$O(n^2)$$$ is a bit too hard for div2B (some people are already saying it was too hard). Maybe having an easy version where $$$O(n^2)$$$ passes and a hard version where it doesn't would work better?
What is the 'fits a div2 B' solution? I see you used pbds to find the order and that is definitely not D2B level. It's more like a D2D.
Well, finding the number of greater elements to the right is too standard to be a D2D, and yes it will be a slightly harder B but will make it not a speedforces at least. And making it a B1B2 is a great idea as the other reply mentioned. (And after considering now, yes the constraints is just alright I was just salty I didn't focus on it)
It adds almost nothing to the problem other than having to know a very standard technique. We don't want a D2B-level idea problem to require a D2D-level data structure, just because a solution for the harder version using such a structure exists.
To be fair, a lot of data structures other than pbds can also solve this in $$$O(nlog(n))$$$ (there are at least $$$2$$$ different segment tree solutions, for example), but I still definitely agree that having this as just div2B would be too hard, and my easy/hard version idea probably isn't actually that great either.
It can be done in $$$O(n log(n)$$$ with sorting and 2 maps.
If the constraint is tighter, I think we could solve it by fenwick tree. do you think so?
couldn't solve B
I'm screwed
You can fix $$$i$$$ as starting element of $$$a$$$ after deleting some elements then simply bruteforce the number of remaining elements after applying Stalin Sort on this $$$a$$$.
For B I was trying to get traverse till the first decreasing slope (i,e. traverse till A[i] < A[i+1]). And then my peak would be A[i]. Any number greater than this peak also is to be deleted. This failed on pretest(3). So I would love new ideas ?
Since n is small, you can count for every index i, number of a[j]>a[i] for j>i.
288174453 When I submit D2 at the last minute:
Passed pretests 1-7 ... :)
MLE in 8 :((
Lesson: use vectors to handle DP with uncertain array lengths ; )
UPD: got AC after only change map to vector, if ML is 512mb map solution will also pass ;)
288182896
How to solve D1You can solve it using DP + Prefix sum, it will run in either $$$O(N * M * log_2(N))$$$ or $$$O(N * M)$$$.
$$$dp[i][j] = $$$ Minimum cost to make array $$$a$$$ of length $$$i$$$ empty with $$$k = j$$$.
$$$f[i] =$$$ prefix sum from 1 to $$$i$$$ in $$$a$$$.
Obviously $$$dp[0][i] = 0$$$ for all $$$1 \leq i \leq m$$$.
Now let's fix $$$i$$$, $$$j$$$. Call $$$p = $$$ furthest position in range $$$[1; i]$$$ satisfies $$$f[i] - f[p - 1] \leq b[j]$$$, then we have 2 cases:
Then your answer is stored in $$$dp[n][m]$$$.
You can calculate $$$p$$$ using either binary search or 2 pointers.
My submission using binary search.
I am so stupid, I forgot to return my memoized solution for C so kept getting TLE but didn't realize until after contest ended. I think I'm just not cut out for this.
Can someone tell me what's wrong with my D1?
Solved it. nevermind
D2 is a good problem.
I agree, even though I struggled hard to debug it (eventually managed; it's also the first time I managed to make a debugger throw an exception, and it was completely my fault).
jiangly ORZ :0
Why $$$O(n^2)$$$ in B, eventhough it's easy to solve in $$$O(n)$$$ ?
Yup, using pbds or Fenwick tree with coordinate compression in n*log(n) is not ok for div2.B to have such semi-advanced data structures. The core idea is ok for div2.B tho.
You can solve B with argsort.
Yeah any method that finds the number of inversions can do it
How? $$$O(nlog(n))$$$ is doable, but what's an $$$O(n)$$$ solution?
By using stacks
I finally solved C by sorting the edges, but I wonder why the bfs solution got a TLE?
288136031
I used discretization to avoid
map<ll, vector<ll>>, but then I got 3 MLE :(288160146
Can anyone help me with the time complexity or the memory use of my solution?
Before pushing y, you should check if it is already visited . If not,then push y into the queue and mark it as visited. You can use a set to do so
is there any reason to avoid map<ll, vector>
I have used it and got it accepted
you forgot the "visited part" about bfs 288178077 heres mine with map bfs
Could someone please explain their D2 approach?
See this comment.
Did anyone solve C with DP? Please share your approach!
basically it's
dp on tree(same as dfs+ keeping track of maximum), Code: https://pastebin.com/k0VTY8ZTVery inspiring contest! I love it!
I'm like a little baby,don't konw d1 why？
You can solve $$$D1$$$ using DP. For more information check this comment.
dpforces
Thank you very much for the contest.
ahhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh i passed c with map but got tle with umap ahhhhhhhhhhhhhhhhhhh
Nice shirts :)
Interesting problems!
Took way too much time for B and C. Good contest nevertheless!
For Problem C, I submitted the same code in contest, it got TLE'd. And when I submitted the same solution in practice, it got accepted.
Can anyone explain the reason behind it? Thank you!!
TLE submission
Accepted submission
Looks like a c++20 vs c++17 issue.
idk why this happens tbh tho
because of c++20, It happened to me several times.
Somebody submitted a hack in the last 4 seconds of the contest to TLE an
unordered_mapsolution. It seems that maybe the hashing function works differently in different C++ versions, so when you changed the version it passed.unordered_map + different c++ versions + poor (not poor exactly) test cases
Solved A & B in 8 minutes but couldn't do C because I forgot to keep track of visited for my BFS solution :(
omg it's the anime cat
I reached blue with this one :D
I just want to understand, how my rating dropped if I solved 1 problem (A) say (+100pts) and then gave 1 wrong submission on B (-50pts). I got -44 delta. So I'll be glad if someone explains the drop.
Rating change is only dependent on your ranking in the contest, not on number of points gained. More info on how the rating system works is here.
Thanks for lmk!
I hate DP
Problem C, Most of the codes have used dfs, I used bfs and got MLE.
I used the same adjacency list as others using map. The map will contain atmost 3e5 elements, The queue can have a maximum of 3e5 elements at a time. So that shouldn't give MLE. What am I missing here?
Submission Link : https://mirror.codeforces.com/contest/2027/submission/288164685
I also got MLE on pretest 5 while using a queue . Then I switched to a priority_queue and removed all occurrences of the currently visited index from the map so that I don't revisit same index twice, which led me to get an AC. Hope it helps.
But wouldn't keeping a visited array also make sure that you don't revisit the same index twice? I used a visited array and got MLE.
Actually i just saw my code, and I was implementing BFS wrong (I was updating the vis array outside the for loop, so duplicates were coming). I figured it while typing the above comment.
Thanks to you I figured it.
You're setting
vis[ind] = 1only when it's popped from the queue, so your queue might contain something like $$$\mathcal{O}(2^n)$$$ numbers on that test since you're adding a lot of duplicates. Maybe if you move that line to where you're pushing into the queue, then it will pass.Yeah I did just that and it did pass. Thanks a lot for the help!
Can't believe I made such a rookie mistake.
Overall very nice round!
Tomorrow morning КГБ knocks on the door of the author of problem B (Stalin Sort)...
Auto comment: topic has been updated by myst-6 (previous revision, new revision, compare).
Took me forever to solve problem B.
I liked the contest, (luckily) there wasn't much diff for me between $$$D1$$$ & $$$D2$$$.
What is the chance of getting $$$+3$$$ or more after rating roll back?
Tourist is your father, the GOAT of cp
I was thinking of solving C using a tree, but I couldn't figure out how to implement it.
UPD: nvm the editorial is out
please rename title of contest as "Educational DP Contest — AtCoder"
Boss: "umm.. What happened to the user records in the database?"
Me: "Deleted"
Wait who even consensually name themself nathan_higgs like this name is weird man
How to do B if the bounds were more strict?
Use pbds to count the number of elements to the right greater than the current element.
Dumb question, but what is pbds?
Policy-based data structures
For CP purposes solely, you can see this blog by great sir adamant.
Thanks
can we use pbds in mac? as they are gcc stuff right?
seg tree with relabeling, but annoying for coding.
I would like to report suspected cases of cheating in Codeforces Round 982 (Div. 2). I have identified multiple pairs of submissions with identical or nearly identical solutions. Here are the relevant submission links:
Pair 1: https://mirror.codeforces.com/contest/2027/submission/288161794 https://mirror.codeforces.com/contest/2027/submission/288145385
Pair 2: https://mirror.codeforces.com/contest/2027/submission/288152323 https://mirror.codeforces.com/contest/2027/submission/288137323
Pair 3: https://mirror.codeforces.com/contest/2027/submission/288163896 https://mirror.codeforces.com/contest/2027/submission/288155729
Each pair of submissions shows a high degree of similarity.
Finally, I'm Pupil!!
288252108 This is the accepted solution of mine.
288248589 In this, I got mle, and also time taken was high.
The only difference I made was just how I was using the visited set while doing bfs so can someone explain more about what exactly happened with me?
UPD: Got it!Why would my java8 code run error through java21, and just a depth-first search shows stack overflow
Clarification Regarding Solution 288171719(https://mirror.codeforces.com/contest/2027/submission/288171719) Code... ~~~~~
include <bits/stdc++.h>
using namespace std;
define int long long int
define pb push_back
define input(arr,n) for(int i=0;i<n;i++){cin>>arr[i];}
define MOD 1e9+7
signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t; cin>>t; while(t--){ int n; cin>>n; vector<pair<int,int>>a(n+1); for(int i=1;i<=n;i++){ cin>>a[i].first; a[i].first+=i-1; a[i].second=i-1; } a[1].first=0; sort(a.begin(), a.end()); map<int,int>dp; dp[n]=1; for(int i=2;i<=n;i++){ if (dp[a[i].first]) dp[a[i].first+a[i].second]=1; } int ans=0;
for(auto it:dp){ if(it.second){ ans=it.first; } }
cout<<ans<<endl; } return 0; } ~~~~~ Dear Codeforces team,
I recently received a notification about a significant similarity between my solution (ID: 288171719) for problem 2027C and several others. I would like to clarify the circumstances and defend the originality of my work.
Explanation of My Solution
Request for Consideration
I assure you that I have always strived to compete fairly and in accordance with Codeforces' rules. I did not share my code or collaborate with others. If further clarification or investigation is needed, I am ready to cooperate.
Thank you for considering my explanation.