Contest Link: Battle of Brains 2024, University of Barishal
The solution approach is to use combinatorics. We can iterate over the possible number of Arenians in the team, starting from X to the min(P,A).
For each number of Arenians, we calculate the number of ways to choose that many Arenians from A and the remaining members from B.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e9+7;
const ll N = 2e6+7;
ll fact[N], invFact[N];
ll bigMod(ll base, ll power) {
if (!power) return 1;
ll result = bigMod(base, power/2);
result = (result * result) % M;
if (power & 1) result = (result * base) % M;
return result;
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
ll a, b, p, x; cin >> a >> b >> p >> x;
fact[0] = 1;
for (ll i = 1; i < N; i++) fact[i] = (fact[i-1] * i) % M;
invFact[N-1] = bigMod(fact[N-1], M-2);
for (ll i = N-2; i >= 0; i--) invFact[i] = (invFact[i+1] * (i+1)) % M;
ll ans = 0;
for (ll i = x; i <= min(p, a); i++) {
ll firstTeam = (fact[a] * ((invFact[i]*invFact[a-i]) % M)) % M; // aCi
if (b-p+i < 0) continue;
ll secondTeam = (fact[b] * ((invFact[p-i]*invFact[b-p+i]) % M)) % M; // bC(p-i)
ll temp = (firstTeam*secondTeam) % M;
ans = (ans+temp) % M;
}
cout << ans;
}
This is a Bisection problem. For time t seconds, ith student can be anywhere within segment [xi−vit,xi+vit]. In the binary search we need to check within t seconds whether there is a common point among all the segments.
For all segments [l1, r1],...,[ln, rn], we can calculate min ri and max li.
If ri<li, there is no intersection. Otherwise [max li, min ri ] is the intersection.
#include <bits/stdc++.h>
using namespace std;
// Function to check if all students can meet at a common point within time t
bool canMeet(double t, const vector<int>& positions, const vector<int>& speeds) {
double min_meet = -1e9;
double max_meet = 1e9;
int n = positions.size();
for (int i = 0; i < n; ++i) {
double left_bound = positions[i] - speeds[i] * t;
double right_bound = positions[i] + speeds[i] * t;
min_meet = max(min_meet, left_bound);
max_meet = min(max_meet, right_bound);
if (min_meet > max_meet) {
return false;
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<int> positions(n);
vector<int> speeds(n);
for (int i = 0; i < n; ++i) {
cin >> positions[i];
}
for (int i = 0; i < n; ++i) {
cin >> speeds[i];
}
double left = 0;
double right = 1e9;
double precision = 1e-7;
while (right - left > precision) {
double mid = left + (right - left) / 2;
if (canMeet(mid, positions, speeds)) {
right = mid;
} else {
left = mid;
}
}
cout << fixed << setprecision(10) << left;
}
The base of a number system determines the range of values that can be represented with each digit. For example, in base 10, the digits are 0−9, and any number can be represented using these digits. In base 2, the digits are 0 and 1.
To find the smallest base in which a given number can be represented, we simply need to find the largest digit or letter that appears in the number. This is because the base must be at least as large as the largest digit in order to represent that digit.
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
int n;
cin>>n;
string s;
cin>>s;
int mx = 2;
for(int i=0; i<s.size(); i++){
if(s[i]>='0' and s[i]<='9')mx = max(mx,s[i]-'0'+1);
else mx = max(mx, s[i]-'A'+11);
}
cout<<mx<<endl;
}
...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+7;
ll n, total, arr[105], dp[105][N];
ll solve(int i, ll sum) {
if (i >= n) return abs(total - 2*sum);
if (dp[i][sum] != -1) return dp[i][sum];
else return dp[i][sum] = min(solve(i+1, sum), solve(i+1, arr[i]+sum));
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
total += arr[i];
}
memset(dp, -1, sizeof(dp));
ll ans = solve(0, 0);
cout << ans;
}
If a player moves some peanuts from box i to i+1, in the next move the other player can also move these peanuts from box i+1 to i. So first operation has no effect in this game. Suppose a player moves some peanuts from box 2 to 1. Then the other player can move these peanuts from box 1 to 0.
For all ith box where i is even, if a player moves peanuts from it, the opposite player will make the last move. So these moves also have no effect. For determining the winner, we only need to xor all peanuts from ith box where i is odd.
If you are wondering why we are doing xor, you should learn Nim strategy.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t; cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<ll> ar(n);
for (int i = 0; i < n; i++) cin >> ar[i];
ll xor_sum = 0;
for (int i = 1; i < n; i += 2) xor_sum ^= ar[i];
if (xor_sum == 0) cout << "NO" << endl;
else cout << "YES" << endl;
}
}
The problem asks you to find the absolute difference between the number of occurrences of each character in two substrings of strings A and B, for multiple queries.
By using prefix sum arrays, we can efficiently calculate the result for each query without having to iterate through the entire substrings.
Create two 2D prefix sum arrays to store the count of each character up to index i in strings A and B. For each query, use the precomputed prefix sum arrays to calculate the difference between the number of occurrences of each character in the substrings A[l:r] and B[l:r]. Sum up the absolute differences for all characters to get the final result.
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
int n;
cin>>n;
string s, p;
cin >> s >> p;
s="#"+s;
p="#"+p;
int pre_s[n+2][26];
int pre_p[n+2][26];
mem(pre_s, 0);
mem(pre_p, 0);
for(int i=1; i<=n; i++){
pre_s[i][s[i]-'a']=1;
pre_p[i][p[i]-'a']=1;
for(int j=0; j<26; j++){
pre_s[i][j] += pre_s[i-1][j];
pre_p[i][j] += pre_p[i-1][j];
}
}
int q;
cin>>q;
while(q--){
int l, r;
cin>>l>>r;
int ans = 0;
for(int i=0; i<26; i++){
ans += abs((pre_s[r][i] - pre_s[l-1][i]) - (pre_p[r][i] - pre_p[l-1][i]));
}
cout<<ans<<endl;
}
}
A prime number has 2 divisors. A number m has 3 divisors if m=p2, where p is a prime number.
For example: 4=22 has divisors {1,2,4}
For a prime number p needed operations are abs(n−p2). So we need to check this for all prime numbers up to 2⋅106 (cause 1012<2⋅106∗2⋅106).
#include<bits/stdc++.h>
using namespace std;
#define mxn 2000000
ll chk[mxn+5];
void sieve(){
for(int i=2; i<mxn; i++){
if(chk[i]==0){
for(int j=i+i; j<mxn; j+=i){
chk[j] = 1;
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
sieve();
ll n;
cin>>n;
ll ans = 1000000000000000ll;
for(ll i=2; i<mxn; i++){
if(chk[i]) continue;
ll x = i*i;
ans = min(ans,abs(x-n));
}
cout<<ans<<endl;
}
If n is 0 or 2, the values of 2n and n2 are the same.
If n is 1, 2n is greater than n2.
For n greater than 2, 2n grows linearly while n2 grows quadratically. Therefore, n2 will eventually become greater than 2n.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
ll n; cin >> n;
if (n == 0 or n == 2) cout << "Same";
else if (n == 1) cout << "Double";
else cout << "Square";
}
...
#include<bits/stdc++.h>
using namespace std;
#define AS 250000
int i,j,k,l,m,n,p,q,r,a,b,c,u,v,x,y,z,ts=1;
int ar[AS],discover[AS],vis[AS],low[AS],br[AS];
vector<int> graph[AS];
set<int>st[AS];
vector<pair<int,int>>bridge;
void dfs(int nod,int par=-1) {
discover[nod]=low[nod]=z++;
vis[nod]=1;
for(auto i:graph[nod]) {
if(i==par)continue;
if(vis[i])low[nod]=min(low[nod],discover[i]);
else {
dfs(i,nod);
low[nod]=min(low[nod],low[i]);
if(low[i]>discover[nod]) {
bridge.push_back({nod,i});
st[nod].erase(i);
st[i].erase(nod);
}
}
}
}
int component_count;
void biparted(int nod,int col)
{
component_count++;
vis[nod]=2;
ar[nod]=col;
for(auto i:st[nod]) {
if(vis[i]==1)biparted(i,!col);
else if(ar[nod]==ar[i])c=1;
}
}
int main() {
cin>>n>>m;
for(int i=1;i<=m;i++) {
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
st[u].insert(v);
st[v].insert(u);
}
c=0;
for(int i=1;i<=n;i++) {
if(vis[i]==0) {
dfs(i,-1);
}
}
c=0;
int ans=0;
for(int i=1;i<=n;i++) {
if(vis[i]==1) {
component_count=c=0;
biparted(i,0);
if(c)ans+=component_count;
}
}
cout<<ans<<endl;
}
Thanks for Participating!