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 Dec/09/2023 19:05 (Moscow time). 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 :)
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.
rainboy enters the chat
Brooo 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
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?
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.
what does (1250+750) mean?
Problem has easy and hard versions.
oursaco orz
Mokuroh54 orz
the unusual time note was very helpful
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).
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.
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
Bruh without Chinese it's only 3500 people
Is that really div.2!!
its so tough
C>D
Cool problems, especially $$$C$$$(with idea that we must check only $$$K \leq 2$$$) and $$$D$$$.
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?
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)
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)
It 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
Great 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).
It 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 !
I 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!).
I 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)
I 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)$$$
make a binary search back in array for that (a[i]-a[j]) to find best move in next run.
brute force every possible |Ai — Aj| think of bs
AdamantChicken2 didn't participate :(
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 :(
Only now I realized that I attached a link to the wrong task, but I can’t find the right one...
amazing problems! but E and F is too hard for div. 2 (
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 :)
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?
Skill 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
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
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
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
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
kis2and there exist three elementsa,b,cin the list such thata + b = c, the answer should be0.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
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.
Bruh both codes are basically the same, the only thing you change are variables. And I think that this account is clearly your alt.
good problem C and D :D