Привет! В 04.04.2023 17:35 (Московское время) начнётся Codeforces Round 863 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 6-8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin и Vladosiya.
Также большое спасибо: 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 за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.
Всем удачи!
UPD: Разбор
4 is my lucky number though :)
You're not welcome in Japan.
In China,4 is also not welcomed.
Edit : He changed his original comment
случайно поставил минус, я думал это див2 2 апреля
Finally 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://codeforces.me/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 againAt 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://codeforces.me/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.
[deleted]
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 53will remain as it is then the sequence will bemin(3,4),min(4,4),min(4,5)and the last element5will be as it isso the ans will be
3,3,4,4,5what 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
bis created from the arrayaby taking the maximum element between two consecutive elements.So array
bwill 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 it
https://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 it
https://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 it
https://codeforcer.blogspot.com/2023/04/problem-863d-umka-and-long-flight-full.html
Where is the full explanation in 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
I got it. Thanks for your reply.
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 alli=0 to n-1what 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
int find(int x, int y, int n){ return min({x,n-x+1,y,n-y+1}); }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 intuition for problem E? Thanks also just want to know if it is some type of standard 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.
Numerous individuals have replicated content from YouTube, and it is imperative that Codeforces takes action regarding this issue.
Catch Cheaters https://codeforces.me/blog/anosh21
F is quiet confusing.
Great Contest, couldnt solve many questions in the contest but as i upsolve, i realize that the problems were really good.
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 <= 2e5
but 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://codeforces.me/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.
at this point, i wanna become an expert to never participate in a rated div 3 ever again..
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
This server has been crashing for few months already. either fix this or make contests unrated.
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://codeforces.me/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.
recursion is useful.