Vladosiya's blog

By Vladosiya, 3 years ago, translation, In English

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, ibraevdmitriy and Vladosiya.

We would like to thank: Sugar_fan, doreshnikov, powergee101, pashka, KseniaShk, 74TrAkToR, stefanbalaz2, playerr17, diskoteka, FiniteMoves, 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

  • Vote: I like it
  • +38
  • Vote: I do not like it

| Write comment?
»
3 years ago, hide # |
Rev. 2  
Vote: I like it +20 Vote: I do not like it

4 is my lucky number though :)

»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Finally a Div 3 after a month :)

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i hate kanye west

»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +6 Vote: I do not like it

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

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Scoring distribution should be added..!

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hopefully I'm able to participate.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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.

»
3 years ago, hide # |
 
Vote: I like it +38 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Hope to become Expert again

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +12 Vote: I do not like it

Need more frequent Div.3 contests for beginners.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

lessgo..

»
3 years ago, hide # |
 
Vote: I like it +38 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope to become pupil today!

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

hoping for Expert

»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Is it Div2.25?

»
3 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it -25 Vote: I do not like it

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.

»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

worst Div. 3 contest ever.

»
3 years ago, hide # |
 
Vote: I like it -20 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

should i register for contest for 1minute i think i can solve all problems in 1min

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

khatam

»
3 years ago, hide # |
Rev. 2  
Vote: I like it -22 Vote: I do not like it

[.]

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    3 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    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 is

    so the ans will be 3,3,4,4,5

»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

G1 was much easier than C/D/F

»
3 years ago, hide # |
Rev. 3  
Vote: I like it +24 Vote: I do not like it

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

image

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +13 Vote: I do not like it

chromate00 Orz for the great performance!

»
3 years ago, hide # |
Rev. 4  
Vote: I like it -6 Vote: I do not like it

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.

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you prove this conclusion?

  • »
    »
    3 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    Common conclusion ? Ahh you are from china, never mind

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, hide # |
Rev. 5  
Vote: I like it +1 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

This is probably my worst-ever performance in a div 3 contest, never felt more let down in my coding...lol!

»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

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

»
3 years ago, hide # |
Rev. 3  
Vote: I like it -44 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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?

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone provide an unofficial editorial for problem C?

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like 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

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      what about this test case 0 1 2 1 0

      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Well, E is really tricky and F is a little trash.

»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Nice problemset. I like task D

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

E is classical and F is kind of bad.

BCD are nice problems.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
Rev. 5  
Vote: I like it +21 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

How to solve Problem D

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +55 Vote: I do not like it

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.

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +93 Vote: I do not like it

What the fucking description of F!

»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it
»
3 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

F is quiet confusing.

»
3 years ago, hide # |
 
Vote: I like it -21 Vote: I do not like it

make it unrated

»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Can someone provide a counter example for this submission?

»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

there is some issue with testcases of A problem.
N <= 2e5
but in hacking phase, i could not generate testcases where N > 10000

»
3 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

»
3 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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 "

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, hide # ^ |
      Rev. 3  
      Vote: I like it +1 Vote: I do not like it

      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

»
3 years ago, hide # |
Rev. 4  
Vote: I like it 0 Vote: I do not like it

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 \gt 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 \lt 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

»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

So hard div3,(sad).

»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

seems that few people will pass F

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

When do the ratings update??

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +2 Vote: I do not like it

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.

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +2 Vote: I do not like it

toooooooooooooooooooooooooooooo hard 4 div3

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

When will the system testing perform???

»
3 years ago, hide # |
Rev. 2  
Vote: I like it -10 Vote: I do not like it

This round is hard for me.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
    Rev. 4  
    Vote: I like it +1 Vote: I do not like it

    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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think most people who step on it are because of A or F

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why ratings are not visible till now for this round

»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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.