Hello, Codeforces!
We are pleased to invite you to Pinely Round 4 (Div. 1 + Div. 2), which will start on Jul/28/2024 17:35 (Moscow time). The round will be rated for everyone.
You will be given 9 problems and 3 hours to solve them. There is at least one interactive problem, so please read the guide for interactive problems if you are unfamiliar with it.
The problems were authored and prepared by me.
We would like to thank:
- errorgorn for the excellent coordination.
- dXqwq, StarSilk, strapple, Endagorion, JCY_, jiangbowen, QwertyPi, chen_zexing, YocyCraft, zeliboba, HackerMonk, axs7384, Vladithur, davi_bart, prvocislo, leinad2, Andyvanh1, stasio6, hychyc, bitset, bonopo, Mucosolvan, RandomLB, CSQ31, Myrcella, NamelessOIer, guapisolo, Enigmurl, satyam343, Vingying0, qinyuzhou, 7oSkaaa, GeiselLibrary, EpicChadGamer, AXXWTGST, and pengrui for testing the round and providing valuable feedback.
- Alexdat2000 for translating the statements to Russian.
- MikeMirzayanov for the great Codeforces and Polygon platform.
We hope you will enjoy the round!
Score distribution: $$$250 - 500 - 1000 - 1500 - 2000 - 2500 - 3000 - 3500 - 4000$$$
The editorial is here.
Congratulations to the winners!
This round is made possible with the support of Pinely!
Pinely is a dynamic algorithmic trading firm with a presence in Singapore, the Netherlands, and Cyprus. We specialize in high-frequency and ultra-low latency trading. Our team of mathematicians, programmers, engineers, and computer scientists tackles everyday challenges like developing trading strategies, optimizing systems for minimal latency, saving and processing large volumes of historical data.
Working at Pinely demands exceptional C++ coding, algorithmic thinking, and mathematical intuition, attracting top talent, including winners and awardees of such competitions as ICPC, IMC, HITB PRO CTF, Google HashCode, etc.
Learn more about us on our website or find our employees on CF. To join our team, please send your CV to hr@pinely.com, even if you are not participating in the contest.
Prizes: The top 30 contestants will receive a branded plush pine tree!
Hope I can get back to the blue in this round!
UPD: I will try again =)
I believe in you, La Pluma :)
shitty problems
same
rooting for ya
Good luck to you!
Hoping for a good contest！
Hoping to lock in the day of the round! First this Codeforces round then Teamscode! Good luck to everyone on all of the contests!!!
First reaction: wow the plush pine tree is so lovely, but I can't reach the top 30 :(
Then, after some searching: omg it could be found in amazon.
i didnt know i needed a plush tree until now
i didnt know i needed a plush tree until now
Why people on codeforces are so childish?
what? do you want us to be hard or smth
what do you mean? 80% of redcoders in cf are underage
As a tester, I tested the round.
Did you get any compensation for no longer being able to compete for a plush pine tree?
Very nice round. I am a little bit upset because I tested so I could not participate officially.
You can if you are Psychotic enough :D
lmao
Is that a reference to someone called "Psychotic" or what does that mean?
It is a reference to Dhruvil Kakadiya who was international master from India who used to set the questions and participated in the contests. This way he even got global rank 2 once (imagine an IM getting above many LGMs). His username was PsychoticD
As a participant, hope everybody good luck and win lots of pines!
If the same comment was posted by some <= green, it would have 0 upvotes or maybe negative.
Hope I can reach pupil :)
All the best! I believe in you!
All the best Guys:)
As testers, jiangbowen and I tested the round.
Why downvotes? Of course they are not the same person or Mike would have already banned one of them.
Orz wmh.
Why more downvotes? Orz wmh.
This round will contain some really challenging problems ig :)
As a participant, I will participate in the round.
I really want to be a specialist, hope to get a positive delta :)
samee, good luck!
Never be desperate for rating else you will be under high pressure, just try to give your best .
agree
first contest as a pupil, hoping for specialist after this one!
Hope I can solve 4 problems!
Every time I see any Chinese coder from Zhou dynasty my mind reads Zhou Guanyu (avg F1 fan me :-))
Hope the race gets over before 8pm tomorrow so i don't have to skip this contest :<
Congrats to Russell and see you on the leaderboard :)
Scoring distribution when?
do you mind explaining how you can benefit from scoring distribution? isn't the best strategy to always solve problems in order?
For example, if D and E give same score or small difference and you don't like D you should probably read E to not waste time. Or generally just to see expected difficulty difference between problems.
thx
Stop interactive problems :(
Indeed, interactive problems are interesting:)
I have a question There is an indicators array of size n and corresponding profit array of size n. We have to select indicators in such a way that their bitwise or is <= k while maximising the profit. n<=1e5 k<=2^30 indicators[i]<=1e9 profit[i]<=1e9 Can someone provide an algo?
isn't it just, we take out the indicators which have only those bits set which are set in k and then add all the profit? since its bitwise or it should always work
No, because the bitwise or can be smaller than k also, so not all bits will match
isn't that what you want? you wrote bitwise or <= k
No, I want the profit to be maximised say k is 1111 in binary then may happen na that an indicator is 1111 but its profit is less than that of three other indicators which are 1,11,111
you can take all the indicators. for e.g. here you can take all
speedforces loading...
Hoping to become green after this round
tourist will win this round : )
Too difficult for me :(
same
same for me as well
Staring at D for 2 straight hours
same. Tried a few things either TLE or MLE :)
feels like your pfp
Why so many boring detail Problems ???????
There's no interesting idea in A-F !!!
ARE YOU CREATING CHINESE COLLEGE ENTRANCE EXAM'S MATH PROBLEMS ?????
the best guess I made in C is that the best next step is x = sum of array / size of array
it seems to work but I'm getting wrong on test 2 so it's maybe not optimal
It doesn't work the best is actually x = max(array) / 2
I just hope that someone can tell us why and not just like most of the time where it's just a pure guessing
Intuition is that you keep halving the biggest number — because smallest cannot become than x -, meaning that eventually everything will become 0 (as long as parity is equal and you choose ceil(max/2)). It will also take log2(initial max) steps.
I did the same :(
Can someone please tell me what is wrong with this solution for problem E. If the graph is bipartite I play as Bob and just greedily color the graph, otherwise I play as Alice and spam "1 2"?
your solution is mostly correct but when you play as bob the greedy is a bit more complicated
Can you elaborate?
let S1 be the nodes that you will color 1, S2 be the nodes that you color 2
what would you do once you color all nodes in S1 (or S2)
if you just fill S1 with 1 or 3 then S2 would be a really chaotic mess of 2s and 3s that might fail (and vice versa)
to be more specific, once you color all the nodes of S1 then alice could just keep sending "1 3" and if S1 contains any nodes that's colored 3 then that's WA
Yeah, but the hardest case is if the interactor only plays the same 2 numbers, if it plays the third, even easier. I colored it in the same way you check a graph for bipartiteness. I can't think of a counterexample
then you could just pick all the first numbers into S1 and all the 2nd numbers into S2
you should've spammed "1 3" I think
What is the difference lmao
1 3 is lexicographically larger than 1 2
doesnt change anything
I hate constructives so much now
To continue the streak of "unconventional solutions", now with today's D:
1 2 3 4 1 2 3 4 ...Did you mean problem D?
Edited, hehe. I think I was absolutely drunk~
it was really just that?
Yes. I actually came up with a proof (sorta) before doing that.
If you don't mind, can you please share?
Nodes $$$u$$$ and $$$v$$$ if sharing the same parity will have an edge only when $$$u \oplus v = 2$$$. The remaining edges are always from one parity to another, i.e. virtually bipartite graphs. For large enough $$$n$$$, each parity will need $$$2$$$ colors, and thus maximum colors should only be $$$4$$$. $$$n = 6$$$ already reaches $$$4$$$ as most optimal ones, therefore all $$$n \gt 6$$$ should do the same.
my solution was:
observe that odd verticies will only connect with even verticies
with the exception of u^v = 2 -> just alternate between a and a+2
tho there's the edge case of n = 3
so turns out the output still ends up as 1 2 3 4 1 2 3 4 1 2 3 4 ...
Pretty much the same problem as E: 1503B - 3-Coloring though it's probably just a coincidence.
Regardless, I really enjoyed the round!
D is the worst problem I've ever seen in my life.
can't agree more
Here's my thought process for C: Absolute Zero.
$$$10^9 \lt 2^{30}$$$. Therefore, either the constraints are bluffing and the optimal number of moves is very small (like 3-5), or the solution involves some binary searching like idea (where you keep on trimming the range in half).
Even if the constraints are a bluff, let's explore the binary search idea. If they want you to trim the range in half, what happens when you select the midpoint of $$$[0, 10^9]$$$ as the first $$$x$$$. Notice that every point can be at a distance of $$$mid$$$ on either side. Therefore, the maximum array element has been reduced by at least half. If you repeat this process 30 times by taking midpoint of $$$[0, max]$$$ (and let's do it 39 times instead just to be sure), then at the end, the array would contain identical elements. So you can use the last operation to subtract that identical element to convert it to zero.
Code
How to solve problem D?
The rough approach for E and F felt way more obvious to me, I've got zero intuition for D after trying it for 30+ mins.
The only odd cycles in the graph must include pairs $$$(n, n + 2)$$$ where $$$n \oplus (n + 2) = 2$$$. So, removing just these edges, the graph is bipartite with the two sides being the parities. Then, we can 2-color each parity since the only edges between vertices of same parity are those of the first kind. This gives a 4 coloring for all $$$n\ge 6$$$.
Oh wow, that's actually a really cool solution. I completely missed the importance of 2 being the only even prime even though I analyzed cycles for edges of 2 and 3...
D is one of those problems (that I hate) where the solution is really simple but 99% of coders are unable to prove the greedy algorithm. For $$$n\leq6$$$ we copy the sample solutions. For $$$n\geq7$$$, we take the periodic sequence $$$1, 2, 3, 4, 1, 2, 3, 4, \dots$$$.
PS can someone share the solution for E?
The solution is very simple and stupid. I also wandered in incorrect direction for some time.
1 2 3 4 1 2 3 4 1 2 ...$$$a \oplus (a + 4k) = \dots 00$$$ which is divisible by $$$4$$$ and hence not prime.
D much harder than E??? I stare D at 90min, while I spend 15min solving E.
D > E, F in my opinion, the starting point for E (non-bipartite are definitely winnable for Alice) / F (answer is always yes for arrays with $$$\gt 63$$$ elements for $$$a_i \leq 10^9$$$) is fairly obvious to me.
But I just spent ~30 mins working out cases and trying random stuff on D with no luck.
D makes me feel stupid. It's so simple but somehow I used 1h.
[deleted]
how it feels to have no idea what the solution for D is after 2 hours of solving it:
F: Ancient Japanese knowledge is now blooming...
UTPC2011-G
Why is k = 1 and k = min(n,m) allowed in the input for G? It's just more stupid casework...
EDIT: Looking back i was just salty. The problem is fine, my code was just impossible to debug. Just recoded it today and it worked relatively quickly
I have no casework in my solution. I actually had two WA2 from trying casework on K = N
Few samples for harder problems!
Problem E has only two samples with $$$n=m$$$, so when I made a mistake in my code(it plays $$$m$$$ rounds instead of $$$n$$$), it passed the samples and got wrong answer on test $$$2$$$! Spent two minutes staring it out.
Problem F,G both have only one sample??
For problem F, here's one similar problem (similar trick) on luogu, and it's in one of the recent contests.
For problem E, can anyone explain why 273228602 fails on Test case 1 (second test), even if my output matches for second test matches with the output given in the problem statement.
Code Link
Can someone give me a hint for D (not the solution)
the answer is very small
hey Tourist why you so smart,
the way you solve problem is just pure art.
How are you so fast
You come first, I come last.
glaze of doom
Problem E is a repeated problem Original Problem
I think the idea is just a somewhat intuitive approach that keeps popping up for this kind of problem. For example, this problem is an even earlier problem I set that uses the same key idea.
At the time I came up with it, I hadn't seen any problem use this approach before, but since then I've seen multiple other problems use the exact same idea of "3-colour bipartite colouring with restrictions on when / how many times you can use a given colour".
n=1 on E was hell to debug for 2 hours, this is the worst i've tilted since this round lmao
ConstructiveForces
A<B<C<E<F<D ???
A<D<B<C<E<F. Thus averaging out to intending difficulty.
GuessTrickForces :(
Thank you for the round!
what was C? and why am i getting WA in this
In this case: 1 1 0 Your code would output 1 0 but the correct answer is 0.
Poor experience
Feeling quite retarded , not able to get old form back. That's the thing with CP... if we stop practising. Performing in contest is a different skill. Anyways CP is best.
G is a great challenge to the player's guessing ability. But I don't like it. ()(())
This Round is the worst round i have ever seen
Where is $$$998244353$$$? X(
The fact that both H and I are solvable surprised me a lot. Strange feeling. Thanks for the preparing the round!
Thanks for the round! Maybe the best round in this year!
ofc no. The best are Tractor rounds
I really hate problem of D kind
guess until get it right
interesting constructives early on.
can some one tell the reason for problem C approach or what is your thinking process
Think of a set of points with different height, and you are trying to draw a line in between them. If you drew perfectly and mirror the points below that line (which is literally this problem), you'll see that the maximum height difference between any two points will be halved.
How do you know that if it is going to converge to 0 ?
We can quickly halven until the maximum height difference being at most $$$1$$$ (never going to take more than $$$40$$$ times). If it is $$$1$$$, it won't converge (drawing a line between two consecutive height is invalid as we're only allowed integers). Otherwise, it will.
Can you tell me how we can think like this during contest.
I simply guessed subtract sum(arr)/size(arr) as it was giving correct output for given samples and also, for most of the testcases this guess was correct but got WA on testcase 2
Refer to my root comment, that was how I envisioned the problem. Absolute values on differences feel like a mirror and/or interrupting borderline to me, so that idea just comes naturally (also perhaps given the fact I used to learn basic linear regressions before, so the imagery was engraved).
Taking 1st and 2nd max element each time and doing operations each time with the average of both, will it work in 40 operations? Or will it work ever irrespective of number of operations?
0 0 5e8 ... 5e8 1e9 1e9This test will make you loop indefinitely.
humorous problem D
Thanks for speedforces and cool problem G, enjoyed the round!
A sample test with $$$\min(n,m)=k \lt \max(n,m)$$$ wouldn't hurt in G. Very silly bug.
As wouldn't $$$k = n = m$$$
ZhouShang2003 Is there any issue with problem E? I was getting WA in pretest1 but now it is accepted?
is there some bugs in judging system of prob E? Somehow my E become AC after the contest ?
Same for me
I just spent 45 minutes crying and finding for a bug in vain, feeling completely meaningless
when does it get ac ?
idk, when I was crying after the contest, it suddenly became AC somewhen
can u check my code plz ? i also cried tho its regular event xD
nb: I commented my soln below 2/3 comments
Same here :/
Human intelligence round
if you feel so, then problem D makes me Idiot of the century.
I went to color the graph greedily, and messed up.
To get constructive, I built a graph for n = 20,
Then I started colouring the graph greedily.
Then I went to node 3, and node-3 is connected to node-1 ( we are checking colors from node 1 to node (i-1)). So, I assigned node-3, also color-2.
And this is where I went wrong :( . I was getting answer 36, for n=2054. and was trying to find pattern here :( .
Honestly, kind of demotivating D problem.
I know that any planar graph is 4 colorable, but this is no planar graph :( .
why it is wrong ?
idea: odd cycle: alice else
even level fill by 0 and odd level fill by 1. if any level full others level fill by 3.
try this case:
1
1 0
1 3
I updated my soln. can you check again plz ? this soln handle of case n=1 ig
thanks btw
upd: got it. thanks
E was amazing!
nice contest
This round wins the "Cutest prizes" title
construct, construct, construct...
Can anyone help me find out why my 273201975 on 1991E - Coloring Game received a WA verdict, Checker comment is "wrong answer Integer 3 violates the range [1, 1] (test case 19)" :)
Your code can't handle the case when there is only one vertice. Try this:
1
1 0
1 2
Update: I figured it out with the coordinators. It seems that most people affected by this are already taken cared of, it is just that most code ends in WA and I got hit with TLE so it was missed.
ZhouShang2003 I am having the same issue in problem E.
TLE during contest (50+ of them) AC after contest, codes identical.
TLE code in contest: 273157246, AC code resubmission 273253391. Please check that the code are identical.
Please look into the situation,
Far more importantly, please clarify what made the differences and so I can avoid running into it again: If the interactors or test case 1 had been changed between the contest and after systest.
Plus please consider un-rating the affected people. I lost at least 30 minutes and all my momentum and mood, (in fact I think I would have gotten at least a moderate positive delta without this).
https://mirror.codeforces.com/blog/entry/124418
arvindf232 = bruhopen (= FastFreeTask)
I see, you certainly have the right to be unrated.
Clearly I made no attempts to hide that, when I link my submissions from main. Though, I think it is the right time to make a quick comment why I choose to use alt even well aware of the single account policy.
It is a combination of a few things:
Firstly, codeforces have nonzero incentive for staying at >=3000 rating that is LGM. You can say that no one cares about ranks and colours but it is there, and I do care, and I believe many do. In fact I care about it a lot. Everything that follows will seem nonsense if you don’t believe 3000 is something meaningful, so please bear with me
(It is the only final goal of CP, if you don’t count dethroning tourist etc.)
After my second ICPC world finals, I decided that I have to focus on my studies. If my studies do not work out, I basically have to quit CP for a decently long time, even if not, I cannot train for CP seriously competitively for two years or so.
My current rating in this retirement state is somewhere between 2900 and 3100, I don’t know because I did not play enough rounds. A safe bet would be 2950 now.
At my prime, this would be closer to 3100, so there is less risk of losing LGM — and if I lose it I do deserve it, by either a very bad round or just not actually maintaining a good skill above 3000. I am fine with losing it if I am currently seriously looking for improvements in CP, that just means an impactful lesson (I did lost it a few times across the 3 accounts). However, I don’t want to lose it just because I cannot spend time to maintain the same level of “not rusty”, especially when I have proven I can hold it with ease when not in rust.
Therefore the idea is simple: I just play on bruhopen when I am in “retirement state” and on this account when I am serious and aiming for improvements and even higher ranks. I just keep the two records separate, which they really should be. I wouldn’t hesitate to play on an “unrated” option if there is one, which is supposingly being implemented but it is not happening yet.
This is the current reason why I chose to play on bruhopen. This was very different from the reasons I play on FastFreeTask in the past, those reasons do actually seriously violate the spirit of the blog so I stopped doing that.
I think the harm done to the community by this action is within manageable magnitude, for the following reasons:
I am actually not top 50:if I were comfortably top 50, I would be far away from the 3000 line that I don’t have to worry about it. There shouldn’t be much impact on the rating list you see on the right.
I only talk and play on unrated round on my main account( this one). The above is an unfortunate exception because I need to signify it was this account that I had an in-contest submissson. I am not trying to hide the fact that I have multiple accounts, it is just not actually useful information for anyone so there is no reason to bring it up.
In terms of rating dist(arvindf232,bruhopen) is actually very likely within 100. It is simply unfortunate that this difference cross the 3000 barrier that makes it an issue for myself.
(Plus the usernames are cool ok? My main name have to stay serious but I definitely want to use other names)
Therefore I will stop using alts altogether when i can be 3200 at my prime = not losing LGM even when rusty = firmly step into top 50, but that day will have to wait because I don’t have time to train on CP.
Finally I didn’t actually care about rating, rating on this account is inconsequential (cool if it hits 3000 though), and unrating it is just a consolation (recalculate submission time for E and remove 30 minutes of penalty for F and G, I am already at +50 delta, not counting the impact of momentum and losing opportunity to do H). It is just that rightful requests should be made.
How did you make D's checker?
You can use xor convolution to check each colour, so the time complexity is $$$c n \log n $$$, where $$$c = 4$$$ is the number of colours.
A naive checking in n * number of primes would be $$$4 * 10^9$$$ roughly (2e4 primes less than 2e5), it is possible that this is fast enough as is.
Sorry for the coincides but i don't know about that I don't no zhe ID is others but i have not copy any code of the problem 1991C and 1991B this is just a coincidence i don't violate any rule of the contest and the codeforces so pls give my rating back and consider my solution for the contest.
Do you mind explaining why did you put 11 unwanted for loops in this Submission
Because I know that I mixed up the code, submitting it again would lead to skipped, so I naively thought it could be done this way.
Could anyone explain what happened to the rating changes from this contest? On profiles of contestants, ratings are updated, but in the "rating" tab, they aren't, even though they used to be at some point. Colors are updated everywhere, including the rating tab (which leads to strange situations like mine, where the rating tab shows me as a pupil with a rating of 682). Thanks in advance.
EDIT: The ratings on the ratings tab are back, ignore this now
EDIT 2: And they're gone again. Really confused now.
EDIT 3: About 5 minutes ago, the rating changes were applied on the ratings tab again, and now they, again, aren't. What? (also, not going to bother with edits anymore when the situation changes as often as it does)
D is interesting... took my 2 Memory limit and 1 TLE to figured it out.. Thx
greedy round. but it's so intersting!