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

Автор sevlll777, история, 3 года назад, По-русски

Спасибо за участие, надеемся, что вам понравились задачи! Также мы просим вас оценить каждую из задач раунда в соответствующем спойлере, чтобы улучшить качество будущих соревнований.

Все задачи были подготовлены Alexdat2000 при помощи соавторов.

Почему AI не участвовал

1634A - Разворачивай и конкатенируй
Идея: sevlll777

Подсказка 1
Подсказка 2
Разбор
Решение
Оценка задачи

1634B - Гадание на массиве
Идея: crazyilian и antontrygubO_o

Подсказка 1
Подсказка 2
Подсказка 3
Разбор
Решение
Оценка задачи

1634C - ОКЕЯ
Идея: sevlll777

Подсказка 1
Подсказка 1.1
Подсказка 2
Разбор
Решение
Оценка задачи

1634D - В поисках нуля
Идея: sevlll777

Подсказка 1
Подсказка 2
Подсказка 2.1
Подсказка 3
Разбор
Решение
Оценка задачи

1634E - Честный делёж
Идея: sevlll777

Подсказка 1
Подсказка 2
Подсказка 3
Подсказка 4
Разбор
Решение
Оценка задачи

1634F - Прибавления Фибоначчи
Идея: Mangooste

Подсказка 1
Подсказка 2
Подсказка 3
Разбор
Решение
Оценка задачи
Разбор задач Codeforces Round 770 (Div. 2)
  • Проголосовать: нравится
  • +333
  • Проголосовать: не нравится

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

Thanks for fast editorial!

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

Problem B is the best problem I have seen in a long time!

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

Lightning-fast editorial

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

fast editorial!

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

Thanks for the fast tutorial

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

    This problem has a bit of a similar statement, but the solution and the idea are very different.

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

Problem B is very good! Thank you for so good 1200 problem!

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

What a great problem set! Thank you !!

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

B is nasty

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

E and F are great!I like them!

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

My solution to problem A is hacked

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

Great Problem E & F!They're the best problems I've seen in div2 :)

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

thanks for providing hints!!!

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

