**Note the unusual time of the round.**

Hello Codeforces!

lunchbox, Apple_Method, and I are pleased to invite you to participate in Codeforces Round 914 (Div. 2) on 09.12.2023 19:05 (Московское время). You will be given 2 hours to solve 6 problems (and one subtask).

**The round will be rated for participants of Division 2 with a rating lower than 2100**.

We promise the statements will be clear and concise, suitable for AdamantChicken2 to read *wink wink*.

Also, we would like to thank:

- errorgorn for the epic coordination.
- Alexdat2000 for the Russian translations.
- MikeMirzayanov for the amazing Codeforces and Polygon platforms (and finally taking Polygon off beta).
**[VIP] EnDeRBeaT**for testing and statement assistance.**[Upsolver+] omeganot**and TonightV for breaking our problems.**[Upsolver+] Yuu**,**[Upsolver+] Andreasyan**,**[Upsolver+] PurpleCrayon**,**[Upsolver+] BucketPotato**,**[Upsolver+] willy108**,**[Upsolver] hyforces**,**[Upsolver] wuhudsm**,**[Upsolver] cry**,**[Upsolver] htetgm**,**[Upsolver] Beaboss**,**[Upsolver] Akksharvan**, sum, BossBobster, priyanshu.p, maxrgby, and PoloniumLuke for testing the contest and providing us valuable feedback.

We hope you will enjoy the contest and receive positive delta!

**Scoring distribution**

$$$500 — 750 — 1000 — (1250 + 750) — 2750 — 3500$$$

**UPD**

The editorial has been posted!

Congratulations to our winners!

**Div. 1 + 2**

**Div. 2**

Congratulations for our first solvers!

**Div. 1 + 2**

bad time for chinese programmers

bad time for chinese programmers

bad time for chinese programmers

bed time for chinese programmers

bed time for chinese programmers

bed time for chinese programmers

Real example for recursion ><

bed time for chinese programmers

bed time for chinese programmers

did we just witness a full byte getting flipped by soft errors?

no, there's only a little bit difference :)

bed time for chinese programmer

return thienguyen;

bald time for chinese programmers

there is no bad time for chinese programmers.

best time for chinese programmers, there's no Saturday without staying up late.

bad time for chinese programmers

Happy to know that the statements will be clear and concise. Best of luck to all contestants!

And when you’re done with the contest, you can come watch the Hacker Cup Finals stream!

Thank you for the invitation, sir! I will definitely come to watch. However, could you please let me know where I can find the stream?

facebook.com/hackercup

As a tester, I enjoyed these problems quite a bit! Hope you will too!

how to be a tester

you get a private message from a contest organizer asking you if you want to test a codeforces round

orz

As a tester,the problemset is phenomenal!Hope you enjoy it :)

As a tester, I am not allowed to write anything about the problems which includes my opinion of the problems.

As a tester, I upvoted the blog twice.

lunchbox hard carry orz

As a tester, these were some really fun problems.

I'm a simple man, I see a lunchbox round, I register

Being a tester, I hope you enjoy the problems!

W time for PST

I really wanted to participate in this round but it's too late for my schedule :/

It would be great if the round could be held at the regular time.

The scoring seems to indicate a speedforces.

rainboyenters the chatBrooo i feel so happy when you promise us for the statements... And a nice choosing the TIME

Upsolver's round

I'm 27th

Big score difference between D and E, speedforces vibes.

Midnight for chinese

Lovely

5 minutes after finish of LeetCode Biweekly Contest.

Gotta skip or will try to give both

Step 1 : Give Atcoder regular round . Use 30 min break for dinner.

Step 2 : Speedrun Leetcode biweekly .

Step 3 : Put on Umnik's playlist and start codeforces round 914.

Update — Afterwards,watch livestream here to see who wins Hacker cup.

Can anyone tell me what are

[VIP],[upsolver+]beside the handles? I searched but couldn't find anything about it.They're just a thing the authos added to the announcement, probably referencing some games.

These probably refer to how the testers tested the contest but they don't have any deeper meaning.

