akcube's blog

By akcube, 5 weeks ago,

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

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

1957E - Carousel of Combinations

Idea: SilverTongue1729

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
• +84

 » 5 weeks ago, # | ← Rev. 2 →   +24 Find any differencesRound 700 DRound 837 F2 (easy version of the previous one)F2
 » 5 weeks ago, # |   +2 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
•  » » 5 weeks ago, # ^ |   +1 $a \le 100$, not $a \le n$
•  » » » 5 weeks ago, # ^ |   +3 Thank you, i didnt notice that :( Fixed it 257651745
 » 5 weeks ago, # |   +76 My official reaction to the 3rd question
 » 5 weeks ago, # |   +5 I think the complexity of E1 must be $O((n+q)log^2n)$, since we have to insert and query $(n+q)logn$ times.
•  » » 5 weeks ago, # ^ |   0 My bad. Updated editorial, thanks!
 » 5 weeks ago, # |   +30 In the Solution of 1957F1 — Frequency Mismatch (Easy Version), the article Hashing and Probability of Collision is written by rng_58, not rng68.
•  » » 5 weeks ago, # ^ |   0 Oops :P Fixed, thanks.
 » 5 weeks ago, # |   0 can anybody explain why (i-1) is multiplied in dp code of problem C ?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 There are 2*n-2 possible places where the rook can be placed for reducing the size of the chessboard without worrying about overcounting.
•  » » » 5 weeks ago, # ^ |   0 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
•  » » » » 5 weeks ago, # ^ |   0 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}$.
•  » » » » » 2 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } 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.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 weeks ago, # ^ |   0 thanks bro got it
•  » » 5 weeks ago, # ^ |   +5 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|_| 
 » 5 weeks ago, # | ← Rev. 2 →   0 https://codeforces.com/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.
•  » » 5 weeks ago, # ^ |   0 If $n = 1$, you are accessing $dp[2]$ which isn't defined.
•  » » » 5 weeks ago, # ^ |   0 omg I feel so dumb. I dropped more than 100 rating points because of that line XD. Thanks for the help.
 » 5 weeks ago, # | ← Rev. 2 →   0 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".
•  » » 5 weeks ago, # ^ |   0 Fixed this mistake, thanks for pointing this out.
 » 5 weeks ago, # |   +22 1957C is OEIS-A047974. Can be solved by dfs-brute force for small n, then search for formula.
 » 5 weeks ago, # |   +8 Could someone send me some problems like D please.
•  » » 5 weeks ago, # ^ |   +1 Search by math in the problemset, then filter out those that have XOR in the name
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   +1 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.
•  » » » 5 weeks ago, # ^ |   +1 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).
•  » » » » 5 weeks ago, # ^ |   0 me too, could someone detail their intuition behind their sol
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +2 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
•  » » » » » » 5 weeks ago, # ^ |   0 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<
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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 MSBthey must be odd odd or even even to make the MSB bit unset when xoring yes , with that it becomes same parity not different ?
•  » » » » » » » 5 weeks ago, # ^ |   0 in the editorial it says that it shouled be both set or both unset in ( f (x , y-1 ) and f ( y+1 , z)
•  » » » » » » » 5 weeks ago, # ^ |   0 $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$.
•  » » » » » » » » 5 weeks ago, # ^ |   0 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; }
•  » » » » » 5 weeks ago, # ^ |   +3 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.
•  » » » » » » 5 weeks ago, # ^ |   0 Thank you, your explanation is crystal clear. I completely trolled this.
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 deleted
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 deleted
 » 5 weeks ago, # | ← Rev. 2 →   +3 question on CWe 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 onbut 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]
•  » » 5 weeks ago, # ^ |   0 i have same question
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 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]?$
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » » » 5 weeks ago, # ^ |   +1 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.
•  » » » 5 weeks ago, # ^ |   0 why base case dp[0]=1 ? i couldn't undestand that
•  » » » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   0 How can we solve B if we change the condition to a_i>0
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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)
•  » » » 5 weeks ago, # ^ |   0 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
•  » » » » 5 weeks ago, # ^ |   0 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 :)
•  » » » » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   +4 Best div ever , even if you disagree B⁠-⁠)
 » 5 weeks ago, # |   +8 I was criminally close to solving C. Just couldn't make correct dp. Good contest
 » 5 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   0 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
•  » » 5 weeks ago, # ^ |   0 Yup you're right, just fixed this typo in the editorial.
 » 5 weeks ago, # |   +1 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.
