Hello Codeforces!
We (pwned, ACGN, HappyPacMan, maomao90, Saudi, and trunkty) are thrilled to invite you to Codeforces Round 987 (Div. 2) on Nov/15/2024 15:35 (Moscow time) (note the unusual time)! After more than two years of preparation and nearly thirty problems on our shortlist, our contest is finally here for your enjoyment!
In this round, you will help Penchick as he embarks on a world trip through the Philippines, Indonesia, and even through the Australian beaches and attempt six problems in two hours!
The score distribution will be as follows: $$$500-1000-1500-2000-2500-3000$$$.
This round would not be possible without the support of everyone behind this round:
- maomao90 and KAN for their excellent coordination and problem setting,
- pwned, ACGN, Saudi, and trunkty for the creative tasks,
- HappyPacMan for his amazing technical skills in making the problems come to life,
- Alexdat2000 for translating problem statements,
- PiejanVDC, Syrian, heavylightdecomp, ryuusama, and SlavicG for their unique problem ideas,
- ArvinCiu, irmuun, bestial-42-centroids, dbscts, zscoder, NeroZein, and wfe2017 for their advice in creating interesting problems,
- _Body, ljuba, Dominater069, pavement, Rideris, Error_Yuan, trash-can, GM_Dan4Life, lunchbox, DilshodbekX, SHZhang, micho, Muhammad-Saram, culver0412, ErrorAssassin, AlperenT, iLoveIOI, newb_programmer, mwen, Erering, Friedrich, and AkiLotus for testing our round and providing invaluable feedback, and
- You for being an awesome member of the CF community!
Lastly, we thank MikeMirzayanov for creating the incredible Codeforces platform, where many of us have engaged in friendly competition, honed our problem-solving skills, and forged lasting friendships throughout the years!
From our keyboard to yours, we (and Penchick) wish you good luck, positive delta, and an exciting competition experience!
Note: There is at least one interactive problem, so please read the guide for interactive problems if you are unfamiliar with them.
UPD: Editorial has been posted, go check it out!
UPD: Congratulations to the winners!
Div. 1 + Div. 2:
- tourist, as expected, fully solving all problems in 53 minutes
- antontrygubO_o, who did so just 2 minutes later
- noimi
- A_G
- Pyqe
- StarSilk
- dyppp
- kotatsugame
- busamate
- tarjen
They, along with 8 other contestants, are the only AKers (full-solvers) in the whole contest!
Div. 2 only:
- LGlcx, who full-solved in 100 minutes!
- Sky_Maths
- G2Esports
- boboquack
- ac_de_taffy
- Jack.YT
- Alex2184
- MrPizza
- priyanshu.p
- CC_cccc
We hope you all enjoyed the round!
pwned orz!
Omg “highschool CPers” CF round!!! Expecting an interesting problemset!!
Yes, the Highschool CPers (HSCP) CF round has finally come to fruition!!! We hope you like it!
It's funny how we've graduated highschool since the proposal of the round lol
uncs
not all of us are studying in CS
- me, a med student
u fr an unc if you dont know what unc means
:penchickpride: pwned orz!!
:pinoypride: penchick pwned orz!!
I waddle for the fish!
pwned orz!!
As a taster, I found the problems very delicious
So true, the flavortext is very delicious! Especially the diverse cuisines and dishes featured in the round!
I admire you, testers. It looks like this round will be cool. I'll give it my all this round.
hi orz ppl @pwned @culver0412
i will definitely join! :penchickcheer:
As a tester, maomao90 is gay
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
As a setter, I'm surprised Penchick hasn't had jet lag yet.
pwned orz
excited for penchick-pilled round !!!!! (pwned orz)
As a tester, I'll let you in on some facts:
GL&HR!
your guy looks so professional
as a participant, here is an obligatory penchick image that nobody has posted yet
After more than two years of preparation and nearly thirty problems on our shortlist
Couldn’t be more excited to get into this
Excited to participate, pwned amazing!
As a tester W round
As a unique problem idea-er, W round.
as someone giving their advice in creating interesting problems, please upvote
As a participant, I love Penchick!
As a participant, i love high rating
As a participant, I read all the comments and wondered why only one peng' has orange beak and why are the 2 rubik's cubes having 2 different "**shades of green**" ?!
duckforces
Hoping for the best Div.2 Round! Btw, the penguins are cute <3
penguinforces
So excited,hope that the problems are as cute as the announcement and the penchicks.
As a tester, good luck and
How'd you make the emoji?
Penguiiiiiiiiiins
"Why is there no Div 4? The last one was 1.5 months ago..."
You for being an awesome member of the CF community! The "You" of this sentence is surprising!!!!!!!!
As a tester, after creating six problems for us, Penchick is now resting peacefully.
i will get another positive contribution with this comment
As a participant, I am not a tester.
Hope to comeback CM after this round.
Good luck! Also I hope to comeback S after this round
orz
omg NeroZein mentioned
Masters Masters Everywhere.
I think "note the unusual time!" should be bold and large font like
note the unusual time!
Oh,this Penchicks are so cute!
As a tester, did I come late? I kept asking Penchick for the delicious feast and almost forgot the time for this round.
Finally, a plush toys photo session in round announcement <3 Thanks, guys!
Penchick
I'm back :)
Very cute!
what are penchicks?
very good unusual time, very scary interactive problem, like from porcelain
NO way C is a real problem
https://mirror.codeforces.com/contest/2031/submission/291653468 what's wrong with my submission ?
It's possible to solve the problem for all n > 25. (Using the 3, 4, 5 Pythagorean triplet)
Can you share an example for n = 27?
1 3 3 4 4 5 5 6 6 1 2 7 7 8 8 9 9 10 10 11 11 12 12 13 13 1 2
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 1 10 11 11 12 12 13 13 9 1 10
This is true SpeedForces.
i choked really hard today. C is the worst C i ever met in a div 2 too
Anybody forgot $$$3^2+4^2=5^2$$$ in contest? Note: I spent an hour remembering that lol
Lol I had to spend some time remembering.
i remembered the pythagoras but im too dumb
i just spent 30 minutes searching for a mistake just to discover that i wrote cerr instead of cout
is D a graph problem?
edit : can you give some hints
Yes.
How did you solve it as a graph problem? I used
a monotonic stack
I used a segment tree can you share your logic
Can you explain your Solution
just as said in the problem you can travel to larger elements in the left
so first i calculated the prefix maximum for the array this will tell you what is the largest element that you can travel if only first operation is allowed now i created a segment tree that can give maximum in any range of array , then traversed the array from right to left
if i am at an index i what is the value that i can reach anything smaller in the left from 1, prefixmax[i]-1 (as going to the prefix maximum will increase the scope of traversal in left ans the result will be even larger) so just calculate the maximum for this modify answer[i] with max(query(1,prefix[i]-1),prefix[i])
I used DSU too, but basically I maintained a monotic stack for the heights of the trees, where $$$a_{i-1} \le a_{i}$$$ for all entries of the stack. I also stored the array index in each stack item. Then, I looped through the whole array, starting from index 0, and for each iteration, I popped the top stack values if their height is greater than that of $$$a_i$$$, then made a union of (i, index of top value) since you can jump to $$$a_i$$$ from wherever the earlier value is. However, I also stored the largest height popped and returned it back to the stack after all the pops, so that the resulting union can add more entries in future iterations.
To get the answer, I created an array res[], which contained the query for the i-th tree, with default values as the array values. Then, when performing a union of (i, j), I set the value of res[i] to max(res[i], res[j]), since you can reach either max height
I used dsu and set. Iterate from left to right, and for current val, all the left side larger than the val should be connected with current val (and we can do this recursively with dsu.find).
At least my solution has nothing to do with graphs.
plz provide enough test cases
Sometimes there is a deliberate shortage of provided test cases since otherwise the pattern to the problem would be obvious. Few test cases often indicates you just need to find a pattern yourself by working through some examples.
What is the solution for odd in C ?
$$$n \ge 27$$$ always works.
n>=27*
Ah, my bad. True.
I realised this that 3,4,5 is the smallest pythagorean triplet but could not construct it
1 10 26 can have same fillings as they have diff of square of 3,4 and 5. Also, we can set 27 and 23 with same fillings. Now we are only left with consecutive even length numbers {2,9}, {11,22}, {24,25} and {28, inf}. Set every 2 consecutive numbers with any same fillings [2,3] [4,5] [6,7].....
how for n==25
my code get AC for n>=27
Yeah, it was a mishap in my mind. Edited to 27.
there is a fixed pattern of length 27 291641087 in odd cases and then the remaining part becomes even.
Asking for the same :(
"1 3 3 4 4 5 5 6 6 1 2 7 7 8 8 9 9 10 10 11 11 12 12 13 13 1 2"
works for 27 and beyond
In your solution, 3 3 are adjacent while there distance is 1, How so?
1 is a perfect square
OK, I should visit KOTA(suicide Center) now :(
Just hit the gym, watch some anime and you will be fine.
Real hit the gym!!
Your physique tells everything about you. Respect ++ Although I have seen one your solution in Edu section .. maybe in Binary Search course if I am not wrong.
I literally implemented with the similar doubt. Actually the problem becomes quite complicated if the solution excludes similar adjacent elements.
Exactly :(
I challenge you to solve the problem when adjacent elements aren't allowed (i.e. you cannot use $$$1$$$ as a square)!
Yes, I have solved this exact problem in the contest. Here are some observations I've made; please correct me if I'm wrong:
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 10 11 11 12 13 13 1 12Observe if we can have a
Pythagorean triplet, where x^2 + y^2 = z^2then the odd case can be done easily, and the smallest Pythagorean triplet = (3,4,5) so the gap should be minimum 25, so if start with 1, then last value should be >=26, and the smallest odd number for which it's satisfied is 27. Sofor all odd values >= 27we can have a valid possible ordering.what was the distribution technique for question 3rd... I thought of pairing in 2 because their difference will be 1 which is a perfect square but for odd N, i paired index 1 10 and 26 as their difference is also perfect sqaure.
Anyone ? whose solution got AC ? Thanks !!
with this approach you get a dist of 2 between idx 25 and 27 since there is gonna be an odd number of elem between 10 26.
Is this correct for F? I was not able to submit it due to the fucking internet
Did thought about pythagorean triplet, and still choke at problem C.
Double the pain again.
So can we find out a valid filling when n<101 and n is odd?
Yes, It is.
I completely miss it
the B problem has an issue with python solution did you ever test it with python? i always get TLE
We tested it and it works on our side. Not sure what went wrong with your solution :(
I submitted your solution in python 3 and it works. 291715567
sorry i cant acces your link
and i resubmit again my solution 291721673 still got TLE
Use Python 3 instead of Pypy
I submitted E in the last 10s of the contest but unfortunately got WA.
Anybody got an idea why this got WA on pretest 23?
floating point inaccuracies can accumulate; floats are not accurate enough for this problem, you need an exact way to solve it.
Man that's such a pity! I could've solve it >_<
Why does cpp23, cpp20 and cpp17 give different results for these solutions??
291657006 291656787 291655971
nvm, overkilled it, realising it now that it could've been solved in a much more easier manner T_T
Haven't looked into the code yet, but if the same code gives different results in different compilers, there's a good chance that it's undefined behavior and some hidden errors.
yeah, tried looking for that, couldn't find so pasted the code here
I really thought I would end up screwing up this round because I spent way too long on B, but I pulled off C and D quickly enough :D
Did anyone else get Runtime error pretest 61 on E? Sys tests aren't happening and the suspense is killing me T-T
Imagine getting RTE on pretest 61 because you declared a priority_queue local instead of global.
local, RTE: 291650692
global, AC: 291666454
local, AC: 291685566.
My solution:
[D]
Observation1: note the maximum value as mx, and the number to the right of mx will definitely reach mx.
Observation2: if a[i]>min(mxpos,n), all a[i,...n] can reach mx.
So we can maintain a variable pos and continuously execute the following process:
pos=posmx initially.
find min i (1<=i<pos) such that a[i]>min(a[pos,...,n])
update pos:=i, or break if no such i
So we found a suffix that can reach mx. Then recursively solve the sub-problem.
[E]
Consider reverse operation: add nodes from the given tree to make it a perfect binary tree.
DP. Note dp[x] as the minimum depth at which subtree x becomes a perfect binary tree.
Observing the process of adding nodes (from leaves to roots) is actually a classic Huffman tree.
So we can use greed+priority queue to process dp [son[x][i]] to obtain dp[x].
I did same thing in problem D. Here is my submission 291639130
Why is there such an important change in E so much later into the contest??? I was already working on the solution according to the problem statement by then, trying to write this complicated re-rooting dp code, and after submitting towards the end of the contest notice this change. How is this fair?? Please make this contest unrated.
The roots of the trees have always been well-defined in the statement. The binary tree is rooted by definition.
The clarification was made to point this out, and didn't change the statement.
What do you understand from this statement — "Since Penchick and Chloe are good friends, Chloe wants her tree to be isomorphic to Penchick's tree"? I don't know why whould you change a well known definition for your convenience. Please make clear problem statements.
We did not change a well known definition for our convenience. The two trees are rooted, and rooted isomorphism is defined exactly as we did in the footnote.
Footnote 2: A full binary tree is rooted tree, in which each node has 0 or 2 children.
Combined with
Footnote 1: A rooted tree is a tree where one vertex is special and called the root. The parent of vertex v is the first vertex on the simple path from v to the root. The root has no parent. A child of vertex v is any vertex u for which v is the parent.
Is sufficient to define that the root of the binary tree is the top-most vertex.
The root of Penchick's tree is defined as 1 in the statement "... with vertex 1 as the root".
In footnote 3, isomorphism of rooted tree is clearly specified "Two rooted trees, rooted at $$$r_1$$$ and $$$r_2$$$ respectively, are considered isomorphic if there exists a permutation $$$p$$$ of the vertices such that an edge $$$(u, v)$$$ exists in the first tree if and only if the edge $$$(p_u, p_v)$$$ exists in the second tree, and $$$r_1 = p_{r_2}$$$."
Hence, there are no issues with the original statement.
D can be solved with dsu. For each point, merge it with the point to the left of this point and with the highest height, and also merge it with the point to the right that is farthest away from it and with a height smaller than it. The answer corresponding to the set is maintained while merging. It can be shown that this merging is optimal.
Is there any reason for the memory limit to be smaller than the size of the stack for max N in python? I had a very inelegant solution to D that failed due to stack not fitting the memory.
Actually, there's no easy way to expand the stack size of Python on Windows, as the Python executable is already compiled with the default stack size (1MB, IIRC).
eee you can,
sys.setrecursionlimit(10**5)increases memory usage so I suppose also the stack limit, but with 256MB you can fit just about 10**5 and N is 5 times more in D.That function increases the internal recursion limit, but it does not expand the stack size of Python runtime.
For example, running the following code with custom invocation will give you a stack overflow error (both in PyPy and Python). This means Python can't handle recursion calls nested just 10000 times, which indirectly shows Python runtime's stack size remains small even if you call
sys.setrecursionlimit.C and D were interesting
All problems here are bangers!! E is my favorite, but F is cool as well
comeback CM now (probably)
indeed
How is it that suddenly 2000+ people solved C problem in the last 20-30 mins? Hope the cheaters are found and removed!!
Will I get back to 1900 after rollback?
Of course, I will
https://mirror.codeforces.com/contest/2031/submission/291676661
Can anyone let me know why my solution for B is wrong? I cannot find any edge case for this.
Please let me know why my solution is wrong, thank you very much
When $$$n=1$$$, you didn't read the input array, which causes the testcases afterwards to be shifted.
I spent so much time trying to figure out what is wrong with the algorithm LOL; never forget to read everything from cin before outputting the answer
So many new accounts on top positions :(. One has to improve if they want to simply keep their rating (otherwise they will be in an equilibrium rating lower than their “true” rating. Maybe this is not a problem if the amount of Smurfs is constant between contests, but I feel like this one has quite a lot)
Making $$$2 \le k \le n$$$ i.e., asking subsequence of length atleast $$$2$$$ will make the problem $$$F$$$ as troll D2C ig ;)
Good contest, thanks.
Also the problem F is amazing.
Congrats to programpiggy for finally reaching M!
Thanks for the contest! Participated virtually. Love problem C!
There is a cheat alert sent to me says that my code is similar to other codes (about 12 or 13 person), I didn't do that but of course my code will be similar it's an idea and it's my implementation for it of course another person made the same. So please let me understand what's your point of view. finally sorry for inconvenience.
Orz maomao90