akcube's blog

By akcube, 7 months ago, In English

1957A - Stickogon

Idea: keyurchd_11
Problem Setting: shakr lezirtin
Editorial: shakr TheRaja

There were a few solutions which passes pre-tests with the assumption that $$$a_i \leq n$$$. We apologize for the pre-tests on A not including this case.

Hint 1
Solution
Rate this problem
C++ Code

1957B - A BIT of a Construction

Idea: akcube
Problem Setting: Prakul_Agrawal
Editorial: Prakul_Agrawal TheRaja

Hint 1
Solution
Rate this problem
C++ Code

1957C - How Does the Rook Move?

Idea: SilverTongue1729
Problem Setting: ppt1524 GenghizKhan
Editorial: ppt1524 TheRaja

There are 2 ways to approach the problem. The combinatorics approach is slightly more involved and might be more difficult to come up with.

Hint 1
Hint 2
Solution
Alternate Solution
Rate this problem
C++ Code

1957D - A BIT of an Inequality

Idea: fangahawk
Problem Setting: fangahawk shiven
Editorial: JadeReaper TheRaja

Hint 1
Hint 2
Solution
Rate this problem
C++ Code

1957E - Carousel of Combinations

Idea: SilverTongue1729
Problem Setting: JadeReaper
Editorial: SilverTongue1729 JadeReaper TheRaja

Hint 1
Hint 2
Hint 3
Solution
Rate this problem
C++ Code

1957F1 - Frequency Mismatch (Easy Version)

Idea: fangahawk
Problem Setting: fangahawk
Editorial: akcube

Hint 1
Hint 2
Solution
Rate this problem
C++ Code

1957F2 - Frequency Mismatch (Hard Version)

Idea: fangahawk
Problem Setting: fangahawk
Editorial: fangahawk TheRaja

Hint 1
Hint 2
Hint 3
Solution
Rate this problem
C++ Code
  • Vote: I like it
  • +84
  • Vote: I do not like it

»
7 months ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

257613633 Hey everyone im currently a beginner at cp , I'm asking if anyone can tell me why i got a runtime error in my submission for the first problem Thanks

»
7 months ago, # |
  Vote: I like it +76 Vote: I do not like it

My official reaction to the 3rd question

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I think the complexity of E1 must be $$$O((n+q)log^2n)$$$, since we have to insert and query $$$(n+q)logn$$$ times.

»
7 months ago, # |
  Vote: I like it +30 Vote: I do not like it

In the Solution of 1957F1 — Frequency Mismatch (Easy Version), the article Hashing and Probability of Collision is written by rng_58, not rng68.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody explain why (i-1) is multiplied in dp code of problem C ?

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    There are 2*n-2 possible places where the rook can be placed for reducing the size of the chessboard without worrying about overcounting.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How the count comes 2*n-2 I find there are 2*n place u can place rooks to reduce states by 2 can please explain

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Consider the i'th row/col pair. There are $$$ 2\cdot (i-1) $$$ squares on it. One of them is the diagonal square, $$$(i, i)$$$, and the rest $$$2\cdot(i-1)$$$ are normal. Diagonal square removes 1 row/col pair, the rest remove 2. Thus, $$$dp_i = dp_{i-1} + 2\cdot(i-1) \cdot dp_{i-2}$$$.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I was thinking about $$$dp$$$ in this way. Take the grid of free $$$n \times n$$$ squares. There are $$$n$$$ ways to choose a diagonal square and $$$n \times n - n$$$ ways to choose non-diagonal sqaure. If we choose a diagonal square, the number of free squares would decrease by $$$1$$$ and by $$$2$$$, if we choose a non-diagonal square. So, $$$dp[n] = (n \times n - n) \times dp[n-2] + n \times dp[n-1]$$$. I know it is over counting somewhere, but cannot figure out where.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    There are i rows and columns left.

    Now you take the i element and to pair it, you need a j. You can choose any of the other i-1 elements as j.

    The pairing matters as choosing a different j for the i makes the board look different.

    Also, you get the factor of 2 when you swap i and j.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The intuition here is that when you have i*i matrix left, you fixate on one of the columns (and the corresponding row) and calculate for remaining matrix.

    Let's say we are only selecting the column and row on the boundary of the matrix, we will have 2*(i-1) cells to select from and then we can continue using dp[i-2]. This guarantees the we don't overlap the formation we get from dp[i-2].

    For example, if i=4, we decide to select one of the cells marked with X. Obviously, we ignore the corner cell as it is counted in dp[i-1].

    |_|_|_|X|      
    |_|_|_|X|
    |_|_|_|X|
    |X|X|X|_|
    
