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

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

Hello, Codeforces!

Hope you enjoyed the round! Editorials for all problems are out now. I hope this editorial be informative and helpful.

1557A - Ezzat and Two Subsequences

Hint 1
Solution

1557B - Moamen and k-subarrays

Hint 1
Hint 2
Solution

1557C - Moamen and XOR

Hint 1
Hint 2
Hint 3
Solution

1557D - Ezzat and Grid

Hint 1
Hint 2
Solution

1557E - Assiut Chess

Hint 1
Hint 2
Solution
Разбор задач Codeforces Round 737 (Div. 2)
  • Проголосовать: нравится
  • -34
  • Проголосовать: не нравится

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

Auto comment: topic has been updated by AhmedEzzatG (previous revision, new revision, compare).

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

even though the round has many problems, but no one can disagree that the problems were great and beautiful.

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

So there is no explanation on how this wrong solution passed the system tests?

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

    ok. It's maybe wrong. but it's just hard to make an Interactor counter all such solutions I guess. We tried to kill all the wrong solutions of the testers. actually, there were only 2 testers who could solve the problem.

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

I think using math formula in C more beautiful and easier than editorial

My solution using some binomial theorem and flt 125416610

It faster than editorial solution

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

    can you explain what did you do?

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

      $$$\binom{n}{0}+\binom{n}{2}+ \cdots = 2^{n-1}$$$

      You can calculate this by using Binomial Theorem, which you subtract $$$(1+1)^n$$$ with $$$(1-1)^n$$$

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

        However, there's an exception. When $$$n=0$$$ , the left part is 1. That's because $$$(1-1)^n$$$ will become undefined.

        Don't ignore that during exam :)

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

    explain please, I solved it pure math too, you can look at my 125416186 to see what things I already understood so that you could skip them if you want to.

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

    Dude, your logic for when n is even was really funny. Good one!

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

    m[max_ele] = 0

    and 0 can be a valid element in your input array.

    so thats reducing your cnt1 by 1 in test 3. and hence a WA.

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

    If input array have duplicates your m[a[i]] will be over written and hence some data is lost this will produce an error suppose that array is 2 2 2 2 then always a[i]=2 and m[2] will be over written 3 times and eventually will store the last value and previous will be lost

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

Back to back segtree problems for the past 3 rounds.

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

Can you share the interactor as well? Would be interesting to know how does it decides where to move the king.

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

    We try a lot of strategies for each cell, some greedy (for example, we try to make the king stay in the mid cells, Or try to go Up\downs if possible), and others random. maybe I will share the code later.

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

Randomized approach for E:

  1. First, I put my queen at one of $$${(4,4),(4,5),(5,4),(5,5)}$$$(random choice)
  2. For each move, I calculate $$$S$$$, which is the set of square which have a possibility of king's square. The size of $$$S$$$ is going small with the progress of the game.
  3. Next, I make some random horizontal or vertical move. As a reminder, through this progress, $$$S$$$ is going small.
  4. The important thing is, when we know where's the king, we can checkmate in $$$8$$$ turns.
  5. For example, if we have only $$$5$$$ candidates of king's square, we can finish the game in additional $$$40$$$ turns. When $$$S$$$ becomes small enough, try all candidates.

It seems that this solution uses far less than $$$130$$$ queries, or can you kill my solution?

my code

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

    We can actually checkmate the king in 5 (4 if the queen stays out of the edges) moves by checkmating on the edge!

    https://imgur.com/a/mwBV1Zk

    I think that can get rid of the randomization part as if we place the queen at (4, 4), there are at most 31 squares the king can initially occupy. Thus, we have an upper bound of 4 * 31 = 124 queries.

    However, in practice, the solution generally uses <10 queries.

    Code: 125423506

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

Can someone elaborate what are the leaves of seg tree used in D? If rows would have up to 10^5 columns the seg tree would be trivial, but with 10^9 I wasn't able to come up with seg tree structure and editorial didn't help neither.

