Блог пользователя magnus.hegdahl

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

Thanks for participating in the round! We hope you enjoyed it.

In addition to the usual text-editorial below, namanbansal013 will explain Div. 2 solutions on his stream, and ak2006 has made video explanations for Div. 2 B, C, D, and E.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Codeforces Round 767 (Div. 1)
Разбор задач Codeforces Round 767 (Div. 2)
  • Проголосовать: нравится
  • +202
  • Проголосовать: не нравится

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

So fast editorial!

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

Thanks for the fast editorial ;)

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

for D

a bxx ba => abxxba , which is a palindrome and it requires concatenating 3 strings

isn't this a counter example for the proof

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

    Why should it be a counterexample? Taking pairs still works, as you can use only the first and last element and get the palindrome aba.

    Also, note that a by itself is already a palindrome ;)

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

    a ba is enough

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

    For problem D

    s1 = "abcd"

    s2 = "edc"

    s3 = "ba"

    It requires concatenation of all 3 strings to be a palindrome => "abcdedcba".

    Isn't it a counter example? if not plz explain.

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

In D1 you didn't need to have a constraint on sum of $$$n$$$, because $$$dp_k[n][m] = dp_1[n][m] \cdot k$$$ and everything can be precalculated in $$$O(maxn^2)$$$

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

    True, but we wanted the easy version to be strictly easier than the hard version.

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

    I didn't read the constraint on n in the harder version (facepalm) and had the solution formula written on paper for a solid 20 minutes in contest thinking that an O(n) per testcase solution TLEs...

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

      So did I!!

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

      I didn't notice it at first too. Just after I relalized that "I probably can't precalculate everything and it seems hard to make it faster than linear" I have re-read it.

      By the way

      This is the hard version of the problem. The difference is the constraints on $$$n$$$, $$$m$$$ and $$$t$$$. You can make hacks only if all versions of the problem are solved.

      is technically incorrect, the difference is the constraints on $$$n$$$, $$$m$$$ and $$$t$$$ and sum of $$$n$$$

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

Could anybody prove why I was able to cheese D:143658044? I simply handled trivial cases separately and then ran a nested loop with early exits and it somehow passed

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

    Uphacked. To be fair, it's hard to prepare a test case that breaks your solution without seeing your solution beforehand, so I can't really fault problemsetters for missing this test case.

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

      Hey, I have a similar issue in problem C, I think my solution should give TLE to a test case where the array a is n consecutive numbers between 0 and n-1.

      Here's my code.

      Since I'm using a set, I don't know how to traverse only the values greater than the previous MEX, so I'm traversing the entire set at each iteration.

      Thank you in advance :)

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

        Yes you're right, the solution gets hacked with an array from $$$0$$$ to $$$n - 1$$$. Instead of resetting the mex to 0 each time you have to update the mex, note that the mex always monotonically increases, so you can just start incrementing mex further. This bounds the work done by $$$\mathcal O(n)$$$.

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

          Thank you so much, I already fixed it. But, I wonder why this test case was not included in the testing phase, my idea's pretty similar to the editorial one. Don't get me wrong please, the contest was great, but my code fails to find the MEX of the subarray in an optimal way. This test case should have been used during hacking phase.

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

          How the time complexity of this is o(N)?

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

            The value of the MEX is monotonically non-decreasing, so each time a new element of the array is parsed, the MMEX is incremented or kept. Since there are n elements in the array, the while loop will do at most n iterations. Total time complexity O(N*logN).

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

      Good catch, but what about this one: 143751547? Now I remove duplicates and random shuffle for better luck, so I think it's way stronger.

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

        This one was much harder to hack but still possible. Basically I only have one pair in the input that forms a valid palindrome. Then it just comes down to how lucky you get with the random shuffle and if you reach the valid pair early enough. I had two unsuccessful hacking attempts at first simply because of the randomness, so this submission would definitely be difficult to hack in a real contest scenario.

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

I have implemented div 2 c in this link but it is giving me a memory limit exceeding error. Can any one pls suggest where I have implemented it wrong.

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

    Maybe because you are making too many vectors(which have values stored in them) inside a method which is running recursively. Without comments it hard for me to see what you are trying to do hence it is only a guess.

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

.

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

Another solution for problem D1C(D2E): Try to take the XOR of the red cells in the picture, then what happened?

picture

code: 143676971

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

My solution for D2C is slightly different

If MEX of the entire array is mex and mex is small then we should remove as many equal mexes as possible. This way we guarantee that next mex will be even smaller

On the other hand if mex is large, then we already remove a significant number of elements

This way removing part becomes cheap because the total number of iterations when we actually remove becomes small

The complexity seems to be O(n * sqrt(n))

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

