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: Vitaly503, goncharovmike, ikrpprppp, step_by_step.

Thank you very much Alexdat2000, dan_dolmatov, fastmath, FBI, Nickir, nikhil97agra, pavlekn, PMiguelez, SashaT9, senjougaharin, 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://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

SpoilerAm 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 3`

Wishing my next one to be the same!

I hope to reach pupil rank one day :).Good luck

Thanks mate <3hoping for +ve delta in this round.

This comment has been deleted.

My first unrated div 3i wish get 1400

Same :)

how?

Good morning pashka <3

In the points it is written rated upto 1600 and then in the last it is written less than 1600.. which is true?

Both have the same meaning.

Up toxis all numbers`<=`

xwhileless thanxis all numbers`<`

x.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)

ॐ

Bunch of handsome peoples

wow pashka here, I thought that we face a lot of interesting and educational problem

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.

No, that's not what they meant. You should be aware that if you got a accepted after(for example) two failed submission and someone got it from the first time (consider that both of u solved it at same time) he will get penalty less than u .Also,He rank higher than you.

Got it. Thank you.

If I have registered for the round but I do not enter the contest, will my rating get affected?

No, if you do not submit any problems, then it will be unrated for you.

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!

is there any chance to rated this contest

anxiety

Amazing round I love U all <3<3<3<3

As I write this round, I can say with confidence that it was a great round that I enjoyed.

with all due respect, problem C is just kind of shit.

Bruh, you solved upto F but couldn't solve C :/

If there's no problem C, it's easy for me to solve all the problems. I can't understand the problem, maybe I'm poor in English.

Why? Because of the problem’s statement? I don't see any problems and it's a good problem.

Maybe the problem is hard to understand for a Chinese English speaker. I spent almost 60mins to try to understand it but failed.

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 > 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

Nice contest

I can't see myself in the standings. I have participated in 5 rounds and have solved at least 1 problem in each.

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.

Oh my, haha! I got used to putting 64 bits everywhere and being sure it works for any input. I completely forgot I'm dealing with a bitset, not an integer or anything else.

Thank you. It's accepted now! <3

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

just need to participate in as many contests as you can

well you are wrong here is why.... but jokes asides its like you tell someone to play more blitz games to get better at chess

uhm but it's not about getting better at something what he/she is asking, it's about getting used to something so you can overcome nerves

well if that what u mean u got a point then sorry but thats how i interpreted your comment sorry again :)

no problem :D

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 don't think so man, I passed all example cases through different approaches but two of them were wrong and then the third one finally got me AC.

Another fun round for a newbie like me :) Please somebody should try to hack my solutions

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.

Do continue practice. It will improve your problem solving skills and logic building skills. I am also a amateur coder .But now i taking it seriously I was able to solve two problems. Earlier i was not able solve any problem. But with continuous practice i have some improve skills

Wow!

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

Just few cases :

if d = vertical distance between them is odd or even ,

If d is odd then Alice will Eat B or B will escape ,

If d i seven then Bob will Eat Alice or Alice will escape.

Escape condition needs max right you can go and max left you can go, if by going to any extrema ( left or right ) , if you are able to escape the Eater, then draw or else lose.

Link to code

Single if is enough to compare two intervals where two players could meet.

Naisu contest, I felt climaxed by the AC in the final seconds =))

https://codeforces.com/contest/1921/submission/241827411 https://codeforces.com/contest/1921/submission/241799752 https://codeforces.com/contest/1921/submission/241816938

All the submissions seem to be extremely similar!!

Could someone look into it??

241806826 241811094 241818999 241814972 this particular method was posted online

using a while loop seems to be hackable. I would write some test case but meh

can someone give me clean implementation of F?

Maybe this can help

My solution (241838398) precalculated prefix sum of

`a[i]`

and prefix sum of`a[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 < 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.

Spoiler...#include

## include

## include

using namespace std;

int main() { int N; cin >> N;

}

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

You are using erase, I did the same and got tle. Either use a dequeue or two pointers.

Good Round

Hi, Can somebody explain why this Code for Problem D gives Runtime Error 241826844.

this segment will cause Index Out of Bounds for Array "a"

Nice F, btw this is the worst E i have ever seen in div 3

F-ed Up big time. Submitted E just after the contest ended and got Accepted on the first attempt. FML :').

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?

Binary search is only applicable for monotonic functions, in this case, the function isn't monotonous. So binary search won't work

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

i think solving 4 fast is pretty good to reach specialist. In some cases if E is easy then solve that too.

(take advice with grain of salt I am newbie)

I did some calculations and i figured that if u managed to solve A and B in div 2 under 15 min u might reach specialist without ever solving C or rarely solving it. Similarly solving 4 in 45 to 50 min will get you to specialist through div 3.

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.

okay thanks bud

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.

241784087 here my solution with two pointer

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://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 :

Hi, does this apply to all Div.3 contests? thanks

I love this round from A-F(I didn't read G), except for E.

How much time will it take for the ranks to be updated?

Hope I reach pupil :)

And also can anyone explain what are 'hacks'?

So, I just need to suggest a test case like

N = 3, p = 4.... and the algorithm of contest preparer gives a "YES" answer but the hacked participants give a "NO" answer. That means I hacked successfully. Did I understand it correctly?

Right. Basically participant's code fails while dealing with edge cases or due to integer overflow. Read More

https://codeforces.com/blog/entry/107753

Hacking means finding bugs/testcases in other people's solutions that make the code fail.

Overall, Another fun round for me :)

when the ratings will get upated?

it will take approx 24hrs

Thanks buddy and my rating drop eventhough I didn't gave wrong answer and I solved 1 question though the same

When will you release the editorial?

when will the rating change happen?

When will the ratings for this round be updated

within 24 hrs after contest.

Can you say how many problems have to be solved in div3 to become pupil?

Bro got no chill to become a pupil.

how many did u solve?

I did 4 questions. D was hard for me.

I did 3, I considered two pointer for D, implemented it also and it was not giving correct answer for tc1.So left it.

after the contest i came to know that there was some issue with my implementation though the approach was right. T_T

Has system testing finished??

Yeah. System Testing takes less than 30min after the hacking period concludes. You can go to "contests" in the navigation bar and see the final standings.

Nooo

Sorry. I was wrong. This is what I found-

"It takes a while (can be a few hours, or even more) to finalize things such as detecting cheats and confirming test results, or there can be other issues that need investigation"Why is the rating for this round not updated yet?

Ratings?

Ratings take up to 24 hours to update in div 3 and div4. Also in a contest that has an official 12 hour hacking phase the rating will never be updated before it ends.

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!

A,B failed in system tests... :)

thank you for making me green

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

Thank you. Next time I'll better choose java 17 :)

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

When will the results be declared?

F Video editorial + Live Coding C++ (English): https://youtu.be/mJVq_nW8iQk

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 😱 😱