•  » » 5 weeks ago, # ^ |   0 This helped a lott!!!! by the way, i'm just curious to know if (m−c−1)(m−c−3)(m−c−5)...=(m−c−1)!! is just your notation or if at all there is a concept resembling with that of factorials
•  » » » 5 weeks ago, # ^ |   0 It's called the double factorial
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 deleted
 » 5 weeks ago, # |   0 257439291 ez
 » 5 weeks ago, # |   0 257439291[submission:257439291]
 » 5 weeks ago, # |   0 Here: f(x,z)⊕ay>f(x,z) Doesn't this just mean that ay > 0 ?
•  » » 5 weeks ago, # ^ |   +6 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$
•  » » » 5 weeks ago, # ^ |   +3 Yes yes I get that, but I mean mathematically, why's taking the xor for both parts of the inequality is wrong?
•  » » » » 5 weeks ago, # ^ |   +6 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
•  » » » » » 5 weeks ago, # ^ |   +6 Oh okay, Thanks.
 » 5 weeks ago, # | ← Rev. 2 →   +4 can someone please explain the second part of dp transition in problem c?Edit: Doubt cleared.
•  » » 5 weeks ago, # ^ |   +3 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)
•  » » » 5 weeks ago, # ^ |   +3 thank you for your response. i have understood it.
 » 5 weeks ago, # |   0 interesting problem D
 » 5 weeks ago, # |   -16 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
•  » » 5 weeks ago, # ^ |   +12 I found logic easily for D but couldn't implement the solution (T_T).
 » 5 weeks ago, # |   0 what would be the approach of B if the question would have asked to maximize 1 using XOR operator?
 » 5 weeks ago, # |   +27 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!
•  » » 5 weeks ago, # ^ |   +19 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!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +19 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.
 » 5 weeks ago, # |   0 C的题解似乎出错了，没有考虑重点的情况
•  » » 5 weeks ago, # ^ |   0 看错了sorry
 » 5 weeks ago, # |   0 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.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 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.
•  » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   +8 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
 » 5 weeks ago, # | ← Rev. 2 →   0 what does the most significant bit in k mean?
•  » » 5 weeks ago, # ^ |   0 MSB mean the last bit to the left who is 1 in binary representation
 » 5 weeks ago, # |   +23 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
 » 5 weeks ago, # |   +11 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?
•  » » 5 weeks ago, # ^ |   +3 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.
•  » » » 5 weeks ago, # ^ |   0 Oh good to know. Thanks.
 » 5 weeks ago, # |   0 What was the difficulty rating of Problem A and B
 » 5 weeks ago, # |   +8 Damn, really great problems. Its a shame i didnt know modularni inverse at the time but lnow i do.
 » 5 weeks ago, # |   +8 Can anyone please refer more problems like C & D
 » 5 weeks ago, # |   0 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.com/contest/1957/submission/257638050
 » 5 weeks ago, # |   0 Can someone help me know what's going wrong in my solution for F1 and F2? 258029636So 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) -> vI 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.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +3 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.
•  » » » 5 weeks ago, # ^ |   0 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,
•  » » » » 5 weeks ago, # ^ |   +3 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$.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
 » 5 weeks ago, # | ← Rev. 2 →   0 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
•  » » 5 weeks ago, # ^ |   0 Fixed. Thank you
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   0 What does these two line means ? Can you explain?
 » 5 weeks ago, # |   0 Can anyone explain what's wrong with my Solution
 » 4 weeks ago, # |   0 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.258270314Lets 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.
 » 4 weeks ago, # |   0 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？
 » 4 weeks ago, # |   0 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.
 » 4 weeks ago, # |   0 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
 » 3 weeks ago, # |   0 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
 » 3 weeks ago, # |   0 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.
•  » » 3 weeks ago, # ^ |   0 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.
•  » » » 3 weeks ago, # ^ |   0 Thank you!
 » 3 days ago, # |   0 Comment should be there in editorial, It gets unnecessarily difficult to figure out what the writer has coded
 » 7 hours ago, # | ← Rev. 5 →   0 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 notebookhttps://ibb.co/bgcCqXpLook at my submission, i commented it out.[submission:https://codeforces.com/contest/1957/submission/262824863]262824863code well and never give up :)
•  » » 4 hours ago, # ^ | ← Rev. 2 →   0 ![ ]()i am very sorry, that will be xor(x,y-1)^(y+1,z)=1