»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1957/submission/257592898 Does someone see why I'm getting a runtime error in test case 2 of problem C ? I'm not getting any error while testing the same thing on my side and it also passed the pretests during the contest so I'm a bit confused. I shouldn't get outside the bounds of the array either I think.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If $$$n = 1$$$, you are accessing $$$dp[2]$$$ which isn't defined.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      omg I feel so dumb. I dropped more than 100 rating points because of that line XD. Thanks for the help.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In the solution of D shouldn't it be "where $$$f(x,y−1)$$$ has $$$i$$$ set" instead of "where $$$f(x,y−1)$$$ has $$$x$$$ set".

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fixed this mistake, thanks for pointing this out.

»
7 months ago, # |
  Vote: I like it +22 Vote: I do not like it

1957C is OEIS-A047974. Can be solved by dfs-brute force for small n, then search for formula.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Could someone send me some problems like D please.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Search by math in the problemset, then filter out those that have XOR in the name

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain the idea behind the D solution please? What do the params in pref[Z][MAX_N][2] represent? I'm assuming Z is bits, MAXN is array elements, what is the final dimension there for?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    pref[i][j][k] gives the number of possibilities for choosing a suffix from |a1..aj| such that the xor of the suffix for bit i is k.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks. I felt so weird reading the solution: I've realized everything that's written there during the contest but couldn't figure a way to count ranges efficiently (which is not explained in the solution itself).

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        me too, could someone detail their intuition behind their sol

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          Rev. 2   Vote: I like it +2 Vote: I do not like it

          We want to have $$$f(x,z)⊕y>f(x,z)$$$ where $$$x<=y<=z$$$. This will happen if $$$MSB$$$ of $$$y$$$ in $$$f(x,z)$$$ is unset, therefore on doing $$$f(x,z)⊕y$$$, it will become set and the value will increase. We are only considering the $$$MSB$$$ because sum of all the rest of the set bits is smaller than $$$MSB$$$ so unsetting $$$MSB$$$ and setting all other bits will still be reducing the value so the deciding factor is only $$$MSB$$$. For $$$f(x,z)$$$ to have unset bit at $$$MSB$$$, $$$f(x,y-1)$$$ and $$$f(y+1,z)$$$ should have different parity of set bits at $$$MSB$$$. Picking all pairs of $$$(x,z)$$$ satisfying the condition above can be fastened to $$$O(1)$$$ for every $$$1<=y<=N$$$ using prefix and suffix arrays. Overall TC will be $$$O(32*N)$$$. I myself was unable to implement the logic I mentioned in the contest. :(
          Code Link :- 257668182

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I'm sorry what I meant is I got all these observations in contest but could you specifically explain your code here.

            fors(i,1,n){
                    int msb=0;
                    fors(bit,0,31){
                        if((a[i-1]&(1<<bit))!=0){
                            msb=bit;
                        }
                    }
                    int ro,re,lo,le;
                    int val=right[msb][n]-right[msb][i];
                    if(right[msb][i]!=right[msb][i-1]){
                        re=val+1;
                        ro=n-i-val;
                    }
                    else{
                        ro=val;
                        re=n-i-val+1;
                    }
                    val=left[msb][0]-left[msb][i-1];
                    if(left[msb][i-1]!=left[msb][i]){
                        le=val+1;
                        lo=i-1-val;
                    }
                    else{
                        lo=val;
                        le=i-val;
                    }
                    ans+=lo*re+le*ro;
                }
            
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            could you explain this

            For f(x,z) to have unset bit at MSB , f(x,y−1) and f(y+1,z) should have different parity of set bits at MSB

            they must be odd odd or even even to make the MSB bit unset when xoring yes , with that it becomes same parity not different ?

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              in the editorial it says that it shouled be both set or both unset in ( f (x , y-1 ) and f ( y+1 , z)

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              $$$odd + even + 2*odd = odd$$$
              Here, $$$f(x,y-1)$$$ and $$$f(y+1,z)$$$ have different parity resembling the first 2 values of $$$LHS$$$ and as $$$y$$$ already has set bit at $$$MSB$$$, it gives the third part as it is counted twice in xor operation. Finally, we have odd value at $$$MSB$$$ so set bit at $$$MSB$$$.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Bro can u explain this conidition and why the value of even and odd has been swapped if(right[msb][i]!=right[msb][i-1]){ re=val+1; ro=n-i-val; } else{ ro=val; re=n-i-val+1; }

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Repsaj21o gave a great answer. For each element a_i, you need to find a combimation of prefix [l,i] and suffix [i+1,r] such that adding it decreases the xor. As outlined in the solution, this can be done by checking the most significant bit in a_i and comparing it to the ones in the prefix and suffix.

          So essentially, we can a formulate the problem like that: for each element a_i and its 'msb(a_i)', find all the combinations of prefixes and suffixes where this bit is set in prefix/unset in suffix or the other way around — unset in prefix/set in suffix, and multiple those.

          Do do that, we'll keep array pref[bt][index][value] (same with suffix), which represents the amount of suffixes of prefix [0..index], where bt bit is set to value. It's easy to recalculate it: suppose i-th element has bt bit 0. Then, pref[bt][i][0]=pref[bt][i-1][0] + 1 and pref[bt][i][1]=pref[bt][i-1][1]. If the bit is set to 1, then pref[bt][i][1]=pref[bt][i-1][0]+1 and pref[bt][i][0]=pref[bt][i-1][1]. Same idea with suffixes.

          Then we just iterate through the elements and multiply the amounts.

»
7 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

question on C

We place a rook (i,i), resulting in the deletion of only the last row and column leaving an (i−1)×(i−1) grid. The number of final configurations in this case are given by dp[i−1]. and so on

but there are i positions on i x i grid, why we shouldn't add i * dp[i — 1]? Yes I know this will lead overcount but don't get exactly why, similarly why we shouldn't add (i * i — i) * dp[i — 2]

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i have same question

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Let's say you are left with $$$x$$$ unused rows/columns. For any unused row, you have 2 options-
    1. Place white rook on $$$(r,r)$$$, which is a single pair, in which case you are left with $$$x-1$$$ unused rows/columns.
    2. Place white rook on any $$$(r,c)$$$ such that $$$r$$$ $$$!=c$$$, which has $$$x-1$$$ pairs possible, in which case you are left with $$$x-2$$$ unused rows/columns, and as colour of rook matters, this case itself got 2 options as $$$(r,c)$$$ and $$$(c,r)$$$ generate equivalent solutions. So, finally our formula for any state, we will get-
    $$$dp[i]=dp[i-1]+2*(i-1)*dp[i-2]$$$ where base case being $$$dp[0]=1$$$ and for $$$i<0$$$, $$$dp[i]=0$$$.
    How are you getting $$$dp[i]=i*dp[i-1]+(i^2-i)*dp[i-2]?$$$

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Place white rook on (r,r),... since there are i # of single pairs where r = 1,...,i from i x i grid that's where i * dp[n — 1] came from and similarly for i — 2 unused rows/columns case.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Why are you putting rook in $$$(r+i,r+i)$$$ when it's time for the $$$r^t$$$$$$^h$$$ row to get filled? We are not filling all the combinations at one go, we are going row by row and our $$$dp$$$ is taking care for the same. By your case, you are also giving preference to the order in which the rooks are getting placed which is overcalculation.
        Let's say if we want to place white rooks at $$$(1,1)$$$,$$$(2,2)$$$ and $$$(3,3)$$$, your code gives $$$3! = 6$$$ by giving preference to the order of filling of rooks while in reality this should give answer $$$1$$$ as only three squares with three filling positions are there.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why base case dp[0]=1 ? i couldn't undestand that

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        dp[i] represents no of configuration's you can get by making valid moves upon having i rows and columns.

        When building the recursion tree using all valid i rows and columns you will reach a state where you will not have any valid positions to place rooks i.e All rows/columns are restricted. That particular arrangement of rooks is only one valid configuration at that state.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can we solve B if we change the condition to a_i>0

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think the solution remains similar. Find such 2^x-2, so that you don't exceed sum of k if you fill 1s in the array(2^x-1+n <= k). e.g. n=4 and k=10, max x meeting the condition is 3, the answer code returns is 6, 1, 1, 2. However the solution is different for n=2. (I think it's 2^x-1 instead of 2^x-2)

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm afraid your solution is wrong.For n=8 and k=19,you will get [6,1,1,1,1,1,1,7],whose bitcount is 3.But we can construct [1,2,4,8,1,1,1,1] with bitcount = 4

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In this case $$$x=4$$$, so you put $$$2^x-2=14$$$, then fill the array with 1s. $$$14_{10}=1110_2$$$. I think I messed up the condition, it's $$$2^x-3+n\le k$$$ rather than $$$2^x-1+n\le k$$$. Apologies :)

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Seriously?[14,1,1,1,1,1,1,1] is invalid since its sum is 21 and > 19. Besides,the max $$$x$$$ that satisfes $$$2^x-3+n\leq k$$$ is $$$3$$$ rather $$$4$$$ for $$$n=8,k=19$$$.Maybe you misread my case.
          By the way,apparently the problem is unsolvable when $$$n>k$$$.And when $$$n=k$$$,you will get $$$x=1$$$ and put $$$2^1-2=0$$$,invalid too.Seems that there are quite a lot to consider.

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Best div ever , even if you disagree B⁠-⁠)

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I was criminally close to solving C. Just couldn't make correct dp. Good contest

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Idk if this is another alternate solution but for Problem C I got the following:

