Блог пользователя Vladosiya

Автор Vladosiya, 19 месяцев назад, По-русски

Привет! В 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: Разбор

  • Проголосовать: нравится
  • +38
  • Проголосовать: не нравится

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

4 is my lucky number though :)

»
19 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

случайно поставил минус, я думал это див2 2 апреля

»
19 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Finally a Div 3 after a month :)

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i hate kanye west

»
19 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Scoring distribution should be added..!

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hopefully I'm able to participate.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    If I'm not mistaken, you will participate unofficially

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Hope to become Expert again

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

Need more frequent Div.3 contests for beginners.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

lessgo..

»
19 месяцев назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to become pupil today!

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hoping for Expert

»
19 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Is it Div2.25?

»
19 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

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.

»
19 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

worst Div. 3 contest ever.

»
19 месяцев назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    LoL, nice problem...

  • »
    »
    19 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    consider the number k in base 9.

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится
  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you tell me your digit dp approach?

    • »
      »
      »
      19 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        19 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          19 месяцев назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          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

        • »
          »
          »
          »
          »
          19 месяцев назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Yeah sorry, check the edited answer now.

      • »
        »
        »
        »
        19 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          19 месяцев назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          • »
            »
            »
            »
            »
            »
            19 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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

            • »
              »
              »
              »
              »
              »
              »
              19 месяцев назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

              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)

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    https://codeforces.net/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.

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

[deleted]

»
19 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

khatam

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится

[.]

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    19 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

    • »
      »
      »
      19 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

      what is the logic behind this?

      • »
        »
        »
        »
        19 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

G1 was much easier than C/D/F

»
19 месяцев назад, # |
Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

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

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

chromate00 Orz for the great performance!

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

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

      • »
        »
        »
        »
        19 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        yes actually I have saved the blue version for that

        • »
          »
          »
          »
          »
          19 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
Rev. 4   Проголосовать: нравится -6 Проголосовать: не нравится

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.

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you prove this conclusion?

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      • »
        »
        »
        »
        19 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks, did you solved D? Approach?

        • »
          »
          »
          »
          »
          19 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          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.

        • »
          »
          »
          »
          »
          19 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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

  • »
    »
    19 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Common conclusion ? Ahh you are from china, never mind

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
19 месяцев назад, # |
Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
19 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
19 месяцев назад, # |
Rev. 3   Проголосовать: нравится -44 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone provide an unofficial editorial for problem C?

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      what about this test case 0 1 2 1 0

      • »
        »
        »
        »
        19 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Nice problemset. I like task D

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E is classical and F is kind of bad.

BCD are nice problems.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Bro relax lmao(I totally agree).

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    why

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
Rev. 5   Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    Your solution for E is very cute

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        19 месяцев назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        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?

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
19 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve Problem D

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +55 Проголосовать: не нравится

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.

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +93 Проголосовать: не нравится

What the fucking description of F!

»
19 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится -18 Проголосовать: не нравится

    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

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      3rd party code posted before contest is allowed

      • »
        »
        »
        »
        19 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          19 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      19 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Numerous individuals have replicated content from YouTube, and it is imperative that Codeforces takes action regarding this issue.

»
19 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
»
19 месяцев назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

F is quiet confusing.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great Contest, couldnt solve many questions in the contest but as i upsolve, i realize that the problems were really good.

»
19 месяцев назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

make it unrated

»
19 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone provide a counter example for this submission?

»
19 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 "

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      19 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      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

»
19 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.net/contest/1811/submission/200724266

»
19 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

So hard div3,(sad).

»
19 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

seems that few people will pass F

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

When do the ratings update??

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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.

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

toooooooooooooooooooooooooooooo hard 4 div3

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will the system testing perform???

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

This round is hard for me.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

at this point, i wanna become an expert to never participate in a rated div 3 ever again..

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This server has been crashing for few months already. either fix this or make contests unrated.

»
19 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
5 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

recursion is useful.