Hello! Codeforces Round 863 (Div. 3) will start at Apr/04/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of **open hacks**.

You will be given **6-8 problems** and **2 hours and 15 minutes** to solve them.

Note that the **penalty** for the wrong submission in this round is **10 minutes**.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participant of the third division*, you must:

- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin and Vladosiya.

We would like to thank: Sugar_fan, doreshnikov, powergee101, pashka, KseniaShk, 74TrAkToR, stefanbalaz2, playerr17, diskoteka, BF_OF_Priety, nigus, erankyun, plourde27, Be_dos, donghoony, lucasxia01, Jostic11, sansen, gigabuffoon, akulenok, pwned, vrintle for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

**UPD**: Editorial

4 is my lucky number though :)

You're not welcome in Japan.

In China,4 is also not welcomed.

Edit: He changed his original commentFinally a Div 3 after a month :)

i hate kanye west

me too

why?((((

he never went to paris

What's your favourite song of him? Mine is No More Parties.

"Bad News" from 808's & Heartbreak

how I can be a tester? plz don't downvote me, I just want to know :((

hidden...

Why are you so sure of yourself? After all, no one knows what he knows and can do. You can't just judge a person!

Bro shut up, if he were qualified he would know asking it from his main account will be better.

oh sorry, i was in a hurry

I just want to know that will the hacking a solution improves ranking of the user in contest ??

You don't get points from hacking, but if people ranked higher than you and get hacked, their rank might become lower than yours

All the best to everyone may this be you last div3 and you all become experts :)

Scoring distribution should be added..!

there are no scores for each problem as such, in div3/4 rounds. Every problem has equal score.

Hopefully I'm able to participate.

I hope that it will be my last div 3 round :)

I registered for the contest before I became an expert, will this round still be rated for me? I ask this because I don't see an asterisk(*) next to my name in the registered participants' list.

If I'm not mistaken, you will participate unofficially

Unregister and then register again, you'll see the asterisk

Yep, I know that, but I was just curious to know what would happen if I participated without registering again.

as a tester , I can assure that problems are challenging enough and there is hardly any problem which is a cakewalk and recommend to read all the problems

I hope your health is way better now. I have prayed for you every single day since then.

Those who don't know for them ---- https://mirror.codeforces.com/blog/entry/114330

thanks , better but still uncertain ,keep praying , I need all the prayers

Don't worry everything will be alright. And you will live a normal life. This just matter of time.

you were right, not a cakewalk

Legendary grandmaster to test Div3. No need to have open hacking :).

As a tester...! wait a minute, something ain't right

`Hope to become Expert again`

At last a Div. 3, a good opportunity for improve rating.

Lol, it didn't age well.

Need more frequent Div.3 contests for beginners.

lessgo..

As a tester, I feel that the problems are very interesting and everyone should participate in this round.

Just asking to confirm, there wil be no interective problem,right ?.As, in a previous contest there was interective problem and didn't mentioned in blog.

You can trust this blog.

Hope to become pupil today!

Hello, can we make frined? Or, we can make progress each other.

hoping for Expert

Is it Div2.25?

came back here in the middle of the contest, just to downvote. what kind of div 3 is that?

I don't think this round is too hard for a Div. 3 Round after AKing it, I think it normal and DE is even too easy for their place.

I am not so sure About D .

I like how you submitted C and G in the same minute, with completely different templates lmao. Imagine cheating then bragging online about it ICANT.

See if I'll be skipped then.

So do you really think that all the people here are little babies and they don't know how a code can be changed after being copied. Such a fool you are!

I'm not foolish enough to copy one code without editing the template.

it seem unrated.

worst Div. 3 contest ever.

Nice problems except for F. F is simply a trash problem.

LoL, nice problem...

For F: You need to get all the simple cycles in the graph,

check if there is exactly one cycle where its nodes degree is 4

And for all other cycles, the degree of its nodes should be 2 except for only one node (wich is part of the main cycle and its degree is 4).

Easy :)

Is there any way to solve "Living Sequence" without digit dp ?

consider the number k in base 9.

https://oeis.org/A052406

Can you tell me your digit dp approach?

First you need to binary search for the number, let's say x.

Then, the check(x) function is pretty straightforward if you know the standard digit dp approach. Just skip "4" at all the order from $$$0$$$ to $$$log_{10}(n)$$$ in x, and do calculations for other numbers as usual.