Even the "dpi,j = maximum number of rows (from row 1 to row i) that make a beautiful grid, and has 1 in column j at the last row." doesn't make much sense to me, as there can be up to 10^9 j indexes.

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

    yes they didn't wrote it explicit, but in the end they wrote you can use coordinate compression.

    that would reduce columns from $$$10^9$$$ to $$$2m$$$.

    Example

    and you only $$$\text{dp}[i-1]$$$ to compute $$$\text{dp}[i]$$$ . so you can use one single row of $$$2m$$$ size and use segment tree to maintain it. all m updates in $$$\log{n}$$$ time.

    i did got the idea in the end and also implemented but i am getting WA at test 4.

    if anyone can help be debug.

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

      I used the same approach and got AC. I think you made a mistake in the update function. While updating the segment tree we need to check whether a higher value is updated to lower value. 125463800

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

        thanks, yes i did that check with ppgt() function which will propagate any changes that were made along the path we need for query/update, i missed a part in ppgt() to reset current root's lazy value to null after upddting its children. silly mistake, took me hours to find out.

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

Solution for first three questions. https://www.youtube.com/watch?v=vBqSLVoXYsI

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

Love this round. Hoping to have more lovely rounds like this in the future. (◍•ᴗ•◍)❤

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

My heart starts bitting faster every time I see 5 problems in a contest. I was at the top of my abilities to solve C today

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

SegmentTree for D is such an overkill.

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

    Can you please brief your approach without segment tree for D.

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

    Do you mean you can do it without segment tree?

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

      We can get every set of rows $$$i$$$ that for each column $$$j$$$, $$$grid_{i,j}=1$$$. Then construct a DAG by connecting the edges of each row in the sets from the first to the last, and find the longest path on the graph. The comlexity is $$$O(n+m)$$$.

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

        How did you do it without a log factor?

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

          Yes you are right. It's difficult to get rid of a log factor on the work before DP. I mean you can find the longest path on the DAG in $$$O(n+m)$$$.

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

            how does this work tho? doesnt longest path in dag have complexity O(V + E), how do you make sure there aren't too many edges cause then i would assume it becomes O(N^2). I looked at your code and it looks like there are only N edges but I don't get how something like that would work unless you are compressing the dag?

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

        Can you explain how to generate the graph in O(n+m)?

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

Hello , I didn't get the logic behind 2nd problem .

https://ide.geeksforgeeks.org/8684Y9kbwQ

  • this is my idea . But got wrong output on pretest 2. Can anybody help me in this ?
»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Why do I get WA on pretest 2? https://codeforces.me/contest/1557/submission/125391145 Brief explanation: If $$$n$$$ is odd, the answer is just $$$(2^{n-1}+1)^k$$$. Otherwise, if $$$A_n(j)$$$ is the number of ways for the bits from 0 to $$$j$$$ such that $$$And\geq Xor$$$, I get the recursion $$$A_n(j+1)=2^{nj}+2^{n-1}A_n(j)$$$, which solves to $$$A_n(k)=2^{nk-k}+2^{kn-n+1}-2^{nk-n-k+2}$$$. Where is the flaw?

EDIT: found it, wrong recursion, it should be

$$$A_n(j+1)=2^{nj}+\left(2^{n-1}-1\right)A_n(j)$$$
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

AhmedEzzatG Do you mind looking into why this solution fails on D? I used the approach described in the editorial during the contest, but really have no clue why the 4th pretest is failing. It's giving me headache. Thanks.

