### -kirito-'s blog

By -kirito-, history, 4 months ago,
Problem A
Problem B
Problem C
Problem D
Problem E
• +30

 » 4 months ago, # |   +5 anyone explain me C can't understand editorial
•  » » 4 months ago, # ^ | ← Rev. 2 →   +5 The approach is: To start from the last and greedily choose whether the final string (i.e. once the flips are done and all strings are the same) has a 0 or a 1 in this position. Now, say at position i from the beginning, if the count of 0 is less than the count 1 then we flip the strings that have 0 in this position. We also keep a note of all the strings we have flipped and how many times so that when we move positions lesser than i we know whether it is the same bit as given or whether it has been flipped.When the count of 0 and 1 is the same it does not matter which one we choose to have in the final string as it does not affect the subsequent count of 0 or 1. (i.e what we choose in position i, in this case, results in the same count for 0 and 1 in i-1 position).
•  » » » 4 months ago, # ^ |   +5 if count of 0 is less than count of 1 at position i then wont we flip strings with 0 at i?
•  » » » » 4 months ago, # ^ |   +5 You are right. Sorry, it was a typo. My bad. Will edit it.
 » 4 months ago, # | ← Rev. 4 →   +5 Can someone prove that the minimum weakness in $D$ will always be $\sqrt{n-1}$? I was able to guess this from dry running up to $n=5$ but wasn't sure about it.
 » 4 months ago, # |   +5 I had a very simple dp solution for C code#include using namespace std; using ll = long long; #define ndl '\n' #define int long long void solve(ll tc) { int n, m; cin >> n >> m; vector a(n); for(auto &i: a) cin >> i; vector> dp(m, vector(2)); for(int i=0; i>T; for (ll tc = 1; tc <=T; tc++) solve(tc); return 0; } 
•  » » 4 months ago, # ^ |   0 THANK YOU BRO
•  » » 4 months ago, # ^ |   0 please explain your dp state and transitions also. Will be helpful
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 $dp[i][0]$ stores the min cost required to make every string equal uptill index $i$ with the character of $i^{th}$ index being 0.For the $(i+1)^{th}$ index we have 4 cases, I'll explain one of them, let's say the character chosen at the last index was 0 and for the current index you want to choose 1, then $dp[i+1][1] = dp[i][0] + 2 \times$(no of strings in which last character was 0 and current character is 0),because you want to retain the previous character and change the current character, which would require 2 flippings for each such string.
•  » » » » 4 months ago, # ^ |   0 thanks