I am really sorry if the question sounds dumb , but in the questions that I've done based on digit dp, we are always given an upper bound , which we dont have here, how can I compute the kth number

You need to count number of numbers less than or equal to k, that have a 4 in them (or don't have a 4 in them).

This is you recursive function. You can use it along with binary search to solve the problem

Yeah sorry, check the edited answer now.

Thank you so much man, helped a lot!! :)

My digit DP solution was giving TLE E Solution

I did binary search for the answer with low=1 and high = 5*k, and in checker function i used Digit DP which tells me how many numbers are there which has digit as '4'. According to me in worst case no of operations : 100 (for binary search)* 50(checker fn Digit DP)*10000 (t) = 10^7. Am I missing out something or is there any way this approach can be optimized. Thanks

Just change endl to '\n'.

Thank you so much for the reply. But why that is happening I am curious to know

Isn't it this piece of code takes care of that. Sorry if I am bothering you Thanks

std::endl prints a new line and also flushes the output stream, where '\n' just prints a new line, that is the difference as far as I know.( which is why endl takes more time comparably)

Define $$$f(x)$$$ as the number of integers that don't have 4 in them. Now for each power $$$i \le 15$$$ we can find $$$f(10^i)$$$ which is $$$9^i$$$. Now for any other integer $$$x$$$ we can find $$$f(x)$$$ by going through each digit $$$i$$$ of value $$$x_i$$$ and adding to the answer $$$f(10^i)*x_i$$$ if $$$x_i \le 3$$$ or else adding $$$f(10^i)*(x_i -1)$$$. Now we can do binary search to find the answer.

We can have 9 digits. So just check if the number can fit if my ith digit was k. Then subtract the weight of it. Do this for every possible digit

https://math.stackexchange.com/questions/3958169/find-nth-number-which-does-not-contain-the-digit-c