$$$ans += \Big[ 2^{\frac{x}{2}}\binom{n}{x}[(x-1)!!] \Big] \mod 10^9+7$$$

where x runs over all even numbers between 2 and n. At the end, we add ans=ans+1 to account for the case where all the rooks are on the diagonal.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is similar to the alternative solution in the editorial, you would obtain it by decomposing the $$$(m-c)!$$$ in odd and even terms, then use the even ones to simplify the $$$(\frac{m-c}{2})!$$$, leaving you with a power of two and the product of odd terms.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is a mistake in the solution of D: The last sentence of para.2 "where $$$f(x,y−1)$$$ has $$$x$$$ set while $$$f(y+1,z)$$$ is unset." The $$$x$$$ should be replaced with $$$i$$$.

Or maybe I'm understanding the whole sentence wrongly?:) Plz tell me

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yup you're right, just fixed this typo in the editorial.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For problem C, my combinatorics approach was a bit different.

Assume that $$$c$$$ type-1 moves were played. Then we're left with an $$$(m - c) \times (m - c)$$$ grid where only type-2 moves are allowed. Since the order of the moves doesn't matter assume that he plays from left to right and always selects the left most column available. For his first move on the first selected column he has $$$m - c - 1$$$ available squares (-1 because the main diagonal is not allowed), for his second move, there are 2 fewer squares left. 1 because the row he played move 1 is unavailable and 1 because the row where the computer mirrored the first move is unavailable.

