### awoo's blog

By awoo, history, 2 months ago, translation,

1948A - Special Characters

Idea: BledDest

Tutorial
Solution (Neon)

1948B - Array Fix

Idea: BledDest

Tutorial
Solution (Neon)

1948C - Arrow Path

Idea: BledDest

Tutorial
Solution (Neon)

1948D - Tandem Repeats?

Idea: BledDest

Tutorial
Solution (awoo)

1948E - Clique Partition

Idea: BledDest

Tutorial
Solution (BledDest)

1948F - Rare Coins

Idea: BledDest

Tutorial
Solution (Neon)

1948G - MST with Matching

Idea: BledDest

Tutorial
Solution (BledDest)
• +93

 » 2 months ago, # |   0 In problem B why do we need to iterate through array from right to left and not from left to right?
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 Counterexample:1312 46 20If we will iterate from left to right we will get:1) 12 < 46. Don't change the array2) 46 > 20. Split 46 by 4 and 6And we got:12 4 6 20. Which is not a non-growth sorted array.If we will iterate from right to left we will get:1) 46 > 20. Split 46 by 4 and 62) 12 > 4. Split 12 by 1 and 2And we got:1 2 4 6 20. Which is a non-growth sorted array.Summary, iterating from left to right will give us the wrong answer. This is because the right element can split and become smaller than the left element, but we have already checked that the left element is larger than the right element and will not go back to check it again.
•  » » » 2 months ago, # ^ |   0 thx
•  » » » 2 months ago, # ^ |   0 Nice Explanation , Thanks
•  » » 2 months ago, # ^ |   0 Suppose initially $a_{i-1} \le a_i$; but after considering $a_i$ with $a_{i+1}$, we find out that we have to split $a_i$. This might break the condition $a_{i-1} \le a_i$, so if we iterate from left to right, we sometimes have to backtrack to fix the conditions we've broken
•  » » » 2 months ago, # ^ |   0 thx
•  » » 2 months ago, # ^ |   0 You can go from left to right also. My logic while going from left to right: https://mirror.codeforces.com/contest/1948/submission/251609551
•  » » » 2 months ago, # ^ |   0 ^read lastDigit as lastNumber
•  » » 2 months ago, # ^ |   0 I solved the problem by iterating from left to right with following logic: you want current element (CUR which can also be last digit if we divided the number in previous step) to be as small as possible because that can only help for next numbers, so you have two cases: 1) if you CAN divide current element i into it's digits with equality holding: CUR <= dig1 <= dig2 you do so, because then CUR = dig2 which is smallest possible. If you can't, if CUR <= a[i] then CUR = a[i]. If both do not hold, return NO. This works because at any moment, last element you have in your new array will be smallest possible which can only help for both of previously mentioned checks.
 » 2 months ago, # | ← Rev. 2 →   0 I write a simple brute force for Problem :B. But it is failing of hidden case.I am not able guess what it lacks. Can you please help. https://ideone.com/g5da0S
•  » » 2 months ago, # ^ |   0 you are iterating from left to right , as explanied in above comment ( https://mirror.codeforces.com/blog/entry/127182#comment-1128987 ) iterate from right to left then it might results in correct answer.
 » 2 months ago, # |   +3 In the place of tutorial of G ,it is showing tutorial of F.Update it please.
•  » » 2 months ago, # ^ |   +3 Fixed it, sorry.
 » 2 months ago, # |   +4 is it possible to solve Div2-D in less than O(n^2)?
 » 2 months ago, # | ← Rev. 2 →   0 Can someone please explain in solution of problem C. What are ok1 and ok2 actually signifying? How are we taking the indices of ok1 and ok2. I have been trying to understand for an hour, please help.
•  » » 2 months ago, # ^ |   +4 $ok1[i]$ and $ok2[i]$ refer to the second solution from the editorial. If $ok[i]$ is true, then the $i$-th diagonal pair of odd cells has at least one arrow to the right ($ok1$ and $ok2$ denote different diagonal directions).You can instead check every diagonal pair by bruteforcing all pairs of adjacent odd cells.
•  » » » 4 weeks ago, # ^ |   0 but if n=4 and i,j=0,3.then (j-i+1)/2=2.ok2.size() is 2,so will cross the border?
 » 2 months ago, # |   0 I thought D was hashes, wasnt able to implement it well tho... The author's solution is kinda weird
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Let me explain my solution of D -- I hope this might be easier to understand.First, let's fix the length of a tandem, and call it $2d$ ($d$ is the length of each half of the tandem). For each $d$, we try to find a tandem repeat of length $2d$, and the answer to the problem is the length of the longest one we could find. Also let's define the length of $s$ as $n = |s|$.A substring $s_l s_{l+1} \cdots s_{l + 2d - 1}$ is a tandem repeat if, for all indices $i \in \{ l, l+1, \ldots, l+d-1 \}$, $s_i = s_{i+d}$ is held. So, what matters here is the relationship between characters with distance $d$. With that in mind, let's define an array $\{ a_i \} \; (1 \le i \le n - d)$ as follows: $a_i = 1$ if $s_i = \text{'?'}$ or $s_{i+d} = \text{'?'}$ or $s_i = s_{i+d}$; $a_i = 0$ otherwise. Intuitively, $a_i$ is $1$ if $s_i$ and $s_{i+d}$ are equal or can be made equal. With this array $\{ a_i \}$, we can rephrase the condition that $s_l s_{l+1} \cdots s_{l + 2d - 1}$ can be a tandem repeat to: $a_l = a_{l+1} = \cdots = a_{l+d-1} = 1$ (selection of $\text{'?'}$s do not matter because each pair of letters in a tandem do not interfere with any other pairs). Thus, if there is a contiguous sequence of $1$s of length $d$ in $\{ a_i \}$, we have a tandem repeat of length $2d$; otherwise, there's no such tandem.Building $\{ a_i \}$ and finding contiguous $1$s can be done in $O(n)$-time, so $O(n^2)$-time overall.
•  » » » 2 months ago, # ^ |   0 Thank for explaining
•  » » » 2 months ago, # ^ |   0 nice explanation
 » 2 months ago, # |   +1 "Kruskal's algorithm with DSU might be a bit slower, but can also get accepted"I don't thinks so :(
