Hello, Codeforces!
This Saturday VIII Lipetsk Team Olympiad, a competition for high school students from all over the country, will be held in Lipetsk. Maybe you participated in previous Codeforces rounds based on our problems (rounds 643 and 791).
The round will start at Apr/15/2023 12:05 (Moscow time) and will last for 2 hours. Please notice the unusual time. Each division will have 6 problems. The round will be held according to the Codeforces rules and will be rated for both divisions.
Problems were proposed and prepared by Um_nik, DishonoredRighteous, FairyWinx, golikovnik, teraqqq, grphil, Kon567889, TeaTime, Tikhon228 and dshindov.
I would like to thank Artyom123 for great round coordination and our testers: Ormlis, bashkort, Umi, I_LOVE_ANTON_DONBASS, Egor.Lifar, iakovlev.zakhar, Mangooste, Siberian, SomethingNew, stepanov.aa, talant, rt3, towrist, Aaeria, Alexdat2000, qxforever, Renatyss, Renedyn, sevlll777, towrist, valerikk, Tiagodfs, wiz_cs, Setsuna, ezraft, Gornak40, HunterXD, kbats183, Nathan_McKane, nik_sn, Nitelike, Tilt, ak2006, KiruxaLight, 9kin.
Of course, I would like to thank all Codeforces team for this beautiful platform!
Scoring distribution will be announced later.
I hope you will enjoy our problems. Wish you good luck and high rating!
UPD: Scoring distribution:
Div.1: 750 – 1250 – 1500 – 2000 – 2750 – 3000
Div.2: 500 – 1000 – 1750 – 2000 – 2500 – 3500
UPD: Winners!
Div 2:
Div 1:
UPD: Editorial is available here
Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
As a participant, I will appreciate the work of authors and testers. Thank you for the contest!
easy Mathforces
As a tester, video editorials for some problems will be available on my channel after the contest.
why the dislikes?
Welcome to Codeforces
Hope I will have a wonderful round.
You and everyone else too !! :)
Раньше по Липецкой были див 2, теперь див 1. В этом году гробовой тур?
Good luck everybody!!!Hopefully to reach specialist again.I wish to all get positive delta.
Good luck
good luck
this will be my first round,Hopefully to get positive delta, Good luck everybody!Thanks for doing contest!!!Sorry for my poor english.
You will get positive delta no matter what. Don't worry just enjoy.
Hope to be Expert this time, just few points away :)
feeling sad for you !
At least got to know my current level and where I have scope for improvement :)
Will try my best in coming contests.
Hope you become expert soon mate ! Good luck!
Thanks a lot Mayank.
omg um_nik round
Not really, I just send an idea for one problem for the olympiad, I didn't even know it will be in the round (or that there will be a round based on the olympiad) before yesterday.
scoring distribution when?
Still no score distribution.
As a tester, I tested 10 minutes before the contest.
Really liked the thinking:coding ratio in the problems and the clarity of the statements.
Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
Score distribution comes finally.
Очень классный раунд получился! Мне задача про ДжоДжо понравилась :D
Yare Yare Daze
StringCompression-Forces
Constructive-Forces!
D1C/D2E was googleable: https://www.researchgate.net/publication/231827662_Trees_with_Hamiltonian_square
Yeah let me just square the tree
https://codeforces.com/contest/1820/submission/202227633 Can anybody tell why my code gets wrong answer on pretest 2 in Problem B
try test like 11111, answer should be 25
1 111011 answer should be 9
It is not $$$2(mx - 1)$$$.
If $$$mx$$$ is odd, it is $$$(\frac{mx+1}{2})^2$$$.
If $$$mx$$$ is even, it is $$$\frac{mx}{2}(\frac{mx}{2}+1)$$$
I just do this with for loop, max((i+1) * (m-i))
Regret for missed the time of the contest...
D1A/D2C: Let MEX(a)=t. If there's no occurence of t+1 in the array, we need to change an element (expect the single occurence of i where i<=t-1) into t. Otherwise, we need to change all occurences of t+1 into t, so we can check the minimal segment containing all t+1.
D1B/D2D: First we can see h=max(a) or w=max(b) (because there will be a rectangle cut in the first time), so there will be at most 2 answer. Assume h=max(a) (situation for w=max(b) is similar), then w=sum(a[i]*b[i])/h. If w is integer, we need to find all rectangles with a[i]=h whose height is equal to the initial height and cut vertically. Whenever we find a rectangle, we reduce w by b[i] to simulate cutting. After we find all such rectangles, if there's any remaining, they must be cut horizontally, so we need to find rectangles with b[i]=w and reduce h by a[i]. We repeat these 2 processes alternatively until we used all rectangles or we can't find any rectangle with a[i]=h or b[i]=w. If we used all rectangles, h=max(a) is a possible situation.
D1C/D2E: If the tree is a caterpillar (which means the distance of all nodes to the diameter don't exceed 1), we assume the diameter contains k nodes 1, 2, ..., k, and we denote the list of nodes which is not on the diameter and adjacent to node i as L[i]. Then 1 --> L[2] --> 3 --> L[4] --> ... --> 4 --> L[3] --> 2 --> L[1] is an answer (L[i] can be empty and it doesn't matter). If the tree is not a caterpillar, there's no solution (but I can't prove it).
D1D/D2F: We denote next_empty[i] = the minimum j where j>=i and shop j is unknown, next_conflict[i] = the minimum j where range [i, j] has duplicate element. Then we let dp[i] = the answer when considering only the suffix [i, n], and consider 4 different situations:
next_conflict[i] doesn't exist, and next_empty[i] doesn't exist. We only need to simulate this process to the end, and here dp[i] = sum of number of elements in range [i, n].
next_conflict[i] doesn't exist, and next_empty[i] exist. We can assume the unknown shop has all unknown elements, so dp[i] = m.
next_conflict[i] exist, and next_empty[i] doesn't exist or is greater than next_conflict[i]. We will clear our backpack at shop numbered next_conflict[i], so dp[i]=dp[next_conflict[i]+1].
next_conflict[i] exist, and next_empty[i] is smaller than next_conflict[i]. We can set unknown shop properly to clear our backpack at any shop between next_empty[i] and next_conflict[i] (For example, consider the configuration (12), (34), (?), (56), (78), (12), then next_empty[1]=3, next_conflict[1]=6. If we let (?)=(1), we will clear our backpack at 3; if we let (?)=(5), we will clear at 4; if we let (?)=(7), we will clear at 5; and if we let (?)=(empty), we will clear at 6), so dp[i]=min(next_empty[i]+1<=j<=next_conflict[i]+1)(dp[j]).
Thank you for an explanation, understood everything except for the first fact on my own during the round, but had problems with TL. You helped me to find the missing piece^D TY!
To prove D2E start by proving that the following tree has no solution:
Since we want a cycle we can start from anywhere so WLOG we start from node
3. Now WLOG we have 2 possibilities: move to1or move to2.If we move to
1then the only possible move is2, then we can move to4WLOG and then we are stuck as moving to 5 blocks us and moving to6leaves5unreachable.If we move to
2instead we find a simmilar situation: moving to1prevents us from moving anywhere and moving to4or6makes1unreachable.Now we just proved that if the graph has this configuration then there is no solution but we need to prove that without it it is solveable.
If we have a caterpillar graph(i.e. a graph without such a configuration) We can start at one of the end points and go two by two through the diameter and consume the leaves as we go. When we reach the end just turn around.
Odd length diameter:
1 - 6 - 3 - 5 - 8 - 4 - 7 - 2 - 1.Even length diameter is similar:
1 - 7 - 3 - 9 - 5 - 6 - A - 4 - 8 - 2 - 1.I hope you can see this can be extended to any length.
I got RE on pretest 4 on div. 1 B......Anyway, good problems.
I think giving 2.5 hours is better.
Half the time I was solving problems, Half the time i was verifying that i am Human and my connection is secure. Anyhow nice problems. Another speedforces xD.
The checker output for Div.2 D may leak that $$$1 \leq m \leq 2$$$?
Input:
Answer:
2 2is an invalid solution.Nope! According to the problem statement, there's no way to split the 2x2 rectangle and get 4 1x1 parts.
You are wrong. The answer is 1 4 and 4 1.
i read the problem wrong,too :) i realized it when my friend told me the sloution after the contest
My current rating is 1243, now my rank in this contest is 605, can anyone predict what might be my rating after the system testing? Hoping to become specialist :)
There are browser extensions which can show you the expected rating change during a contest. I use Carrot, which I find to be pretty accurate. Usually the actual rating change differs by +/- 10 rating from what Carrot says.
For you, Carrot is saying +149 (the right number shows how much you need to rank up):
But its not even close for me,why so ?
first 6 contests are in a weird zone due to extra free delta
But i participated in more than 25 contest It showed me pupil delta of 130 but it's 29 :)
You are IM will you get accurate prediction ?
i always got accurate prediction from carrot, you probably checked during system testing or within contest.
Iam i not supposed to check within contest..?
I mean when should I see for accurate rating
Thanks in advance:)
after system testing, during contest/during system testing, it will give you delta according to your current ranking.
However, other people might beat you later on, which is why your delta changes.
gratz
problem quality here is becoming so bad....
Why do you say so?
I was confronted with extremely unstable network connection.
Almost every time I try to reload the page or get into a new page, I got this sent by CF.
How to solve D2D/D1B?
First, suppose that the first cut was vertical. This means that the piece thrown in the box has the height of the original rectangle and no other piece will have a height larger than this. The same applies to the width if the first cut was horizontal.
This means that there are two options:
In both of the cases you can calculate what the other side length must be since you know the total area $$$A$$$ of the original rectangle and $$$A = hw$$$. If the other side length is not an integer, you know that it is impossible.
From here, you need to solve the case where both could be possible. You should make two lists containing all rectangles sorted in decreasing order of heights and decreasing order of widths, respectively. From here, you can do 2 pointers to figure out if the division was possible for each of the two options.
You should try to figure the rest out on your own but if you don't want to, I can also explain the rest.
My approach is similar but I'm not able to figure out why is it failing test case 2. Could you take a look at my code 202226566? I believe it is clean and shouldn't take a lot of time to understand. I have basically simulated a process. At every iteration, if the dimensions are $$$h,w$$$, I look for piece $$$h,y$$$ or $$$x,w$$$ where $$$y<=w$$$ and $$$x<=h$$$. If we find either of these pieces, cut them out from our rectangle.
UPD: I found your mistake. You used
setinstead ofmultiset. 202236563You can now see the test cases where your code fails. For you, the checker comment was
wrong answer Integer parameter [name=m] equals to 0, violates the range [1, 2] (test case 4)
i.e. you didn't find a solution.
Here is the test case:
Yes. Just figured it out. Very unlucky ;_;
d1 A how?
At first, find $$$MEX$$$ of the array. Let it be equal to $$$m$$$. If $$$m$$$ is equal to $$$n$$$, then the answer is No. Else, we need to add m and erase all $$$m + 1$$$. To do that, we find a segment $$$[l, r]$$$ so that it has min length and all of the occurences of $$$m + 1$$$. If there is none, the answer is Yes. Else, we change $$$a_l, a_{l+1}, ..., a_r$$$ to $$$m$$$ and then count $$$MEX$$$ once again.
Here goes how I passed Div1 A-C pretests
Possible construction for Div1 C with a drawing
Nice explanations.
I understand the meaning of D2D incorrectly as arbitrarily cutting a rectangle into n-1 small rectangles QAQ
Ikr same here. wcyd
same, time to learn how to read problems.
I misread the "he will put one of the parts in the box" part in the whole contest ToT
The damn E has a too tight constraint for memory! My STL get fxxked for lots of times.
Why I keep failing on test 1 in problem E:
You forgot to use 'fflush(stdout)' in the function 'unblock'?
I didn't notice I need to read an integer after outputting the answer.
I also do a as stupid mistake,as well as mistyping nm when I output.
Author d2E/d1C is sadist
Why I can't submit my code for D2E now? And are there any tutorials about these problems?
need to wait the tutorials for about 1day
div 1D was very evil, no sum(m) = 1e5 * 1e5 in pretests
I guess someone thought it was very funny to not make a limit for sum of m in Div1D and create no pretests for that, even though it contributes nothing to the problem and only decreases it's quality
I guess this might help
I'm not arguing that it's not my fault that I didn't notice it. But the fact that there is a limit for each individual test but not for sum and that all tests with big sum of $$$m$$$ are in system tests implies that it was done with a single intent to make peaple get FST, and I think that problemsetters shouldn't make counterintuitive statements rather than participants should "git gud" at deciphering them
So your argument is that either the limit m should not exist or that every kind of apple should exist?
Not exactly. Either the limit for $$$m$$$ shouldn't exist or the limit for sum of $$$m$$$ should exist or there should be a pretest with big sum of m (although the first 2 options are better)
Pretests are not a part of the problem statement, they should always have some caveats for hacking. Personally, I'm not too big of a fan of this multitest format either, it does help to test a lot of small cases for correctness I guess.
the problem is deliberately misleading and its obvious from the statement.
they could have given m <= 10^9 and made it clear m isnt bounded.
they could have given sum of m <= 2e5, but they did neither just to catch people who didnt pay attention to the minute details in the statement.
Stop acting like this is a reading issue, its a problem setter issue, instead of focusing on correctness of approaches, they focus on such random things.
Pretty sure they just didn't focus on this specific detail instead of trying to trip up some of the contestants
Yes, it's the kind of thing that's best put in pretests. Especially when there are 40 pretests! Either use a small number of weak pretests or a large number to make them strong, not put ballast in pretests — it has 0 benefits.
At least this time I didn't get caught on assuming. Rather than read everything carefully, I specifically wondered while implementing "wait is M also small? it often is, but there's no reason it'd have to be" and checked the statement for it.
From the comments below it seems that intended author solutions got hacked then they removed the ones that didn't handle this sort of case, which leaves me even more salty.
Even if the authors find that bit of optimization really necessary, why not just increase the constraint on $$$m$$$ to $$$10^9$$$ or something? The current ones can only mislead people. Thankfully I didn't debug D in time. I would've fallen for this and it would've been far more enraging.
I think such cases should be included in pretests too (my solution also gets TLE ><), but I guess that the w/ts didn't notice or forgot this strange constraint and the original system tests didn't include such cases. The killer cases are placed last, and I heard some hacks didn't work properly because some solutions marked correct in polygon TLed.
After the contest ended, the scoreboard showed this:
I reloaded the page many times and it still showed this. But then after the system tests started I saw this for problem D:
Does anybody understand why this hack was not shown to me during the contest?
hacks are done after contest, not during. hos.lyric well played
Did something change? Since when?
wasn't hacking phase (12 hour time duration) always after the contest..? i don't think it is ever done during the contest
The 12-hour hacking phase is for educational rounds. Normal round hacks are during the contest. On the screenshot, you can see that solution was hacked during the contest.
During standard Div.1, Div.2, Div.1 + Div.2 and Global rounds hacks are always done during the contest and never after the contest.
During Educational rounds (rated for Div.2), Div.3 and Div.4 rounds hacks are always done after the contest and never during the contest.
The hack process is somehow extremely slow. iirc the last time that I got hacked, I received the notification about 10 minutes after the hack happens.
could codeforces ban hacks in the last few minutes of the contest for people to actually be able to see if they were hacked? It feels very stupid to fail a problem just because of weak pretests + long hack times
It seems more likely that AC solutions in polygon got hacked. That sort of thing happens, but usually it's early into a contest and fixed quickly. It's reasonable to think the contest should be unrated due to it happening this late, but I'm not sure what I feel about this.
It is possible that one of the solutions marked correct in the polygon was also hacked. And this hack had unknown verdict. (Not sure, just a guess)
I indeed made the hack made during the contest, and I got "Unexpected verdict", which I believe is because some writer's or tester's solutions were incorrect (in fact TLE). I made a clarification request but the issue was not announced during the contest...
As a tester...
UPD: Oh, it turned out that I submitted a solution to the problem when there was only one testcase per test
Can anyone tell me why my solution with multiset in problem div1 B does not pass the time limit? https://codeforces.com/contest/1819/submission/20223568
Got it :d..
Finally, after 4 months of hard work, I went from a 0-base cfer to a CM.
Congrats!
where do you usually practice?
codeforces problem set To improve, you need to select the appropriate rating range.
I think there is a misunderstood. In div 2 problem C. in pretest 2
If you change 2 to 1 mex increases by 1.
The system tests for problem D2D are weak. My submission has an indexing typo and fails for the following
How to get 2 6?
speed forces round
Nope. That's when a big jump in difficulty appears so a lot of people are only ranked by speed even though a better distribution could've avoided it. In this case, the deciding factor for many high positions was correctness instead of speed.
For the problem "E. The Fox and the Complete Tree Traversal" (Div2 : E) and third case, why is say [8, 4, 9] not a solution? In general any why is any 3 nodes connected not a solution as we can make a sequence from them and form a cycle
It could've been the solution to Incomplete Tree Traversal.
How can 202225617 pass pretests in E while being so stupidly wrong? Changing the error gives AC: 202244038
Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
KONO DIO DA!
Got unexpected verdict for a hack on 1820D - The Butcher, can someone fix?
Fixed
The data on Div.1 B is too weak.
Is there a tutorial for this contest?
.
Auto comment: topic has been updated by DishonoredRighteous (previous revision, new revision, compare).
What is going on with tests currently? I see lots of sumbissions in queue along with mine.
Maybe plagiarism test
tourist barely got in top 5