In total, the player will make $$$\frac{c - d}{2}$$$ moves and there are $$$(m - c - 1) (m - c - 3) (m - c - 5) ... = (m - c - 1)!!$$$ choices.

Now, for every move, the computer plays the mirror image. From the $$$\frac{m - c}{2}$$$ white-black rook pairs, the player could have selected either the position of the white rook or the black rook so to account for that we multiply by $$$2^{\frac{m-c}{2}}$$$.

$$$\displaystyle posible\_states = 1 + \sum_{c=0} ^{c=m-1} \left[(m - c)\mod{2} = 0\right] \binom{m}{c} \cdot (m - c -1)!! \cdot 2^{\frac{m-c}{2}} $$$

The $$$+1$$$ is to account for the case where every rook is on the main diagonal.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

257439291 ez

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

257439291[submission:257439291]

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here: f(x,z)⊕ay>f(x,z) Doesn't this just mean that ay > 0 ?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    No.$$$f(x,z) \operatorname{xor} a_y$$$ is not always greater than $$$f(x,z)$$$. Example:$$$f(x,z)=6$$$ and $$$a_y=2$$$.so that $$$f(x,z) \operatorname{xor} a_y = 4 \leq f(x,z) = 6$$$

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yes yes I get that, but I mean mathematically, why's taking the xor for both parts of the inequality is wrong?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        I guess you mean that: if $$$a \geq b$$$, then $$$(a \operatorname{xor} c) \geq (b \operatorname{xor} c)$$$. It is obvious thar $$$(1 \operatorname{xor} 1) \lt (0 \operatorname{xor} 1)$$$ but $$$1 \geq 0$$$. Generally, the operator $$$\operatorname{xor}$$$ does not have associative laws as addition or subtraction. $$$(a+b) \operatorname{xor} c$$$ is not always equal to $$$a \operatorname{xor} c + b \operatorname{xor} c$$$. Hope to solve it. :D