Why the time is unusual?

it's not that unusual, it's just that some snowflake kids complain even if the round is 30 minutes off these days.

there was a time when there were rounds as late as 6pm UTC and maybe that was an unusual time.

anything between 2pm UTC and 4pm UTC is part of the historical time range of the rounds.

Problem writers are in PST

As a tester, I enjoyed solving the problems; they're all excellent problems! Problem [REDACTED] is very nice in particular!

Will give the contest almost after one month.

why?

glhf everyone :)

what does (1250+750) mean?

Problem has easy and hard versions.

oursaco orz

Rowlet1 orz

the unusual time note was very helpful

feels like that's going to be a shit round

It is indeed a shit

Could anyone please explain what it mean by "(and one subtask)" , cause I don't get it

This contest will have $$$6$$$ problems, one of which has two versions (easy and hard).

So they are actually 7 problems

Bad time for south Asians. 4 am in the midnight awww

Can someone please confirm whether "Kotlin Heroes: Practice 9 (release 2)" has been rated or not?

It is not rated because all the problems are from problemset.

Good luck for everyone!

If I have registered but not able to participate will my rating fall?

no it does not fall as long as you dont sumbit a solution

I hope that AdamantChicken2 participates.

I'm feeling sleepy now, maybe I should give up.

i'm a beginner can anyone give me advice

Refer Codeforces Catalog

thanks bro

Just do your best (Bro)

i will

Bad Time for Bangladeshi Programmers.

Bruh without Chinese it's only 3500 people

Is that really div.2!!its so tough

is it

div 2 a, b?C>D

Cool problems, especially $$$C$$$(with idea that we must check only $$$K \leq 2$$$) and $$$D$$$.

I should do D first T-T.

Cool problems and cool starting time

A > C > B

for me C>A>B

Found the error in D1 one second after contest ended. Nice!

Can anyone tell me if this works for F? I ran out of time to implement in contest.

First we build a directed graph $$$G$$$ whose vertices represent paths in the tree as follows:

For each vertex $$$u$$$ and number $$$0 \leq i \leq 20$$$ we construct a vertex corresponding to the path between $$$u$$$ and its $$$2^i-1$$$th ancestor along the path (LCA stuff). We draw directed edges from the "vertex" $$$[u, p^{2^i}(u))$$$ to vertices $$$[u, p^{2^{i-1}}(u))$$$ and $$$[p^{2^{i-1}}(u), p^{2^{i}-1}(u))$$$.

This directed graph $$$G$$$ has $$$\leq 20n$$$ vertices, each of which has at exactly two edges going outward. So the graph has at most $$$40n$$$ edges. Create another copy of such a graph, but now with edge directions reversed, call it $$$G'$$$. Finally consider the $$$1$$$-vertex paths in both graphs $$$G, G'$$$ and merge them (they are one single vertex now).

This new graph $$$G+G'$$$ has $$$\leq 40n$$$ vertices and $$$\leq 80n$$$ edges. Now for each of the $$$m$$$ conditions we do the following. Suppose that the condition is of the first kind, the second kind is analogous. Split the paths from $$$[a, c)$$$ and $$$(c, b]$$$ into at most $$$40$$$ vertices of $$$G$$$. Draw a directed edge from vertex $$$c$$$ to each of these $$$40$$$ vertices of $$$G$$$ (in the opposite direction if $$$G'$$$ were considered).

Now just check if the $$$G+G'$$$ graph has a topological sort. If it does, then the order of $$$1, 2, \dots, n$$$ in that is the answer, otherwise there is no answer at all. Time complexity of above is $$$\mathcal O((n+m)\log n)$$$

Yes, this ought to work.

ahghghgh thank you for confirming, after bricking C, D1, D2 I read F in last 30 min and figured this out but hands too slow ugugugughghh

What? D1 is actually EJOI 2020 Day 1 Task "Exam" Subtask 6.

datastructureforces

C was cool, D1, D2 were also good, crossing 1800 barrier for the 1st time after so long from being stuck and lot of demotivation.