Thank you for this nice Mihai round ! I hope to see more Mihai rounds in the future !!

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

For C we can prove that any initial arrangements of row 1, yields a valid unique solution that can be constructed greedily. This is done by choosing row 2 in such a way it makes row 1 valid, and its obvious to see there is just one solution for that.

Let us assume there exists some solution. If we swap some element in row 1, $$$(1,x)$$$ you can notice it will change elements $$$(2,x+1)$$$ and $$$(2, x - 1)$$$, which will similarly change $$$(3, x - 2)$$$, $$$(3, x)$$$, $$$(3, x+2)$$$. By $$$\frac{n}{2}$$$ rows it will just swap $$$(\frac{n}{2}, 2x)$$$ or $$$(\frac{n}{2}, 2x + 1)$$$ for all $$$x$$$. This will make no difference in the last row, as it symmetrically loops after that. All other rows are taken care of in propogation.

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

    Hi, can someone please explain this proof of the editorial construction in a bit more detail? I am unable to understand even from the above proof. Thanks in advance.

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

    Could you explain that why "by n/2 rows it will just swap (n/2, 2x) or (n/2, 2x+1) for all x"? I have thought it carefully but I still can't understand that, thanks. :)

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

    Nice solution! jschnei and I had a bit of trouble following your write-up, but eventually we figured it out, so hopefully this comment helps anyone else in the same boat.

    The idea is that you can basically fill a $$$45^{\circ}$$$ rectangle with a checkerboard pattern and it perfectly touches all 4 sides of the $$$n \times n$$$ grid.

    Example:

    · · X · · · · ·
    · X · X · · · ·
    X · X · X · · ·
    · X · X · X · ·
    · · X · X · X ·
    · · · X · X · X
    · · · · X · X ·
    · · · · · X · ·
    

    Notice that every cell is adjacent to an even number of Xs, and we can change how we construct this rectangle to place exactly 1 X in the top row wherever we want. Then we can xor this pattern with any valid solution to get a valid solution with 1 cell of the top row toggled.

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

      Thank you a lot! :P

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

      Thanks for sharing. I understood the pattern in figure but how does it prove the original construction in editorial. By toggling a cell (1, x) in row 1, do you mean that we take that cell by querying the below cell (2, x) which in turn triggers this pattern?

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

        The greedy approach is that if (x, y) is calculated even times, you should choose (x+1, y).

        Assume there is a soltion, call it S. By toggling (1, x), the greedy approach will generate the pattern above. If more than one cells in row 1 is toggled, the result is the xor of their patterns. Now for any initial arrangements of row 1, they all can be treated as S toggled some cells in row 1. So the approach will works.

        Also to mention that the proof is based on the fact that there is at least one legal solution, you can prove it by the solution 2 in the editorial.

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

      Thanks a lot AnandOza for clarifying the statement. So this means that if we have an original grid $$$orig$$$ satisfying the given XOR-sum grid, and we XORed the value of a cell with position $$$(1, c)$$$ with $$$x$$$ (for each bit set in $$$x$$$, toggle it in $$$(1, c)$$$), we need to XOR cells marked by $$$X$$$ in the other rows with $$$x$$$ for the XOR-sum grid to be the same.

      So this proves that a first row with arbitrary values always belong to a grid $$$g$$$ satisfying the given XOR-sum grid, as row $$$1$$$ in $$$orig$$$ can be converted to row $$$1$$$ in $$$g$$$ using the previously mentioned operation on each cell.

      However, unlike the Editorial says, I do not think this proves the greedy strategy mentioned there. The strategy mentioned in Everule's solution retrieves one of the grids satisfying the given XOR-sum grid and calculates its total XOR-sum.

      However, the Editorial's greedy strategy operates on the XOR-sum grid directly. It guarantees that after processing row $$$r$$$, all the cells of row $$$r-1$$$ in the original grid will be used odd number of times. But what guarantees that after processing row $$$n$$$ the cells of this row itself will be used odd number of times as well?

      To answer the previous question, I tried to write the pattern of used cells in the XOR-sum grid for multiple values of $$$n$$$, and found that they always satisfy some recurring strategy which I tried to explain here.

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

I have another solution to C :

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

    Thanks for your solution. I was thinking in a very similar direction during the contest but couldn't complete my solution, maybe since, I had never solved such a problem using a checkered board or bipartiteness in a grid.

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

There's a typo in the editorial of Problem D2. $$$DP[i][i] = i$$$ should be replaced by $$$DP[i][i] = k \cdot i$$$

Cc: SlavicG magnus.hegdahl

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

I've found an alternative solution to Div2 C — Meximum Array that is quite elegant, if I may say so myself.

