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

Автор satyam343, 2 года назад, По-английски

Hello, Codeforces!

mtw, naman1601 and I are glad to invite everyone to participate in Codeforces Round 825 (Div. 2), which will be held on Oct/10/2022 17:35 (Moscow time).

This Round will be rated for participants with rating lower than 2100.

You will be given 5 problems with one subtask and 2 hours to solve them

We would like to thank:

The score distribution will be announced closer to the start of the round.

UPD1: Score distribution is 500 — 1000 — ( 1250 + 2000 ) — 2000 — 2500.

UPD2: Congratulations to the winners!

Overall:

Rated:

UPD3: Editorial is out.

Good luck and have fun!

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

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

As a tester, I tested because valeriu told me to.

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

    I hope any problemsetter asked me too for testing. I wanna try testing a round so bad xd

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

      I don't know what you are trying to imply

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

        Nothing, just that I'd love to test some rounds but I have never been contacted for it so far

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

          Maybe you can add my discord, I won't turn anyone down, but you have to be good friends with me before I invite you to test, it can be very difficult, you have to spend a lot of time communicating with me and making me feel like you can Trust, so it is recommended that you do not aim to test the competition, but to make friends with me.

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

As a tester, I can assert that the problems are amazing and recommend everyone to participate in this contest!

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

    X: doubt. UPD: I really enjoyed the contest. Problems were great. My performance was worse than usual but still I really liked the contest. Big thanks to the problem setters!

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

Seeing green and cyan testers give me hope that the difficulty of A will be fit for its position.

Hope to see a balanced round friendly to greys.

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

As a tester, I think the problem is really great, and I recommend everyone to participate.

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

i love Mo2men <3

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

As a tester, I still don't know half the problems oops

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

I have a feeling that this round's quality will match the date ... 10/10 :)

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

As a...

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

naman1601 Sir round, can't wait to participate. Good Luck Everyone

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

Hoping to reach a bit closer to that green zone. Have a great contest everyone ^_^

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

Lets hope A is easy this time, so that more people participate.

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

As a tester, the problemset is really enjoyable!
Being a tester for the first time for a CF contest, I tried to contribute and provide suggestions to the best of my ability. I would recommend everyone to participate!

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

As a tester, your mom

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

As a tester, I want upvotes. Problems are great. You will surely enjoy the round.

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

As a tester, I wish to solve three problems in this round

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

Give me some upvote to get out of the negative contribution please ..

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

I hope no one will cheat in this round.

I am the biggest cheater in China OI,all people hate me.Do not do stupid things,like me!

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

What is meaning of subtask?

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

rp++!

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

Seems strange score distribution, C1+C2 = 3250 > E. Usually [C1,C2,D,E] is [E1,E2,C,D] in this case. I'm looking forward to see the tasks!

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

I am a little scared seeing the 1250+2000 distribution.

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

All the best @everyone. Hopefully the problems will be worth solving.

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

All people now looking at standings and waiting to do another things xd!

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

the joke about speedforces is already too hackneyed, but how can I not make a joke???

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

Where is the distinction? the participants can't show the difference。the problem C2 is too hard

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

all of these div2 testers, and none of them informed you that your round is too hard?

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

how to solve B?

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