Congo man!

Thanks man !

I absolutely totally did not stare at $$$C$$$ for $$$30$$$ minutes with no ideas until I realised you can make it $$$0$$$ in $$$3$$$ trials.

I absolutely did not spend 20 minutes staring at my solution for C without realizing that it works.

nice contest i enjoyed the problem thanks to authors. First time solved 4 problems

C is such a troll problem with $$$K$$$ up to $$$10^9$$$, you could have taken it a step further and not include a case with $$$K = 3$$$ in the samples. Not a bad problem though.

D was okay, just hoping I don't get

FSTed.Looks like I didn't get FSTed after all. Is there an easier way to do D2?

What I did:Yes there is an easier way, Let $$$R(i,x)$$$ denote the smallest index $$$j$$$ such that $$$j \ge i$$$ and $$$a[j] = x$$$, similarly $$$L(i,x)$$$ denotes the largest index $$$j$$$ such that $$$j \le i $$$ and $$$a[j] = x$$$.

Now, the answer is "YES" iff for every element $$$i$$$,

1) $$$Min(b[i],b[i+1]...b[R(i,b[i])] \ge b[i]$$$

2) $$$Max(a[i],a[i+1]...a[R(i,b[i])] \le b[i]$$$

OR

1) $$$Min(b[i],b[i-1]...b[L(i,b[i])] \ge b[i]$$$

2) $$$Max(a[i],a[i-1]...a[L(i,b[i])] \le b[i]$$$

Yeah, this looks like a more concise way to do it. Basically, in my solution I'm checking the same conditions, just in a more roundabout way (it was heavily influenced by my brute force solution of D1)

I'm curious what is the authors intended solution (it might as well be the same as the one that you have proposed)

236555393 Though I'm not sure about the time complexity.

Hacked. But I think you can optimized it a bit and pass.

I was thinking it's time complexity to be $$$O(n^{2})$$$ in worst case.

Your solution solved my test case in about 6 seconds while most of the N^2 solution takes more than 1 minutes.

That's why I think your solution might pass if you can somehow optimized it.

I did something similar for D2. It barely passed in time lol

Was that for only me initially the diagram for problem A was incorrect?

Yes it was. They could've announced it.

couldn't solve c

even though found case work k >= 3, k == 1, k == 2

too unfortunate

A is miles harder than B and C for me lol (and maybe even D1 but i didnt have enough time)

Wow A was unusually difficult to understand and implement.

Weak pretest on A

Congratulations to the authors for this great round :))

As usual, here is my advice about the problems (not correlated to my performance)

AIt is an SSS tiers div2A ! It's about implementing something simple, there is some idea. The only issue is that I think the picture for the first sample was wrong ? I got a bit confused by it. It could have been better to show the positions from where the knight could fork

BGreat great amazing perfect div2 B ! I find it extremely hard to set a fitting div2 B as it's very easy to set something too hard or too simple. I think this problem was perfect and it felt algorithmic (which is a bit uncommon for that position).

CIt is a good problem. I don't find it that amazing, but again, it requires a small observation (k >= 3) and then some basic algorithmic knowledge (for example binary search) which is, again, not that common !

DI like that D2 had a low score to avoid giving too much points for knowing segtree. The problem is interesting and I think it's quite nice to have an "easy sided" problem with a segtree (a lot of people complain about never being able to apply the ds they learn in contest, this problem is a perfect occasion for it!).

EI find the problem pretty cool, I couldn't solve it in time but it was very enjoyable. (although I think it's possible to bash it with a BOI problem where you maintain a dynamic diameter)

FI tried it for a bit, again very enjoyable problem!

I think the only downside of this round is that the gap between D2 and E was quite high but I don't know if that's a really big deal as usually E don't get that many ACs anyway.

Looking forward to compete in another of your rounds :)

I couldn't do problem A, what a shame.

‘Think of rising higher. Let it be your only thought. Even if your object be not attained, the thought itself will have raised you.’ — Thirukural