»
7 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

can someone please explain the second part of dp transition in problem c?

Edit: Doubt cleared.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If we place a rook at $$$(i,j)$$$ and $$$i \neq j$$$,the computer will place a rook at $$$(j,i)$$$. The $$$i$$$-th row and the $$$j$$$-th row cannot be placed any rook now and the $$$i$$$-th column and the $$$j$$$-th column cannot be placed any rook as well. It just like the $$$i$$$-th row, the $$$j$$$-th row, the $$$i$$$-th column and the $$$j$$$-th column disappear from the board. So we will only consider the condition of $$$(n-2)\times (n-2)$$$ board (if the board is $$$(n \times n)$$$ now)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

interesting problem D

»
7 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Am I the only person to find D a lot easier than C ?

If I went to D before C maybe I would be a master now

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I found logic easily for D but couldn't implement the solution (T_T).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what would be the approach of B if the question would have asked to maximize 1 using XOR operator?

»
7 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Wow. Obviously I cannot solve E within the contest, but I managed to get the correct approach after 1 hour of thinking yesterday and 30 more minutes today. It's at least 3 twists. I didn't know Wilson's Theorem.

But I did it without the editorial!

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Ayy, that's great! Discovering all the twists when coming up with the problem was soo fun, it honestly the best part about this problem imo. Hope you enjoyed solving it!

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    Roadmap:

    • 10min after contest: worked out the formula of the answer, thought this is a high school math problem because $$$\sum_{i=m}^{n} C_i^m = C_{n+1}^{m+1}$$$ but later found the $$$\bmod j$$$ cannot be processed this way
    • 20min: realized the result is $$$0$$$ for composite j except $$$4$$$ and proved it
    • 35min: guessed Wilson's theorem with observations from $$$3$$$, $$$5$$$, $$$7$$$ and $$$11$$$, then Googled it out (Twist 1)
    • 50min: Confirmed that the answer for each j starts at $$$-1$$$ and -- once every j elements, cyclic-wise. (Twist 2) I was confident enough that I can code it and went to sleep.
    • Today 0min: learned Euler's sieve. I should have learned it earlier.
    • 10min: began coding but soon found sum of $$$n$$$ is unbounded and a bunch of TLE2 solutions! Start looking for offline method.
    • 30min: Realized I could generate duplicate elements with prefix sum, and the answer with another pass of prefix sum. (Twist 3) Time $$$O (n*\sum_{p is prime}^{p\le n}1/p)$$$.
    • 45min: AC first try.
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C的题解似乎出错了,没有考虑重点的情况

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hey guys! can u explain why I can ignore the exact positions of the rooks in the initial configurations and that only the number of free rows and columns matter.

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    initially we have rook on some squares. it will block entire row and col. after that we can't put rook on that row and col. now if we want put rook ,our new position will only depend on which row-col are currently available, not on the position of on initial rooks are placed on, so if we are ignoring them then why not resize board to (n-initial_row) size.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can try to draw 4*4 picture,thinking about how to take two position,and then remove the rows and columns of two position,drawing any possiblity,I think you will find the law.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I am a pupil, and after I thought about the C for three hours, I did it using the combinations, and I feel good because I'm improving

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

what does the most significant bit in k mean?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    MSB mean the last bit to the left who is 1 in binary representation

»
7 months ago, # |
  Vote: I like it +23 Vote: I do not like it

thank you for the problem E, for the first time I felt that I was not studying mathematics for nothing, when I realized that Wilson's theorem was applied there, sorry I didn't think of two difference arrays, but still thank you very much for the problem

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Has anyone solved F without hashing?

A similar problem with only one path can be solved with MO's but I don't think it's possible in this scenario.

I also thought of persistent data structure for k-smallest elements but didn't figure out the hashing part, I still don't quite understand it well. What happens in the case where on the same path there are multiple nodes with the same value, do they contribute to the hash all in the same amount? and doesn't that increase the collision?

