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

Автор Wind_Eagle, история, 4 недели назад, По-русски

38-20230104210158

Привет, Codeforces!

Я очень рад пригласить вас на Codeforces Round #843 (Div. 2), который пройдет в 10.01.2023 14:15 (Московское время). Этот раунд будет рейтинговым для участников, чей рейтинг ниже, чем 2100.

Моя искренняя благодарность:

У вас будет 2.5 часа на решение 6 задач, одна из которых будет разбита на простую и сложную версии. Раунд основан на задачах первого тура третьего этапа республиканской олимпиады по информатике в Беларуси. Просьба всех белорусских школьников, участвовавших в третьем этапе, воздержаться от участия в раунде и обсуждения задач публично до конца раунда.

Я надеюсь, вам понравится раунд!

Тестировали раунд: MathBoy, FairyWinx, nnv-nick, K1ppy, olya.masaeva, Septimelon, PavelKorchagin, 4qqqq, kova1.

Разбалловка: (500+1000)-1000-1500-2000-2000-2500.

UPD. Разбалловка была изменена: (500+500)-1000-1500-2000-2250-3000.

UPD2: Поздравления победителям!

Победители

Проголосуйте за вашу любимую задачу!

Задача А: Садовник и капибары

Задача B: Садовник и массив

Задача C: Интересный ряд

Задача D: Дружелюбные пауки

Задача E: Уравнивание людей

Задача F: Лаборатория на Плутоне

UPD3: Наконец-то готов разбор: тык сюда

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

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

omg subtasks for A round

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

I wish Belarusian students good luck on Belarusian Regional Olympiad.

I hope tasks will be interesting for you :)

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

Thanks for inviting


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

Please no more problems like edu 141B

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

    Delete this they will surely give it then

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

    That's was a good constructive problem. I like those problems because even newbie can solve it and i have seen even master are sometimes not able to solve them. Try till you get the right approach.(It's just how i see them haha).

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

      Well I literally hate problems like edu 141B and div2 842C. I feel like these problems are all about guessing. The faster you guess the better rank you get

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

could u try to post a blog about this server recently i got to know about this server where mass copiying happens https://discord.gg/6RskCNmG

»
4 недели назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

could u post a blog about this server i recently got to know about this where mass copiying is happening https://discord.gg/6RskCNmG

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

As a tester, I'd like to say that problems are interesting imo and I recommend you to participate!

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

hope this time problem statement is clear :/

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

First time see a problem A with hard version

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

WOW Problem A 1500 point

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

long time since A had a subtask

now could you imagine if it was interactive as well :D

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

Good luck everyone!

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

for the first time i think there would be subtasks for a this is very exciting!

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

Omg! Yellow round.

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

So it seems like from the score distribution, the whole problem A has the same difficulty as B right?

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

OMG,there are subtask for problem A.

»
4 недели назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Dont include Mathematical Problems please.

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

Will this contest be as beauty-full as the last one.XD.

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

Finally a contest with friendly time to Chinese coders! Gl, hf!

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

    Actually, 22:35(UTC+8) is not TOO unfriendly for who are used to staying up late. It's better called friendly time to Australian coders.

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

    I remember that once there were two contests held at about 15:35(UTC+8) and 18:35(UTC+8) on the same day.

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

    Exactly, very friendly time! Hopefully, this is also a fantastic round!

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

    Of course it's a very friendly time.I can't stay up late because my father don't allow me to do that:)

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

    nice

»
4 недели назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