Let's keep track of current MEX value, which is initially zero, and look at each array element from left to right. We can store already seen array elements in a hash table, std::set or an array of size $$$2 * 10^5$$$ and update MEX value in $$$O(n)$$$ time. Notice that MEX can only change it's value when it's equal to current array element — and also that it can only grow. If we could somehow predict the future and know that we won't ever encounter an element equal to MEX, then we could conclude that current value of MEX is global maximum for entire array, add it to answer and reset MEX-tracking machinery (set current MEX value to zero and forget all seen elements). But we can do exactly that, we can predict the future in $$$O(1)$$$ time if we spend $$$O(n)$$$ time in preparation — for that we need to store count of not-yet seen elements for each element value in a hash map or an array and later update (decrement) it when going over each element from left to right.

Final complexity depends on what data structure we use for storing seen and unseen elements. I've got TLE with std::vector of size $$$2*10^5$$$ and using std::fill to reset it because of large hidden constant, but a solution with std::unordered_map was accepted.

Here is my code: https://codeforces.com/contest/1629/submission/143691434

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

    Hi,I have a question here. How to find out prefix mex for an array in O(n) or O(nlogn) ? I mean, for each i from 1 to n,I want to find out mex from 1 to i ,

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится
      mex = 0
      For every i form 1 to n
      	appeared[a[i]] = true
      	while(appeared[mex])
      		mex++
      	print mex
      

      Amortized cost is linear.

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

    This was my idea but I don't know what's wrong in this.

    Traverse from back and find the max element that you've encountered till i, store this in the "Back" array;

    Now traverse from front and keep inserting v[i] onto the set s. Let mFound be the max(mFound, back[i]) Now if s.size() == mFound + 1, that means we have all the elements less than mFound add mFound + 1 into the ans array, and reset set s. Also setting last_index to i.

    For the end, ex, 0 2, the ans should be 1, so we traverse from the last_index+1 to n and find the minimumn no not available.

    143663484

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

Peculiar Movie Preferences Video Solution.

Don't forget to like and subscribe!!

https://www.youtube.com/watch?v=xBkDyMHVTJ0

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

If anyone's wondering, here's the genfunc sol for D2...

So, for Div. 1 D1, we can determine that the solution is

$$$D[n][m] = \begin{cases} 0&,m=0,\\ k \cdot n&, m=n,\\ \frac{D[n-1][m]+D[n-1][m-1]}{2}&,\text{ otherwise}. \end{cases}$$$

Let $$$A_n(x) = \sum\limits_{i=0}^{n} D[n][i] x^i$$$, then the recurrence above rewrites as

$$$A_n(x) = \frac{1+x}{2}A_{n-1}(x) + \frac{k(n+1)x^n}{2} = \sum\limits_{i=0}^{n-1} \left(\frac{1+x}{2}\right)^{i}\frac{k(n+1-i)x^{n-i}}{2} = \frac{k}{2^{n+1}}\sum\limits_{i=1}^n (1+x)^{n-i}(i+1)(2x)^{i}.$$$

This rewrites explicitly as

$$$\frac{k}{2^{n+1}} \sum\limits_{i=1}^n \sum\limits_{j=0}^{n-i} (i+1)2^i\binom{n-i}{j} x^{i+j} = \frac{k}{2^{n+1}}\sum\limits_{a=1}^n x^a \sum\limits_{i=1}^{a} (i+1)2^i \binom{n-i}{a-i},$$$

Thus the final answer is

$$$D[n][m] = [x^m]A_n(x) = k\sum\limits_{i=1}^m \frac{i+1}{2^{n-i}}\binom{n-i}{m-i}.$$$