125401562

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

    Hi, sorry for delay. you have a small bug in segment tree code in line 68. return tree[v] = max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));

    it must be return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));

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

      Thank you so much, I appreciate it. A dumb mistake that yet again cost me -200 delta.

      Regardless, I liked D very much (the only problem I attempted, so I can't say for others) and I had a great time solving it, although it gave me some trouble. Thanks for the round!

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

really quick pure combinatorics sol for C:

We'll look at each bit independently. The bit for the LHS will be 1 iff all the bits are 1 and 0 otherwise. For the RHS, the bit will be 1 iff the number of bits that are ones is odd, and 0 otherwise. In order to handle both at the same time, you need to split into cases based on the parity of $$$n$$$.

Suppose $$$n$$$ is odd. Then, you can never have the case that the LHS is strictly greater than the RHS, because if the AND is equal to 1, then the number of bits that are 1 is odd, meaning the XOR is 1. Thus, you must have equality.

If both the LHS and RHS is 1, then it must be all ones so that is 1 way. Then if both sides are equal to 0, we must have exactly an even number of ones, or

$$$\binom{n}{0}+\binom{n}{2}+\cdots + \binom{n}{n-1}$$$

which is equal to $$$2^{n-1}$$$. Thus, in the odd case, the answer is $$$\left(2^{n-1}+1\right)^k$$$.

Now suppose $$$n$$$ is even. This time, it is possible to have the strict inequality by taking all ones. You then must consider two cases: when we have equality for both sides and when we have the strict inequality.

We tackle the first case. Both bits can not both be equal to one, as that would require all the bits to be one, for an even total, and an odd number of ones, contradiction. Thus we need both to be 0, meaning not all bits are equal to 1, and we must have exactly an even number of ones. This corresponds to

$$$\binom{n}{0}+\binom{n}{2}+\cdots+\binom{n}{n-2}$$$

Again, this can be seen to be equal to $$$2^{n-1}-1$$$ through whatever method you want. Thus, there's a total of $$$\left(2^{n-1}-1\right)^k$$$ arrays in this case.

Now suppose we have a strict inequaltiy. What we'll do is fix the bit where we have a 1 on the LHS and 0 on the RHS, and iterate over the positions for that bit: suppose the $$$i$$$'th bit will satisfy this. For the $$$i-1$$$ bits before it, we must have equality, which gives $$$\left(2^{n-1}-1\right)^{i-1}$$$ from the analysis of the previous case. Then, we have exactly 1 way to get the $$$i$$$'th bit, which is to take all ones. Then, the remaining $$$k-i$$$ bits don't matter, so there are $$$\left(2^n\right)^{k-i}$$$ choices here.

Putting both cases together and summing over all $$$i$$$, we have

$$$\left(2^{n-1}-1\right)^k+\sum_{i=1}^k \left(2^{n-1}-1\right)^{i-1}\cdot \left(2^n\right)^{k-i}$$$

different arrays in the case that $$$n$$$ is even. Compute this now however you want.

If you wanted a closed form for this, you can see that the summation is actually equal to

$$$\frac{\left(2^n\right)^k-\left(2^{n-1}-1\right)^k}{2^{n-1}+1}$$$

where you use the factorization

$$$a^k-b^k=(a-b)\cdot\left(a^{k-1} b^0 + a^{k-2}b^1 + \cdots + a^0b^{k-1}\right)$$$

EDIT: sorry for the typoes oops as you can tell i am terrible at proofreading

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

    hey, I implied your method: can you tell me, why I'm getting the wrong answer my submission: 125428860

    could you please amend it as well?

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

      if n is even,it should be

      $$$\left(2^{n-1}-1\right)^k+\sum_{i=1}^k \left(2^{n-1}-1\right)^{i-1}\cdot {(2^n)}^{k-i}$$$
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится -114 Проголосовать: не нравится

        Yes, of course... thanx This dickhead has wasted my 3 hours posted the wrong solution. And I was thinking something is wrong with my modular template.

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

    In the 4th paragraph, "we must have exactly an even number of zeroes" => "we must have exactly an even number of ones"

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

    Nice comment, however be careful with the case: $$$2^{n - 1} + 1 \equiv 0 \mod M$$$.

    In this problem it won't occur, but it could happen if $$$M = 998244353$$$, for example:

    $$$ 2^{249561088} + 1 \equiv 0 \mod 998244353 $$$

    and the answer is $$$2^{n k} + k \cdot 2^{n(k - 1)}$$$ for this special case.

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

      How did you conclude that for M = 1e9 + 7, ((2^(n-1) + 1) mod M) won't ever be 0. And why is the answer 2^{n k} + k * 2^{n(k — 1)} for this case?

      Also, I'd be glad if anyone could recommend learning resources (preferably text) for the same.

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

        compute all $$$2^n, n = 0, \cdots M - 1$$$ or some primary number theory.

        You may need to learn markdown, mathjax or tex.

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

        Use contradiction.Assume that there exists an $$$n$$$ such that

        $$$ 2^n+1\equiv 0\bmod 10^9+7 $$$

        Assume that $$$n$$$ is the smallest root of that equation.

        Assume that $$$m$$$ is the smallest root of the equation

        $$$ 2^m-1\equiv 0\bmod 10^9+7 $$$

        It's easy to see that $$$m|10^9+6$$$ and $$$m\mid 2n$$$ but $$$m\nmid n$$$.

        So we can know that $$$2|m$$$ and $$$\frac{m}{2}\mid n$$$ and $$$\frac{2n}{m}$$$ is an odd number.

        It's easy to see that

        $$$ 2^\frac{m}{2}\equiv \pm 1\bmod 10^9+7 $$$

        However

        $$$ 2^n=(2^\frac{m}{2})^\frac{2n}{m} $$$

        So we can know that $$$2^\frac{m}{2}\equiv -1\bmod 10^9+7$$$.

        According to $$$m|10^9+6$$$ we can know that $$$\frac{10^9+6}{m}$$$ is an odd number.

        So we can know that

        $$$ 2^{5\times 10^8+3}\equiv -1\bmod 10^9+7 $$$

        In other words

        $$$ (\frac{2}{10^9+7})=-1 $$$

        However

        $$$ (\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}=1 $$$

        Contradiction.

        Sorry for my bad English :(

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

    hey, can u tell me that in your even n case, in sub-case of inequality, while setting i bit as most significant, for k-i bits answer should be (2^n)^(k-i) because we do not have to set any specific bit in all n numbers as same (in those k-i bits)..

    and in your case of 2^(k-i), we imply that ith bit is same in all n numbers(in those k-i bits), which is not necessary..

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

    Could you explain how exactly did you arrive at the closed form equation?

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

      It's is a geometric series so one can get it by applying the formula for summing a geometric series and then simplifying; however I actually got it by working through all the steps:

      $$$f=\sum_{i=1}^{k}\left(2^{n-1}-1\right)^{i-1}\left(2^{n}\right)^{k-1}$$$

      Divide by the ratio of consecutive terms (one would normally multiply, but dividing seems simpler here):

      $$$\frac{2^{n}}{2^{n-1}-1}f=\sum_{i=0}^{k-1}\left(2^{n-1}-1\right)^{i-1}\left(2^{n}\right)^{k-1}$$$

      Take the difference between the sum from 1 to k and the sum from 0 to k-1:

      $$$\left(\frac{2^{n}}{2^{n-1}-1}-1\right)f=\frac{\left(2^{n}\right)^{k}}{2^{n-1}-1}-\left(2^{n-1}-1\right)^{k-1}$$$

      Simplify:

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

could some one tell me why this is wrong https://codeforces.me/contest/1557/submission/125421372

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

    You could have a contiguous subarray but you might have a value that splits that contiguous array into parts E.g- 1 2 3 7 4 and k=2 your solution would give yes but the answer is no because 1.2.3.7 is contiguous but 4 needs to be put in between 3,7 so it needs 3 subarrays

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

I think it's meaningless to set the space of problem D so tight…… It's hard for $$$O(m\log10^9)$$$ to get pass, since it's easily getting MLE.

But also great problems, thanks for the contest!

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

    Discretization please! Codeforces Round NEVER set space limits tightly!

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

      But a time complicity of $$$\mathcal{O}(n + m\log{}10^9)$$$ was given by the problem writer as a accepted one.

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

        I think #define int long long is the culprit here. Maybe try removing that line and see it fits inside the memory limit or not.

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

I have a different solution for E.

In the beginning the possible positions for KING is the whole chessboard. And if the king do a move , some positions will become impossible. So you can do $$$30$$$ random walk , to make the possible positions become very few(may be greater than one).

And for each possible position , you try to checkmate it .

You can do it for a known position in at most 8 steps :

  1. move the queen to that row .
  2. move the king.
  3. if the position is in your left , move left and move to the row where the king is ,vice versa.

And remember to maintain the possible positions after every move .

It seems that it use only about total $$$40$$$ moves for a test case.

code

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

    we cannot rely on random walks what if the king is oscillating back and fro in two squares and doing random walks yr queen doesn't give check I know that probability of this is less but is not 0 so this approach can fail once in a million

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

      In fact if you try to checkmate a position , you can also find some positions impossible .

      So I think it is impossible to be hacked .

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

        if the king only oscillates in two squares then the possible positions will be 64-16=48 and if u are unlucky enough u can exhaust 130 moves

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

I find the interactor for E a little "dumb": in all testcases, I made no more than 20 moves to kill the king lol (if the output of the testcase is the number of moves)

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

Thanks a lot for a detailed editorial.

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

problem E was super cute and I recommend everyone to just take a look at it :)

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

Well, D is a good problem. I solved many problems that can directly construct schemes through dp arrays before. But problem D ISN'T such problem, so I got Wrong answer on pretest 4. This is a good reminder to me that the record transfer is used to construct the scheme, rather than backward pushing according to the dp array.

But I'm still disappointed that I didn't passed D in the round. I am so close to the correct solution!

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

thank you for the nice editorial

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

What would be the rating of Div2C question?

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

AhmedEzzatG Thank you, Sir, The problems were really Good, We can learn a lot from them.

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

i did this in D problem: if the first and second row have something in common(which I am precomputing) then we can just move on to next row and set previous column as current index and if they don't have anything common, then we have to find the minimum of the two cases: removing the first row and removing the second row. So I call for two functions, with previous values as current index for one and the previous index for the other.

Recursive Code:


int fn(int prev, int cind, set<pair<int, int>> adj[]) { if(cind >= n)return 0; if(dp[cind] != -1)return dp[cind]; if(isMerging(cind,prev)) return dp[cind] = fn(cind, cind + 1, adj); return dp[cind] = min(fn(cind, cind + 1, adj),fn(prev, cind + 1, adj)) + 1; }

But I am doing isMerging step in O(n), can we do it in less than that? Also, I was not able to print the rows deleted.

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

on what concept problem c is based upon.?

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

hello everyone In Problem B is showing runtime error in testcase 2 but the code seems to be fine have a look guys. https://codeforces.me/contest/1557/submission/125441413 kindly help if you can. Thanks

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

Problem C Video Editorial

I solved it in contest and I show my thought process so it might help some of you

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

Can someone explain my WA? All my tests is AC, but here WA on pretest 2. https://codeforces.me/contest/1557/submission/125395144

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

How my approach is wrong for the submission of 1557B — Moamen and k-subarrays problem ? Please help 125447732

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

Hey, In problem A we proved that taking the maximum number in one subsequence is better than taking the two greatest numbers (instead of only one) in one subsequence.My question is how we can generalize this argument for the whole problem as there might be the other cases except for taking the two greatest number.AhmedEzzatG

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

    I proved it a bit differently:
    Suppose the array is split into 2 sub-sequences: $$$A$$$ with $$$k$$$ elements and sum $$$S_A$$$, and $$$B$$$ with $$$n-k$$$ elements and sum $$$S_B$$$, and further assume that $$$k \leq n-k$$$.

    Step 1. We can show that if $$$x \in A$$$ and $$$y \in B$$$, then $$$x \geq y$$$.
    Proof by contradiction. Assume that $$$y > x$$$, then we can swap $$$x$$$ and $$$y$$$ to get a larger result:

    $$$\frac{S_A - x + y}{k} + \frac{S_B - y + x}{n-k} = \frac{S_A}{k} + \frac{S_B}{n-k} + (y-x)(\frac{1}{k} - \frac{1}{n-k}) > \frac{S_A}{k} + \frac{S_B}{n-k}.$$$

    Step 2. If $$$A$$$ has more than 1 element, we can move the smallest element of $$$A$$$ to $$$B$$$ and increase the result. Let $$$x$$$ be the smallest element of $$$A$$$. By the previous step, $$$x$$$ is larger than any element of $$$B$$$, so after moving $$$x$$$ from $$$A$$$ to $$$B$$$ both the average of $$$A$$$ and average of $$$B$$$ will increase.

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

      I had the same problem with the editorial proof, but I easily understood yours. Truly elegant. Thanks

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

      One interesting observation — if both subsequences have the same length ($$$k = n - k$$$) then the result does not depend on how we do the split and is equal to twice the total average.

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

      Thanks for the help.You are amazing!!

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

      The proof is not so trivial to be arrived at during the contest for div2 problem A. So, I think, most of the participants just made a guess and hoped for the best.

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

        On the other hand, it's still problem A of div2, so if you get a hunch and go over some examples to "convince" yourself that it's the right observation, it's probably OK to trust your intuition and submit fast, and only try to prove it formally later.

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

      A correction — the statement in the first step is true only if $$$k$$$ is strictly less than $$$n - k$$$ (otherwise $$$\frac 1 k - \frac 1 {n-k} = 0$$$).

      If $$$k = n - k$$$ the result is the same no matter how we split, and if $$$x \geq y$$$ for any $$$x \in A$$$, $$$y \in B$$$ it is as good as any other split.

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

Problem C,forgot to add enough mod,and failed twice.100 points T T

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

In problem D,why adding $$$ dp[i][j] = max_{k\in C_i} {dp[i - 1][k]} $$$ step as call modify(1,1,N - 1,mx) is useless and wrong? In my opinion,tutorial's definition points out that $$$ grid[i][j] = 1 $$$ so the transfrom $$$ dp[i][j] = max_{k\in C_i} {dp[i - 1][k]} $$$ is not exist.And that's why add modify(1,1,N - 1,mx) will casue wrong?:/

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

In Problem E, this is a false promise:

If at any point you make an invalid query or try to make more than 130 queries for each test case, the game will terminate immediately and you will receive a Wrong Answer verdict.

after 30+ submissions of getting RTE and TLE I realized that my code making a move of the type : $$$(6, 1)$$$ -> $$$(6, 1)$$$. I should have got WA verdict but didn't.

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

    But I got a "Wa" verdict. 125371395

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

      It is a bit random. I got many TLEs. There is no reason I should get TLE.

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

    I also wasted a lot of my time trying to debug why my code was getting TLE, when it should be getting WA. Honestly, this E should have been tested more, I don't know how it got published with such a weak and inconsistent interactor

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

I can't understand "You can make i-th bit = 1 in an even number of indices, then Andi will be 0 and Xori will be 0 too." only one position is 1, then the xor could 1 why is 0?

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

For Problem C, I think the editorial is wrong because $$$dp[i][0]$$$ is just a product of $$$2^n$$$ which corresponds to all possible cases.

Let's define two vectors of size $$$k$$$ :

  • allcases[i] : number of ways to buid an array of size n from bit $$$0$$$ to bit $$$i$$$ (included)
  • dp[i] : number of ways to buid an array of size n from bit 0 to bit i s.t. (a[1]&...&a[n])[i...0]>=(a[1]&...&a[n])[i...0]
  • with (x)[i...0] = $$$2^i x[i] + ... + 2^0 x[0]$$$

Then for allcases:

  • allcases[0] = $$$2^n$$$
  • allcases[i] = $$$2^n$$$ allcases[i-1]

And for dp:

  • n is odd. two cases for bit i:
    • all 1 : AND=1, XOR=1
    • even number of 1 : AND = 0, XOR = 0. number of cases : C(n,0) + C(n,2) + ... + C(n,n-1)
    • dp[i] = (1 + number of cases) * dp[i-1]
  • n is even. two cases for bit i:
    • all 1 : AND=1, XOR=0 then for the bit 0...i-1 we can use all possible cases i.e. allcases[i-1]
    • even number of 1 (except n) : AND = 0, XOR = 0. number of cases : C(n,0) + C(n,2) + ... + C(n,n-2)
    • dp[i] = allcases[i-1] + (number of cases) * dp[i-1]
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I got WA on test 43 125484134 , test 43 seems random...., can somebody tell me why

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

I dont know what someone expected for when trying to copy code to on top of the leaderboard of virtual participation. Lmao

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

I hope that each example of the problems can be more valuable.

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

In the solution of D it said:

$$$dp_{i,j}$$$ — maximum number of rows (from row $$$1$$$ to row $$$i$$$) that make a beautiful grid, and has $$$1$$$ in column $$$j$$$ at the last row.

What does it mean here "last row"? Is it the row number $$$i$$$ or it is the last row of the biggest beautiful grid?

If it is the row number $$$i$$$ then the following doesn't make sense. It should be just 0.

Otherwise, $$$dp_{i,j} = max_{k\in C_i}{dp_{i-1, k}}$$$.

Otherwise $$$dp_{i, j}$$$ should somehow depend on $$$j$$$, but the right hand side doesn't contain $$$j$$$ in any way

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

    The tutorial of problem D truly has confused me a lot. Now I've figured it out:

    Is it the row number i or it is the last row of the biggest beautiful grid?

    The last row is not necessarily $$$i$$$ or $$$i-1$$$, it means the last row of the biggest beautiful and in that row at index $$$j$$$ it stores $$$1$$$.

    The Otherwise part is also not correct. It should be $$$dp_{i,j}=dp_{i-1,j}$$$

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

Why is this blog getting so many negative votes, Codeforces community doesn't appreciate the authors' effort!

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

    That's just because the terrible interactor of problem E.

    I don't know any other reasonable causes.

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

      I'm really sorry that this happened but we did everything we could to make all the wrong solutions fail. But it is difficult to find a general way for all solutions. But now I've worked on it and it's a bit better. We apologize once again for that.

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

    Because the tutorial is badly written... and some of the problems' pretest is tremendously STRONG.

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

In the tutorial of problem D, the following statement is not correct:

Otherwise, $$$dp_{i,j}=\max{..}$$$

Should be: If $$$grid_{i,j}\not=1$$$, $$$dp_{i,j}=dp_{i-1,j}$$$.

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

Is the solution for problem A wrong? I think we can not sum things up like that

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

    What do you mean?

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

      If we devide sequence to the biggest number and the others. He proved that moving second biggest num to the group of biggest number wont have better solution. But this does not mean its true for other cases, I know there is another solution, you can read comments above

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

        You can generalize the proof to any size of the sequence, not just 2. However, I think the proof in this comment is better than the editorial proof.

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

The first edi that has -100 downvotes :/

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

    This is not the worst, the worst is the announcement of a contest with several hundred downvotes :/

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

Can somebody please help me figure out, why my code, which quite literally implements the solution described in the editorial (except that I am scanning from left to right instead of top to bottom), not work? It gives runtime error because my queen somehow enters the 8th column, whereas it should be able to checkmate while it is in the 7th column. Any help in figuring out the error (either in the solution or the implementation) would be appreciated.

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

Why so much hate around this contest? It wasn't bad at all, C and D were interesting enough and the other tasks were good, maybe only E wasn't finally prepared but it's not the point to hate the whole thing :\ what a heck

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

AhmedEzzatG I don't understand the following part: If equal is false at any moment, then you can choose any subset of indices to contain 1 in the i-th bit.

You could select the odd number of indices to contain the i-th bit and then And would become less than Xor.

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

    If $$$equal$$$ $$$=$$$ false that mean $$$And$$$ > $$$Xor$$$ in the previous bits. Therefore, whatever the value of $$$And$$$ or $$$ Xor $$$ in i-bit, $$$And$$$ will remain greater than $$$Xor$$$.

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

I have a solution to problem E that only needs 16 moves in worst case, verified by DFS.

https://codeforces.me/contest/1557/submission/125862124

I believe it can be made better, but that means slower runtime and will be hard to verify.

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

A simple random solution for E: 126166286. Just do random moves and try to keep a list of valid starting positions for the king each time. When just one starting cell remained, simply trap the king.

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

Why this entry has so many downvotes?

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

About B,I use map<int,int> nxt,directly link the next value,but I failed Test3 in 58th case,I don't know why,anybody can find the mistakes in may code?It will help me a lot,thanks so much!

My code here...
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

void solve(){
	int n,k;
	cin >> n >> k;
	VI a(n),b(n);
	rep(i,0,n){
		cin >> a[i];
		b[i] = a[i]; 
	}
	sort(all(b));
	map<int,int> nxt;
	rep(i,0,n-1)nxt[b[i]] = b[i+1];
	int i = 0,piece = 0;
	while(i < n){
		while(i + 1 < n && a[i+1] == nxt[a[i]]){
			i++;
		}
		piece++;
		i++;
	}
	if(piece > k){
		cout<<"NO"<<endl;
	}else{
		cout<<"YES"<<endl;
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	caset{
		solve();
	}
  	return 0;
}



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

I used a different approach in C, then given in editorial. If n is odd, then for each i from 1 to k, either the ith bit should be on for all the n numbers or the number of on bits should be even so that the XOR does not become one. If n is even, we will follow similar approach but there are some extra cases. For each i from 1 to k, we will count the number of cases where number of on bits for each i should be even(but less than n). Then for each i from 1 to k, consider that the ith bit in all n numbers is on and there is no j from i+1 to k such that the jth bit is on in all n numbers. All the bits less than i can be on or off in all n numbers. All this counting can be done using simple combinatorics. You can look at my solution here https://codeforces.me/contest/1557/submission/144063292 Sorry for the text wall.

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

Hi guys, i can't understand what wrong with my solution for C. Please help me. My solution:here.I found my mistake.

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

Is there a way to solve D without coordinate compression ?