i give up :(

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

Div2 A with subtasks? Sounds interesting,but I don't know if it will be a good problem.

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

OMG unusual starting time and subtasks for A!! Wish you positive delta!!

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

harder version? omg with the same rating

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

Finally, the opportunity presents itself. I will become a newbie again.

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

Unusual time :(

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

I hope that this round will be a starting point for me to succeed in the new year 2023 ! And I wish good luck and success to everyone this year.

»
4 недели назад, # |
  Проголосовать: нравится -77 Проголосовать: не нравится

Hello can you upvote me to help me with my contribution.

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

Plan to take part in this contest. Hope $$$\Delta>0$$$ for me, and you too!

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

pupil round

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

NOTE THE UNUSUAL TIME

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

I am waiting for this

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

Why some hacks are still in queue.

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

wow

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

OMG, subtasks in problem A!

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

My GPA is crying out

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

I just want to be green name.QAQ

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

8 pm is best time . We have classes at college .

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

Hope it will be a wonderful contest with fantastic problems!

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

As a Chinese,I usually have to stay up late for the cf round, but today I can go to bed earlier, so enjoy it and have fun!

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

Ok so in this round I will not able to do problem A as well (interesting).

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

I suggest to do more A , B subtasks in the future

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

orz 244mhq

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

Why Delay 10 min Sir ??

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

 

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

10 min. delay!

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

Contest start time changed?

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

10 min. delay!

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

DelayForces

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

Now it's delay-master-forces.

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

Will there be second delay if the rating update of last contest still uncompleted?

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

Чёт так жалко белорусских школьников стало.

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

I did not understand at all what to do in the task B

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

I love this world.

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

Love this contest! As I expected from CF Round #741's author.

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

F is 100491E - Expedition to Mars on higher constraints but it's possible to adjust the intended solution to 4e5.

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

    Actually, I agree with you it's just a matter of time to solve this version if you have a solution for that gym problem and 144 participants solved that problem already I guess so it's easy for them.

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

      Tbf $$$n$$$ up to $$$500$$$ allows a lot more different approaches. When my team and I were solving that gym contest, we went for a solution that isn't really viable for $$$4 \cdot 10^5$$$. Well, at least I failed to fix it :(

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

The most balanced contest

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

I kinda feel bad for spiders with one leg(

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

For C when i run the code in my system it was giving correct output for testcase 1 , but its giving wrong output when run on codeforces for testcase 1 . Any Idea why so ? https://codeforces.com/contest/1775/submission/188754539

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

Nice problemset..

How to solve C?

  • »
    »
    4 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится
    • If $$$x = n$$$, the answer is trivially $$$n$$$ itself.

    • If $$$x = 0$$$, this means that the most significant bit of $$$n$$$ must become 0 at some point. If this is the $$$a$$$-th bit from the right, then the first number to flip this bit is $$$2^a$$$ (single 1 followed by $$$a$$$ 0s). So the AND must include $$$2^a$$$ and we can see that $$$x$$$ AND $$$2^a$$$ is 0, so the answer is $$$2^a$$$.

    • Now $$$x$$$ must have at least one $$$1$$$. Find the last $$$1$$$ in $$$x$$$, and let's say it's at position $$$\ell$$$. Because bit $$$\ell$$$ is a 1, this means it was never flipped while incrementing the numbers, suggesting that all bits to the left of bit $$$\ell$$$ remain unchanged. So the prefix of $$$x$$$ up to bit $$$\ell$$$ must be equal to the prefix of $$$n$$$ up to bit $$$\ell$$$. If there is a mismatch, the answer is $$$-1$$$.

    • We can now write $$$x$$$ as some $$$prefix$$$ (which ends with a 1) followed by all 0s, and $$$n$$$ as the same $$$prefix$$$ followed by some $$$suffix$$$ (whose length matches the block of 0s at the end of $$$x$$$). There are two further cases to consider:

    1. If the $$$suffix$$$ begins with a 1, then we have a problem. Since this bit is 0 in $$$x$$$, it must be flipped at some point. But flipping this 1 will also flip the 1 to its left, i.e., the last bit of the $$$prefix$$$. But we know that the $$$prefix$$$ cannot change, so this scenario cannot happen, i.e., answer is $$$-1$$$.

    2. Otherwise, find the first 1 in the $$$suffix$$$. Let's say it's in position $$$c$$$ (from the right). This bit is 0 in $$$x$$$, so it must be flipped at some point. When this bit is first flipped, the bit at its immediate left (position $$$c + 1$$$) becomes 1, and everything after it becomes 0. This number is $$$x + 2^{c + 1}$$$, i.e., the common $$$prefix$$$ followed by all 0s except a 1 in position $$$c + 1$$$. Conveniently, applying AND between this number and $$$n$$$ will already yield $$$x$$$ (the only $$$1$$$ after the prefix is at position $$$c + 1$$$, which is a 0 in $$$n$$$), so this number is the answer.

    My submission: 188732906. I converted the numbers to binary first, and worked from there, converting back when printing the answer (except when the answer was $$$n$$$ or $$$x$$$ itself).

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

      "I converted the numbers to binary first, and worked from there, converting back when printing the answer."

      Conveniently for me, my computer stores numbers as binary internally so I never need to convert back and forth.

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

        lol, yeah, I know I can use bit shifts to process them faster, but binary strings are more readable imo. I don't have enough experience with bit shifting to be confident that I can code the correct solution with lower thinking + typing time.

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

    Answer will always lie between n and INT64MAX and bitwise and from n to k >= bitwise and from n to k+1 therefore you can apply binary search . To find bitwise and from n to k you can search on net and get method easily .

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

      "bitwise and from n to k >= bitwise and from n to k+1"

      How did u arrive at this property? Can you please explain/elaborate as i am unable to understand.

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

        just try to analyze the truth table of AND.after applying and operator you will realize that, it keeps value as it is or make it decrease.

        1&1=1 0&0=0 value remains as it is in above two cases.

        0&1=0 1&0=0 value decreases in these cases.

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

"Time limit exceeded on pretest 12"

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

I hate A so much that I mistook subarray for subsequence in B.

OMG I didn't read this in problem A

Spoiler

Problem A-D is interesting.

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

How to solve F?

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

    I suspect giant casework.

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

      Actually, no. The short idea is that all the possible answers are just rectangles with their angles cut somehow. You need to make a DP on how you cut the angles and iterate over the possible rectangles.

      For example, if $$$n=7$$$, then the optimal perimeter is $$$12$$$, and you need to try out the rectangles $$$3\times3$$$, $$$4\times2$$$ and $$$2\times4$$$ and cut their four angles somehow. A cut of an angle is just removing a stair-like figure, so it's calculated with DP.

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

        Ah got it, problem seems interesting now!

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

        The idea is actually obvious, can you tell how to calculate the DP?

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

          You may precalculate $$$dp_{n,k}$$$, that is the number of stairs from $$$n$$$ blocks which are $$$k$$$-block tall. This DP can be computed in $$$O(n^2)$$$, but, since the number of blocks to be cut from angles is no more than $$$O(\sqrt n)$$$ in total, it's OK.

          Then, you just need to write another DP which decides on how much blocks to cut from each angle. It's $$$d_{i,j}$$$ where we have decided about the first $$$i$$$ angles and have already cut $$$j$$$ blocks.

          Note that all these DPs can be calculated in the beginning and used to answer all of the testcases.

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

            Got it, thanks!

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

            But how do you check that the stairs in different angles do not intersect while calculating $$$d_{i, j}$$$?

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

              You don't have to check it.

              If they are going to intersect, then the perimeter is just not optimal.

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

                Oh yeah, fair enough. It was the only part I was struggling with and this observation is so easy (( Thanks a lot!!

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

              They will not intersect. Because if it is possible, you can decrease the perimeter of your figure.

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

Any idea of B? I've tried many times but always got TLE

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

    Also please update the rating of last educational round quickly

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

      What I have done, is to count the no of occurrence of a bit throughout the whole array. Then for each element in the array if any bit which is set for this element is also set for any other element, Then the ans is always yes otherwise no

      Let me explain the reason with an example ,consider a no whose bit 2 and 4 is set. Another no whose bit 2,1 and 3 is set and another no whose bit 4, 5 and 7 is set. Since For First No, every bit that is set for this, also set for either b and c, so we can always take Or of every no in the array and Or of every No except that No(First one in this case). In Other words f(a) = Second No | Third No, f(b) = First No | Second No | Third No. Hence Ans is always possible.

      Here is my submission 188728251

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

    If bits set in one number is a subset of another number , then the answer is always possible.

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

    Did you by any chance used a fixed-size frequency array? freq[200001] * n <= 10e5 = TLE... I should know from having fallen for it 5 times this contest.

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

    I've thought Double linked-list and priority-queue could solve E, but got WA.

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

    when I used vector to store the frequencies I got the TLE, but then changed to unordered_map it passed. not sure why vector[i] is slower than map[i] :(

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

      I used int[200001] and got TLE 5 times because I forgot n <= 10e5 so I was doing 200000 operations per test case just setting up a frequency array.

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

    Two cases:

    1) if second character is ‘a’, then place s[0] s[1] rest

    2) if second character is ‘b’, then place s[0] allCharactersExceptLast s[n-1]

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

    Hint: the first subsequence is the whole array, the second is the whole array except only one number.

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

      I've noticed that but my approach got TLE

      It seems that we need to store frequencies by map instead of array

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

        You can use array, but it should be global. Furthermore, you should only set the elements you touch to 0, not the full array.

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

How to solve E?

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

    Let $$$s_1$$$ be the maximum sum over all subarrays and $$$s_2$$$ be the minimum sum over all subarrays, then the answer is $$$\max(s_1,-s_2)$$$.

    Lower bound

    Clearly you can change the sum of some subarray by at most 1 per operation, so the answer can't be lower than $$$\max(s_1,-s_2)$$$.

    Upper bound

    For simplicity we suppose $$$s_1>-s_2$$$.

    Consider the following rules:

    1. Adjacent positive elements are automatically merged into their sum. (The same for negative elements)

    2. Zeros are automatically removed from the array.

    It can be shown the answer won't change if we apply the rules.

    After merging, we can repeatly try to change every element closer to 0 and apply the rules after each operation. It can be shown it's optimal. The sum of the greatest subarray will always reduce by 1 after each operation. (If we can't at some moment, then it's not the greatest subarray.)

    If the answer is greater than $$$s_1$$$, then there exists a subarray with sum greater than $$$s_1$$$, which is a contradiction.

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

      currently, your comment helps pretty much noone except those who just who want to see a AC and be done with the problem.

      What was the idea? how did you come up with it?

      Errorgorn's solution makes much mose sense in that regards

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

        The intuition is that after each operation, the total sum of the elements changes by $$$-1, 0$$$, or $$$+1$$$. So if the current sum is $$$s$$$, then the answer is at least $$$abs(s)$$$.

        The second thing to note here is that the answer for the whole array is at least the answer for some consecutive subarrays. So the answer is at least the maximum of the absolute value over all subarray sums.

        Seems like this is achievable. But I currently don't have a proof for this. I have solved it using the same approach that errogorn used in the next comment.

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

        Sorry, it's my bad. I've added some details.

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

    We will process elements left to right. When processing some element, we either create new operation or extend some old operation.

    Intuitively, it makes sense that we would not have to using operations to both add and subtract from an element. So a simple $$$O(n)$$$ greedy works.

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

      Thank you very much!

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

      Is there any formal proof? (or an outline of a formal one)

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

    Think about a sequence of prefix sums and observer how such operation affects this sequence of prefix sums.

    If you analyze carefully enough, then you'll see that one of the operations just adds $$$1$$$ to any subsequence of prefix sums, and the other operations just subtracts $$$1$$$ from any subsequence of prefix sums.

    So, AFAIK you just need $$$\max(0, \max(p_i)) + \max(0, \max(-p_i))$$$ where $$$p_i$$$ is the array of prefix sums.

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

I take back my words, it was a nice round.

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

F: Why did you set two types of questions as one problem? The difficulty levels of the two questions are different, so I think they should be set as separate problems.

A problem of calculating the number of ways was very interesting!!

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

    I think subtask 1 is as easy as problem A...

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

    You are right probably, it should be split.

    By the way, the original contest is OI-style, so there two problems were combined as one, with different groups for each of the subproblems. For Codeforces, the problem was just retained as-is.

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

can we use binary search for Problem C? since & is decreasing function, bitwise and of all number from n to m will be higher than x initially. We need to find first position where bitwise and of all number from n to m is x

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

Problem E almost = This Problem

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

    Yes, you are right, sorry for that :(

    It's interesting that the round with the similar problem is also of Belarusian origin, but the authors came up with the idea independently AFAIK, so it's an unfortunate coincidence.

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

Very nice contest! Congrats to the authors!

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

lol, img when i got wrong ans on test 15 problem D and it was only 5 minutes left

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

bruh I feel like a total loser, but at least I'm trying and participating lol

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

if i solved a problem correctly in contest and later during contest , by mistake i submit wrong code for that problem then is question point are added or not to my points

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

In problem B, I read "exclusive or" instead of "bitwise or" and was thinking how to find out if the set of sparse binary vectors is linearly independent and why it is Div2.B

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

String consists of letters 'a' and 'b' only :) could have written it in black :)))

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

    Well, I just knew about it know.....

»
4 недели назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

I think B problem cannot be solved by people who use JAVA because my O (n * k) solution is getting TLE even after using the fastest I/O operations. Link to my Submission :- https://codeforces.com/contest/1775/submission/188733443

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

    change your "int[] freq" to "map freq" and try, it worked for me in c++.

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

    Fixed-size frequency array is unsafe, n <= 10e5 so setting up a frequency array for each test case will instantly TLE you. USe map/hashmap because k constraint is guaranteed to be <= 10e5

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

      You are saying that as t <= 10^5, so the freq array of size 2 * 10^5 (max p) will be iniatialized for each t which will give TLE and everytime initializing a fixed length array is not good beacuse there may be a case when max p is very small but still I am iterating till 2 * 10^5 every time which is unnecessary and the reason for TLE. But HashMap will not give TLE beacuse when we initialize a HashMap its initial size is very small due to which it will not give TLE. Right?

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

if i solved a problem correctly in contest and later during contest , by mistake i submit wrong code for that problem then is question points are added or not to my points

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

how to solve problem b??

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

I can't understand the Input of B :(

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

    in problem b n is size of array and n line is given in each line first no is the no of set bit in that number and after that positions of set bit is given

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

      I still don't get it, but thanks anyway.

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

        The very first number is the number of test cases.

        The first number of each test case (say k) is the number of elements in the array of that case.

        Now k lines of space-separated numbers follow — each line is an element of the array represented in this form: the first number (p) is the count of set bits of that particular element of the array.

        The numbers that appear after p (there are p of them) are the positions of each of the set bits.

        Edit: Essentially, each individual line represents an element in the array.

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

          If a line is 3 1 2 5,the binary number is 10011,to decimalism is 19. In the contest I understand it this way,Is it so?

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

            Yes, 3 1 2 5 implies 10011

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

              Wow!!

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

              The "Note":In the second test case, one of the possible answers are following subsequences: the subsequence a formed by the element at position 1, and the subsequence b formed by the elements at positions 1 and 2. 2 2 1 2 1 2 This is a array{3,2},but 3 != 3 ^ 2.this is why? Can you tell me? Thanks.

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

                I don't completely understand your question, but I can explain the second test case:

                2
                2 1 2
                1 2
                

                like you said, this represents the array [3, 2].

                The given solution for this case is that the two subsequences would be [elem_at_pos_1] and [elem_at_pos_1, elem_at_pos_2].

                So the text claims the subsequences would be s1 = [3] and s2 = [3, 2].

                And this is true because the bitwise OR of s1 = 3 (as there's only one number) and the bitwise OR of s2 = 3 | 2, which is also 3. Clearly, they're both equal.

                I think you may have misunderstood the bitwise OR operation to be something else.

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

                  Oh, I see. I mistake bitwise OR as XOR. QwQ My English is not good.I didn't expect to make such a mistake. Thank you very much.

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

                  No worries, cheers!

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

In task A, either the string b is lexicographically not smaller than the strings a and c at the same time, or the string b is lexicographically not greater than the strings a and c at the same time. @authors kindly look into the language

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

how to solve B? also in C is there any relation between x and m?

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

didn't read "The string consists of English letters 'a' and 'b' only." this part in A, So I solved it for every character and I had to use Z function for prefix comparison XD

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

Accepted in last 4th sec.

Screenshot-20230110-191726

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

Can't understand why for B:

1
2
3 8 2 2
3 8 3 3

answer is YES?

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

    Next follow ki distinct integers pi,1,pi,2,…,pi,ki (1≤pi≤2⋅10e5)

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

    Ki integers are guaranteed to be distinct

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

    This input is not valid, since the set bits must be distinct. For example, in the line 3 8 2 2, the given set bits are 8, 2, and 2, which is not a valid input. In the line 3 8 3 3, the given set bits are 8, 3, and 3, which is also not a valid input.

    If you actually meant the following:

    1
    2
    2 8 2
    2 8 3
    

    then the answer is NO.

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

Nice problems. Hope to see more contests like this in the future

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

Will this round be rated for who has reached 2100+ from 2100- in the last educational round?

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

Overlooking "the characters are A or B" from A2 took me 1hr...

I can't proof my solution for A2 (but it's allowed to use A-Z) so please hack it: 188722831

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

    This is actually a correct solution, if I'm not mistaken. For an arbitrary alphabet, if answer exists, then there exists such answer that |b| = 1. You can now solve task by bruteforce in O(n).

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

    I saw the A or B part, but didn't have a very good proof, so I solved it the most stupid way imaginable.

    • thought that the solution will have a border somewhere around the first/last occurrence of A or B
    • literally bruteforced every combination of first A/first B/last A/last B $$$\pm 1$$$
    • prayed for that there cannot be too many combinations where we needed to scan
    • got AC, still have no proof

    submission: 188710406

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

    I also overlook the a or b term which waste my 1.5 hours. And if am not wrong, the sentence which told that specific a or b term in A2 is added later on the contest. I have solved this through an observation that excluding the first and last character, if there exists an a then if I take it as the second word then it remains the smaller or equal the other two word which are the left and right part of the taken second word. If excluding the first and last character, there not exists an a then it should be the occurrences b and if I take those consecutive b as the second word and the first and last character respectively as the first and last word then the second word remains bigger or equal than the first and last word. In such these way, under the constraints of the problem there always exists a valid answer.

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

      And if am not wrong, the sentence which told that specific a or b term in A2 is added later on the contest

      You are wrong and just try to justify yourself.

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

        Thanks for the confirmation. It is honor for me to your reply. I don't try to justify myself. Everyone do mistakes. From next I will be aware of this.

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

    Intrestingly, this is the original problem that was given in the olympiad. It took me 1h40m to solve it, and when I saw codeforces standings, I was absolutely shocked by amount of people who solved it that quickly.

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

How to solve B and C ?

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

didn't notice the unusual timing :facepalm:

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

For C when i run the code in my system it was giving correct output for testcase 1 , but its giving wrong output when run on codeforces for testcase 1 . Any Idea why so ? https://codeforces.com/contest/1775/submission/188754539

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

Best ever standing and solved problem C in Div. 2 the first time! But I didn't have any clue of problem B :(

  • »
    »
    4 недели назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    Hint
    Solution
    • »
      »
      »
      4 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      but how are we sure that if we cant remove any element such that or of remaining element is same then answer will not exist?

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

        If for every number there is a unique bit that only appears into that number than to make the difference in the sequence you need to not take this one. If all the numbers contains a bit that is unique in them you have only two options either take all of them or nothing. To make them different we take both as these are the only options but there OR is not same.

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

      It seems that we should check every number in array c, if there exists one i, every bit in c[i] appears 2 times in the whole input, then the answer is "YES", otherwise "NO".

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

    poor English :( Obviously the maximum set is a1 or a2 or ... or an .So let p is this subsequence.

    To find q, the number of elements in q must be at least 2.In this case, without q the p has no elements left.

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

Some discussion for E:

The main purpose of operation is to decrease the value of sum(|ai|) (the sum of the absolute values of ai), to achieve this purpose, we need to subtract from positive numbers, and add to negative numbers.

So every time when we choose subsequence, we can assume we always choose it with alternative sign (which like {+a1, -a2, +a3, -a4...} or {-a1, +a2, -a3, +a4...}), because if not, we can remove 2 adjacent element with same sign, and the total change of sum(|ai|) remain the same.

Therefore, we can always choose the longest subsequence with alternative sign. We can regard some consecutive elements with same sime as one element, and regard zeros as not exist. So we can rewrite the initial array as some non-zero numbers with alternative sign, each element represents the sum of a maximal block with same sign.

So we can get the answer: In each step, we do min(|ai|) times of operation, and all |ai| will be decreased by that value, then we remove zeros from the array, and merge adjacent elements with the same sign. However, this naive approach will be O(n^2) and get TLE. How to optimize it? Notice that if we do min(|ai|) times of operation, some elements will become 0, and it's adjacent elements will be in the same "block with same sign" now. So we could store the initial array into a double linked-list, whose node is like (long:value, Node:prev, Node:next, boolean:valid) and put each node in a priority queue. Each time we poll out a valid node from the priority queue, we merge it with node.prev and node.next to get a new node, link it with node.prev.prev and node.next.next, add it to the priority queue, then mark node.prev and node.next as invalid. Then we could get an O(n*log(n)) solution. (Also do not forget check nullity)

Update: Now my submission:188766704 has got AC. Unfortunately, I've not implemented it properly during the contest. Sad!

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

can anyone let me know the way to solve C and how to imrpove concepts regarding bit , bit manipulation and bit masking

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

Mmmmmm

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

Mmmmm

Right after the contest :D

»
4 недели назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Wonderful round with great problems, it seems they all have clean solutions, but require "cute" observations. A2 is harder than E for me though (failed system testing on A2).

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

To problem B: Why is this case no? 1 3 2 1 2 2 3 4 2 5 6

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

    But the rating of last educational round has not updated yet! Please update it first! I should have been div1 in this contest......

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

      Oh, sorry for that, our fault. Will fix soon.

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

      I might be wrong, but I think whether the contest is rated for you or not depends on which rating you had at the time of registration. Even if the rating for the edu round was updated before this contest but after registration, this contest would still have counted for you.

      In fact, this is why some users deliberately register for as many contests as they're able to when they're close to the border, so that they're all counted even if they cross the border sometime in the middle, e.g., earning Div2 rating boosts even after reaching Div1.

      So regardless of when the ratings are updated, it should not change the fact that this round will be rated for you. In the future, please consider your rating at the time of registration before you decide to register for a contest, since rating changes that were not yet applied would not be considered for the contest you're registering for.

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