Unfortunately, it took me quite a while to derive everything and I could only solve it after the contest has ended :(

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

    I think, one can also find a closed formula for $$$A_n(x)$$$ as a rational polynomial function, so it should be possible to calculate $$$D[n][m]$$$ for a fixed $$$n$$$ and all possible $$$m$$$ in something like $$$O(n \log n)$$$.

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

      Finding the rational function actually gives you a way to compute it for all possible values in $$$O(n)$$$.

      I'll assume $$$k = 1$$$, since you can just multiply by $$$k$$$ at the end. Let $$$a(x) = \frac{1 + x}{2}$$$. Now the equation,

      $$$A_n(x) = a(x) A_{n - 1}(x) + \frac{n + 1}{2} x^n \implies A_n(x) = \sum_{r = 1}^{n} \frac{r + 1}{2} x^r a(x)^{n - r}.$$$

      On differentiating,

      $$$ \sum_{r = 1}^{n} x^{r + 1} = x^2 \cdot \frac{1-x^n}{1-x} \implies \sum_{r = 1}^{n} (r + 1) x^{r} = 2x \cdot \frac{1 - x^n}{1 - x} - x^2 \cdot \frac{n x^{n - 1}}{1 - x} + x^2 \cdot \frac{1 - x^n}{(1 - x)^2}. $$$

      I'll call the above expression $f(x)$ for now.

      Now, rewriting

      $$$A_n(x) = \frac{a(x)^n}{2} \sum_{r = 1}^{n} (r + 1) \left(\frac{x}{a(x)}\right)^r = \frac{a(x)^n}{2} f\left(\frac{x}{a(x)}\right).$$$

      Plugging this in and simplifying, you end up with

      $$$A_n(x) = x \cdot \frac{2 a(x)^n - (n + 2) x^n}{1 - x} + 2 x^2 \cdot \frac{a(x)^n - x^n}{(1 - x)^2}.$$$

      You can compute $a(x)^n$ in $$$O(n)$$$ using Binomial theorem, dividing by $$$1 - x$$$ is the same as computing partial sums of the numerator (equivalently, divide using long division) so you can compute the whole thing in $$$O(n)$$$. 143777320

      Edit: I played around it with a bit and you can get a cleaner expression,

      $$$A_n(x) = 2x \cdot \frac{a(x)^n - (n + 2) x^n + n x^{n + 1}}{(1 - x)^2}.$$$

      However, you can get rid of the two $x^n$, $$$x^{n + 1}$$$ terms from the numerator as they only make sure that $$$[x^m] A_n(x) = 0$$$ for $$$m > n$$$. Ultimately, you end up with the very slick,

      $$$D[n][m] = [x^{m - 1}] \frac{2a(x)^n}{(1 - x)^2}$$$

      for $0 < m \le n$. 143779641

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

Regarding the editorial of Problem D2:

I think the reason why the $$$x$$$ value that maximises the expression $$$min(DP[i−1][j−1]+x,DP[i−1][j]−x)$$$ is always valid (namely, $$$0 \le x \le k$$$ is satisfied) should be mentioned in the analysis of the solution.

Cc: SlavicG magnus.hegdahl

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

    If anyone is interested, I will put a proof here. But it's not a short proof, so I might have overcomplicated it. If anyone has a simpler proof, feel free to share it. Maybe there is some obvious observation that I'm not seeing.

    First I need to prove the following lemma.

    Lemma

    Then the proof of what you asked for:

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

      Your proof can be made pretty short, just get rid of the lemma. You need to prove that $$$DP[i][i] - DP[i][i - 1] \le 2k$$$. You know that $$$DP[i][i] = ik$$$, so equivalently you have to prove that $$$(i - 2)k \le DP[i][i - 1]$$$.

      This is true because Alice has a strategy to force a score of $$$(i - 2) k$$$. Always pick $$$k$$$, Bob needs to do $$$i - 1$$$ additions and $$$1$$$ subtraction, giving a score of $$$(i - 1) k - k = (i - 2) k$$$.

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

      (actually its the same as all the written above)

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

pronblem B was hell for me because i am not really good at math problems otherwise everything was perfect thanks for this round

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

Did someone else not notice D2 having the "sum of N is bounded" restriction and sat on the solution for half of the contest? :|

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

I didn't solve E during contest, but I solved it after contest! Here's the solution:

Observation 1: We know that our final answer will just be the bitwise XOR of some elements of our grid. This is kind of hard to prove (I think), but it's intuitive enough.

Observation 2: We're choosing some subset of elements in our matrix and bitwise XORing all of those elements which we chose.

Observation 3: We can imagine this as a binary matrix, where 1 means that we chose that element and 0 means that we do not chose that element. We want to construct the matrix in such a way that each element has an odd number of neighbors which are 1. That way, we include everything in our bitwise XOR.

Observation 4: If we fix some row of our boolean matrix, the rest of the matrix is fixed.

Observation 5: If we fix the first row to contain only ones, we're done.

So the idea is to fill the first row with ones and then fill out the rest, which is fixed.

143706309

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

For Problem Div2 D, tags are showing twice.

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

Where does my solution for C go wrong? I didn't do anything with suffixes so that may have been an issue but I fail to see how $$$\text{MEX}(l,N)$$$ and $$$\text{MEX}(r,N)$$$ could be used to calculate $$$\text{MEX}(l,r)$$$ (following the notation of the editorial).

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

    If we calculate MEX of all suffixes then we can get MEX(i,n) for any i, which is what editorial is asking to do.

    Think in this way — Reverse the array and then calculate MEX till each index. This is same as MEX of a suffix in original array.

    Edit — Take this example : -

    a,b,c,d,e

    If we want to know MEX of c to e, we can easily do it if we have calculated MEX of e to c, since both are same.

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

      Please forgive me if i'm wrong, but we need not only MEX(i,N) but also MEX(i,j) because in editorial (at paragraph 3) we calculate MEX(p,j) where p and i are some numbers from 1 to n. But in editorial there is nothing about it (and in your answer too) only about to calculate MEX(i,N). I have the same question — how we can calculate MEX(i,j) or why we have not to do it. Thanks in advance.

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

        This is the comment I was looking for. The way I did it was based on sets. I took a set and initially kept from 0 to n. From 0 to i-1, I delete array values from set if that exists in set, thus mex till i-1 can be obtained from set.begin(). Now at i-1, I insert 0 to mex-1 in set and repeat the set delete process till j. Now set begin will give mex(i,j).

        Complexity won't change as those set insertions take extra mex number of operations for a segment i to j and array length covered in that segment is greater than equal to mex(i,j). So if you divide the array in some segments and each segment i has a size of ki then you are doing at max sum(2*ki) operations and as sum(ki)=array size, total number of operations are less than equal to 2*n. (For each segment with size ki, we need ki deletion and maximum ki insertion in the set)

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

          Thanks, that was a great answer. I have understood all only just now. Your solution is very beatiful.

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

    The complexity of your solution O(n * n * logn)

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

I am getting WA25 on My solution of D, Would some give me an example so I could understand, Thanks for helping in Advance

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

In Div 1A for test case -

1 3 1 1 1

Why is answer 0 0 0 wrong? According to the definition in problem statement 0 0 0 is larger than 0. We can obtain 0 0 0 by choosing k=1 3 times.

Upd: Nvm. Realized its correct answer. I did changed break to continue in my code before submitting..

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

In Div2 D, I don't think it's enough to pair at most 2 strings. Consider the following example z yxa xyz

I don't see how we can select 2 strings to form palindrome, but selecting all surely works. What am I missing ?? Help me!

z is a plindorome. I am stupid.Please ignore.

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

I'm confused about the test data of problem E (div. 2). What I understood from the problem statement is "each cell contains the xor sum of all its adjacent cells". Suppose we have a grid of $$$2\times2$$$ like this:

$$$ x = \begin{bmatrix} x_{1} & x_{2} \\ x_{3} & x_{4} \\ \end{bmatrix} $$$

The xor sum of neighboring cells for each cell will be:

$$$ y = \begin{bmatrix} x_{2}\oplus x_{3} & x_{1}\oplus x_{4} \\ x_{1}\oplus x_{4} & x_{2}\oplus x_{3} \\ \end{bmatrix} $$$

So the conditions $$$y_{1,1} = y_{2, 2}$$$ and $$$y_{1,2} = y_{2,1}$$$ should be satisfied for a valid $$$2\times 2$$$ grid.

But why the test contains test data like this?

What is a possible original grid for this test data? Am I missing something?

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

    In order to make sure the tests are actually obtainable as neighbor sums, we made the problem a "fake interactive". The tests are made as Victor's original grid, and then the interactor finds the neighbor sum before giving it to your solution.

    When you look at the test cases on the submission page, you see Victor's original grid, not the neighbor sum.

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

is there a DP-solution for problem D — div2 ?

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

    No there is clearly no DP solution

    However I can explain you my thought process which might help you ?

    First you see that it's written in bold that strings are of length at most 3 so it must be really useful ! Usually this kind of stuff allows us to use pigeonhole principle or something like this.

    Notice that if you have any string of length 1 then the problem is solved (it's in the samples)

    Now, by trying very basic casework we see that it's obvious that if you have a string and it's reversed version, then you can answer yes.

    This let's us with a very few number of strings...Indeed, the number of strings of size 3 in a set that has NO symmetrical strings is $$$\frac{26^3}{2}$$$

    So we might use some sort of bruteforce (because we wouldn't have the special constraints over length of strings otherwise).

    Now you might finally try to show that you can always get a palindrome using one string of length 2 and one string of length 3.

    I hope it helped :p

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

For div 2E, you can visit each cell and include it in the xor if the neighbours haven't been marked. Initially all cells are unmarked. After including a cell mark all its neighbours, as they will be included in the xor.

Accepted solution

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

    Wow, this solution is surprisingly simple, can you explain why this would works? Thanks.

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

      It works because each cell contains xor of the neighbouring cells, and we need the xor of all elements, so we need to find a combination of cells that will include each element once or odd number of times. By trial and error I found out that there is always a combination possible which includes all cells once.

      We can't include cells that share neighbours as those neighbours will be included twice and xor of a number with itself is 0.

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

For problem E . It seems that many problem requiring finding a path to any node in the tree can be turned into find the path to the ending nodes of "diameter" of the tree (the diameter here can be the sum of length,max ...). And the ending nodes of diameter can be easily maintain by segment tree.

I first saw this trick here : https://codeforces.com/contest/1434/problem/D

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

Can anyone explain how come the number of odd numbers in the range [l,r] is given by (r-l+1)+(r/2+(l-1)/2)???

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

    r - l + 1 is the number of numbers in [l, r]

    r / 2 is the number of even numbers in [1, r]

    (l - 1) / 2 is the number of even numbers in [1, l - 1]

    so (r / 2) - ((l - 1) / 2) is the number of even numbers in [l, r]

    subtracts the number of even numbers from the total number of numbers -> you get number of odd numbers

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

fun contest, thoroughly enjoyed the problems :D

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

Can anyone tell me what's the error in my implementation of problem D 143737471

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

I think the 1628C — XOR-сетка method seems a little troublesome, I have a very concise writing here

Starting from the second row, you only need to select those cells that have been selected an even number of times in the previous row for XOR

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

My solution for Div1D:

Let $$$f(n, m)$$$ be $$$2^{n - 1}$$$ times the answer for $$$k=1$$$, so that this value is always an integer.

Note that we have the recurrence relation $$$f(n, m)=f(n - 1, m) + f(n - 1, m - 1),$$$ as well as the known values $$$f(n, n) = n\cdot 2^{n - 1}.$$$

Let $$$F(n, m)$$$ be the same function as $$$f$$$ but extended by the recurrence relation to values where $$$m > n$$$ (so $$$F(n - 1, n)=F(n, n) - F(n - 1, n - 1)$$$). We can compute $$$F(0, m) = m.$$$

We can easily use these values as a basis for computing $$$F(n, m)$$$ as a sum, as the value $$$F(0, m')$$$ will contribute to this $$$\binom n{m - m'}$$$ times.

Then $$$F(n, m)$$$ is just $$$\sum_{i=1}^m i\binom n{m - i},$$$ from which we can easily compute the desired answer.

Code: 143689440

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

Hey in the question 1628A - MEX-массив , can anyone explain the correctness of second test case as per the problem statement :

I think the second test case should be like this

2 2 3 4 0 1 2 0 -> [2 2 3 4 ] = 5

0 1 2 0 -> [0 1 2] = 3

0 -> [0] = 1

so vector b becomes [5,3,1] and this is lexicographically greater than the given b -> [5,3,1]

Kindly clarify this.

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

Explained 1628D1 — Game on Sum (Easy Version) DP Concept much clearly up here:

DP Concept Video Explaination

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

Can anyone check my solution for Div2 D? I can't find what's wrong here. https://codeforces.com/contest/1629/submission/143764101

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

How to solve Div2C/Div1A in o(n) ?

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

There is a slightly easier solution for the Div1 C task. I noticed that if we suppose the table is chessboard, every cell would contain information only about the other color. So, we can calculate XOR of all the white and black cells separately. If left up cell is white, to calculate answer on the black cells, we simply need to go from the left up diagonal to the right down. To count every cells one time, we can use the previous diagonal and add cells as on the picture. (x is diagonal we want to count, 2 is diagonal we already know, 1 is for cells we need to take). Counting the answer for other diagonals is pretty similar.

Scheme: https://imgur.com/a/ut95K9y

My solution: https://codeforces.com/contest/1629/submission/143699683

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

Great Contest

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

For 2C.. What is the output for

6
0 1 2 0 1 2

I think the answer should be 4?

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

This is a much easier solution for Div1C, we can calculate the white cell in the same way.

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

I have a question about div2C (which is much harder than div2D btw). Let m be an array of MEX suffices. That is, m[i] is MEX of all elements from a[0] to a[i]. From this, how to calculate MEX of all elements from a[l] to a[r] for any l and r?

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

    I think you meant prefixes. I don't think we can calculate mex of a range using this information alone efficiently. For example, let mex of a[0] to a[l] be x and mex of a[0] to a[r] be y, then it could mean that a[l] to a[r] could contain some or none of the numbers in the range 0 to y-1, and depending on what numbers are present in a[0] to a[l], the mex of a[l] to a[r] could vary.

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

About the problem D1 (Div 1), what if $$$\frac{DP[i-1][j] - DP[i-1][j-1]}{2} > k$$$, in that case the optimal $$$x$$$ would be $$$x = k$$$, but the fact that we're working under $$$\mathbb{Z}_{10^9 + 7}$$$ makes impossible to identify this case. I would appreciate some explanation about this. I'm probably missing something.

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

    It's always worse for Bob to be forced to add more. But how much worse? The difference between an add and a subtract cannot be more than $$$2k$$$, So the difference between $$$DP[i][j]$$$ and $$$DP[i][j-1]$$$ cannot be more than $$$2k$$$. One can also use induction to show that the optimal value of for Alice to pick is always in the range $$$[0, k]$$$.

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

How do we efficiently calculate the Mex for the Mex problem?

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

    Store a bool list of whether you have seen some number or not. Start with saying the mex is 0, and then while you have seen the mex, increment it. But you must be careful about resetting this structure, since it involves a big list, and clearing the entire list might be slow if you need to do it many times. Therefore, you can keep another list of which numbers where actually changed, and then you only need to reset those.

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

      I thought of something similar actually. I implemented it using a set, a counter variable, and a current MEX variable

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

Regarding the Editorial's solution for Div2E, I have wondered why does this strategy always work, I mean why do the $$$n^{th}$$$ row cells always get used odd number of times by the time the $$$(n-1)^{th}$$$ row cells get used odd number of times. After some thinking I reached the following proof:

Assume a matrix $$$mat$$$ such that $$$mat[i][j]$$$ is $$$1$$$ if we XOR the result with $$$xor\_sum[i][j]$$$ and $$$0$$$ otherwise. We want to prove that using a valid (every cell in the original grid is included odd number of times) matrix $$$mat$$$ of size $$$n\times (n-1)$$$ ($$$n$$$ is even) where the first and last rows are all ones, and the first and last column values from top to bottom are $$$1, 0, 1, 0, ..., 1, 0, 1$$$, we can always build another valid matrix $$$mat2$$$ of size $$$(n+8)\times (n+7)$$$.

Define boundary cells of a matrix of size $$$n\times m$$$ to be the cells with row $$$1$$$ or $$$n$$$ or column $$$1$$$ or $$$m$$$. Using matrix $$$mat$$$ of size $$$n\times (n-1)$$$, let's add new boundary cells in $$$4$$$ steps to reach our desired matrix $$$mat2$$$:

  1. The first boundary cells: All zeros, now the matrix size is $$$(n+2)\times (n+1)$$$.
  2. The second boundary cells: The first and last rows are all zeros, and the first and last column values from top to bottom are $$$0, 1, 0, 1, ..., 0, 1, 0$$$, now the matrix size is $$$(n+4)\times (n+3)$$$.
  3. The third boundary cells: All ones, now the matrix size is $$$(n+6)\times (n+5)$$$.
  4. The fourth boundary cells: The first and last rows are all ones, and the first and last column values from top to bottom are $$$1, 0, 1, 0, ..., 1, 0, 1$$$, now the matrix size is finally $$$(n+8)\times (n+7)$$$.

Observe how all the new rows/columns are added in a way such that their respective original grid cells are used odd number of times. The base cases are for $$$n = 2, 4, 6, 8$$$, using these we can build the matrix of any other even positive $$$n$$$.

To obtain the $$$n\times n$$$ matrix, simple append a first row of all zeros, its cells will be always valid (as the row below it is all ones) and will not affect the validity of other cells.

Example for obtaining $$$mat2$$$ of size $$$12\times 11$$$ from $$$mat$$$ of size $$$4\times 3$$$:

$$$mat$$$:

$$$mat2$$$ ($$$mat$$$ is highlighted in yellow):

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

The binary tree, LCA stuff in the editorial of E are essentially proving this cool fact:

Let $$$f_T(x, y)$$$ be the maximum weight along the simple path from $$$x$$$ to $$$y$$$ in an edge-weighted tree $$$T$$$. Then, given any edge-weighted tree $$$T$$$, there exists a tree $$$T'$$$ such that $$$\forall x, y : f_T(x, y) = f_{T'}(x, y)$$$, and every vertex of $$$T'$$$ has degree $$$\leq 2$$$ (i.e. $$$T'$$$ is a line).

And here is how to construct $$$T'$$$ in $$$O(n\log n)$$$:

code

To solve problem E, just do the tree replacement, and then it reduces to an easy problem on an array. :)