Use digit dp too but got hacked. The time is too tight for this approach. :(

what was your complexity? I used digit dp for E. Time complexity was $$$O(logMX*20)$$$ per test case Where $$$MX=1e18$$$

I set Mx to 5e12

the $$$MX$$$ refers to the upper bound of the binary search... how did you pass samples with setting it to $$$5e12$$$?

When k = 1e12 the answer is about 3e12, so I set it to 5e12

oh mb, I calculated wrongly lol.

I find a litte mistake which leads to a big constant. It's my fault:(

oh :(

https://mirror.codeforces.com/contest/1811/submission/200755771

You can look at my submission. I just thought of the elements of the sequence as base 9 numbers, and then converted back. Very short code. Though I could see it being confusing (for non IMs haha) if you didn't think of that way of viewing the problem.

khatam

[.]

How to solve C?

Just check the minimum of the consecutive elements. The first and last element will be as it is. For example

`3 4 4 5`

`3`

will remain as it is then the sequence will be`min(3,4),min(4,4),min(4,5)`

and the last element`5`

will be as it isso the ans will be

`3,3,4,4,5`

what is the logic behind this?

$$$min(3,4)$$$ is the largest value of $$$a_2$$$ that you can pick (otherwise $$$b_1$$$ will become more than 3, a contradiction). It turns out this suffices as well (after copying the edge values).

G1 was much easier than C/D/F

This round was pretty interesting for me. Found C much harder than D. Although I did copy E after googling from here, had an insane last minute adrenaline rush trying to guess/brute-force necessary conditions for flower graph in F!

Thanks for the interesting problems — will go and prove F now :blobsweat: Update: hacked lmao

same, had to google for E as well

kill yourselves

i stand by what i said

Woah edgy boy

vužgal bum te ognjene

chromate00 Orz for the great performance!

Thank you! The contest was very fun (Thinking about G was not, but anyways, it was fun)

Will you make miku's hair blue again after you reach expert?

yes actually I have saved the blue version for that

Having saved the blue version, you should start thinking about the purple one :)

I dont think problem D is a good problem that if you know the conclusion fn*fn+1=f0*f0+f1*f1+...+fn*fn, it will be very easy to solve it, otherwise it's very difficult. Although it's a comman conclusion.

Can you prove this conclusion?

Here it is

Thanks, did you solved D? Approach?

Even after getting to know about this during contest, i couldn't. Like removing $$$(x, y)$$$ from grid creates some regions and i was getting confused in how to divide them such that we get fibonacci squares and that too distinct.

Since you konw the conclusion then every time you must cut off the biggest square,otherwise you cannont cut it into only n+1 sqaures. Then we can solve it recursively

Common conclusion ? Ahh you are from china, never mind

Nope. It's not common Sir up until you aren't from china.

I think if you draw it up, and look at some examples it is not so bad. Basically if x can be written as sum of distinct even-numbred fibonacci numbers, and y odd ones (or opposite depending on parity of n), you get the answer. And its not that difficult to see if you look at the sample images they provided, and draw some bigger examples yourself, and try to see how the single square can move around.

Why my code tle at test 24 in G1, i think it's pretty decent enough to pass, just running 2 dp's one for maximum length and second one to calculate answers. Please help submission:200780428

for problem C, How can you get output for this test case 0 1 2 1 0 ? the described constrains were incomplete I think.

I think there will be no such case as the setter says array

`b`

is created from the array`a`

by taking the maximum element between two consecutive elements.So array

`b`

will be in increasing order always.Not necessarily true, b doesn't have to be in increasing order as the first test contains such examples as

[2, 2, 1],[0, 3, 4, 4, 3]and so on. But 0 1 2 1 0 isn't a valid input for our problem either, closest we can get is:[0, 1, 2, 2, 1, 0]from 0 0 1 2 1 0 0.This is probably my worst-ever performance in a div 3 contest, never felt more let down in my coding...lol!

I'm curious about there will be how many FST of problem F.

Problem E editorial: https://oeis.org/A052406

Problem :- 863A Insert Digits Solution is here with explanation and code of ithttps://codeforcer.blogspot.com/2023/04/problem-863a-insert-digit-full-detailed.html

Problem :- 863C Restore the array Solution is here with explanation and code of ithttps://codeforcer.blogspot.com/2023/04/problem-863c-restore-array-full.html

Problem :- 863D Umka and a Long Flight Solution is here with explanation and code of ithttps://codeforcer.blogspot.com/2023/04/problem-863d-umka-and-long-flight-full.html

Where is the

full explanationin your blogs? Do not misguide other participants.He's just copying YocyCraft's explanations

E maybe little tricky,but others are interestring. And feel the difficulty of D than that of E.

E maybe little tricky,but others are interestring. And I feel the difficulty of D than that of E.

In problem statement of D. Umka and a Long Flight it states,"A checkered rectangle with a height of Fn and a width of Fn+1" means width always greater then height. Then, how can y be y > Fn at test case 3 (3 1 4 , output: YES)? n=3 x & y should x<=5 and y<=3. what did I miss?

1 <= x <= Fn, 1 <= y <= Fn+1

Can someone provide an unofficial editorial for problem C?

Obviously, ans[1] = b[1] and ans[n] equals b[n-1], we can fill the rest by taking min(b[i], b[i+1]), because then, max(a[i], a[i+1]) = b[i] will hold

lol this is how you prove it?

first and the last element will be in their place as it. Other element will be

`min(a[i],a[i+1])`

for all`i=0 to n-1`

what about this test case 0 1 2 1 0

It's an invalid input. Consider for

`1 2 1`

. If 1=max(a, b), 2=max(b, c), 1=max(c, d), then b==2 or c==2 must hold. If b==2, then 1=max(a, b)>=b==2, or if c==2, then 1=max(c, d)>=c==2. Both of them will have contradiction.Well, E is really tricky and F is a little trash.

BTW, I think BD is nice.

Nice problemset. I like task D

E is classical and F is kind of bad.

BCD are nice problems.

B is the worst

The person who came up with problem b should be beheaded!!!

Bro relax lmao(I totally agree).

Tbh, B ruined my contest ... I am pretty bad at grid and these pattern problems. Had to move to C, which felt quite confusing and then somehow i got a simple solution to work. In the end even after solving E, it took me 25 mins to solve B.

Well I solved A, B, C, D but because of the wasted time on B I couldn't solve E in time.

why

my solution to B:

it's quite easy!!

you can shorten your find function to

Wow that's nice

A: Find the first digit less than d and insert d before it. If there's no such digit, insert at the end.

B: We need to find there are how many cycles between start and end. Let's number cycles from outside to inside 0, 1, 2, ... then (x, y) is contained in cycle min(x-1, n-x, y-1, n-y). Then the answer is the difference of cycle number of start and end.

C: b[1], min(b[1], b[2]), min(b[2], b[3]), ..., min(b[n-2], b[n-1]), b[n-1] is an answer.

D: If n<=1 answer is true. Otherwise, let h=fib[n], w=fib[n+1], we must cut a h*h square from left or right. If we cut from left and (x, y) is remained in the right part, which is a fibonacci ractangle of order n-1, we can solve the problem recursively. Similar for we cut from right and (x, y) is remained in the left part. If no matter we cut the square from left or right, (x, y) can not be remained then answer is false.

E: Represent k in base-9, and add 1 to digits >=4.

F: First for a k-flower, number of nodes n=k*k and number of edges m=k*(k+1). Then there must be k nodes with degree 4, and other nodes with degree 2. If so, 4-nodes must form a cycle of size k (we can take all edges between 4-nodes and check if they're a cycle), and all other edges must form k cycles of size k, and each cycle contains one 4-node and k-1 2-nodes.

G: First calculate prefix-sums of occurences of each number in range [1, n]. We first run dp for max_size[i]=(max size of nice path end at i). Let max_size[0]=0, and for max_size[i], we check for each 0<=j<i, if there're at least k occurences of c[i] in range [j+1, i], we update max_size[i] with max_size[j]+k. Then we let dp[i]=(count of nice paths of size max_size[i] end at i). Let dp[0]=1 and dp[i]=0 (1<=i<=n) at first. Then for each j<i, if max_size[i]-k==max_size[j], we have dp[j] ways to choose first max_size[i]-k elements, and we have C(cnt, k-1) ways to choose other k elements (here cnt is count of occurences of c[i] in range [j+1, i-1], we can calculate it by prefix-sums).

Your solution for E is very cute

Can you explain your

intuitionforproblem E?Thanks also just want to know if it is some type ofstandard problem.Because digit 4 is forbidden, we only have 9 available digits, so remained numbers are some modified version of base-9 numbers(012345678 --> 012356789).

I am just curious that suppose if there would have been two numbers forbidden then would the same approach have worked...like base-8 numbers. and if yes...then can you please tell how?

in B can you explain how did you deduce that the cycle is min(x-1, n-x, y-1, n-y).

It's the minimum distance from a cell to the boundary of square.

For problem F, can you explain how you come to the conclusion that there must be k nodes with degree 4, and other nodes with degree 2 ? Are we assuming the entire graph is connected?

That's by the defination of k-flower.

I see. I misunderstood the statement of F and tried to solve a different problem.... Thanks!

How to solve Problem D

Is the validator of problem A wrong?

It says $$$1\leq n\leq 2\times 10^5$$$ in the problem statement, but when I hacked with n = 2e5, it showed

" Validator 'validator.exe' returns exit code 3 [FAIL Integer parameter [name=n] equals to 200000, ...e range [1, 10000] (test case 1, stdin, line 2)] ".

Also, I think the pretests are weak too, $$$O(n^2)$$$ and $$$O(n^2\times\log(n))$$$ solution can pass.

you'd better show your generator.

What the fucking description of F!

It's not thaat bad tbh)

most of my friends took 10-20 minutes to understand what k-flower actually looks like.

then most of your friends aren't very bright

if you think so, whatever, you are right

I thought I should determine whether there is a flower in the given graph...

https://www.geeksforgeeks.org/finding-the-nth-term-in-a-sequence-formed-by-removing-digit-k-from-natural-numbers/

Problem E has striking similarity with above gfg article. Maximum users have googled it and copied the snippet of this article as it is without any changes. Please try to filter out those code solutions while checking for plagiarism. MikeMirzayanov

Wolfester 200768712 Solution can be seen to copy exact helping functions from the above mentioned article. This is a serious concern for the integrity of contest. Pls ban this user from codeforces

3rd party code posted before contest is allowed

So, will these questions be taken into consideration for plagiarism?

Problem E? I dont think so. Div 3 is usually inteded to be more classical, so expect some similar problem ideas.

This doesn't come under cheating. Using third-party code available before the start of contest is allowed.

Catch Cheaters https://mirror.codeforces.com/blog/anosh21

F is quiet confusing.

make it unrated

Can someone provide a counter example for this submission?

Thanks for the counter example!

there is some issue with testcases of A problem.

N<= 2e5but in hacking phase, i could not generate testcases where N > 10000

Div.(2+1e-6) round.

One other way to do E is my considering 9 based numbers instead of 10 based(decimal) numbers. Convert k to a 9 based number and change all 4's to 5, 5's to 6, 6's to 7, 7's to 8 and 8's to 9

Thanks you StackExchange !!!Hats off for working this out yourself.

I was trying to hack A, but getting the following error!

same issue i am facing

i guess this contest should be unrated as solution to problem E was available online and a lot of people just straight away copied the code!! Link:https://stackoverflow.com/questions/54851335/program-to-compute-n-th-number-that-doesnt-contain-given-digit

Come on, it's Div3. There must be several easy problems in such contests, so for almost every easy problem you can find a " coincident problem "

I think there is a mistake in the G2 problem's tests ( 29th test ), in my opinion the answer is at least 1, but the right output for the 29th test is 0. Can anyone explain how is it possible? My submission

The answer is probably divisible by $$$10^9 + 7$$$.

I made the same mistake and it passed G1. Can you try hacking me with the same test case ?

My Submission

UPD: The test-case does not fit the constraints of G1 so a test-case with answer divisible by $$$10_{}^{9} + 7$$$ which satisfies $$$1 \leq k \leq n \leq 100$$$ is needed

An alternative solution of C, which might be easier to come up with (compared to the $$$(b_1,min(b_1,b_2)...)$$$ solution):

First note that if $$$b_i > b_{i+1}$$$, we must have $$$a_i = b_i$$$, otherwise if $$$a_{i+1} = b_i$$$ then $$$b_{i+1} \geq b_i$$$. Similarly, if $$$b_i < b_{i+1}$$$, then we must have $$$a_{i+2} = b_{i+1}$$$.

After doing one pass and dealing with these cases, there may still be some $$$a_i$$$ that are left assigned. Now we check whether for each $$$b_i$$$, at least one of $$$a_i$$$ and $$$a_{i+1}$$$ is equal to $$$b_{i}$$$. If not, we assign them. If we traverse in increasing i, we assign $$$b_i$$$ to $$$a_i$$$ first, and if $$$a_i$$$ is already filled we assign to $$$a_{i+1}$$$. In optimization terms, we make sure all constriant are active.

Finally fill the rest with 0.

This always works if the input is correct.

solution: https://mirror.codeforces.com/contest/1811/submission/200724266

So, problems B and D ruined the contest, right?

Are submissions going to be re-tested with successful hacks?

Yes

So hard div3，(sad).

seems that few people will pass F

I wonder when can rating changes be calculated,though I'm unrated :)

Great contest! I found E much more interesting than I thought.

When do the ratings update??

There is code available for problem E before contest? Is it ok to submit that code during contest.

It is just sad to know Problem E’s code was available on the Internet and many people have copied directly from there. First time downvoting any post on CF.

toooooooooooooooooooooooooooooo hard 4 div3

When will the system testing perform???

it's performed

No, I think that you're joking.

I think you are joking too.

This round is hard for me.

Can anyone explain it to me, yesterday I solved 5 questions in Div 3, cf predictor showed an increase in rating, but now when I go and see the contest page it shows 1 solution submitted wrong and a decrease of -24 in my rating

It's currently performing System Testing and all accepted submits need to be rejudged with stricter testcases. So the information on the contest page might be not correct until all tests are finished.

In problem A, why the maximum $$$n$$$ in pretests is less than $$$10^5$$$? I don't think pretests should be like this.

So it's a chance for you to hack. I'm too late to realize this ...

Can someone explain to me why in Problem G,the output of example(fifth example) "n=5,k=1 1 2 3 4 5" is 1?I thought the maximum length is 1,and 1,2,3,4,5 are both nice paths.So I think the answer of it should be 5.

maximum length is 5

take the whole sequence and count of it is 1

oh thank u I got it,k=1 is really special case.

Was this round rated, i have accepted submission but my rating haven't been updated yet

It'll take some time bro

I just received this message:

Attention!

Your solution 200772354 for the problem 1811B significantly coincides with solutions IshaanKapoor/200738434, kaiboy/200772354. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I just want to say that I never cheated. Your accusation is false. As a protest, I will not touch any problems A, B, C from divisions 2, 3, 4 anymore.