PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Shanu Singroha
Tester: Jeevan Jyot Singh,Nishank Suresh
Editorialist: Yash Kulkarni
DIFFICULTY:
1567
PREREQUISITES:
PROBLEM:
For a binary string A, let f(A) denote its badness, defined to be the difference between the number of zeros and number of ones present in it. That is, if the string has c_0 zeros and c_1 ones, its badness is |c_0 - c_1|. For example, the badness of “01” is |1 - 1| = 0, the badness of “100” is |2 - 1| = 1, the badness of “1101” is |1 - 3| = 2, and the badness of the empty string is |0 - 0| = 0.
You are given an integer N and a binary string S.
You would like to partition S into K disjoint subsequences (some of which may be empty), such that the maximum badness among all these K subsequences is minimized. Find this value.
Formally,
- Let S_1, S_2, \ldots, S_K be a partition of S into disjoint subsequences. Every character of S must appear in one of the S_i. Some of the S_i may be empty.
- Then, find the minimum value of \max(f(S_1), f(S_2), \ldots, f(S_K)) across all possible choices of S_1, S_2, \ldots, S_K satisfying the first condition.
EXPLANATION:
Let there be O ones and Z zeros in S. After dividing S into K boxes let there be Z_i zeros and O_i ones in box i.
We can write, Z - O = (Z_1 - O_1) + (Z_1 - O_1) + ... (Z_K - O_K).
If Z > O then it is always better to divide S so that for each of the K boxes Z_i \geq O_i. This is because if for some box x we have Z_x < O_x, there has to be at least one box y having Z_y > O_y because Z > O overall. Reducing 1 zero from box x and placing it in box y instead would have helped to reduce the badness for both boxes x and y by 1. This is clearly not optimal. Using the above observation it is clear that Z_i- O_i is the badness for box i. Hence, we need to minimize the maximum among (Z_i - O_i) and this is achieved when all the K terms have as close values as possible and add up to Z - O which is known. The maximum term after such division is \lceil{\frac{Z-O}{K}}\rceil, which is our answer.
For Z<O the vice versa (replace ones by zeros and zeros by ones) is true and the answer is \lceil{\frac{O-Z}{K}}\rceil and if Z=O then the answer is 0 because we can place the entire S into 1 box.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Setter's solution
using namespace std;
#define fo(i,n) for(i=0;i<n;i++)
#define int long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define el cout<<"\n"
#define max3(a,b,c) max(max((a),(b)),(c))
#define max4(a,b,c,d) max(max((a),(b)),max((c),(d)))
#define min3(a,b,c) min(min((a),(b)),(c))
#define min4(a,b,c,d) min(min((a),(b)),min((c),(d)))
/////////////////////
int dx[] = {0, 0, -1, 1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, -1, 1, 1, -1};
//////////////////for vectors
# define maxv(a) (*max_element(a.begin(),a.end()))
# define minv(a) (*min_element(a.begin(),a.end()))
# define sumvi(a) (accumulate(a.begin(),a.end(),0LL))
# define sumvd(a) (accumulate(a.begin(),a.end(),double(0)))
# define printv(v) {auto i = v;for(auto j : i) cout<< j << ' ';cout << "\n";}
# define printvv(v) {auto i = v;for(auto j : i) {for(auto k : j) cout<< k << ' ';cout << "\n";}}
# define prints(s) {auto i = s;for(auto j : i) cout<< j << ' ';cout << "\n";}
# define printm(m) {auto i = m;for(auto j : i) cout<< j.first << ':' << j.second << ' ';cout << "\n";}
/////////////////////////
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
/////////////////////////
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0, lim - 1);
return uid(rang);
}
/////////////////////
const int inf = 1e9;
const int INF = 1e18;
const int mod = 1000000007;
// const int mod = 998244353;
const int N = 3e5 + 5, M = N;
////////////////
int total = 0;
void solve() {
int i, j, n, k;
cin >> n;
total += n;
assert( n >= 1 && n <= 200000);
cin >> k;
assert( n >= 1 && n <= mod - 7);
string str;
cin >> str;
fo(i, n) {
assert(str[i] == '0' || str[i] == '1');
}
int ones = 0;
int zeros = 0;
fo(i, n) {
if (str[i] == '1') ones++;
else zeros++;
}
int ans = abs( ones - zeros);
ans += k;
ans -= 1;
ans /= k;
cout << ans << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
int t = 1;
cin >> t;
while (t--) {
solve();
}
assert(total <= 200000);
return 0;
}
Editorialist's Solution
using namespace std;
int main() {
int T;
cin >> T;
while(T--){
int n,k;
cin >> n >> k;
string s;
cin >> s;
int x=0;
for(int i=0;i<n;i++){
if(s[i]=='0')x++;
else x--;
}
x=abs(x);
cout << x/k + (int)(x%k!=0) << endl;
}
return 0;
}