in last div-3 I couldn't solve $$$C$$$ sometimes these things happen

Not sure you feel the same. But for me, B > A and C > D. lol

Can you give me an edge case for this solution why it is not working B

In general, I will write a data generator and a brutal force baseline solution to test it. I did that sometimes in the contest (like for the C today), not a good way but the last resort to self-debug.

how to solve c when k = 2?

i tried to take every element of a with the nearest abs(a[i] — a[j]) but it gave wa

Just check all pairs. if you have $$$f = abs(a[i] - b[j])$$$, you current answer must be $$$answer = min(answer, f, \text{first_el_greater}(f) - f, f - \text{last_el_less}(f))$$$. The last two can be calculated using binary_search = std::lower_bound. So $$$O(n^2 \log n)$$$

oh thanks alot i tried to do this in one of my submissions but i was only looking for the adj elements thanks

maybe you can get a zero if any difference already exists

i already handled this by setting the default answer to be min absolute value

make a binary search back in array for that (a[i]-a[j]) to find best move in next run.

ok thanks alot

before it, sort(a),then try every s=(a[i]-a[j]), after it, look for minimize(a[i]-s). every step should update answer.

brute force every possible |Ai — Aj| think of bs

AdamantChicken2 didn't participate :(

I have to say it is a little late for me, but I outdo myself. Unbelievable!!!!

You changed the order of picture of problem A and didn't send a notification. Is it because it's not statement?

Additionally, I feel that the description of the new way of movement of the knight in statement A is inappropriate.

I think we should write statement even someone who doesn't know how the knight in the original chess moves can understand how the knight moves with that statement alone.

I think the current statement is open to misunderstanding.

