Hello! On Jan/15/2024 17:35 (Moscow time) will start Codeforces Round 920 (Div. 3), the next Codeforces round for the third division.
The round was coordinated by Vladosiya, and prepared by me and the students of Neapolis University Pafos: Vitaly239239, goncharovmike, ikrpprppp, step_by_step.
Thank you very much Alexdat2000, dan_dolmatov, fastmath, FBI, Nickir, nikhil97agra, pavlekn, PMiguelez, JuicyGrape, ibraevdmitriy, Sergey140146659, Sparrow_Guo, Toy_mouse, vladmart for testing the round.
As usual for the third division rounds:
- there will be 6-8 tasks in a round
- round duration is 2 hours 15 minutes
- the round follows the ICPC rules, penalty for an incorrect submission is 10 minutes
- round is rated for participants with ratings up to 1600
- after the round there will be a 12-hour open hacking phase
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behaviour. To qualify as a trusted participant of the third 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 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Good luck to all!
UPD: Editorial
Can't wait to pass 1500
Impossible bro
You will get back to PUPIL
Yeah you're right Lol
Lol, go and see his blue badge tomorrow.
Passed 1600 hundred LOL
Congrats bro. Any tips ?
https://mirror.codeforces.com/blog/entry/124464?#comment-1105140
Thanks bro
same goal in this contest
Good luck my friend
Congrats on becoming a blue
Thanks bro
Wow! Translation into Russian
.
Good news!
As a tester, I fucked up during previous contests because I was poisoned( but I wont give up and will restore my CM status.
As a participant i am at a loss how this information is relevant to this contest
As a good person, I just wish you all best in the upcoming round
Am I right that round was rescheduled from 16th of January ? If so, its very unusual. For me I was planning to take part and made some effort to free 2 hours on Jan 16, but tomorrow it will be impossible... Or I just had a glitch about 16 ? )
Yet another post-contest discussion stream Upd: I have updated the link. Sorry for issues in the begining.
Finally my turn to write this...
My first unrated div 3This comment has been deleted.
My first unrated div 3
i wish get 1400
Same :)
Good morning pashka <3
I usually skip div3 these days, but I'll do this one just because of pashka :)
Me too ^_~
but "do not have a point of 1900 or higher in the rating."
You can alwayes participate as unofficial participant
with a rating higher then 1600 you can't register(I think)
I have already registered and participated, and there are alot of div1 people doing the same thing (the only diffrence is it's unrated for us)
The top10 in scoreboard during the contest had only 2 people that have rating less than 1600 and the most of the others are reds
Please restart your youtube channel with some new series, pashka orz
Any way to lower by rating by 12 ?
Transfer it to me
the round will be good if pashka prepared it)
ॐ
My first contest here :)
Got a question: a "penalty for an incorrect submission is 10 minutes" means that there is a timer and it takes 10 minutes away (so the round is 1h 5m for me), OR does it mean that I'm just banned from submitting code for the next 10 minutes, but I still have the same remaining time for solving problems.
You get points like you submitted it 10 minutes later.
As non-tester i confirm this is the first Div.3 after new year!
Hopefully, the problem's statement will be short, precise, and easy to understand!
My first unrated Div 3.
And pashka as one of the setters , can already confirm it's going to be an awesome coding contest!
Amazing round I love U all <3<3<3<3
with all due respect, problem C is just kind of shit.
Bruh, you solved upto F but couldn't solve C :/
Why? Because of the problem’s statement? I don't see any problems and it's a good problem.
time to attempt the first question only to get it wrong on pretest 2 and ragequit (my rating still gonna go up lmao)
i had the same thing, try virtual contests, they bring less stress gl
your profile picture reminded me of Sam Hogan. Good old days
it is sam hogan we will never the days he actually posted sadly he disappeared but tbh i don't know why anyone would want to leave such a successfully channel
Game development can be exhausting. Brackeys and Dani have also not uploaded anything for quite some time.
Brackeys left and im pretty sure Dani also quit also sam went off to college but yeah game dev is just generally like that
How to solve E ?
nvm, looks like it's just checking all the cases. I thought it's some classic algorithm.
You can check out my solution for e, it's just maths :)
is F solvable using Mo's?
You can just precompute prefix sums for d <= sqrt(n), and for d > sqrt(n) just brute force the answer. In the first case a query takes O(1) and in the second case its O(sqrt(n)). Preprocessing takes O(n sqrt(n)).
I thought about prefix sum for small d as well but not yet implemented, tks for the clear solution!
I thought of precomputing the prefix sums but just not for d <= sqrt(n), I was thinking of every d <n. Is sqrt(n) common in these type of problems? Why do we select that as the cutoff?
it's very common indeed. U can read this for more detail
Because memory is limited and if $$$d \gt sqrt(n)$$$ then it's easier to just iterate instead of precomputing for every element.
Imagine , if you take d as a cut-off , then final complexity will be n*d + q*n/d = n(d + q/d) , which will be minimised at d = sqrt(q).
sqrt(n) observation not necessary. you can do offline query method. for all the queries put the s%d,d in some set. now for only these (start,difference) you need to precompute and this would be somewhat n*(q)^(1/2) Submission
ah that's really clever
Basic idea is precomputing answers for all d <= $$$\sqrt{N}$$$, which can be done by prefix sums in O(N*$$$\sqrt{N}$$$). For d > $$$\sqrt{N}$$$, simply iterate and get your answer.
Nice contest. F and diagonal prefixes in G are tricky, nice problems for educational rounds.
nice round especially providing many sample test cases thank you
Exposing cheating case please make the contest unrated the solutions were live streamed on the following channel
https://www.youtube.com/live/q5YxSQlknAQ?si=rM_nl9XokelPGkJF
why have it unrated for all, just the cheaters should be eliminated
Got Stucked in Problem E.
Thousands of cheaters in this round. saw some noob coders solving DE faster than specialists. hoping they will get filtered out for fair rating update
In problem E what do they mean by if both opponents play optimally , do we have to check every possible move from current position, and move only in those direction in which player is winning?? i am not able to understand this problem please explain. Thanks!!
play optimally means that if there is a winnig state for player A, then player A will play in such a way that will win.
No need to check every possible move if you find a general case for wich A wins
I tried to come up with a one-line formula for B, but this approach gives WA in the 3rd test:
max(((s & f) ^ s).count(), ((s & f) ^ f).count())Does anyone have any idea what I might be missing here?
#define bin bitset<64>Your bitsets only store $$$64$$$ bits, not enough for $$$10^5$$$ bits.
mind solved f in 10 minutes, could not debug my code in contest with more than an hour left. then debugged within 5 minutes after the contest!!!!!
can you explain your approach for the problem F ?
2 cases case 1: when d>sqrt(n) in this case you can just brute force each query because will take O(sqrt(n)) time because if d>sqrt(n) there will be no more than O(sqrt(n)) elements to choose from i.e., k cannot be greater than O(sqrt(n))
case 2: when d<=sqrt(n)
for each element in i store prefix sums and for each d and also store increasing prefix sums (1*arr[i], 2*arr[i].. like this) then solve in O(1) per query.
i did not explain case 2 very clearly i am finding it very hard to explain.
got it , thanks
for case 2 I'll explain how to solve when d=1
given an array a, answer queries of given [l,r) find S = a[l]*1+a[l+1]*2+...+a[r-1]*(r-l)
define sum[l..r) = a[l]+a[l+1]+...+a[r-1] = pref_sum[r] — pref_sum[l]
notice S = sum[l..r) + sum[l+1..r) + .. + sum[r-1..r) = (r-l)*pref_sum[r] — pref_sum[l] — pref_sum[l+1]-...-pref_sum[r-1]
so we can do a second prefix sum array over our original prefix sum array
how to get the answer from second prefix sum array when d>1?
I seriously think this is the reason why you couldn't debug your code within an hour. It may make sense to explain your solution to yourself until you understand all the details completely before implementing it
Or understand during the implementation. Sometimes it's nice to write down something to free up some space for understanding missing bits.
ps. Congrats with impressive performance in the round.
ya i think so to, i jumped into implementation too soon.
I don't know why, but I do very well outside the contests but when I participate I feel stupid, I didn't even solve D.
Same lol :)
I kept tripping over the math for B and C.
Then for D, I was thinking it was a heap/priority queue solution, but I couldn't figure it out.
Was hoping to make Pupil this round, but oh well :_(
D has really counterintuitive solution.
I partially agree. I first decided E, and then I figured out that in D you need to put 2 pointers to the array A, not one :D
(This is KillerQueen from tg)
No fucking way
I found that D is extremely likely to be fakesolved for me. I cannot find the bug since my code pass all examples and got WA on test 2.
I am an amateur I have just solved one problem I just want to ask can I have some score? I hope I will have 1200 through this vacation's effort Can someone explain to me how can I get some score
With 1 solve and your default expected performance being 1400 you should expect a huge drop in rating. However since you're unrated, there's a +500 bonus on the first round, so your rating will still increase.
You would need to wait for the system test to end, which would happen about 18 hours from now, since there is open hacking phase.
Such a nice contest! really liked the F. overall quality was great and the contest was balanced , 10/10 honestly.
how to solve F and G??
F can be solved in O((n+q)*sqrt(n)) , by dividing in two cases d <= sqrt(n) {for which you can use suffix sums) and d > sqrt(n) for which just sum directly. However , I believe taking d <= sqrt(q) , will be more better.
Too many cases in E, solved just after contest ended :(
you can just simulate it !
constraints are large. can't simulate it.
"It is guaranteed that the sum of $$$h$$$ over all test cases does not exceed $$$10^6$$$."
sorry my bad, didn't see. I just saw the constraints of w and assumed h to be similar :(
I think it can be simulated as the sum of h over all testcases is guaranteed to not exceed 1e6
Single if is enough to compare two intervals where two players could meet.
can someone give me clean implementation of F?
Maybe this can help
My solution (241838398) precalculated prefix sum of
a[i]and prefix sum ofa[i]*i, for all $$$d\leq\sqrt{n}$$$. It's $$$O(n^{3/2})$$$ time and $$$O(n^{3/2})$$$ space, which seems to just fit the time and memory limit.How to solve G?
Make diagonal prefix sums, like 2d prefix sum and try each of 4 possible directions in O(1) for n*m shooting squares.
I failed to implement it in time
Bruteforce every possible starting location. To move the starting position by one cell you need to add/remove subsegments of a row, column, or diagonal. From here it's down to your implementation skills.
There is a simple solution in $$$O(nm*min(n,m))$$$.
Assume WLOG $$$n \le m$$$, The solution is: iterate over every $$$(i,j)$$$ as the start location, iterate over every row $$$x$$$ that the $$$(i,j)$$$ will reach with the operation, find the sum of the elements of the row that is in the range of the operation with simple prefix sum.
This work in O(n^2 m), if $$$m \lt n$$$, just rotate the input. This is code: submission
Oh, I thought this will TLE, but min(n,m) can be at most sqrt(1e5), which idk why, I missed :(
I had a slightly different solution:
Solve the problem for the down/right diagonal only. Rotate the grid four times and print the best answer over each rotation.
To solve for the down/right diagonal, notice that a shot from point (r, c) of size k is equivalent to a shot from point (0, 0) of size k + r + c, minus the combined number of targets in the first r-1 rows of that shot and the number of targets in the first c-1 columns of that shot. This can be found using inclusion/exclusion and prefix sums.
So, we can enumerate the targets in order of their Manhattan distance from (0, 0) and check starting points for the shot using a sliding window technique.
Problem D
In some test cases, t is 10000 (which is not correct)
Yes, we will fix it and rejudge all affected submissions.
Done. We changed the tests so they have at most 100 testcases. It affected a very small number of participants. They got AC instead of TL or WA.
...#include
include
include
using namespace std;
int main() { int N; cin >> N;
for (int k = 0; k < N; ++k) { int n, m; cin >> n >> m; vector<int> l1(n); vector<int> l2(m); for (int i = 0; i < n; ++i) { cin >> l1[i]; } for (int i = 0; i < m; ++i) { cin >> l2[i]; } sort(l1.begin(), l1.end()); // Sort in descending order sort(l2.begin(), l2.end()); // Sort in ascending order reverse(l1.begin(),l1.end()); int sumi = 0; while(n>0){ if( abs(l2[0]-l1[0]) >= abs(l2.back()-l1.back()) ){ sumi += abs(l2[0]-l1[0]); l2.erase(l2.begin()); l1.erase(l1.begin()); n-=1; }else{ sumi += abs(l2.back()-l1.back()); l2.pop_back(); l1.pop_back(); n-=1; } } cout << sumi << endl; } return 0;}
Can anyone tell me why my solution of D is giving me wrong answer on test case 3
Perhaps overflow?
i tried by using long long too but still it is giving wrong answer
oh i got it
Also, vector erase method is $$$O(n)$$$, so your code is $$$O(n^2)$$$ which doesn't fit the time limit. Instead, try to use a pointer
int L = 0, and increment it to simulate erasing the first position.Ok Thanks, I did badly in this contest
Good Round
Nice F, btw this is the worst E i have ever seen in div 3
Can today's D be solved by binary search?
my approach was to club max elements of A with min elements of B and Max elements of B with min elements of A.
And there will always exist an index i before with we'll club max elements of B with min elements of A and after index i we'll club max elements of A with min elements B
I brute forced it. It gave tle on tc7
Now i want to ask that if this can be optimized using BS. BS to find that optimal index i?
Brute forcing like that is how I did it, you can optimize by using prefix sums to calculate the answer for each cut-off point in O(1).
why didn't i think of that T_T
I have solved all the problems except the last one. I am willing to discuss the solutions with you. If you need help for the hints or solution idea, you can knock me.
Can you explain the problem F
Of course, I sent my whatsapp number to your inbox.
Just curious, is D solvable using ternary search?
my thought process included noticing the ternary searchable array. But since we're trying to maximise the answer, optimal points will be on either left or right ends.Therefore no need to do ternary search. just have to check ends
How many problems I need to solve in Div3 as a pupil, to reach specialist ? Can someone tell ?
Want to know the same
Can anyone tell me what the time complexity of my code(Problem G) is? 241841658
In F, I am trying to solve this question O(n*root(n)) but it is giving me TLE. I saw many people did it in O(n*root(n)). can anybody help me to find out where I am going wrong? My submission: [241845077]
Yeah, your solution is O(n*root(n)), but your index in vector is [arr_index][step]. If you know, vector stored continuously in memory. When you refer to [ind1][step] you need calculate offset to [ind1][0]. If say simply, need to calculate [0].size() + [1].size() + [ind1-1].size() and it's not effective. But if you start iterate by first index and after by second index it's more faster, because your elements in memory was close. You can turn your vector and get accepted 241873500. Or you can use matrix, because program know size of every lines. 241875600
Thanks bro, it is helpful for me.
Hi, I am new to codeforces. I submitted a code 10 minutes before the contest ended and it was accepted after 3 failed attempts , why is it still showing as unrated for me? And when will I get it get rated for me. Someone plz reply
Div.3 and Div.4 usually take up to 24 hours after the end of the contest before ratings are published.
Hello everyone. For D i used the 2 pointer approach to solve it. Basically sorting both the array then checking for each term in nth size array which difference is the maximum. Depending on the term chosen, the pointer moves and rechecks.
You can see my submission. I have gotten a test case where the solution fails. But i am not sure what is wrong with my approach. One of my friends used the same approach but deque and got the correct result. Any help would be appreciated.
Who else say E and thought: "oh yeah this is like opposition in chess endgames"
lol
me
My D's solution got WA on tc2 when submitted during contest. After System test it got AC. Now after System test again it got WA on tc24 .
What's the issue here? I meant on CF site, why did it happen?
https://mirror.codeforces.com/blog/entry/124696?#comment-1107429
241860369
Problem E.
Easy to understand one liner solution C++.
So you're saying this is easy to understand.
Got it.
lolololololololol
Don't worry guys, the problem is solvable by one line. the line :
How much time will it take for the ranks to be updated?
Hope I reach pupil :)
And also can anyone explain what are 'hacks'?
Hacking means finding bugs/testcases in other people's solutions that make the code fail.
When will you release the editorial?
When will the ratings for this round be updated
Ratings?
Can't wait to become PUPIL
congrats and u lacked 2 points T-T
How many did you solve?
I hope I also become pupil
I solved A B C D in under 1 hour. Good luck!
Congratulations
Good luck in next contests!
Please, help me to understand problem )
This submission gives TL on test #12: 241773908
If I change only language (java 17 instead of java 8), the same solution gets AC: 241948448
I can't understand, why the same solution gets TL and AC on different java versions?
Thanks
I think the problem here is that sorting in Java 8 has $$$O(n^2)$$$ worst case time complexity. They fixed it in later versions
This round Problem F have nearly same idea with recent atcoder abc contest 335 problem F. Problem link : https://atcoder.jp/contests/abc335/tasks/abc335_f
Easy video Explanation for problem F
why my rating got reduced by 30+ points even though I did no wrong submission just only one submission I did why on the earth soes this hpnd?
You did one task and in the result you got 20596th place, which is lower than "expected" for your rating. Also note that wrong submissions don't affect your rating directly, only the score obtained during the competition, which translates into your place in the standings.
more info
Easy video explanation for problem G(BRUTE FORCE WORKS !)
Problem D is 1100 rated 😱 😱