Another problem that can be solved using this trick is 609E - Минимальное остовное дерево по каждому ребру.

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

You have changed test case 1 of E in judging but the answer is still the same as the test case 1 given in the question, pls correct it so my answer gets accepted.

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

    It is not changed. The data shown on the submission page is Victor's original grid, not the data given to your solution. What your program reads will still be what you see as the sample in the statement.

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

In Div1 D1 how do we go from this statement

$$$DP[i][j]=min(DP[i−1][j−1]+x,DP[i−1][j]−x)$$$ for x that maximizes this value.

To this statement

$$$DP[i][j]=(DP[i−1][j−1]+DP[i−1][j])/2$$$

Shouldn't it be

$$$DP[i][j] = DP[i-1][j-1] + min(k, (DP[i-1][j] - DP[i-1][j-1])/2)$$$

because of the constraint on x?

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

    Yes, but the difference between Bob adding and subtracting will never be greater than $$$2k$$$, so the $$$DP$$$ state with one fewer forced add will also not be more than $$$2k$$$ less than the other state.

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

Why we are taking MEX of SUFFIX not that of PREFIX ? Please explain. Thanks.

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

    We precompute the mex of the suffix because we always want to take a big enough prefix that the mex is equal to the mex of the rest of the array. The rest of the array is some suffix.

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

