Can some one tell me the problem with just making the new string by adding as many zeroes till both strings have 1 and then adding the one which has more zeroes left after that index . etc.etc
I think the tests are weak. My O(n^3) DP solution passes. I coded this to check my logic and was hoping to optimize this using segment tree but O(n^3) passed.
Code Link: CodeChef: Practical coding for everyone
Can someone plz explain me this doubt :
The editorial mentions that if we’ve merged A[1…i] and B[1…j], now we’ve to take either A[i+1] or B[j+1] but why cant we take both, I mean A[i+1] and B[j+1]
Logic : take substrings of one’s and zero’s and find the value which should be placed before since a string’s own contribution cannot be changed, all we can do is change the contribution in the of a string in the second string.
On your tc my code is giving 20.
But wa ;_;
/* Author : Prakhar Rai */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ln(s) ll(s.length())
#define sz(a) ll(a.size())
#define pb emplace_back
#define fs first
#define sc second
#define vcll vector<ll>
#define all(x) x.begin(),x.end()
#define endl "\n"
#define vc vector
#define FOR(i,a,b) for(ll i = a; i < b; i++)
#define pika(x) cerr << #x << ' ' << x << endl;
#define yes "YES"
#define no "NO"
const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 5;
void test_case() {
ll n, p1(0), p2(0);
cin >> n;
string a, b, s = "";
cin >> a >> b;
while (p1 < n and a[p1] == '0') p1++;
while (p2 < n and b[p2] == '0') p2++;
ll fa = 1, fb = 1, ans = 0; // add individual contributions
while (p1 < n and p2 < n) {
ll a0, a1, b0, b1, sa, ea, sb, eb;
a0 = a1 = b0 = b1 = 0;
sa = p1;
while (p1 < n and a[p1] != '0') a1++, p1++;
while (p1 < n and a[p1] != '1') a0++, p1++;
ea = p1;
sb = p2;
while (p2 < n and b[p2] != '0') b1++, p2++;
while (p2 < n and b[p2] != '1') b0++, p2++;
eb = p2;
// cout << "a " << sa << ' ' << ea << endl;
// cout << "b " << sb << ' ' << eb << endl;
// add edge case - end one's
// cerr << a0 << ' ' << a1 << endl;
// cerr << b0 << ' ' << b1 << endl;
if (a1 * b0 < b1 * a0) {
s += a.substr(sa, ea - sa);
p2 = sb;
} else {
s += b.substr(sb, eb - sb);
p1 = sa;
}
// cout << s << endl;
}
if (p1 < n) while (p1 < n) s += a[p1++];
if (p2 < n) while (p2 < n) s += b[p2++];
// cout << ans << endl;
// cout << s << endl;
// s = "101010110110";
ll len = ln(s);
for (int i = 0; i < len; i++) {
if (s[i] == '1') {
ll z = 0;
for (int j = i + 1; j < len; j++)
if (s[j] == '0') z++;
ans += z;
}
}
cout << s << endl;
cout << ans << endl;
}
int main() {
FIO;
int _tests;
_tests = 1;
cin >> _tests;
for (int i = 1; i <= _tests; i++) {
// cout << "Case #" << i << ": ";
test_case();
}
}
I think, runtime error seems to be caused due to maximum recursion depth getting exceeded.
For fixing this just add the following line after importing the sys module.
My greedy solution works on the test cases given in comments. I calculated which ‘1’ brings how many inversions for both strings, then greedily added the ‘1’ with higher inversions to my answer string. I calculated the total inversions in the answer string and i dont recognize the flaw. Can anyone please point it out.