PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Jeevan Jyot Singh
Tester: Ashley Khoo, Nishant Shah
Editorialist: Prakhar Kochar
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given a binary string of S of length N. For every occurence of 01 in S, a tax of X rupees will be charged, while for every occurence of 10 in S, a tax of Y rupees will be charged.
Example
For X = 3, Y = 5 and S = 100101, then S has 2 occurrences of 10 and 2 occurrences of 01, so the tax charged =2 \cdot 3 + 2 \cdot 5 = 16
Rearrange the string S in any way you want. Minimize the amount of tax needs to be paid.
EXPLANATION:
Given that for every occurrence of 01 in S, a tax of X rupees is charged, while for every occurrence of 10 in S, a tax of Y rupees is charged. We can rearrange the string in any way we want.
Observation 1
If the given string contains only 0's or only 1's then there will be 0 occurrences of 10 and 01 in both the cases. Therefore in this case tax charged will always be 0.
Example
- X = 2, Y = 3, S = 00000
Tax charged = 0.
- X = 2, Y = 3, S = 11111
Tax charged = 0.
Observation 2
In order to minimize the amount of tax needs to be paid the number of occurrences of 10 and 01 in the string should be minimized. In order to do that either place all the 1's at the start of the string or at the end of the string.
CASE 1 : Placing all the 1's at the start of the string ensures that atmost 1 occurrence of 10 and no occurrence of 01 will be present in the string for which the tax charged will be Y rupees.
Example
- X = 2, Y = 3, S = 1010110
Initially there are 3 occurrences of 10 and 2 occurrences of 01; therefore, the tax charged will be 2 \cdot 2 + 3 \cdot 3 = 13.
If we place all the 1's at the start of the string, the string S will become 1111000. Now the number of occurrences of 10 will become 1 and number of occurrences of 01 will become 0. Therefore, the tax charged will be 0 \cdot 2 + 1 \cdot 3 = 3.
CASE 2 : Similarly, placing all the 1's at the end of the string ensures that atmost 1 occurence of 01 will be present in the string for which the tax charged will be X rupees.
Example
- X = 2, Y = 3, S = 1010110
Initially there are 3 occurrences of 10 and 2 occurrences of 01; therefore, the tax charged will be 2 \cdot 2 + 3 \cdot 3 = 13.
If we place all the 1's at the end of the string, the string S will become 0001111. Now the number of occurrences of 10 will become 0 and number of occurrences of 01 will become 1. Therefore, the tax charged will be 1 \cdot 2 + 0 \cdot 3 = 2.
Minimum tax charged using case 1 is Y rupees and minimum tax charged using case 2 is X rupees. Since we can rearrange the string in any way we want, we will rearrange it according to the case which gives minimum tax charged. Therefore final output will be minimum of X and Y if string contains both 0's and 1's.
TIME COMPLEXITY:
O(1) for each test case.
SOLUTION:
Tester-1's Solution
// Super Idol的笑容
// 都没你的甜
// 八月正午的阳光
// 都没你耀眼
// 热爱105°C的你
// 滴滴清纯的蒸馏水
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,x,y;
string s;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
int TC;
cin>>TC;
while (TC--){
cin>>n>>x>>y;
cin>>s;
sort(all(s));
if (s.front()==s.back()) cout<<0<<endl;
else cout<<min(x,y)<<endl;
}
}
Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
/*
---------Input Checker(ref : https://pastebin.com/Vk8tczPu )-----------
*/
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true)
{
char g = getchar();
if (g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if (cnt == 0)
{
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd)
{
if (is_neg)
{
x = -x;
}
if (!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
}
else
{
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while (true)
{
char g = getchar();
assert(g != -1);
if (g == endd)
{
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r)
{
return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r)
{
return readInt(l, r, '\n');
}
string readStringLn(int l, int r)
{
return readString(l, r, '\n');
}
string readStringSp(int l, int r)
{
return readString(l, r, ' ');
}
/*
-------------Main code starts here------------------------
*/
// Note here all the constants from constraints
const int MAX_T = 100;
const int MAX_N = 1000;
const int MAX_VAL = 100;
// vars
int all_same = 0;
int sum_n = 0;
int max_n = 0;
void solve()
{
int n, x, y;
string s;
n = readIntSp(2, MAX_N);
x = readIntSp(1, MAX_VAL);
y = readIntLn(1, MAX_VAL);
s = readStringLn(n, n);
sum_n += n;
max_n = max(max_n, n);
for (auto &x : s)
{
assert(x == '0' || x == '1');
}
vector<int> cnt(2, 0);
for (auto x : s)
cnt[x - '0']++;
if (cnt[0] == 0 || cnt[1] == 0)
{
all_same++;
cout << 0 << '\n';
}
else
{
cout << min(x, y) << '\n';
}
}
signed main()
{
int t;
t = readIntLn(1, MAX_T);
for (int i = 1; i <= t; i++)
{
solve();
}
// Make sure there are no extra characters at the end of input
assert(getchar() == -1);
cerr << "SUCCESS\n";
// Some important parameters which can help identify weakness in testdata
cerr << "Tests : " << t << '\n';
cerr << "Sum of length : " << sum_n << '\n';
cerr << "Max length : " << max_n << '\n';
cerr << "All same : " << all_same << '\n';
}
Editorialist's Solution
/*prakhar_87*/
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define inf INT_MAX
#define mod 998244353
void f() {
int n, x, y;
cin >> n >> x >> y;
string s; cin >> s;
sort(s.begin(), s.end());
if (s[0] == '1' || s[n - 1] == '0') cout << "0\n";
else cout << min(x, y) << "\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) f();
}