I have a different solution to F (I'm not sure if it is correct):

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

Why there are so many FSTs

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

Thanks.

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

In Korea, there is a similar problem with F. It was a great round, thanks.

https://www.acmicpc.net/problem/20305

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

I like Editorial With Hints

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

Congratulations, the author of this round. You scared AI away on behalf of humans.
They didn't compete at all!

The problems are so good, I thought, although they will give me a negtive rating change.

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

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

Here is a more casework-y solution for D using at most $$$2n-4$$$ queries (can be trivially improved to $$$2n-5$$$):

First of all, query all triples of the form $$$(1, 2, x)$$$. Store the values of $$$x$$$ that yield the maximal answer.

Exactly one position yields maximum
All positions yield maximum
Otherwise
»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For B, I just took everything modulo 2 and checked if the result could be obtained by adding Alice's number to the elements of the array modulo 2. I can't believe it worked. But I felt B was a lot harder than normal

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

My solution to D within $$$2n-5$$$ queries: 145449958

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

Problem F really should be swapped to D. It only had less than 100 AC because it's the last problem.

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

I still can't understand problem B

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

    If A[i] is odd, then regardless of which operation they choose, their number will change parity. If A[i] is even, then regardless of which operation they choose, their number will stay the same parity. x and x+3 are different parity, so regardless of what operations they choose, they will remain different parity. Check the parity of x compared to the parity of y after going through k odd numbers.

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

    Since XOR and SUM(or addition) have same effect on parity

    • odd + odd = even

    • even + even = even

    • odd + even = odd

    Hence after performing all the operations on input x there must be some parity of the result that should be same as parity of given output. Say after performing all the operations on x we get the result as odd number so output y given in the question must also be odd hence (sum(a) + x + y)%2 == 0 . And Why is it sufficient to check just the parity? Because it's given in the problem that answer always exist and parity of (x + 3) is different.

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

    In this problem, if the answer is not Alice, it must be Bob (Jury guarantees). Vice versa.

    The + and $$$\oplus$$$ operations have one thing in common: the parity of the res of A + B or A $$$\oplus$$$ B will be opposite with A only if B is an odd number. Visually:

    A B A+B and A $$$\oplus$$$ B are both
    odd odd even
    odd even odd
    even odd odd
    even even even

    So we can count the odd numbers in the input array. If the number of odd numbers is an odd number, the parity of the final result will be opposite to the starting.

    If the number of odd numbers is odd, then the parity of the starting number and ending number must be different. So if $$$x$$$ and $$$y$$$ have the same parity, it's impossible to let Alice win. Then the answer will be Bob.

    On the contrary, if the number of odd numbers is even, the parity of the starting number and ending number must be the same. So if $$$x$$$ and $$$y$$$ have different parity, it's also impossible to let Alice win. Therefore, the answer is also Bob.

    For other conditions, Alice will win.

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

Problem F's Time Limit is 1s,to be honest,I think it is meaningless,boring and FUCKING.My solution is $$$O(n)$$$ but I used "cin" to read a char.During the last 10 sec I submitted it.Then I got TLE on 7?

And what is the fact? Some solutions about $$$O(nlogn)$$$ even $$$O(n\sqrt{n})$$$ passed the systemtests, ridiculously ,some solutions about $$$O(n)$$$ failed the systemtests or failed the pretests.

Don't you think you had the order reversed??

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

    Your account has no submissions in the past two weeks, so evidently, you're outing yourself for competing with an alt in this round. That also makes it impossible for anyone to look at your submission and figure out what was going on.

    But besides that, I'm not sure why it's the authors' fault that you chose a slow I/O method. My solution (145428158) passes comfortably using cin with the standard line of I/O optimizations.

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

    In addition, your solution uses absurd amount of extra % operations, that are very slow when modulo is not constant.

    Nowdays solutions usually requires fast io to work in time because everyone uses it. More people will send slow solutions but just with fast io and get AC if tls were oriented on slow io solutions. The fact that nlogn and nsqrtn were accepted is sad, but we can't do anything about that because these solutions are vety optimized, and we want people not struggle TOO much with linear solutions, so we can't make tl even lower. Anyway, we have pyhton solutions that works under 1 second, so cpp solutions should feel more than comfortable.

    (Also, don't talk too much that you use fakes, it's kinda bannable)

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

    Even a relatively unoptimized solution passes in 280ms, which is very comfortable:

    145479475

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

    Definitely!Just now I submitted a code with "cin" and sentences,such as "ios::sync_with_stdio(false)",to read,and then I got TLE on test 9. 145534508

    Then I change nothing in my code but "cin" to an inline reading function "read()".Guess what?I got AC145534597

    Both my code run an algorithm about O(n) and the first submission failed because of READING!

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

      Now not really, the first submission didn't fail because of reading, it failed because of a combination of slow reading and slow query handling. You needlessly use 10 modulo operations by a non-constant modulo per query, which is pretty damn slow.

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

    I think the problem which can't make the code with right complexity get AC is stupid.

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

My solution to D in around $$$1.5n$$$ queries 145469547

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

задача Е мне немного напомнила Е с первого отбора на Innopolis Open 2022, там так же была похожая подгруппа, когда массив А был равен массиву Б, и там надо было вместо потоков писать эйлеровость

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

Video editorial for anyone wanting looking

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

For problem F:

  1. What is the motivation for the construction of the auxiliary array D?

  2. Is there any solution which utilizes the fact that $$$F_n = \mathbf{A}^n$$$, where $$$\mathbf{A}$$$ is the matrix $$$[[1,1], [1,0]]$$$? Then, the problem would be like adding a bunch of geometric series, which seems maybe possible idk.

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

    My motivation: the difficult part of this problem is clearly performing range Fibonacci updates, so our first order of business is to simplify the queries. One common way of simplifying range queries is to transform the array in order to turn range queries into point queries (consider, for example, the standard trick of storing the difference array instead of the original array in order to handle range updates/point queries using a BIT or standard segtree). When we perform standard range additions, the change in $$$x_n - x_{n-1}$$$ is zero for points in the middle of the array; in this case, we see that for points in the middle of the update, the change in $$$x_n - x_{n-1} - x_{n-2}$$$ is zero. Therefore, after performing the given transformation, the range updates influence only a few points of the array, which is what we hoped to achieve.

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

I bow-down before my master who came up with problem B.

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

Why in problem D , constraints were given for n^2 time complexity as the problem can be easily solved in O(n).

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

swap(B,C)

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

For the pretest 3 667765307 0 150058801 880433548 of D, why my solution gave answer 4 2 locally, but 4 3 on codeforces? (Sorry for my poor English)

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

    There are 6 if conditions when eliminating non-zero elements. There's a typo in 2 of your if conditions, the third and fourth one. (You seem to have accidentally swapped the v.push_back(...) line of these 2 blocks).

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

      The idea is: if a query is equal to mx, it must contains zero, so we just push_back the common ids two queries have, not the themselves id.

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

If problem B was as follows : Alice starts with x and Bob starts with x+1 it woulda been much more solvable coz then one would find easily an answer to the question "What does x and x+1 mean or contribute to the solution" I don't see why the authors chose x+3 over x+1 maybe I missed something that makes it crucial to the problem

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

    I think they chose x+3 in order to make the solution not so obvious.

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

    why would they want to make it more solvable you have to do this thing....

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

    We had 3 options for this number: $$$x + 1$$$, $$$x + 3$$$ and $$$x^2 - 1$$$. Third one tricks you with $$$x^2-1 = (x-1)*(x+1)$$$, so we decided it'll be too hard. We thought that with $$$x+1$$$ problem becomes easier than we want, because it forces you to think about a parity. So finally we decided to pick $$$x+3$$$ as "the golden mean". After contest I can say, that it was better to put $$$x+1$$$ instead of $$$x+3$$$, but we really didn't expect that problem B will be that hard, sorry for this.

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

In problem C, I can't understand why this arrangement is not Correct!!,

n = 2, k = 3,

1 2 6

3 4 5

Please Help!!

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

Can someone explain problem B?

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

    (x+y)%2 == (x xor y)%2 so whatever you do doesn't matter at the beginning alice and bob have numbers with different parity so at the end also they will have numbers with different parity hence only one of these can be winner

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

Was AI participating?

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

I didn't manage to solve B but for me it's the best problem I've ever seen on codeforces. It's so simple when you know the solution. I feel extremely stupid now.

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

If on B we modify the fact that Bob starts with x+3 and lets say he will start with x+z ,is this problem solvable under these constraints? for z odd is the same problem, but i am interested in z even.

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

Can anyone tell me how you came up with a solution for E? Are there any other similar problems that use Euler circuit in a similar way?

I was able to came up with max flow solution but it was too slow. I also now how to find Euler circuit. Just have no idea how some could connect that algorithm with problem E Thx in advance

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

Thank you for writing editorial in this format. It helps beginners like us when hint is given instead of direct solution.

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

Solution for [problem D]:-(https://codeforces.me/problemset/problem/1634/D)

Idea:-

Disclaimer:- min and max here is index of min and max element. I am not claiming index at min to be min and max to be max but instead saying that one of them is for sure min and max.

Think of a situation, where we are able to find the max and min elements of the subarray that we have already traversed and we have the difference diff = element at max — element at min. So traversing to the next element will make changes to the current diff only if next element is smaller than min or greater than max.

We are going to update ** max , min , and diff** according to that and finally max and min is going to be our answer. (i.e if the new element is making changes to diff then update or otherwise skip)

  1. So First, I find min and max of the first four elements.(Took 6 queries).

  2. Second, I am iterating from the 5th element onwards and firing two query for each element

    i.e ? min, "any element that is not min or max", ith element

    **?  max , "any element that is not min or max", ith element**

again if the value we are getting is greater then our current diff value then we update accordingly.

Queries :- 2*n-2

Here is my submission:- Code

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

    Hey, I had the same idea but didn't get it to work during the contest. I have thought about it and am starting to feel convinced that this cannot always work i.e. it not possible to find the max and min of the first four elements reliably. For this, consider the first 4 numbers to be 1, 1, 2, 2. Note that there are exactly 4 possible queries on these 4 numbers (each query leaving out a different number). Moreover, each query must contain a 1 and a 2 which means that each query returns 1. So no matter how your code uses the information of your 6 queries (each of them would return 1), there must be a permutation of 1, 1, 2, 2 such that your min and max both point to 1s (or both point to 2s).

    I personally failed because of this issue on test 5. Since you passed all tests I am wondering whether my argument has some flaw. Or maybe not all permutations were actually checked in test 5?

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

      That is why there is solve2 function asking for two further query. Index 1, 2, 3 ,4 Value 1, 1, 2, 2

      q1-> 1 , 2 , 3

      q2-> 1 , 2 , 4

      q3-> 3 , 4 , 1

      q4-> 3, 4 , 2

      Now for each query, I will get my diff = 1 So, let's select first two queries as deciding one now since in {(1,2,3)and(1,2,4)} first two elements are in both so I am assuming that 1 and 2 is probably going to be my answer but now I will ask query two more query to verify it:-

      q5-> 3 , 4 , 1

      q5-> 3 , 4 , 2

      now if the results are still the same then I can for sure say that one of my min or max is coming from 3 or 4. so now my updated answer will be {3,1} or {3,2}.

      I wrote the solve2 function for solving this issue only. You can dry run and can check by yourself.

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

        Thanks for your answer.

        First note that your queries 5, 6 are redundant i.e. they don't give you more information than you already had.

        Now, based on your example and explanation I would think that your code would fail if the sequence were 1, 2, 1, 2 or 2, 1, 1, 2. Note that all queries would yield exactly the same result even though the input order changed. In particular, your code would have to decide exactly the same on either {3, 1} or {3, 2} to be the max/min pair. But this would be wrong here i.e. {3, 1} would be wrong for 1, 2, 1, 2 and {3, 2} would be wrong for 2, 1, 1, 2.

        However, test 5 checks both these cases and you pass them. So something in your code makes it work despite not having correctly found the min/max pair in the first 4 numbers.

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

          Thanks for pointing it out.

          Seems like they don't have a check for case 1,2,1,2 otherwise my code is not going to pass it.

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

            Thanks, for making me think harder into this. I checked it once more, the fact i.e there is one and only one zero leads my code to run correctly.

            Look that the code is giving {1,3} as its min-max value for {1,2,1,2} ohkk that is not correct but even after that, it is for sure is the condition when zero is not in our first four combinations. but as we move further whenever we encounter zero it will lead our diff to be maximum of all and update once of min or max to its index. And hence zero is always going to be in our min or max.

            You can also think in this way that our first six operations is not for finding min or max but for capturing index of zero, if it is there in the first four combination. And if it is not then it is going to be captured in our further iteration.

            Now, Hope this will help. Again thanks.

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

Can anyone please explain the approach for Problem E ??

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

There is a typo in editorial of Problem D -- $$$\overline{d} = c - a = c$$$, not $$$c - b$$$

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

Can anyone explain the solution to hint 2 of Problem F ?

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

    Make new array $$$D_i = C_i - C_{i - 1}$$$ (also $$$D_1 = C_1$$$). Than adding $$$x$$$ to segment is changing 2 values in $$$D$$$. And $$$C$$$ consists only of zeroes = $$$D$$$ consists only of zeroes.

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

I didn't solve B but when I looked at the solution I kind of went "ooooooohh, that's really cool" Thank you, very cool

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

The n<=1000 constraint in task D was really misleading...

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

    We had to lower the constraints due to, uh, Windows. Input-output is terribly slow on Win32, and if C/C++ programmers have those magic lines for speeding up I/O a bit, Python guys (as well as some other languages) have nothing like that. We wanted Python solutions to pass too, hence a lower constraint.

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

I have a sexy solution for problem D. It uses only ceil(3/2*n) queries.

Here it is: 145493474.

Can anybody hack it?

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

god E is unbelievable!!!

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

For problem D: Finding Zeroes: For every 4 queries that the editorial makes, you can actually do it in 3. Here's a gist of the idea.

First, we need to understand how the editorial eliminates 2 non-zero numbers amongst the given 4 numbers, $$$(x_1, x_2, x_3, x_4)$$$. WLOG, assume that $$$x_1 \leq x_2 \leq x_3 \leq x_4$$$. As given in the sample example, you query for

Tuple Result
$$$(x_1, x_2, x_3)$$$ $$$(x_3 - x_1)$$$
$$$(x_2, x_3, x_4)$$$ $$$(x_4 - x_2)$$$
$$$(x_3, x_4, x_1)$$$ $$$(x_4 - x_1)$$$
$$$(x_4, x_1, x_2)$$$ $$$(x_4 - x_1)$$$

If you consider $$$x_i$$$ as points on the number line, then each query gives you the length of the interval. Now, notice:

  1. $$$(x_4 - x_1)$$$ is the largest interval length, i.e, the maixmal result amongst the 4 queries.
  2. $$$(x_4 - x_1)$$$ is repeated at least twice.
  3. When $$$(x_4 - x_1)$$$ is repeated, the intersection of the corresponding queries represent a $$$(min, max)$$$ pair.

Hence, we have the approach of the editorial. Query all 4 cyclic triplets, find the maximum value, find another occurrence of it, take the intersection and eliminate 2 numbers which aren't in the intersection.

Now, how to reduce this to 3 queries? We know that the maximal result has to repeat at least once. So, if we just make the first 3 queries, either the maximal result has already been repeated, in which case we simply take the intersection, or the maximal result has not yet been repeated, in that case, we know what the result of the last query is going to be (the maximal result itself), so we can avoid making the query :)

Number of queries used: For every 4 queries in the editorial, we use 3. Hence, for even $$$N$$$, we have:

$$$\frac{(n - 2)}{2}*3 = \frac{3n}{2} - 3$$$

For odd N

$$$\frac{(n - 3)}{2}*3 + 3 = \frac{3n}{2} - \frac{3}{2}$$$
»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Problem B is such a nice problem and when I realize the solution of it I was so surprised!I laughed out at the same time. P.S:More B-like problem pls!

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

This contest is for Alphacode with E&F which is not flexible enough.

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

B was really amazing problem i didn't know about that concept yet but now i got that.

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

Problem D is really a great problem (

BTW, Why can't I use fwrite in Problem D even using fflush(stdout) at the end of every output? (It get ILEed at the first testcase)

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

In case someone is interested, Video Solutions for A-D

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

Can problem E be solved using bipartite matching?

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

    Yes, for each row, connect (i,2*j) and (i,2*j+1), for 0<=j for each distinct value, connect the 2*i th position and the 2*i+1 th position of this value's occurrences.

    If every distinct value's frequency is even, we can see that there is no odd length cycle in this undirected graph that we just constructed.

    Why? If 2 nodes are linked, either they are sitting next to each other on the array, or their occurrences as values are next to each other. Our construction allows at most 2 edges for each (i,j), and these 2 edges are of different types. If odd length cycle occurs, then it contradicts our construction.

    Since there is no odd length cycle, the graph is bipartite, and thus can be coloured into equal number of black and white nodes.

    The final colouring will be our answer.

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

Problem E is beauty. Loved it. <3

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

Hi I am facing trouble in problem E 145451100 it is giving WA on Test case 3 I cannot figure out why? I have followed a different approach. Please help Thank u in advance

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

    Your approach seems to be wrong here is the simple test:

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

AI after reading quotes in the Problems:

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

A minor quibble on the tutorial for problem E, but I think an important one nonetheless:

Is it necessarily an Eulerian circuit? To my mind, rather, it is a series of circuits (possibly just one, in which case yes, Eulerian) which start and finish at the same end-point, rather than necessarily being an Eulerian circuit of the whole graph. You could consider each circuit an Eulerian circuit of its connected component.

Consider the following example:

4
2
1 2
2
1 2
2
3 4
2
3 4

Now label the numbers 1 to 4 as vertices 1, 2, 3 and 4, and the arrays as vertices 5, 6, 7, 8.

The two required circuits are 5 -> 1 -> 6 -> 2 -> 5 and 7 -> 3 -> 8 -> 4 -> 7. Neither is an Eulerian circuit of the graph. Instead they are distinct circuits which, together, traverse every edge.

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

My take on Problem B: Reason why + and ^ have the same effect on the last bit is that a+b = a^b+(a&b)<<1, so we are sure that the last bit in (a&b)<<1 is 0. If we add 0 to any number it doesn't change so for the last bit we can ignore adding (a&b)<<1 and simply take xor of all values of a with x and x+3, the last 2 bits in x and x+3 will always be different, so exactly one of them will give the same parity as y and that is our answer.

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

This is a good round. But I think there is a big difficulty gap between Problem C and Problem D.

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

    D should be swapped with F.

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

      A bold claim! I think the order was probably correct. F is easy to understand but tough to have the right idea as seen through the low solve numbers.

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

For problem C, I think the simpler and crucial observation is that any A.P, as long as the common difference is even, is divisible by n (no. of elements in A.P).

Since,

Sn = n/2 (2 *a + (n-1)*d), n = no. of terms in A.P, d = common difference

To Rewrite, Sn = n * (a + (n-1)*d/2 )

Clearly, if 'd' is even then the sum is divisible by 'n', which translates to the number of shelves being even in the problem.

And now, it's easy to see that as long as the number of shelves are even, a solution will exist. And a simple solution is the A.P with common difference = n

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

There is a simpler solution for D. Consider fixing the first 2 numbers. Iterate over all n-2 possibilities for the last number and take the index with the maximum result (if all results are the same we can be assured that the 0 is one of the first 2 numbers). Now we know that the last number is definitely either the maximum element or the 0 element. Next take the second number and iterate over n-2 possibilities for it and choose the one that maximizes it (if all of the results are the same then the first or last number is definitely the 0). Once you have the index that produces the maximum result the second number or the last number is definitely the 0.

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

    I don't think you are right(or I just can't get your idea).What about this example? A array a[5]={1,1,0,2,2}.If you iterate over all n-2 possibilities for the last number,you will find that all result are the same ,but 0 isn't one of the first 2 numbers.

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

      Ok yea I forgot about this case. I’m pretty sure it still works tho if u ignore the first thing I said about terminating early if last number query never changes.

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

        You are right.Just not rigorous in the first time.In fact,I have the same thinking with you.But because of this example,I failed to do it by myself.

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

Because problem B has a "dp" tag involved in it, Can someone tell, how dp can be applied to solve it?

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

I love how in B and D is used alternative thinking: define the answer by knowing which ones are not answer at all. Thanks for the creators of such an amazing contest!

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

I think AI can't solve any problem in this contest.

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

how can I think of the Difference of F

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

Finally got my segment tree accepted in F, but I had to push it very hard. It's also (in my opinion) a lot harder to code than the official solution, so I don't see any reason to punish this one. Which makes me curious, what was the motivation behind the time constraints in F?

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

Another approach for problem E without using eulerian circuit:

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

It is (nearly) the best div.2 D I have ever met.

I wrote a solution to it in chinese link

It seems to be more difficult than the official solution :-(

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

Cool problems!)

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

I really loved the problems this time around. Since I mocked this contest, I felt solving with hints make the learning process x100 times better as I get some help but not too much and can solve the problem still kind of by myself. Finding zero was a really elegant interactive problem, and problems B. and C. were amazing. Thank you for the great practice!

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

Honestly I feel like the F problem is genius and really smart

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

Problem E is pretty similar to IMO 2020, Problem 3

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

I have a solution of $$$D$$$ which requires max $$$2n-3$$$ queries

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

B is insane. I was only able to come up with a naive dp solution and I thought that editorial solution would be some crazy formula. Btwn what if for some k, x and x + k has same parity which is also equal to parity of y? Is there a hard version of this problem?

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

Bonito!