•  » » 2 months ago, # ^ |   +22 I think it's possible to optimize this, for example, by sorting all edges only once, not for every Kruskal run.
•  » » » 2 months ago, # ^ |   0 Didn't think of that, thanks you!
 » 2 months ago, # | ← Rev. 4 →   +28 Here's a formulation of F as a probability problem (mostly because I am in a probability class right now :3). Suppose we have $s$ silver coins in the bag, $g$ gold coins in the bag, $t_s$ total silver coins and $t_g$ total gold coins. The value of the silver coins in the bag is represented by the random variable $S\sim \mathrm{Binom}(s,\frac{1}{2})$. The value of the rest of the silver coins is represented by the random variable $S'\sim \mathrm{Binom}(t_s-s,\frac{1}{2})$. We wish to compute $\mathbb{P}\left(S + g> S' + t_g-g\right) = \mathbb{P}\left(S - S'> t_g-2g\right).$The difference between random variables isn't nice to compute, so we want to turn it into a sum. Notice that the random variable $S' ':= t_s-s-S'$ has the same $\mathrm{Binom}(t_s-s,\frac{1}{2})$ distribution as $S'$ (this only holds because our probabilities are $\frac{1}{2}$). Therefore, $\mathbb{P}\left(S - S'> t_g-2g\right) = \mathbb{P}\left(S + S' ' > t_s - s +t_g-2g\right).$But the sum of binomial random variables is itself a binomial random variable: $S+S' '\sim \mathrm{Binom}(t_s-s+s,\frac{1}{2}) = \mathrm{Binom}(t_s,\frac{1}{2})$, which gives us the formula $\mathbb{P}\left(S + S' ' > t_s - s +t_g-2g\right) = \left(\frac{1}{2}\right)^{t_s}\sum_{k=t_s - s +t_g-2g + 1}^{t_s}\binom{t_s}{k}.$Here is my submission implementing this: 251836049.
 » 2 months ago, # |   0 This n^3 method passed systest. Can anyone hack it?code
 » 2 months ago, # |   0 Video Editorial For Problems A,B,C,D,E,F.
 » 2 months ago, # |   0 Problem G is awesome. I cannot put forward Konig's theory because I didn't realize that a tree is a bipartite graph during the contest. Sad.
 » 2 months ago, # |   0 Can anyone please provide the solution of B using DP , I think we can use bit masking to solve this as the value of Dp[i] (whether performing operation on the i'th index will result in a sorted array or not ) depends on the pervious values too , so we can have a mask that denotes on which of the previous indexes we have performed the operation ,Thanks for the help .
•  » » 2 months ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   0 Can you take a look into this codeI did BF using recursion to find all possibilities, but a test case is failing ?
 » 2 months ago, # |   0 Very fun problems, I like this contest!
 » 2 months ago, # |   0 In problem B i dont understand why when i Used a variable to iterate through the inputs of the array it and manipulate using the same algorithm it didnt work , however when i accepted all inputs in a vector , and started iterating and using my algorithm it worked out ? (check my accepted solution and the rejected one Using the Second Testing table) 252372121 252375040 Would be nice if someone can explain :/
 » 7 weeks ago, # |   0 problem D have weak test casesMy O(N^3) solution passes : O(N^3) submission
 » 7 weeks ago, # | ← Rev. 2 →   0 I have found an alternative solution to problem C only using if condition and do while loops -(https://mirror.codeforces.com/blog/entry/127853)
 » 7 weeks ago, # |   0 Hi, for Problem D, when I run my code locally with the provided testcases I get the correct answer. However, when I submit, I get a different output. Any ideas what's going on? link to submission
 » 5 weeks ago, # | ← Rev. 3 →   0 Hi, can anyone explain for me why the example answer of F — rare coins is that long line of integer?
 » 4 weeks ago, # |   0 1948C - Arrow Path The key observation for this problem that works for all these approaches is that, since we never skip a move and never try to move outside the grid, we can split the cells into two groups: if the sum of coordinates of the cell is even (we will call it "even cell"), we can end up in such a cell only after moving along the arrow (only after the second action during each second); otherwise, if the sum of coordinates of the cell is odd (we will call it "odd cell"), we can end up in such a cell only after making a move on our own (only after the first action during each second). I am not able to understand how the parity of coordinates sum will decide the category of a cell?
 » 2 weeks ago, # |   0 In problem F, why we use pw2 = binpow(binpow(2, MOD - 2), m) but not pw2 = binpow(binpow(2, m), MOD - 2)? I really don't understand it, can anyone explain this for me?
•  » » 10 days ago, # ^ |   0 they calculate the same thing.remember that binpow(x, MOD — 2) is finding the inverse of $x$, which is effectively $1/x$. So binpow(binpow(2, MOD — 2), m) means $(1/2)^m$. And binpow(binpow(2, m), MOD — 2) means $1/(2^m)$
•  » » 10 days ago, # ^ |   0 $(2^x)^y = (2^y)^x = 2^{xy}$