Vladosiya's blog

Codeforces Round #863 (Div. 3)
By Vladosiya, 21 month(s) 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, 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

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

Comments Comments (214)
| Write comment?
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

4 is my lucky number though :)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Finally a Div 3 after a month :)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

i hate kanye west

→ Reply
»
21 month(s) ago, # |
  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 :((

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it -24 Vote: I do not like it

    hidden...

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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!

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        oh sorry, i was in a hurry

        → Reply
»
21 month(s) ago, # |
  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 ??

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      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

    → Reply
»
21 month(s) ago, # |
← 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 :)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Scoring distribution should be added..!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully I'm able to participate.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    If I'm not mistaken, you will participate unofficially

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
»
21 month(s) ago, # |
  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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Hope to become Expert again

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Need more frequent Div.3 contests for beginners.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

lessgo..

→ Reply
»
21 month(s) ago, # |
  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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      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.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become pupil today!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping for Expert

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Is it Div2.25?

→ Reply
»
21 month(s) ago, # |
  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?

→ Reply
»
21 month(s) ago, # |
  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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I am not so sure About D .

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      See if I'll be skipped then.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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!

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

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

          → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        it seem unrated.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

worst Div. 3 contest ever.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -20 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    LoL, nice problem...

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    consider the number k in base 9.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    https://oeis.org/A052406

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell me your digit dp approach?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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

          → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Yeah sorry, check the edited answer now.

          → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Just change endl to '\n'.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              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)

              → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I set Mx to 5e12

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

khatam

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

[.]

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← 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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      what is the logic behind this?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

G1 was much easier than C/D/F

→ Reply
»
21 month(s) ago, # |
← 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

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

chromate00 Orz for the great performance!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        yes actually I have saved the blue version for that

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
21 month(s) ago, # |
← 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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you prove this conclusion?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here it is

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks, did you solved D? Approach?

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

          → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Common conclusion ? Ahh you are from china, never mind

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      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.

    → Reply
»
21 month(s) ago, # |
← 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

→ Reply
»
21 month(s) ago, # |
  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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        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.

      → Reply
»
21 month(s) ago, # |
  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!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← 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

→ Reply
»
21 month(s) ago, # |
  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.

→ Reply
»
21 month(s) ago, # |
  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.

→ Reply
»
21 month(s) ago, # |
  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?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide an unofficial editorial for problem C?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      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

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what about this test case 0 1 2 1 0

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          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.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice problemset. I like task D

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

E is classical and F is kind of bad.

BCD are nice problems.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Bro relax lmao(I totally agree).

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my solution to B:

    il int find(int x, int y) {
	if (x > n / 2) x = n + 1 - x;
	if (y > n / 2) y = n + 1 - y;
	if (y <= x) return y;
	return x;
}

int main() {
	for(int T= read(); T--; ) {
		int x, y, xx, yy;
		read(n, x, y, xx, yy);
		printf("%d\n", abs(find(x, y) - find(xx, yy)));
	}
	rout;
}

    it's quite easy!!

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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});
}
      → Reply
»
21 month(s) ago, # |
← 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).

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Your solution for E is very cute

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your intuition for problem E? Thanks also just want to know if it is some type of standard problem.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Because digit 4 is forbidden, we only have 9 available digits, so remained numbers are some modified version of base-9 numbers(012345678 --> 012356789).

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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?

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's by the defination of k-flower.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve Problem D

→ Reply
»
21 month(s) ago, # |
← 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.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +93 Vote: I do not like it

What the fucking description of F!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's not thaat bad tbh)

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +44 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it -34 Vote: I do not like it

        then most of your friends aren't very bright

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          if you think so, whatever, you are right

          → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      3rd party code posted before contest is allowed

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +20 Vote: I do not like it

F is quiet confusing.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -21 Vote: I do not like it

make it unrated

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone provide a counter example for this submission?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it 
    Input:
1
7
0 1 2 2 1 0

Correct Output (for example):
0 0 1 2 1 0 0

Your Output:
0 0 1 2 0 0 0
    → Reply
»
21 month(s) ago, # |
  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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  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)]
→ Reply
»
21 month(s) ago, # |
  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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      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 "

    → Reply
»
21 month(s) ago, # |
  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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← 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

      → Reply
»
21 month(s) ago, # |
← 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 > 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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

So hard div3，(sad).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

seems that few people will pass F

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When do the ratings update??

→ Reply
»
21 month(s) ago, # |
  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.

→ Reply
»
21 month(s) ago, # |
← 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.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

toooooooooooooooooooooooooooooo hard 4 div3

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the system testing perform???

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

This round is hard for me.

→ Reply
»
21 month(s) ago, # |
  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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← 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.

    → Reply
»
21 month(s) ago, # |
  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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      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 ...

    → Reply
»
21 month(s) ago, # |
  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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maximum length is 5

    take the whole sequence and count of it is 1

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
21 month(s) ago, # |
  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

→ Reply
»
20 months ago, # |
  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.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

recursion is useful.

→ Reply