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;
}
Author: Nocturnality
This is a Bisection problem. For time $$$t$$$ seconds, $$$i^{th}$$$ student can be anywhere within segment $$$[x_{i}-v_{i}t , x_{i}+v_{i}t]$$$. In the binary search we need to check within $$$t$$$ seconds whether there is a common point among all the segments.
For all segments $$$[l_{1}, r_{1}] ,..., [l_{n}, r_{n}]$$$, we can calculate min $$$r_{i}$$$ and max $$$l_{i}$$$.
If $$$r_{i} < l_{i}$$$, there is no intersection. Otherwise [max $$$l_{i}$$$, min $$$r_{i}$$$ ] 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;
}
Author: B_a_k_a
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;
}
Author: RiBNAT
...
#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;
}
Author: GIVE_UP
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 $$$i^{th}$$$ 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 $$$i^{th}$$$ 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;
}
}
Author: B_a_k_a
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;
}
}
Author: RiBNAT
A prime number has $$$2$$$ divisors. A number $$$m$$$ has $$$3$$$ divisors if $$$m = p^{2}$$$, where $$$p$$$ is a prime number.
For example: $$$4 = 2^{2}$$$ has divisors {$$$1,2,4$$$}
For a prime number $$$p$$$ needed operations are $$$abs(n-p^{2})$$$. So we need to check this for all prime numbers up to $$$2⋅10^{6}$$$ (cause $$$10^{12} < 2⋅10^{6}*2⋅10^{6}$$$).
#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;
}
Author: B_a_k_a
If $$$n$$$ is $$$0$$$ or $$$2$$$, the values of $$$2n$$$ and $$$n^{2}$$$ are the same.
If $$$n$$$ is $$$1$$$, $$$2n$$$ is greater than $$$n^{2}$$$.
For $$$n$$$ greater than $$$2$$$, $$$2n$$$ grows linearly while $$$n^{2}$$$ grows quadratically. Therefore, $$$n^{2}$$$ 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";
}
Author: Nocturnality
...
#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;
}
Author: GIVE_UP
Thanks for Participating!