I'm not very strong in hashing, until now I thought in hashing the order of the values always matters to lower collision or is this wrong?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Whether the order of the hashed values matter depends on the hashing function, the XOR hashing or sum hashing mentioned in the article linked in the editorial are actually independent of the order. For the sum hashing (which is the one used in the editorial's solution) in particular the hash will be different if a particular element repeats a different number of times in both multisets.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the difficulty rating of Problem A and B

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Damn, really great problems. Its a shame i didnt know modularni inverse at the time but lnow i do.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anyone please refer more problems like C & D

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B ; my idea in contest was loop from zero to k and count each number number of 1 in binary representation and stock in a vector of pair and after sort it , i don't know what is wrong in my idea my sub : https://codeforces.net/contest/1957/submission/257638050

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me know what's going wrong in my solution for F1 and F2? 258029636

So basically my idea is very similar to the one in the tutorial, but I build a persistent segment tree on the Euler tour of the tree saving the entry of the node as (R + ar[node]) and the exit as inverse(R + ar[node])

In the queries it's kinda messy but I basically cut the the path into two parts for both u1,v1 and u2,v2 where the first path is: u -> LCA(u,v)

second path is: LCA(u,v) -> v

I also need to include the LCA into the answer separately.

I believe the complexity of this should be O(N * log^2(N)) but it's getting TLE.

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Looks like really high constant factor. There are a lot of calls to inv. Changing power from recursive to iterative gives AC. Code Link. Also $$$log^2(n)$$$ is intended to fail F2. It is possible to modify the parallel binary search solution to also solve F2 in $$$knlog^2(n)$$$ by maintaining some deltas, but this will not be fast enough.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot.

      My solution is only log^2 due to calling inv and power in the query function, I just thought of precomputing some part of them.

      The submission link isn't opening,

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Sorry, not sure what the issue is, updated the link. Also for your implementation, I'm not sure but I believe it should be possible to store the inverse values for all the Segment tree nodes when building it. You would need to call inv only at the leaf nodes. Might also be possible to just use a double hash with a smaller modular field $$$\approx 10^6$$$ too. But all of these would increase the constant factor too, so not sure if it will AC even after removing the $$$log$$$.

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I changed power from recursive to iterative as you suggested to pass F1.

        I then changed the hashing type from Hash = (R + val1)(R + val2)... Which required me to use the inverse and power functions a lot.

        into Hash = val1 * p[val1] + val2 * p[val2] + ... Which allowed me to only add and subtract.

        Submission: 258066427. Thanks a lot.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem D's solution cancels out an existing set bit in f(x,y−1)⊕f(y+1…r)

it should be z instead of r

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D,

ans += 1ll * pref[z][i - 1][1] * (1 + suff[z][i + 1][0]);

ans += 1ll * (1 + pref[z][i - 1][0]) * suff[z][i + 1][1];

Why are we adding 1 with the suffix and prefix?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What does these two line means ?

    Can you explain?

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    adding 1, siginfies that we, dont take any suffix portion at all, just prefix and a[i] and similarly in 2nd equation , we just take a[i] and suffix (no prefix portion at all)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain what's wrong with my Solution

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is another solution for F in $$$O( n\sqrt n + q\frac{n}{b} + qkb )$$$ where $$$b$$$ is the block size which will be explained later. My implementation works in 3.5 seconds.258270314

Lets say that for every query we magically know $$$cnt_{1}$$$ and $$$cnt_{2}$$$ where $$$cnt_{1}[i]$$$ is number of nodes on path $$$u_{1}->v_{1}$$$ colored with color $$$i$$$, and $$$cnt_{2}$$$ is the same, but for $$$u_{2} -> v_{2}$$$. How could we find $$$k$$$ colors $$$i$$$ such that $$$cnt_{1}[i] \neq cnt_{2}[i]$$$?

Brute-force way would be to iterate $$$i$$$ from $$$1$$$ to $$$n$$$ and check for $$$cnt_{1}[i] \neq cnt_{2}[i]$$$. A bit faster way would be to split the colors from $$$1$$$ to $$$n$$$ into blocks of size $$$b$$$, and maintain xor-hash for each block(the things that are hashed are ordered pairs $$$(i,cnt[i])$$$, and we can do that by assigning a random integer for every such ordered pair, because there are $$$O(n)$$$ of them), and then we can traverse all the $$$\frac{n}{b}$$$ blocks and in $$$O(1)$$$ check if the pairs of blocks are identical, if a pair is not identical, we can iterate through that pair of blocks and straightforwardly check at which color they do not coincide, that will take $$$O(b)$$$ time per block and we will have to check at most $$$O(k)$$$ blocks per query. This would yield $$$O(\frac{n}{b} + kb)$$$ per query.

