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, Yuu, I_LOVE_DASHA_KARPENKO, 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!

I can confirm that authors put a lot of work into this round and I hope you enjoy it. Good luck everyone!

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 !! :)

The programmers: We are ready :)

idiot

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.

Yare Yare Daze

StringCompression-Forces

OK, I pull up!!!

ok

Constructive-Forces!

D1C/D2E was googleable: https://www.researchgate.net/publication/231827662_Trees_with_Hamiltonian_square

Yeah let me just square the tree

Cool problems, thanks for the round :D

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 to`1`

or move to`2`

.If we move to

`1`

then the only possible move is`2`

, then we can move to`4`

WLOG and then we are stuck as moving to 5 blocks us and moving to`6`

leaves`5`

unreachable.If we move to

`2`

instead we find a simmilar situation: moving to`1`

prevents us from moving anywhere and moving to`4`

or`6`

makes`1`

unreachable.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.

And Iam Missing your explaination for div2 Your explaination is helpfull all contests btw

I got RE on pretest 4 on div. 1 B......Anyway, good problems.

Problems were excellent,I love problem C,thanks for making contest!.

I think giving 2.5 hours is better.

I agree, I had a very small bug and therefore didn't manage to submit on time, only to fix the code 3 minutes after the contest had already finished :(

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 2`

is 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

We may share the same opinion, but I have no ideal about why can't I AC this problem. 202228826

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 :)

Check out "Carrot" in the google chrome extensions

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.

Got it thanks >_<

You can download the chrome extension to get prediction

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`set`

instead of`multiset`

. 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.

i wish i reach pupil ratingWhy 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

Cf testing my humanity more no of times than my total WAs ;-;

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

spent 1 hr in A question. don't know why it just didn't strike me

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.

then I think there has been an error in showing you the hack. this is not good

During standard Div.1, Div.2, Div.1 + Div.2 and Global rounds hacks are always done

duringthe contest and never after the contest.During Educational rounds (rated for Div.2), Div.3 and Div.4 rounds hacks are always done

afterthe 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..

How do I prevent overflow in B??

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 2If 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

Test caseHow to get 2 6?

In case anyone is struggling with Div2-ProblemC

SpoilerHere is my explanation: Let's say that the number k is the initial MEX of array a. Key observations: 1) we cannot touch any number from 0 to k-1 (inclusive), if it occurs only once 2) After performing the segment operation, we cannot have k+1 elsewhere in the array.

if k+1 doesn't exist or occurs only once, and if we have n > k, we can definitely pick a number and print 'YES', otherwise print 'NO'

if k+1 occurs twice or more, all the numbers from 0 to k-1 must exist outside of the segment connecting all positions with value k+1.

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.

someone please explain D2B. I am unable to form the formula which most of the solutions I can see contains.

Use pen and paper and try to solve problem using following strings: 1011, 01101, 0111110, 01111110, 111. You will be able to form the formula after solving problem for above strings using pen and paper. While solving any problem try to take as many examples as you can.

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!Hi, can I have more information about the input for pretest #3 for Div2.B ( https://codeforces.com/contest/1820/problem/B )?

Input 111111111111111111... Participant's output .... Jury's answer 40000000000

By looking at the answer, the input seems to be 200000 ones. Thanks!

Got unexpected verdict for a hack on 1820D - The Butcher, can someone fix?

Fixed

Problem C : Constructive Problem Video Editorial Link : https://youtu.be/bQTOeXc4Zpw

The data on Div.1 B is too weak.

Is there a tutorial for this contest?

.

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

Hi, just got an email about my solution for 1820C matching with some other peoples. Unlike last time I did not run my code through ideone, and I used my local browser instead. I have heard of instances where the codeforces checker makes errors so I went through the people whose code it apparently coincides with and my code does not even have the same variable names and functionality like the others so I am confused. Could this please be fixed? I am happy to provide evidence such as the time the code was submitted on the platform as well as on my personal device.202221757

received the same Email, though i do it through ideone, but I learnt a lesson

Round was good

You'll do great!

I want to ask if (B. JoJo's Incredible Adventures) has different logics to solve. After my successful submission it said that my code is similar to other 50 to 60 users submissions. But how can it possible? (· ╥﹏╥ ·) if my logic is same as others ,is it my fault? (ಥ﹏ಥ) Next time I hope all problems should have multiple logics of solutions .