I have the same idea on problem C, but I don't know how to find MEX on subsegment. Can you explain?

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

    What I have done is that, took the frequency of every element of an array , and then for calculating MEX 'simply check the lowest element in frequency array whose count is 0'. This will we your 1st MEX element of the res array. For finding rest MEX elements I iterate over every element. Meanwhile I also maintain a flag array and the pointer named 'ptr'. flag array only check whether the element below the MEX are present or not, while ptr check whether all the elements which are below MEX occurred or not (if occurred than resizing the flag array).

    Updating this, Now I'm able to passed the 2nd test case but on test case 6 WA occurred. If you are able to figure out than please help me.

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

can anyone tell me why my solution for problem D is not working https://codeforces.com/contest/1629/submission/143927718

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

    hey i dont exactly know what testcase ur failing on but i can give u a couple examples

    2

    plr

    lp

    (plrlp is obv a palindrome, and ur code doesnt check that.)

    another one being

    2

    sf

    sfo

    (you can't make a palindrome from these but your code returns yes.)

    as for fixing this, id take a look at how ur inserting into your map, as bc sometimes u insert the original string, and sometimes you insert the reverse. prob just normalize it into only inserting reverse or only inserting the original. additionally some cases where str1 is len 2 and str2 is len 3 u fail on. the situation where the len 2 string comes before works fine in ur code, like sf ofs, but when it comes after you dont check it. hope this helps :3

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

For Problem-E (Div.2),
Another logic would be to do ans = ans ^ grid[i][j] for all i and j within bounds (0 <= i, j < n) iff all neighbours of grid[i][j] are still unvisited (here grid refers to the grid which is given in input). In this way we guarantee that every element of Victor's actual grid is counted only once while taking xor.

This has been stress tested by harasees_singh for all even n from 2 to 1000.

Here is the link to my submission: 143698533

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

Can anyone help me with my submission of D of Div2.

problem-1628B - Особые предпочтения в фильмах My submission-143689113 Thank you

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

Here's another solution for Div1E, which uses the following observation:

Let $$$A$$$ be any subset of vertices, $$$a_i$$$ be the $$$i$$$-th element of $$$A$$$, $$$f(x,y)$$$ be the maximum edge weight on the unique path from $$$x$$$ to $$$y$$$, and $$$p$$$ be any permutation of $$$[|A|]$$$.

Then the following holds:

$$$\max\limits_{x \in A}\max\limits_{y \in A}f(x,y)=\max\limits_{i=1}^{|A|-1}f(a_{p_i},a_{p_{i+1}})$$$

That is, the maximum edge weight on any path from two elements of $$$A$$$ is the maximum of $$$f(a_i,a_{i+1})$$$ of any ordering of $$$a$$$.

Proof: It's sufficient to show that any edge which is on at least one path of a pair of vertices from $$$A$$$ will be on at least one of the paths $$$(a_i,a_{i+1})$$$. Let's take any such edge. Then the vertices of $$$A$$$ can be split into two subsets $$$A_1$$$ and $$$A_2$$$ based on which side of the edge they are on. It's easy to see that as long as neither of the two subsets is empty, any ordering of $$$a$$$ will contain two consecutive elements, such that one is from $$$A_1$$$ and the other is from $$$A_2$$$. $$$\square$$$

To solve the problem, first notice that if $$$B$$$ is the current set of vertices that are on, and $$$c$$$ is the query vertex, we are looking for $$$\max\limits_{x \in B \cup\{c\}}\max\limits_{y \in B \cup\{c\}}f(x,y)$$$.

Since any ordering works, let's simply take the ordering from the input. Then we can preprocess $$$f(i,i+1)$$$, make a segment tree keeping $$$f(x,y)$$$ of consecutive elements of $$$B$$$, and notice that any update requires the addition of at most two $$$f(x,y)$$$ calls that weren't already preprocessed. This gives an $$$\mathcal{O}(n \log n)$$$ solution. Code: 144633280.

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

Could anyone please explain why my O(n*logn*logn) for problem C is giving TLE?

My submission link: https://codeforces.com/contest/1629/submission/238484131