C2 too hard to implement :(.

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

To C2's author:The problem is good,I like it,but your examples are nearly meaningless lol

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

How to solve problem C1?

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

Problem B really destroyed my brain ,I don't know how about 7000 solved this problem!
problem C just take 15 minutes to solve.

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

critical-observative-forces

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

how to solve C2?

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

    Let $$$b_x = x-a_x$$$, we also set $$$b_0=0$$$ and $$$b_{n+1}=n$$$ for convinience. Then if the sequence of prefix maximas is $$$b_{x_1}, b_{x_2},\ldots,b_{x_k}$$$. The answer is $$$(\sum\limits_{i=1}^{k-1} x_{i+1} \cdot (b_{x_{i+1}} - b_{x_i})) - \frac{n(n+1)}{2}$$$.

    You can probably modify this blog to AC (if it works, we don't require updates to be independent). But I just bashed some stupid case work similar to prefix maximums from ICPC Gwalior-Pune Regionals 2021.

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

    define end[i] = longest position j such that a[i..j] is good

    then do casework on updates (binary search is needed)

    you can try on paper how array end changes between updates

    also note that update that increases a[i] should be considered differently from update that decreases it

    i finished the code just now, not sure if my idea is correct

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

    I made a vector called start, where start[i] indicates the lowest index that you can start a good subarray from and be able to include a[i] in the subarray. Then $$$start[i] = \max (start[i - 1], i - a_i + 1)$$$. This might look familiar if you solved C1 (though you may not have used a separate array for it).

    Before making any changes, the desired answer would be $$$\frac{n(n + 1)}{2} - \sum (start[i] - 1) = \frac{n(n + 1)}{2} + n - \sum start[i]$$$.

    Note that $$$start[i]$$$ is basically the largest value of $$$j - a_j + 1$$$ for $$$j \leq i$$$. We can prepare another vector, second, where $$$second[i]$$$ is the second largest value of $$$j - a_j + 1$$$ for $$$j \leq i$$$. Note that $$$second[i]$$$ can be equal to $$$start[i]$$$ if there are two (or more) indices with the same maximum $$$j - a_j + 1$$$ value.

    We can prepare prefix sum arrays for both $$$start$$$ and $$$second$$$. You can probably figure out the rest from there, but if not, here are some details:

    • if changing $$$a_p$$$ to $$$x$$$ does not change $$$start[p]$$$, then the answer doesn't change, and you can just print $$$\frac{n(n + 1)}{2} + n - \sum start[i]$$$.

    • if changing $$$a_p$$$ to $$$x$$$ would cause $$$start[p]$$$ to increase to $$$newstartp$$$, then use binary search to find the next index $$$j$$$ in which $$$start[j] \geq newstartp$$$. So we use $$$newstartp$$$ for the range $$$[p, j)$$$ and use the original $$$start$$$ values for all other elements, which we can efficiently calculate totals using the prefix sums.

    • if changing $$$a_p$$$ to $$$x$$$ would cause $$$start[p]$$$ to decrease to $$$newstartp$$$, then use binary search to find the next index $$$j$$$ in which $$$second[j] \geq newstartp$$$ (this might be $$$p$$$ itself) and another binary search to find the next index $$$k$$$ in which $$$second[k] \geq start[p]$$$ (original $$$start[p]$$$). Then we use $$$newstartp$$$ for the range $$$[p, j)$$$ and the $$$second$$$ values for $$$[j, k)$$$ and the original $$$start$$$ values for all other elements, again, all calculated efficiently using prefix sums.

    My Submission: 175446833

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

      Wow! Very nicely explained. Also, we might get caught for plagiarism since I used start[i] for my array as well haha. Although I couldn't think about maintaining the second largest value as well for handling updates :(

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

      Can you explain this part please in 2nd point: when start[p] gets increased due to ap, we find j such that start[j] >= newstartp.

      Are we finding a j such that j > p and whose start is beyond newstartp? How did we arrive to this conclusion that we need to find such j only?

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

        Yes. Note that $$$start[i]$$$ is the largest value of $$$\ell - a_\ell + 1$$$ for $$$\ell \leq i$$$.

        Suppose we set $$$a_p$$$ to $$$x$$$ and then recalculate all of the $$$start$$$ values. The $$$start$$$ values before index $$$p$$$ would be the same as before (no changes before index $$$p$$$). Let $$$j$$$ be the first index where the old $$$start[j]$$$ is $$$\geq newstartp$$$. Then the new $$$start$$$ values in the range $$$[p, j)$$$ would now be equal to $$$newstartp$$$, since $$$newstartp$$$ is now the new maximum value of $$$\ell - a_\ell + 1$$$ for this range.

        But for index $$$j$$$ onwards, where $$$start[j] \geq newstartp$$$, we can continue using the old $$$start$$$ values, since they remain as the maximum in their ranges, despite the update to $$$newstartp$$$.

        Of course, we don't actually recalculate and update all these $$$start$$$ values; we simply use prefix sums to calculate what the result would become if we were to have made such changes. The actual stored arrays are unchanged once we start reading queries.

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

      Thanks for good explanation, really beatiful solution, but there is one thing: could you explain, what is the idea of using array second in case of decreased start[p]? Why does it work?

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

        Note that $$$start[p]$$$ is the largest value of $$$\ell - a_\ell + 1$$$ for $$$\ell \leq p$$$.

        But if $$$start[p]$$$ decreases to $$$newstartp$$$, then $$$newstartp$$$ might not be the largest such value.

        Let $$$[p, k)$$$ be the range of indices such that the old $$$start$$$ values in this range all used the old $$$start[p]$$$. Then for these indices, the new $$$start$$$ value should be the new largest value (of $$$\ell - a_\ell + 1$$$), which would either be $$$newstartp$$$ or whatever used to be the second largest value, whichever is larger. We can denote $$$j$$$ as the index where the bigger of the two changes from $$$newstartp$$$ to the previously second largest.

        By maintaining an array of the second largest values, we can easily find indices $$$j$$$ and $$$k$$$ through binary search, and maintaining a prefix sum array for these second largest allows us to easily compute the sum of the "new $$$start$$$ values" for the range $$$[j, k)$$$, where the new $$$start$$$ value should be the previously second largest values.

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

      What's the intuition behind choosing second[j] for searching?

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

For problem E, is there any optimal case where we need to consider the fact that after swapping an element, one of them is set to 0?

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

Can someone give the approach for C1?

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

    Let's f(i) is the left-most index you can take when i is the right-most one, then f(i) >= f(i + 1).

    Then, yeah, as we know, two pointers.

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

problem B in recent div 2 contests is being difficult for B div 2 problem

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

vote unrate

+1

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

I always wondered if MTBB (mean time between bricks) had a minimum bound... love getting closer to it, truly.

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

any idea what's the hack in B?

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

    A lot of the hacked solves look similar and weirdly bad (to my brick-covered eyes, at least)... or they're good but messed up the indexing/bounds in some way that I'm not noticing with quick glances.

    Hypothetically: weak pretests as anti-cheat would be an interesting and terrible choice...?

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

      i went through a few hacked solutions and found people used gcd of first 2 > gcd of last 2 for all triplets which is an understandable mistake so i wouldnt conclude cheating immediately (altho im surprised it passed pretests)

      about the anti cheat method, definitely sounds interesting but would need some good thinking to not make it brutal (as a sufferer of wayyy more fsts than id like)

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

Cheaters yet again, way too many C solves last second

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

Can we solve C2 without segtree?

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

    Yes, I did it that way. Waiting to submit my solution though. BTW how to use segment tree for this? I did not find any way to update.

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

    Yes, by using prefix sums. My submission: 175446833

    I explained my approach in another comment above, because the code might be difficult to read otherwise.

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

huge difficulty gap after C1

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

Sadly, C2, D, E still too hard for me :((

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

    Actually I think everyone had really good chances at solving Problem D, because if you have found the idea, the solution is pretty simple.

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

      I was very close :(

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

      Eye opener. Was never gonna upsolve, but after seeing your post one more question done. Thanks!

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

      Really cool idea!!! There should be one more condition to check after getting rotpos vector in your code that the size is even or odd to make sure the first and last elements are not same in the rotpos vector. i.e., if retpos size is odd then that means the first and last elements are same right? Is this condition required or this case won't happen? Could you please clarify on this. Lemme know if I'm missing something, Thankyou.

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

        The amount will always be even. Assume it is odd. Then we have an odd number of 1's and 0's and no solution is possible, which we check beforehand.

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

Gave up after solving A,B,C1 and 30 minutes left. Suddenly with 10 minutes left, realized how to solve C2. Now waiting to submit it. Why do solutions strike at the last minute?

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

    Biggest mistake -> did not see that the changes were temporary in C2

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

      But your solution should still work (if there are no other errors)? Either you correct your solution, or you put in a dummy query after each one to reset the previous change.

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

        Actually, I wasn't able to solve without temporary. After seeing temporary, some of the problems with a permanent change went away.

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

How to solve B normally?

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

    b2 should be divisible by a1 and a2, so it is divisible by lcm(a1,a2). gcd(b1,b2)=a1, hence b1=a1. Proceeding similarly, you can have bi divisible by lcm(ai-1,ai), and bn+1 = an. For any bi not in [1,n+1], we have multiples of some number as possible inputs. You can convince yourself that taking the smallest one(that is the lcm itself) is most likely to produce a solution(taking a multiple, you only decrease the chances of gcd being whats specified). With this, you have a possible sequence bi. Just check its sanity and answer "YES" and "NO" accordingly. I hope this answers it.

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

      I also guessed whether lcm is optimal, but I have a feeling that bigger choice spares more space for latter numbers. So that I didn't convince myself and get lost, try to find any pattern in $$$A_n$$$ is bad like "4,2,4" XD

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

    I solved it by checking whether gcd(prev, after) divides curr or not.

    If they do not for at least one number in A, then ans is No. Otherwise, yes.

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

      Very nice observation, how did you came up with that approach?

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

        Consider the problem for each prime number (usually useful in gcd/lcm problems)

        Let $$$f_p(a)$$$ be the highest power of the prime $$$p$$$ that divides $$$a$$$. In the other words, if $$$a$$$ is divisible by $$$p^m$$$ and $$$a$$$ is not divisible by $$$p^{m+1}$$$, then $$$f_p(a)$$$ $$$=$$$ $$$m$$$.

        Take any three consecutive numbers in $$$A$$$: $$$prev, curr, after$$$.

        • $$$f_p(prev)$$$ $$$\leq$$$ $$$f_p(curr)$$$ $$$\leq$$$ $$$f_p(after)$$$ => okay (Example: $$$A =$$$ {$$$2, 4, 8$$$}, $$$B =$$$ {$$$2, 4, 8, 16$$$}, $$$p = 2$$$ ).
        • $$$f_p(prev)$$$ $$$\leq$$$ $$$f_p(curr)$$$ $$$\geq$$$ $$$f_p(after)$$$ => okay (Example: $$$A =$$$ {$$$2, 8, 4$$$}, $$$B =$$$ {$$$2, 8, 8, 4$$$}, $$$p = 2$$$ ).
        • $$$f_p(prev)$$$ $$$\geq$$$ $$$f_p(curr)$$$ $$$\leq$$$ $$$f_p(after)$$$ => NOT okay It is easy to see why when you try to construct $$$B$$$.

        For the first two cases: $$$gcd(prev, after)$$$ divides $$$curr$$$, but this does not hold in the last case.

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

          also the missing fourth possibility i.e when fp(prev)>=fp(curr)>=fp(after)=> okay (8,4,2)

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

С2 and D are too hard for normal C2 and D. And I think it`s not normal that C2 is harder than D

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

    I don't think D is too hard, tbh. Once you realize that it's redundant for the cyclic shifts to leave any bits unchanged, i.e., there is always an optimal answer where the cyclic shift will flip all bits of the subsequence or there is no answer, then I think the solution becomes really obvious after that.

    I agree that it's easier than C2, but there isn't much that could be done about that, since it wouldn't make sense to have it before C1 (since it's still harder than C1) nor should C1 and C2 be separated. I suppose it may have helped to give C2 a slightly higher score than D, to encourage participants to check D before trying C2.

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

Huge gap after C1, but otherwise nice contest.

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

Solution for C1 without two pointers or segment tree https://codeforces.me/contest/1736/submission/175446774

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

Could AnyBody Explain What's the logic begin taking LCM of two adjacent no and storing in another array and checking the GCD of two adjacent elements form diffrent array in Problem B and What's the logic being Problem C Because I am not figure out properly where is my test case failing and why

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

    Since $$$a_2 = gcd(b_2, b_3)$$$, both $$$b_2$$$ and $$$b_3$$$ has to be divisible by $$$a_2$$$
    Similarly both $$$b_3$$$ and $$$b_4$$$ has to be divisible by $$$a_3$$$
    So the common element which has to be divisible by both $$$a_2$$$ and $$$a_3$$$ is $$$b_3$$$
    That's why $$$b_3 = lcm(a_2, a_3)$$$
    Now that you have $$$b_3$$$ just check if $$$gcd(b_2, b_3)$$$ is equal to $$$a_2$$$ or not. If it is not then answer is "no". Otherwise continue till $$$n$$$

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

Check out my precise solutions for A,B and C1: A: 175371876 B: 175384691 C1: 175422140

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

    What Your Logic for Problem B and C1

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

      Take an example a = {4,2,4}. Let the array b={b1,b2,b3,b4}. since gcd(b1,b2)=4, b2 is a multiple of 4 and since gcd(b3,b4)=4, b3 is a multiple of 4. Therefore the greatest common divisor of b2 and b3 will be a multiple of gcd(4,4)=4 (i.e. a[i] must be a multiple of gcd(a[i-1],a[i+1])). We cannot construct the array when it is not a multiple.

      (sorry for any language mistakes :))

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

looks like the discord/telegram master copy fails on test case 11.

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

I feel second example for E was way too informative

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

    I would've probably got 2 wrong submissions if not for it, and rightly so.

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

good contest!!!

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

When the ratings will be updated?

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

I loved problem E. Nice one!

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

    Any hints, please? ^-^

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

      Let's consider that $$$x_1$$$, $$$x_2$$$, $$$...$$$ $$$x_n$$$ are the scores that are added to your final score at each moment. Try to prove that for each $$$i$$$, $$$x_i \ne 0$$$, and also try to find some relationship between $$$x_i$$$-s.

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

the problem was clear and intersting thank you for the contest <3

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

Don't want to be too offensive, but check out wildfire032's submissions) (he is rank 13 right now in the standings) He has two different code styles for the problems A, B, and C1 compared to C2 and E. Moreover, he must have a legendary grandmaster mindset to switch problems from A, B to E and then back to C1 and C2)0)

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

    You are so offensive, but I like it.

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

    Well, they certainly didn't copy problem E, given that they got first solve on that problem. (3 minutes before 2nd solve and 23 minutes before 3rd solve!) Though it does seem a bit ridiculously fast, since unlike wildfire032, the 2nd and 3rd solves did not solve A and B first and they are very high ranked.

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

      Someone might have leaked the problem with solution before the start of the contest.

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

        I don't think so. This problem is too easy to be solved in 7 mins. It may be that somebody told him that the E problem is easy and he came to solve it.

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

          Then, I guess, there were two people submitting from this account, one started form A and the other from E.

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

    You are so offensive, but I like it.

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

For D, can someone find what's wrong here 175460824? I first create vectors v0 and v1 which store indices j where s[j]='0' and s[j]='1' respectively. My subsequence p is basically all the indices present at even positions in vectors v0 and v1 in sorted order and subsequence q is the remaining indices in sorted order. Subsequence b is all the indices j where s[p[j]]!=s[q[j]]. It fails in test 190.

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

I think D was not too hard. It will be of rating 1600 approx.

It can be solved by simple observation, that are:-

1) If the no. of ones are odd then answer is -1.

2) Simply divide the array in two subsequences, as per your choice. I personally have divided the array in two subsequences on the basis of parity (i.e. odd and even index)

3) Now, see if the ith index of subsequence (i.e. 2*i and 2*i+1 index of original array) are same then we can just ignore that. else you can store these pairs of index in some temporary vector.

4) You will notice that the size of that temporary array is even (because statement (1) is false).

5) Now for every "two" pair of the vector choose one '0'th index form pair 1 and '1'th index from pair 2.

6) You can notice that after the operation of right shift, all the bits will flip as the size of the array will even always. Ex- 01 01 01 -> 10 10 10.

7) In short, every two pair in temporary vector will satisfy there requirements.

8) example- Lets say pair1(1,0) and pair2(1,0) you take 0'th from pair1 and 1'th from pair2. and apply the operation then the pairs will become pair1(1,1) and pair2(0,0) and that's what we need. "NOTE- Store index in the pairs." I have used 0 or 1 for better understanding.

8) And we get our desired answer.

You can take some reference from my code :) My submission id- https://codeforces.me/contest/1736/submission/175419375

Thanks for reading it, hope this would help.

Happy coding :)

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

    Why downvoting this?

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

    Simply divide the array in two subsequences, as per your choice

    I don't think you can just choose any subsequence pair. Even and odd index works correctly, and is also what I used, because both bits in the same position of the two subsequences appear before all bits in later positions. So for each mismatching position, you can alternate between turning the 0 into a 1 and turning the 1 into a 0. Applying the cyclic shift on a subsequence where the bits alternate (consecutive bits don't match) is equivalent to flipping them all. My submission: 175422432 (note: pz means picking the 0 to add to the cyclic shift)

    But if you tried to construct the subsequences differently, e.g., first half and second half, then it doesn't work. For example, consider 00001111. If you tried to match first half with second half, then there must be at least one half with 2+ indices being chosen for flipping, but then the shifting subsequence would have consecutive elements of the same bit, so the cyclic shift would NOT be equivalent to bit flipping.

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

    How were you able to think of this construction?

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

Where is editorial

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

I think for problem c1, the answer of third test case should be 2. Can anyone explain why is it 7?

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

    Read Problem again , for every new subarray of any size indexing will be according to new one not according to Initial Array .like one of subaarray [1,4,3] of size three is valid as per question.Hope you understand.

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

thank you!!!! very good and balanced contest!!! ily

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

175519849.Based on this submission result, i can find out whether for gcd(b[i],b[i + 1]) < a[i] I must be able to construct bi that satisfies this condition? How do you prove it?

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

My CM dream come true thanks satyam343 , mtw and naman1601

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

shuanq