In order to do this, we need to somehow get rid of the "magically" part from the be second paragraph.

We can easily see that we can calculate the $$$cnt$$$ array along with the $$$hash$$$ array($$$hash[i]$$$ will be the xor-hash of $$$i$$$-th block of size $$$b$$$) for each $$$u->v$$$ that appears in the queries(2 per query) in $$$O(n\sqrt n)$$$ with MO. The problem with this is that we need to have the $$$cnt$$$ and the $$$hash$$$ array for $$$u_{1}->v_{1}$$$ and $$$u_{2}->v_{2}$$$ at the same time. We will try to solve that problem by running MO 2 times and memorizing some stuff in between those 2 runs.

We will run the first MO on all the $$$2q$$$ paths to find out for each query at most $$$k$$$ indices of blocks in the $$$cnt$$$ array which don't coincide, and we will memorize those block indices. To do this, for every query can have $$$hash_{i,1}$$$ and $$$hash_{i,2}$$$ which will be the state of the $$$hash$$$ array at the $$$i$$$-th query. This will take $$$O(q\frac{n}{b})$$$ memory to memorize(note: we can do it with $$$1$$$ array per query instead of $$$2$$$). After finishing the first MO we can easily recover, for each query, which blocks will have at least one non-coinciding color.

We will run the second MO on the same $$$2q$$$ paths, but now, instead of memorizing the $$$hash$$$ array, we will memorize, for each query, the $$$O(k)$$$ blocks whose indices we memorized in the first MO. This will take $$$O(kb)$$$ memory per query. After MO finishes, we can then check all the blocks that we memorized, and find the colors which do not coincide(this part can also be done with just $$$1$$$ array per query).

By setting the $$$b$$$ to $$$\sqrt \frac{n}{k}$$$, which in this case is $$$100$$$, we get a complexity that should barely pass.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can everyone help me? 1957C - How Does the Rook Move? why we are supposed to let dp[0] = 1 according to the official solution?According to my solution 257649223,i let a[0] = 0,but it is wrong.However,in 257649430,i let a[0] = 1,and it is right.Why is that?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F1 can be possibly solved using 4 times Mo's Algorithm + Hashing on a euler path by first scanning the upper square root part and then the lower square root part reaching complexity of $$$O((N+Q) (\sqrt{N} + \sqrt{Q}))$$$. It is also possible to use two hashes to further more avoid collision and meeting time limit. But in my case I need to control the memory to fit the memory constraint because my solution's memory consumption will also be $$$O(Q \sqrt N)$$$. Also, I needed to use winlib's 64 bit GCC to pass the question. Using 32 bit environment will fail to pass.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C,Can someone provide me the prove of the (m-c)!/((m-c)/2)! is the case number. It seems very interestring. Thanks

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F1 can be solved by maintain frequency table's rolling hash of each path from a vertex to root using persistent segment tree, and use binary search on segment tree to find the first different frequency between two path, and the time complexity would be $$$O(n\lg C + q\lg C)$$$

here is my implementation

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an implementation for the alternative solution of problem C? This was my initial idea but I discarded it because I had no idea how to calculate that term in the required time complexity. We have to iterate $$$c$$$ over all values from $$$0$$$ to $$$m$$$ which needs $$$O(m)$$$. Since $$$m \le n \le 10^5$$$ that leaves us with $$$O(log(m))$$$ to calculate

$$${m \choose c} \frac{(m-c)!}{((m-c)/2)!} \mod 1e9 + 7$$$

. As far as I know, it takes $O(k)$ to calculate $$$k!$$$. Of course, we could prepare a lookup table for factorial values mod $$$10^9 + 7$$$ but then we will get problems with dividing. I would really appreciate to see a solution to this.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There exists something called modular inversion which enables to divide two numbers that are some modulo remainders. Here is my solution that you can check out.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Comment should be there in editorial, It gets unnecessarily difficult to figure out what the writer has coded

»
6 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

This is the solution for Question D... Please look at the editorial, then see my explaination you will surely get it easily

link of image, i wrote it in notebook

https://ibb.co/bgcCqXp

Look at my submission, i commented it out.

[submission:https://codeforces.net/contest/1957/submission/262824863]

262824863

code well and never give up :)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The dp solution to C is elegant. Nicely written ,W editorialists and authors.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach for D was great

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ok

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ok