I left the contest for this reason.. After some min i refreshed and saw the change (:

oursaco https://ejoi2020.ge/static/assets/Day1/Problems/Exam.pdf Problem D is a subgroup of this task

Sorry, we were not aware of this :(

amazing problems! but E and F is too hard for div. 2 (

Nice problemset

is there a hack phase ?

No

Solved D1+D2 just 5 seconds after final :'(((

E is a really standard problem

Can you give a slight hint?

Solve it offline and do a dfs.

When you are in vertex v try to have a segment tree maintaining the distances of other vertices from v.

Anyone plz give the idea of A

Let Sq be set of positions from where queen(xq,yq) can be attacked. (xq+a,xq-b) is one such postion. Let Sk be set of positions from where king(xk,yk) can be attacked.

Find the size of intersection set of Sq and Sk.

True, couldn't find better way to implement this

https://mirror.codeforces.com/contest/1904/submission/236573798

https://mirror.codeforces.com/contest/1904/submission/236576012 :)

why my solution for B gets wrong

https://mirror.codeforces.com/contest/1904/submission/236570576

Couldn’t solve A pajn. Nice problemset tho

Can someone hack this $$$O(n^2)$$$ solution for D2? https://mirror.codeforces.com/contest/1904/submission/236575342

I feel like it shouldn't work.

I hacked it

How can we hack any solution now?

Unfortunately they made uphacking available only for div1 participants (1900+)

SpoilerSkill issue tbh

L

Np, happens

This failed on system testing Submission can anyone tell me what is the mistake? n^2logn solutions were not meant to pass for this problem or something else ?

just changing $$$j$$$ from $$$i+1$$$ to $$$n$$$ instead of $$$0$$$ to $$$n$$$ in case $$$k=2$$$. your code runs in 1400 ms. 236577461

Bruh :) this small mistake took me from Rank 1700 to 2800, Thanks!!

System testing completed for this contest? Any idea anyone?

236573136 I believe that my D1 solution shouldn't work in D2 (tl) on max test like this:

1

10

10 9 8 7 6 5 4 3 2 1

10 10 10 10 10 10 10 10 10 10

But it gets accepted with 187/4000ms

can someone try to hack it with

1

200000

200000 199999...

200000 200000... pls? I have some kind of problem with hacking.

Hacked. Really weak test data in D2.

Thanks TryingToBeEnough!

so....

REALLY weak D2 tests lol

i wonder how many n^2 "solutions" got accepted

Sorry for weak tests. We managed to kill some optimized n^2 solutions during testing, but seems it was not enough :(

My O(n^2) solution works as well, should have submitted during contest :(

https://mirror.codeforces.com/contest/1904/submission/236581716

Hacked. sorry

I had same doubt, many O(n^2) solution worked in D2, example is 236567513

Can someone please verify if it can be hacked too with these given testcases

Hacked.

why problem A is so hard

I think the given picture made it so hard

I don't think it was that hard but I really started lauging when I understood I have fallen into the well set airhead trap...

Didnt particularly like the contest, too structure heavy for me. A-D were easy and E was annoying. C also had a stupid corner that wasnt in the samples and A had the wrong picture. F also looks annoying but ill check edi to see if its cool.

Why do you look at pictures?)

I usually don't look at samples.

My sol was bugged so i thought i misunderstood the problem, it ended up making me understand the problem less.

what was the corner case on C?

For me it was "no operations, the answer is in initial array".

yeah, this

Can someone hack my D1? 236559856

Pretests were damn weak it seems.

Testcase —

5 solves for the first time in a div 2

Why doesnt work? C

got it, if element not present lower bound returns element that greater

Surprisingly good contest! Good job!

It was kind of boring

Hey, anyone can have different opinions

Yes, why not

Not sure why everyone thought B was that easy, I solved it but it took longer than A and C.

if they didn't mess up the photos in A I would have solved it faster, I stared at the wrong picture for 10 minutes wondering if I became so stupid to not understand an A problem after not solving problems for more than 2 months

Maybe B wasn't that easy but you just needed one observation to solve it

Can you give me an edge case for this solution why it is not working B

Great contest! Lost some ratings tho...

Why does my submission https://mirror.codeforces.com/contest/1904/submission/236601220 pass tests? It fails when the difference between two elements is exactly an element in the array. Example:

Input:

Output:

Expected Output:

Seems like missing test cases.

If

`k`

is`2`

and there exist three elements`a`

,`b`

,`c`

in the list such that`a + b = c`

, the answer should be`0`

.Exactly ...

BTW, how did hack it? I tried to but couldn't find an option anywhere.

I heard that it is only open to people with rating 1900+

Can you give me an edge case for this solution why it is not working B

You can try this case

The correct answer will be

thanks for the testcase

Its over boyos !!

[Rant]Instead of submitting the code for D2, by mistake, I resubmitted the code in D1, getting my first skipped verdict.When people see "Skipped", resubmission is not the first thing that comes to their mind. So it would be better if there is a "Resubmitted" verdict.

I often observe that I am not able to solve problems like B which involve the use of an algorithm in which the answer of a next element is either dependent or is made equal to the answer of the previous element by some means...

is this literally a type of problems ? Like after doing problems of which rating range I'll be comfortable in doing such problems ?

I remember some more times when I was not able to solve div 2 B just because of this..

@MikeMirzayanov I have been recently alleged for copying the code as my code was found coinciding to ER_HORIZON_XACS/236530851 and mine was spacedate_xacs/236532464. I know copying code or such coincidence are violation of rules and I have also read the terms and conditions before registering for the round. I am really sorry for such coincidence but this has happened because the account ER_HORIZON_XACS is my cousin brother and we both used same code snippet(made before the contest) for our practice and while round we mistakenly used same snippet too for solving the round questions. I assure you we have made the code differently for the contest round we have only shared the snippet. We are sorry for not caring about the snippet. If possible please return our ratings. I assure we will never do this type of violation again. I also assure we will also use different snippet for solving problems. Please if possible return our ratings.

Yeah we both have shared the code snippet for coding practice and mistakenly used it while contest. We are sorry for that we will not do it again. Please return our ratings.

Bruh both codes are basically the same, the only thing you change are variables. And I think that this account is clearly your alt.

Can anyone help me in a OA? I'll pay

good problem C and D :D

hmm