Hello Codeforces!
omeganot and I are excited to invite you to participate in Codeforces Round 919 (Div. 2) which will start on Jan/13/2024 17:35 (Moscow time). You will be given 2 hours to solve 6 problems. One of the problems is divided into 2 subtasks.
This round will be rated for participants of Division 2 with a rating lower than 2100.
We would like to thank
- Artyom123 for his epic coordination and also for translating the problem statements!
- A_G, PurpleCrayon, Yam, Andreasyan, oursaco, hyforces, Apple_Method, GusterGoose27, null_awe, awesomeguy856, lunchbox, jli505, Lemur95, ocasu, EmeraldBlock, EnDeRBeaT, cry, htetgm, SriniV, nonrice, mark, thehunterjames, ETL, AndrewPav, ForgottenDestiny, lazipotato, dutin, and Saq56 for testing the contest and providing valuable feedback.
- MikeMirzayanov for the amazing Codeforces and Polygon platforms.
- You for participating!
The score distribution is $$$500 - 1000 - 1500 - 2000 - 2250 - (2500 - 2500)$$$.
We hope everyone will enjoy the round!
UPD 1: Editorial
UPD 2: Congratulations to our winners and first solves!
Div 1 + 2
Div 2
First solves
As a tester the round is delicious palatable luscious mouthwatering delectable toothsome succulent juicy dainty appetizing inviting tempting piquant.
I keep getting negative deltas. The middle problems get tricky
As a tester, the problemset is even better than pokémon diamond & pearl
but is it better than platinum
who is the fish in your pfp
tatsugiri :3
As a tester, I can confirm that this will be the first div 2 round of 2024.
Hope to get Positive delta
As a tester, the round is delectable.
As a tester, this round is certainly an amazing round!
As a tester, I think this round is very interesting and problems are very cool :)
As a tester, the round brought positive curvature into my life.
It clashes with COCI :(
They changed the time https://codeforces.me/blog/entry/124610
As a tester, this round is certainly a round.
Hope to reach cyan rank
exited......
Fully prepared to drop back down to specialist
You have been on a steady rise. Keep it up!
I have dropped down to specialist
It is first Div.2 round in 2024.
I hope this round is fun.
$$$5000$$$ score Div2F is 💀
anti rainboy round
the round was in fact not anti rainboy
Hope the problem statements are as long as this blog post
Excited for this round! Hoping to achieve green. Best of luck to all contestants! :)
damn they prepared it 2 month ago?
That was when the blog was made. sum has been working on this contest for longer than that :). Orz!
IIRC the hello 2024 round was being prepared in 2022
Wont this round be based on (or coincide with) BelOl like last year same time? Asking just in case, cuz took part
No (idk what that is)
thx. Belarussian Olympiad
I just wish to solve A-D this time.
Thanks Codeforces for another contest!
This will be my first Div.2 round in 2024. I wish this round can have short problem statements
How much time did you spend for solving your the most difficult problem?
Can someone help me with the problem, I am trying to solve it for several days, I think for you it will be a mere task: https://acmp.ru/asp/do/index.asp?main=task&id_course=1&id_section=3&id_topic=37&id_problem=1840
As a participant i will try to enjoy the questions :)
I hope my brain don't lag at the time of contest and I am able to give my best in this winter season without my hands getting freezed :)
Looking forward to crying in a fetal position after round ends
I'm a freshman,I want to know how difficult div.2 is?if it's possible for me to become green?
You have participated in Good Bye 2023 and Hello 2024 — the difficulty should be comparable to those (except that the very difficult last problems are missing here, but that won't affect you).
Is it possible for you to become green? Yes. But is it likely? Probably not. I see that until now, you've only gained rating from contests. Remember that in some contests you will lose rating and you shouldn't get demotivated by it. But anyway, good luck, hopefully you perform well!
I hope so,thank you!!!
As another freshman, it seems doable
As a participant, I want a positive delta :3
Do you know why others (mathematicians, physicists, chemists and...) doesn't have such big communities like codeforces?
Because we didn't make one for them...
Because the most of Math, Physics, Chemistry problem solutions are required checking by people. Here all solutions are checked by the computer.
My Gut tells me it will be a good contest >.<
Hoping to get better at problem solving. Will try my best.
hope to solve 5 problems this round!!!
Hopefully the problems will be short and precise just like the announcement
Atleast this time leetcode ain't clashing.
Anyway it doesn't matter as always would have done codeforces ;)
I need two points to reach pupil :)
Briefly and to the point, it would always be like this
Is it rated?
This round will be rated for participants of Division 2 with a rating lower than 2100.
As a participant I hope I get non negative delta.
(Wait this might be the shortest announcement I have ever seen.)
Hope I can enjoy this round!
Here it is, first div-2 contest of 2024
Hopeful
I hope i get positive delta <3
Excited for this round! First div-2 contest of 2024.
I hope you all get positive deltas.
How to become a tester? I am new here and would definitely appreciate the help!
Was feeling alone without cf contest ;
be ready for defeat
as a round the participant is i am .
Worst contest in a while! Congrats, it is quite an achievement to surpass gb2023!
I am absolutely agree with you!
Wtf is rainboy doing? Why doesn't he solving first three problems after solving the rest??? Somebody explain this to me.
He is doing what he wants, actually you shouldn't care
He doesn't care about rating or placing high in contests. Why solve easy problems if they aren't a challenge for you?
Enjoyed the problem set.
Weird problems, not as good as should be
lol
are these all bot accounts??
They're all from the same anime ig. It's no surprise their submissions are similar
There are much more of them. Some more examples:
need to improve debugging skill
Thanks for contest, I really liked problem $$$E$$$!
Problem B felt rather easy, but took me 1 hour to implement :(
I got stuck with the time limit on the 4th test, and the best time complexity I managed to implement was approximately O(k*(x+a.size)). Damn... How do you guys even come up with fast solutions? Haha.
Greedy Approach worked just fine. Since the order of the array doesn't matter, sort it out in O(n).
for B: he would like to multiply x largest elements with -1. You can pre-calculate this. for A: Max Sum if he doesn't perform any deletion? Max Sum if he deletes 1 largest element? Max Sum if he deletes 2 largest elements?............Max Sum if he deletes k largest elements? Compare answers each time and get the max. You can do this in O(n).
Any counter test for D https://codeforces.me/contest/1920/submission/241485595
One of the best rounds in a while
why the fuck are problems made so that contestants have to handle overflows during contests
it is absolutely insane
Only $$$1$$$ such problem, so i don't think it's bad. $$$D$$$ and $$$E$$$ are really good problems.
NOOOOOOO! I just finished debuging the F1 samples!!!
same :(
Any ideas for D?
You have to consider at most first 64 operations of type 2 (because after size surely is larger $$$10^{18}$$$). So you can handle each query in 64 steps.\
P.S. Out of stupidity I used
size_tand 32x c++17 compiler. And i was late for fixing it, therefore I don't know whether my implementation is correct:)Why not use
__int128? Its usage is the same asintandlong long, except for input and output.I prefer to use standartized features/types. So really I should use
int32_t,int64_tand so on.what is the intended solution for c aside of the bruteforces one? edit : never mind the editorial is out btw is the bruteforces solution (looping over all valid m from 2 to n) for every k intended to pass?
How to do C?
think about gcd
Doesn't help me much, because I always struggle with GCD problems.
For this problem, my approach was that I create an array of every element in the original array mod 2. Then I see if I can group these modulos. Basically fixing m = 2.
Stuck at WA on test 2 :(
I'm still happy though. Going to get at least +70 :)
To find such m, my idea was that if all the elements at the same position of each subarray would have same remainder, then subtracting the minimum value (among these elements) from all of them would make them divisible by m.
Taking gcd of the elements-minValue would get us the required m, if it exists.
That makes so much sense! Thank you!
Actually, the root cause of my error was that I misunderstood the meaning of the word "partition". I thought you could rearrange the array elements, but it turns out you can't :=(
Just do literally what is said in the description, split the array and compare corresponding elements to find suitable
m: 241459859Problem D test 7 ))))))))
Most enjoyable round since I can remember.
Why is D considered an original problem? Isn't it a very simplified version of persistent treap (cartesian tree)?
in fact, it's just this problem but modified
A really interesting round <3
For C, I had to ask ChatGPT because I had no idea how to determine if we can make the subarrays equal. Well-known maths are too hard for me.
https://chat.openai.com/share/f7668e07-29c9-4963-9140-d6d963858131
chatgpt should be banned imo its not like other online resources
https://codeforces.me/contest/1920/submission/241485816 All testcases are passing on vscode but not on codeforces
Where is
#include <bits/stdc++.h>using namespace std;?. I think you forgot to copy smth.Next time I recommend using the flags
-g3 -fsanitize=addresswhen compiling your solution as it will halt your program when it gets stuff like address boundary errors, that is, your program tried to access memory you have not allocated. Without these your program will peform undefined behaviours, which are very unpredictable, and sometimes it will give you the illusion of a correct solution.Notice that in the for loop when calculating the answer at line 42 you have
i >= n - 1 - k. In the case of $$$n = 1$$$ and $$$k = 1$$$ you'll have at some point $$$i = 1 - 1 - 1 = -1$$$, so you'll try to access the vectorprefat index $$$-1$$$, which is undefined behaviour, and can have any value depending on how you compile the program. That's the reason for the wrong answer.I got memory limit exceeded on D ( https://codeforces.me/contest/1920/submission/241477487 ), but as far as I can tell, my solution uses O(n + q) memory, which I assumed would be fine. Is the issue that I was using python, or is O(n + q) memory too much (or does my code actually use more than that)?
The numbers you store in $$$len$$$ will eventually become too big to fit into the memory limit. You have to check whether the number is larger than $$$10^{18}$$$ (You can discard it if it's bigger).
Thanks! It's nice to know that the issue wasn't python, but at the same time it's not so nice to know that I was just the issue.
amazing contest, I enjoyed a lot solving problem D!
W contest, interesting problems
Very good contest, send me to expert.
I was so close to solving my first DP problem during a contest.
Can anybody explain me the approach of satisfying constraint?
We encompass the range from high to low.
Now for a is equal to 3 store them in an array/set
Now find numbers in the set which lie between high and low including high and low, let them be equal to cnt
high-low+1-cnt will be the answer
Good contest, problem C was interesting
why it gives wa ?? 241464609
It looks like you're only checking the factors d that are at most sqrt(n). For each of these, you also need to check n / d. You can do this by just changing the sqrt(n) in your for loop to just an n and it should work (I did that question in python and didn't bother with the sqrt(n) optimisation and it was fast enough).
Its enough to check till sqrt(n) because i check for i and n/i .
Fixed. See 241496238
Ohhhh my goooood i am such a stupiddddd , thanks man
Can anyone tell me why i can't change my handle name?
yo cant change your handle name once you make an account ig
what's ig?
i guess
Nice contest!
nice round
A.Maintain a minimum and maximum variable for operation1 and opeartion2 respectively and for operation3 make a vector of numbers that we can’t take. Now the problem converts into the count of numbers that is between min and max and not present in the vector. we will check how many numbers are in the vector which is between min and max we can’t take these. Then the answer is (max-min+1)-the number of elements in the vector between min and max.
B. The first intuition is that if Alice has to remove some k1(0<=k1<=k) element it will remove the biggest element in the array so that Bob can’t make them negative or Bob will multiply -1 to smaller element. Now in the shorted array, we can check for every k1 (0<=k1<=k) alice will remove the last k1 element and Bob will multiply -1 to the last x remaining element in the shorted array and we can calculate this sum using prefix array(Dp) in O(n).
C. We can divide the array into n/k segments of length k, here k is the divisor of n. The count of possible numbers k will be in O(n^1/3). Now for every k we have to check if there is any m>=2 for which updating the array a[i]%=m makes all the segments equal. For some k we have to compute some m for which 1st,2nd…. kth element %m of every segment equalise. we can represent all first elements like a*m+r, b*m+r, c*m +r…… . We can see that if we pair-wise subtract the elements of the first position we will get some (a-b)*m, (c-b)*m. here we can see that m can be the gcd of all elements or divisor of gcd of all elements of 1st,2nd,3rd…. positions.There may be different gcd of different positions, but m can be the divisor of gcd. so we will again take gcd of all gcds on different positions.we will check if gcd that is m>=2 or not. we will count these numbers and give the output.
Problem C has weak tests. This submission passed with 140 ms, but it's clearly too slow and should have exceeded time limit. I was able to hack it with a simple test where N has many divisors and all elements are the same, except for the last one.
sorry about that x_x, it's my bad
There is a bug in Problem F2 tags, there are double Binary Search and Data Structure tags. (The bug exist when I'm writing this comment)
Tags
Note: Today, the bug has fixed.
Damn that was hard
I don't quite understand how it is possible that three accounts handed in all the tasks at the same time (with a difference of a few seconds, and the solutions were handed in exactly the order in which the participants are in the table), and as a small additional detail — their nicknames are from the same subject.
Task / LeviAckerman1945 / NarutoUzumaki1579 / ItachiUchiha8569
A / 241427625 / 241427527 / 241427718
B / 241440017 / 241439964 / 241440092
C / 241448078 / 241448021 / 241448153
D / 241454923 / 241454872 / 241454992
All these solutions are similar in style, but contain different initialised classes and completely non-obvious solutions. It looks like bypassing the anti-plagiarism system. Could it be cheating?
rm-rf made a blog post and there are at least 39 accounts https://codeforces.me/blog/entry/124673?#comment-1106808
This is outrageous and disgusting behaviour. I want to tag Artyom123 to inform them about this because they are the contest coordinators. Could you suggest someone we could inform?
??? where am I? Why am I being mentioned here? lol
I wish I got a -9 so that I can farm the div. 3
iirc you actually need $$$1599$$$ rating or less to be rated in div3
you misunderstand it
Oh yeah, sorry, I misread your original comment :/
How problem B could be solved if array elements are allowed to be negative as well ?
Can someone tell me why is this failing on some hidden case ?241532507 I'm calculating the prime factors of N and then checking for each prime factor if it is a valid divisor or not. If it is possible for some prime A then for all multiples of A which are also divisor of N should be valid. Is something wrong in it ?
It is true that if some prime $$$p$$$ works, all mutiples of $$$p$$$ (that are divisors of $$$n$$$) work.
But the reverse isn't true: even if some prime $$$p$$$ doesn't work, its multiples can still work.
For example here, you can't split into blocks of size $$$2$$$ but hou can split into blocks of size $$$4$$$ and $$$8$$$.
Thanks for your help
What will be the Rating of C? Great Contest BTW
Thanks for the interesting problems!
Problem C says 1≤ai≤n, but actually it is 1≤ai≤200000. :( My algorithm is too weak.
hm
include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() { int t; cin >> t; while (t--) { ll n; cin>>n; vector a(n,0);ll m=-1e18;ll score=0; for(int i=0;i<n;i++){ cin>>a[i]; m=max(m,a[i]); }
for(int i=1;i<=n;i++){ if(n%i==0){ ll k=i; //cout<<k<<endl; for(int j=2;j<=n;j++){ bool div=true; for(int l=0;l<=n/k;l++){ ll w=a[l]%j;//cout<<w<<endl; for(int o=l;o<n;o+=k){ if(a[o]%j!=w){ div=false; break; } } } if(div){score++;break;} }}} if(n==1){ score=1; } cout<<score<<endl; }}Can someone help as to why this is not a valid solution for problem c? i'm getting wrong answer at test 3 line 17 and hence cant see the test case