We want to extend our heartfelt gratitude to each and every one of you for participating in Code-X-Culture, our online coding event. Your enthusiasm, dedication, and creativity have made this event a remarkable success. We hope you enjoyed solving the questions as much as we enjoyed creating them for you.↵
A: RRR (Robbery Edition)↵
----------------------↵
Idea:[user:rachitkansal,2024-06-21]↵
↵
<spoiler summary="Solution">↵
Since there is a difference of 3 coins generated every day, the answer can be calculated using the formula ↵
$(a−b+2)/3$.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int main(){↵
int t;↵
cin>>t;↵
while(t--){↵
int x,y;↵
cin>>x>>y;↵
cout<<(y-x+2)/3<<endl;↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
B: Hridyansh's Dilemma↵
----------------------↵
Idea:[user:warmachineg,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
Think about maintaining a running total of the money accumulated each day and↵
compare it with the fee subtracted from this total.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
To solve this problem efficiently, iterate through each day while keeping track of the↵
maximum profit that can be obtained by subtracting the fee on that day from the accumulated↵
amount.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Maintain a running total of the money accumulated each day and compare it with the fee subtracted from this total. To solve this problem efficiently, iterate through each day while keeping track of the maximum profit that can be obtained by subtracting the fee on that day from the accumulated amount.↵
Time Complexity: $O(n)$↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <iomanip>↵
using namespace std;↵
void solve()↵
{↵
int initial,days;↵
cin>>initial>>days;↵
vector<int> stock,tax;↵
for(int i=0;i<days;i++)↵
{↵
int x;cin>>x;↵
stock.push_back(x);↵
}↵
for(int i=0;i<days;i++)↵
{↵
int x;cin>>x;↵
tax.push_back(x);↵
}↵
long long int max=initial,curr=initial;↵
int pos=-1;↵
for(int i=0;i<days;i++)↵
{↵
curr=curr+stock[i];↵
if(curr-tax[i]>max)↵
{↵
max=curr-tax[i];↵
pos=i;↵
}↵
}↵
cout<<pos+1<<' '<<max;↵
cout<<endl;↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
cin>>t;↵
while(t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code Explanation">↵
Input Reading:↵
↵
The function reads the initial investment amount initial and the number of days.↵
↵
It then reads the amounts added each day into the vector stock and the withdrawal fees into the vector penalty.↵
↵
Processing Each Day:↵
↵
The function initializes max to the initial amount and curr to the initial amount as well. pos is set to -1 to indicate no optimal day found yet.↵
↵
It iterates over each day, updating curr by adding the amount for that day from the stock array.↵
↵
For each day, it checks if the profit after subtracting the fee (from the penalty array) is greater than the previously recorded maximum profit (max). If so, it updates max and sets pos to the current day index.↵
↵
Output:↵
↵
After processing all days, the function outputs the best day to withdraw (pos + 1 because days are 1-indexed) and the maximum profit. If no profitable day is found (pos remains -1), it outputs 0 and the initial amount, indicating Hridyansh should not invest.↵
↵
We are taking variable curr and max in long long int because maximum value of c, d, a[i] is $10^5$ so our calculation can go upto stage where all are $10^5$ in this case our variable curr need to store value of order $10^{10}$ which is out of range of int.↵
</spoiler>↵
↵
C: A Gust of Wind↵
----------------------↵
Idea: [user:rn_das_2004,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
Answer is $-1$ only when $s[0] = 0$ (first character in string is 0), think about it.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Look at the positions of $1$ in the string and the corresponding position in the permutation. This part of the permutation is always sorted in ascending order.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
If $s[0] = 0$, then no solution exists as first element of p is always maximum of $[p_1]$.↵
↵
Else, A valid permutation is:↵
↵
We iterate over the string in reverse. The last occurrence of $1$ has the maximum value in the entire array, the second last occurrence has the second highest value… We fill p accordingly.↵
↵
With those values from $1$ to $n$ which are still left with us, we iterate in reverse over all the zeros then, using the same process. This creates a valid permutation always in $O(n)$ time.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
string s;↵
vector<int> v;↵
int main() {↵
ios_base::sync_with_stdio(false); ↵
cin.tie(NULL);↵
cout.tie(NULL);↵
int t;↵
cin>>t;↵
while(t--){↵
int n;↵
cin>>n;↵
cin>>s;↵
v.resize(n);↵
int c = n;↵
if(s[0]=='0')↵
cout<<-1<<endl;↵
else{↵
for(int i=n-1;i>=0;i--){↵
if(s[i]=='1'){↵
v[i] = c;↵
c--;↵
}}↵
for(int i=n-1;i>=0;i--){↵
if(s[i]=='0'){↵
v[i] = c;↵
c--;↵
}}↵
for(int i=0;i<n;i++)↵
cout<<v[i]<<" ";↵
cout<<endl;↵
v.clear();↵
}}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
D: The Attendance Problem↵
----------------------↵
Idea:[user:official_ashu_tosh,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
Think about the total no. of gaps available and check how we can distribute them.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Recall the concept of inverse modulo.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let he atteds 1st class after x1 days, 2nd class after x2 days, 3rd class after x3 days and so on the kth class after xk days↵
Let the days left after kth class be x(k+1)↵
↵
Here total no. of gaps available are : $n-k$↵
↵
so, $x1+x2+x3+....+xk+x(k+1) = n-k$;↵
↵
where $x1>=0, x2>=1, x3>=1..... xk>=1$, $x(k+1) >= 1$↵
↵
let $y1=x1$, $y2 = x2-1$, $y3=x3-1$,...... $yk = xk-1$, $y(k+1) = x(k+1)-1$↵
↵
so $y1+y2+y3....+y(k+1) = (n-k-(k-1))$↵
↵
solution for this equation is↵
$(n-k+1) C k$↵
↵
Now since no. can be too large we have to use the concept of inverse modulo↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define int long long↵
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)↵
↵
const long long MAXN = 366;↵
const long long MOD = 1e9 + 7;↵
↵
long long fac[MAXN + 1];↵
long long inv[MAXN + 1];↵
↵
long long power(long long x, long long y, long long p) {↵
long long res = 1; ↵
x = x % p;↵
while (y > 0) {↵
if (y & 1)↵
res = (res * x) % p;↵
y = y >> 1;↵
x = (x * x) % p;↵
}↵
return res;↵
}↵
↵
void factorial() {↵
fac[0] = 1;↵
for (long long i = 1; i <= MAXN; i++) { ↵
fac[i] = fac[i - 1] * i % MOD; ↵
}↵
inv[MAXN] = power(fac[MAXN], MOD - 2, MOD);↵
for (long long i = MAXN - 1; i >= 0; i--) {↵
inv[i] = (inv[i + 1] * (i + 1)) % MOD;↵
}↵
}↵
↵
long long choose(long long n, long long r) {↵
if(r > n) return 0ll;↵
return (fac[n] * inv[r] % MOD * inv[n - r] % MOD) % MOD;↵
}↵
↵
void solve(){↵
int n, k;↵
cin >> k >> n;↵
↵
if(k > (n + 1) / 2) cout << "0\n";↵
else {↵
n = (n - k + 1);↵
cout << choose(n, k) << endl;↵
}↵
}↵
↵
signed main() {↵
fastio();↵
factorial();↵
int t; cin >> t;↵
while(t--)↵
solve();↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
E: Min-Orray↵
----------------------↵
Idea: [user:sarvesh0955,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
What is max OR possible? Take the whole array OR.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Prefix sum of set bits.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
First, we find the maximum possible OR of the given array by taking the OR of the whole array in $O(n)$ time. ↵
↵
Now, we need to find the shortest subarray which will give the OR equal to the max OR found. There are many possible ways to achieve this, some of them are listed below:↵
↵
1) One possible solution is using two loops to iterate over all subarrays and find the minimum subarray, but the complexity of this approach will be $O(n^2)$.↵
↵
2) We can find the minimum subarray in $O(32 \cdot n \cdot \log n)$ using binary search and prefix sum. First, we store the frequency of set bits in a prefix sum 2D array of size $32 \cdot n$. Then, we do binary search ($\log n$) on the answer (from $1$ to $n$) to check if it is a possible answer or not. In the predicate function, we can brute force ($O(32 \cdot n)$) on all possible subarrays of that size. (See solution code for detailed predicate function)↵
↵
3) We can further reduce the time complexity to $O(32 \cdot n)$ using the two-pointer method. (See code for this implementation)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define pb push_back↵
#define endl "\n"↵
#define vl vector<ll>↵
↵
bool good(vector<vl> &pf,ll m,ll maxx,ll n){↵
for(ll i=m;i<=n;i++){↵
ll sum = 0;↵
for(ll j=0;j<32;j++){↵
if((pf[j][i]-pf[j][i-m])>0){↵
sum += (1ll<<j);↵
}↵
}↵
if(sum==maxx)↵
return true;↵
}↵
return false;↵
}↵
↵
void solve()↵
{↵
ll n;↵
cin>>n;↵
vl a(n);↵
for(ll i=0;i<n;i++){↵
cin>>a[i];↵
}↵
↵
ll maxx = 0;↵
for(ll i=0;i<n;i++){↵
maxx |= a[i];↵
}↵
↵
vector<bitset<32>> v;↵
for(ll i=0;i<n;i++){↵
bitset<32> num(a[i]);↵
v.pb(num);↵
}↵
↵
vector<vl> pf(32,vl (n+1));↵
for(ll i=0;i<32;i++){↵
pf[i][0] = 0;↵
for(ll j=0;j<n;j++){↵
if(v[j][i]){↵
pf[i][j+1] = pf[i][j] + 1;↵
}↵
else{↵
pf[i][j+1] = pf[i][j];↵
}↵
}↵
}↵
↵
ll l=1,r=n;↵
while(r-l>1){↵
ll m = l + (r-l)/2;↵
if(good(pf,m,maxx,n)){↵
r = m;↵
}↵
else{↵
l = m + 1;↵
}↵
}↵
↵
if(good(pf,l,maxx,n)){↵
cout<<l<<endl;↵
}↵
else{↵
cout<<r<<endl;↵
}↵
}↵
↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
int T=1;↵
cin>>T;↵
while(T--)↵
solve();↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Second Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define pb push_back↵
#define endl "\n"↵
#define vl vector<ll>↵
↵
void solve()↵
{↵
ll n;↵
cin>>n;↵
vl a(n);↵
for(ll i=0;i<n;i++){↵
cin>>a[i];↵
}↵
↵
ll maxx = 0;↵
for(ll i=0;i<n;i++){↵
maxx |= a[i];↵
}↵
↵
vector<bitset<32>> v;↵
for(ll i=0;i<n;i++){↵
bitset<32> num(a[i]);↵
v.pb(num);↵
}↵
↵
vector<vl> pf(32,vl (n+1));↵
for(ll i=0;i<32;i++){↵
pf[i][0] = 0;↵
for(ll j=0;j<n;j++){↵
if(v[j][i]){↵
pf[i][j+1] = pf[i][j] + 1;↵
}↵
else{↵
pf[i][j+1] = pf[i][j];↵
}↵
}↵
}↵
↵
ll l=0,r=0;↵
ll orr = 0;↵
ll ans = 1e18;↵
while(l<n && r<n){↵
orr |= a[r];↵
while(orr==maxx && l<=r){↵
ans = min((r-l+1),ans);↵
if(l==r)break;↵
l++;↵
for(ll i=0;i<32;i++){↵
if(v[l-1][i])↵
if((pf[i][r+1] - pf[i][l]) == 0){↵
orr -= (1ll<<i);↵
}↵
}↵
}↵
r++;↵
}↵
cout<<ans<<endl;↵
}↵
↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
int T=1;↵
cin>>T;↵
while(T--)↵
solve();↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
F: Chocolate Bar↵
----------------------↵
Idea: [user:inosed,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
Can we think of finding the longest palindrome first and then removing $k$ characters greedily?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Does the constraints allow us to run a loop of $n^2$ .↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Lets just reverse the problem and length of longest palindromic subsequence that could have been made from original $n$ letters be L ? now if $k$ <= $n-L$ then we can directly say that answer would be as for removing $k$ letters we will choose them from $n-L$ pile .↵
↵
Now what if $k>n-L$ . How to remove from this subsequence ?↵
We start with removing the middle and answer is always $n-k$ .↵
↵
For finding the length of longest palindromic subsequence we can use dynamic programming.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define int long long↵
↵
int longestPalindromeSubseq(string s) {↵
int n = s.size();↵
string b(s.rbegin(), s.rend());↵
int dp[n+1][n+1];↵
memset(dp,0,sizeof(dp));↵
for(int i =1; i<=n;++i){↵
for(int j =1; j<=n;++j){↵
if(s[i-1]==b[j-1]){↵
dp[i][j]=1+dp[i-1][j-1];↵
}↵
else{↵
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);↵
}↵
}↵
}↵
return dp[n][n];↵
}↵
signed main() {↵
int t ; cin >> t;↵
while(t--){↵
int n;↵
cin >> n;↵
int k;↵
cin >> k;↵
↵
string s;↵
cin >> s;↵
↵
↵
↵
int lpsLength = longestPalindromeSubseq(s);↵
↵
↵
↵
↵
int remainingDeletions = k - (n - lpsLength);↵
if(k<=n-lpsLength){↵
cout << lpsLength << '\n';↵
}↵
else{↵
int rem = lpsLength -(k - (n - lpsLength));↵
cout << rem << '\n';↵
↵
↵
↵
}↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Bonus">↵
The original question was to also print the subsequence but latter it was discarded to maintain level of contest . Can you do so :).↵
</spoiler>↵
↵
G : RRR (Revenge Edition)↵
----------------------↵
Idea:[user:rachitkansal,2024-06-22]↵
↵
<spoiler summary="Hint 1">↵
For n=4, sequence will be 2,3,3,2.↵
↵
For n=5, sequence will be 2,3,4,2,3,4.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Think of parities.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
It’s very clear that we can’t check rooms randomly.↵
↵
Approach:↵
↵
We will always assume that the thief is in an even-numbered room (why not an odd-numbered one?).↵
↵
So, we will start checking from the 2nd room. If we find him, that's good. Otherwise, if he was in an even-numbered room and we checked the 2nd room, it means now he is in an odd-numbered room, and he can’t go to room 1. Similarly, we will go up to the $(n-2)$ th room, each time eliminating one room.↵
↵
When we check the $(n-2)$ th room and don’t find the thief, we can be assured that he was in room $n$ ( Why ? ) at that time and must have moved to room $n-1$. At this point, we will catch him.↵
↵
However, this approach assumes that the thief was initially in an even-numbered room. If our assumption is wrong, we won’t be able to catch the thief in the $(n-1)$ th room.↵
↵
But this process is not a waste. Now we know whether he is in an odd-numbered room or an even-numbered room. (How?)↵
If he is in an even-numbered room, we will repeat the procedure.↵
↵
If he is in an odd-numbered room, we will start from the last odd-numbered room (but why not from room $1$? Even the question demanded the lexicographically smallest element).↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n;↵
cin>>n;↵
if(n==1) {↵
cout<<1<<" "<<60<<endl;↵
cout<<1;↵
}↵
else if(n==2) {↵
cout<<2<<" "<<135<<endl;↵
cout<<1<<" "<<1;↵
}↵
else {↵
cout<<2*(n-2)<<" ";↵
int x=2*(n-2);↵
int y=x-1;↵
cout<<x*60+y*15<<endl;↵
if(n%2!=0) {↵
for (int i = 2; i < n; i++)↵
{↵
cout<<i<<" ";↵
/* code */↵
}↵
for (int i = 2; i < n; i++)↵
{↵
cout<<i<<" ";↵
/* code */↵
}↵
}↵
else {↵
for (int i = 2; i < n; i++)↵
{↵
cout<<i<<" ";↵
/* code */↵
}↵
for (int i = n-1; i >= 2; i--)↵
{↵
cout<<i<<" ";↵
/* code */↵
}↵
}↵
}↵
}↵
↵
↵
↵
↵
/*----------------------------------------------------------------------------------*/↵
↵
↵
↵
↵
int32_t main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
cout << "\n";↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
H: Just Median↵
----------------------↵
Idea:[user:rishabh_king,2024-06-22]↵
↵
<spoiler summary="Hint 1">↵
Notice constraints on elements of array.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
You can use ones and zeros to represent if an index has been deleted or not.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
You have update a point in a range . Which data structure can be used?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Here, Fenwick Tree(BIT) could be used (alternative can be ordered set or segment trees). Here, constraint on elements of $a$ is $1<=element<=n$ where max value of can be $2\cdot10^5$ . So, we can use an array of n+1 length to store frequency of each element but there is a catch we have to work in a range so make this frequency array a BIT . Now, for index use an array of n+1 elements as a BIT , initialize all elements except 0 with value 1 which represent this value is still present in array. ↵
In each query, use binary search to find where the index prefix sum is equal to given number x . Now update BIT of index -1 where you find $x^{th}$ index . Now use update BIT on frequency array to decrease value found at $x^{th}$ index by 1 . Use binary search again to find median element in frequency BIT .↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void update(int i,int val,int n,vector<int> &bit){↵
while(i<=n){↵
bit[i] += val;↵
i += (i & (-i));↵
}↵
}↵
↵
int query(int i,int n,vector<int> &bit){↵
int ans=0;↵
while(i>0){↵
ans += bit[i];↵
i -= (i & (-i));↵
}↵
return ans;↵
}↵
↵
int binary_mid(int val,int n,vector<int> &bit){↵
int ans = INT_MAX;↵
int l = 1 , h = n;↵
while(l<=h){↵
int mid = l + (h - l)/2;↵
if(query(mid,n,bit)>=val){↵
ans = min(ans,mid);↵
h = mid - 1;↵
}↵
else {↵
l = mid +1;↵
}↵
}↵
return ans;↵
}↵
↵
int main(){↵
ios::sync_with_stdio(false); cin.tie(0);↵
↵
int test;cin >> test;↵
while(test--){↵
int n,q; cin>> n >> q;↵
vector<int> v(n+1,0),bit(n+1,0),freq(n+2,0);↵
for(int i=1;i<=n;i++){↵
cin >> v[i];↵
update(i,1,n,bit);↵
update(v[i],1,n,freq);↵
}↵
int size = n;↵
while(q--){↵
int x; cin >> x;↵
int ans = binary_mid(x,n,bit);↵
update(v[ans],-1,n,freq);↵
update(ans,-1,n,bit);↵
size--;↵
int pri = binary_mid((size+1)/2,n,freq);↵
cout << pri << " ";↵
}↵
cout << endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
A: RRR (Robbery Edition)↵
----------------------↵
Idea:[user:rachitkansal,2024-06-21]↵
↵
<spoiler summary="Solution">↵
Since there is a difference of 3 coins generated every day, the answer can be calculated using the formula ↵
$(a−b+2)/3$.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
int main(){↵
int t;↵
cin>>t;↵
while(t--){↵
int x,y;↵
cin>>x>>y;↵
cout<<(y-x+2)/3<<endl;↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
B: Hridyansh's Dilemma↵
----------------------↵
Idea:[user:warmachineg,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
Think about maintaining a running total of the money accumulated each day and↵
compare it with the fee subtracted from this total.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
To solve this problem efficiently, iterate through each day while keeping track of the↵
maximum profit that can be obtained by subtracting the fee on that day from the accumulated↵
amount.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Maintain a running total of the money accumulated each day and compare it with the fee subtracted from this total. To solve this problem efficiently, iterate through each day while keeping track of the maximum profit that can be obtained by subtracting the fee on that day from the accumulated amount.↵
Time Complexity: $O(n)$↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <iomanip>↵
using namespace std;↵
void solve()↵
{↵
int initial,days;↵
cin>>initial>>days;↵
vector<int> stock,tax;↵
for(int i=0;i<days;i++)↵
{↵
int x;cin>>x;↵
stock.push_back(x);↵
}↵
for(int i=0;i<days;i++)↵
{↵
int x;cin>>x;↵
tax.push_back(x);↵
}↵
long long int max=initial,curr=initial;↵
int pos=-1;↵
for(int i=0;i<days;i++)↵
{↵
curr=curr+stock[i];↵
if(curr-tax[i]>max)↵
{↵
max=curr-tax[i];↵
pos=i;↵
}↵
}↵
cout<<pos+1<<' '<<max;↵
cout<<endl;↵
}↵
signed main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int t;↵
cin>>t;↵
while(t--)↵
{↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code Explanation">↵
Input Reading:↵
↵
The function reads the initial investment amount initial and the number of days.↵
↵
It then reads the amounts added each day into the vector stock and the withdrawal fees into the vector penalty.↵
↵
Processing Each Day:↵
↵
The function initializes max to the initial amount and curr to the initial amount as well. pos is set to -1 to indicate no optimal day found yet.↵
↵
It iterates over each day, updating curr by adding the amount for that day from the stock array.↵
↵
For each day, it checks if the profit after subtracting the fee (from the penalty array) is greater than the previously recorded maximum profit (max). If so, it updates max and sets pos to the current day index.↵
↵
Output:↵
↵
After processing all days, the function outputs the best day to withdraw (pos + 1 because days are 1-indexed) and the maximum profit. If no profitable day is found (pos remains -1), it outputs 0 and the initial amount, indicating Hridyansh should not invest.↵
↵
We are taking variable curr and max in long long int because maximum value of c, d, a[i] is $10^5$ so our calculation can go upto stage where all are $10^5$ in this case our variable curr need to store value of order $10^{10}$ which is out of range of int.↵
</spoiler>↵
↵
C: A Gust of Wind↵
----------------------↵
Idea: [user:rn_das_2004,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
Answer is $-1$ only when $s[0] = 0$ (first character in string is 0), think about it.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Look at the positions of $1$ in the string and the corresponding position in the permutation. This part of the permutation is always sorted in ascending order.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
If $s[0] = 0$, then no solution exists as first element of p is always maximum of $[p_1]$.↵
↵
Else, A valid permutation is:↵
↵
We iterate over the string in reverse. The last occurrence of $1$ has the maximum value in the entire array, the second last occurrence has the second highest value… We fill p accordingly.↵
↵
With those values from $1$ to $n$ which are still left with us, we iterate in reverse over all the zeros then, using the same process. This creates a valid permutation always in $O(n)$ time.↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
string s;↵
vector<int> v;↵
int main() {↵
ios_base::sync_with_stdio(false); ↵
cin.tie(NULL);↵
cout.tie(NULL);↵
int t;↵
cin>>t;↵
while(t--){↵
int n;↵
cin>>n;↵
cin>>s;↵
v.resize(n);↵
int c = n;↵
if(s[0]=='0')↵
cout<<-1<<endl;↵
else{↵
for(int i=n-1;i>=0;i--){↵
if(s[i]=='1'){↵
v[i] = c;↵
c--;↵
}}↵
for(int i=n-1;i>=0;i--){↵
if(s[i]=='0'){↵
v[i] = c;↵
c--;↵
}}↵
for(int i=0;i<n;i++)↵
cout<<v[i]<<" ";↵
cout<<endl;↵
v.clear();↵
}}↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
D: The Attendance Problem↵
----------------------↵
Idea:[user:official_ashu_tosh,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
Think about the total no. of gaps available and check how we can distribute them.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Recall the concept of inverse modulo.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let he atteds 1st class after x1 days, 2nd class after x2 days, 3rd class after x3 days and so on the kth class after xk days↵
Let the days left after kth class be x(k+1)↵
↵
Here total no. of gaps available are : $n-k$↵
↵
so, $x1+x2+x3+....+xk+x(k+1) = n-k$;↵
↵
where $x1>=0, x2>=1, x3>=1..... xk>=1$, $x(k+1) >= 1$↵
↵
let $y1=x1$, $y2 = x2-1$, $y3=x3-1$,...... $yk = xk-1$, $y(k+1) = x(k+1)-1$↵
↵
so $y1+y2+y3....+y(k+1) = (n-k-(k-1))$↵
↵
solution for this equation is↵
$(n-k+1) C k$↵
↵
Now since no. can be too large we have to use the concept of inverse modulo↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define int long long↵
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)↵
↵
const long long MAXN = 366;↵
const long long MOD = 1e9 + 7;↵
↵
long long fac[MAXN + 1];↵
long long inv[MAXN + 1];↵
↵
long long power(long long x, long long y, long long p) {↵
long long res = 1; ↵
x = x % p;↵
while (y > 0) {↵
if (y & 1)↵
res = (res * x) % p;↵
y = y >> 1;↵
x = (x * x) % p;↵
}↵
return res;↵
}↵
↵
void factorial() {↵
fac[0] = 1;↵
for (long long i = 1; i <= MAXN; i++) { ↵
fac[i] = fac[i - 1] * i % MOD; ↵
}↵
inv[MAXN] = power(fac[MAXN], MOD - 2, MOD);↵
for (long long i = MAXN - 1; i >= 0; i--) {↵
inv[i] = (inv[i + 1] * (i + 1)) % MOD;↵
}↵
}↵
↵
long long choose(long long n, long long r) {↵
if(r > n) return 0ll;↵
return (fac[n] * inv[r] % MOD * inv[n - r] % MOD) % MOD;↵
}↵
↵
void solve(){↵
int n, k;↵
cin >> k >> n;↵
↵
if(k > (n + 1) / 2) cout << "0\n";↵
else {↵
n = (n - k + 1);↵
cout << choose(n, k) << endl;↵
}↵
}↵
↵
signed main() {↵
fastio();↵
factorial();↵
int t; cin >> t;↵
while(t--)↵
solve();↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
E: Min-Orray↵
----------------------↵
Idea: [user:sarvesh0955,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
What is max OR possible? Take the whole array OR.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Prefix sum of set bits.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
First, we find the maximum possible OR of the given array by taking the OR of the whole array in $O(n)$ time. ↵
↵
Now, we need to find the shortest subarray which will give the OR equal to the max OR found. There are many possible ways to achieve this, some of them are listed below:↵
↵
1) One possible solution is using two loops to iterate over all subarrays and find the minimum subarray, but the complexity of this approach will be $O(n^2)$.↵
↵
2) We can find the minimum subarray in $O(32 \cdot n \cdot \log n)$ using binary search and prefix sum. First, we store the frequency of set bits in a prefix sum 2D array of size $32 \cdot n$. Then, we do binary search ($\log n$) on the answer (from $1$ to $n$) to check if it is a possible answer or not. In the predicate function, we can brute force ($O(32 \cdot n)$) on all possible subarrays of that size. (See solution code for detailed predicate function)↵
↵
3) We can further reduce the time complexity to $O(32 \cdot n)$ using the two-pointer method. (See code for this implementation)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define pb push_back↵
#define endl "\n"↵
#define vl vector<ll>↵
↵
bool good(vector<vl> &pf,ll m,ll maxx,ll n){↵
for(ll i=m;i<=n;i++){↵
ll sum = 0;↵
for(ll j=0;j<32;j++){↵
if((pf[j][i]-pf[j][i-m])>0){↵
sum += (1ll<<j);↵
}↵
}↵
if(sum==maxx)↵
return true;↵
}↵
return false;↵
}↵
↵
void solve()↵
{↵
ll n;↵
cin>>n;↵
vl a(n);↵
for(ll i=0;i<n;i++){↵
cin>>a[i];↵
}↵
↵
ll maxx = 0;↵
for(ll i=0;i<n;i++){↵
maxx |= a[i];↵
}↵
↵
vector<bitset<32>> v;↵
for(ll i=0;i<n;i++){↵
bitset<32> num(a[i]);↵
v.pb(num);↵
}↵
↵
vector<vl> pf(32,vl (n+1));↵
for(ll i=0;i<32;i++){↵
pf[i][0] = 0;↵
for(ll j=0;j<n;j++){↵
if(v[j][i]){↵
pf[i][j+1] = pf[i][j] + 1;↵
}↵
else{↵
pf[i][j+1] = pf[i][j];↵
}↵
}↵
}↵
↵
ll l=1,r=n;↵
while(r-l>1){↵
ll m = l + (r-l)/2;↵
if(good(pf,m,maxx,n)){↵
r = m;↵
}↵
else{↵
l = m + 1;↵
}↵
}↵
↵
if(good(pf,l,maxx,n)){↵
cout<<l<<endl;↵
}↵
else{↵
cout<<r<<endl;↵
}↵
}↵
↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
int T=1;↵
cin>>T;↵
while(T--)↵
solve();↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Second Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define ll long long int↵
#define pb push_back↵
#define endl "\n"↵
#define vl vector<ll>↵
↵
void solve()↵
{↵
ll n;↵
cin>>n;↵
vl a(n);↵
for(ll i=0;i<n;i++){↵
cin>>a[i];↵
}↵
↵
ll maxx = 0;↵
for(ll i=0;i<n;i++){↵
maxx |= a[i];↵
}↵
↵
vector<bitset<32>> v;↵
for(ll i=0;i<n;i++){↵
bitset<32> num(a[i]);↵
v.pb(num);↵
}↵
↵
vector<vl> pf(32,vl (n+1));↵
for(ll i=0;i<32;i++){↵
pf[i][0] = 0;↵
for(ll j=0;j<n;j++){↵
if(v[j][i]){↵
pf[i][j+1] = pf[i][j] + 1;↵
}↵
else{↵
pf[i][j+1] = pf[i][j];↵
}↵
}↵
}↵
↵
ll l=0,r=0;↵
ll orr = 0;↵
ll ans = 1e18;↵
while(l<n && r<n){↵
orr |= a[r];↵
while(orr==maxx && l<=r){↵
ans = min((r-l+1),ans);↵
if(l==r)break;↵
l++;↵
for(ll i=0;i<32;i++){↵
if(v[l-1][i])↵
if((pf[i][r+1] - pf[i][l]) == 0){↵
orr -= (1ll<<i);↵
}↵
}↵
}↵
r++;↵
}↵
cout<<ans<<endl;↵
}↵
↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
int T=1;↵
cin>>T;↵
while(T--)↵
solve();↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
F: Chocolate Bar↵
----------------------↵
Idea: [user:inosed,2024-06-21]↵
↵
<spoiler summary="Hint 1">↵
Can we think of finding the longest palindrome first and then removing $k$ characters greedily?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Does the constraints allow us to run a loop of $n^2$ .↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Lets just reverse the problem and length of longest palindromic subsequence that could have been made from original $n$ letters be L ? now if $k$ <= $n-L$ then we can directly say that answer would be as for removing $k$ letters we will choose them from $n-L$ pile .↵
↵
Now what if $k>n-L$ . How to remove from this subsequence ?↵
We start with removing the middle and answer is always $n-k$ .↵
↵
For finding the length of longest palindromic subsequence we can use dynamic programming.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define int long long↵
↵
int longestPalindromeSubseq(string s) {↵
int n = s.size();↵
string b(s.rbegin(), s.rend());↵
int dp[n+1][n+1];↵
memset(dp,0,sizeof(dp));↵
for(int i =1; i<=n;++i){↵
for(int j =1; j<=n;++j){↵
if(s[i-1]==b[j-1]){↵
dp[i][j]=1+dp[i-1][j-1];↵
}↵
else{↵
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);↵
}↵
}↵
}↵
return dp[n][n];↵
}↵
signed main() {↵
int t ; cin >> t;↵
while(t--){↵
int n;↵
cin >> n;↵
int k;↵
cin >> k;↵
↵
string s;↵
cin >> s;↵
↵
↵
↵
int lpsLength = longestPalindromeSubseq(s);↵
↵
↵
↵
↵
int remainingDeletions = k - (n - lpsLength);↵
if(k<=n-lpsLength){↵
cout << lpsLength << '\n';↵
}↵
else{↵
int rem = lpsLength -(k - (n - lpsLength));↵
cout << rem << '\n';↵
↵
↵
↵
}↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Bonus">↵
The original question was to also print the subsequence but latter it was discarded to maintain level of contest . Can you do so :).↵
</spoiler>↵
↵
G : RRR (Revenge Edition)↵
----------------------↵
Idea:[user:rachitkansal,2024-06-22]↵
↵
<spoiler summary="Hint 1">↵
For n=4, sequence will be 2,3,3,2.↵
↵
For n=5, sequence will be 2,3,4,2,3,4.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Think of parities.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
It’s very clear that we can’t check rooms randomly.↵
↵
Approach:↵
↵
We will always assume that the thief is in an even-numbered room (why not an odd-numbered one?).↵
↵
So, we will start checking from the 2nd room. If we find him, that's good. Otherwise, if he was in an even-numbered room and we checked the 2nd room, it means now he is in an odd-numbered room, and he can’t go to room 1. Similarly, we will go up to the $(n-2)$ th room, each time eliminating one room.↵
↵
When we check the $(n-2)$ th room and don’t find the thief, we can be assured that he was in room $n$ ( Why ? ) at that time and must have moved to room $n-1$. At this point, we will catch him.↵
↵
However, this approach assumes that the thief was initially in an even-numbered room. If our assumption is wrong, we won’t be able to catch the thief in the $(n-1)$ th room.↵
↵
But this process is not a waste. Now we know whether he is in an odd-numbered room or an even-numbered room. (How?)↵
If he is in an even-numbered room, we will repeat the procedure.↵
↵
If he is in an odd-numbered room, we will start from the last odd-numbered room (but why not from room $1$? Even the question demanded the lexicographically smallest element).↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n;↵
cin>>n;↵
if(n==1) {↵
cout<<1<<" "<<60<<endl;↵
cout<<1;↵
}↵
else if(n==2) {↵
cout<<2<<" "<<135<<endl;↵
cout<<1<<" "<<1;↵
}↵
else {↵
cout<<2*(n-2)<<" ";↵
int x=2*(n-2);↵
int y=x-1;↵
cout<<x*60+y*15<<endl;↵
if(n%2!=0) {↵
for (int i = 2; i < n; i++)↵
{↵
cout<<i<<" ";↵
/* code */↵
}↵
for (int i = 2; i < n; i++)↵
{↵
cout<<i<<" ";↵
/* code */↵
}↵
}↵
else {↵
for (int i = 2; i < n; i++)↵
{↵
cout<<i<<" ";↵
/* code */↵
}↵
for (int i = n-1; i >= 2; i--)↵
{↵
cout<<i<<" ";↵
/* code */↵
}↵
}↵
}↵
}↵
↵
↵
↵
↵
/*----------------------------------------------------------------------------------*/↵
↵
↵
↵
↵
int32_t main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
cout << "\n";↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
H: Just Median↵
----------------------↵
Idea:[user:rishabh_king,2024-06-22]↵
↵
<spoiler summary="Hint 1">↵
Notice constraints on elements of array.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
You can use ones and zeros to represent if an index has been deleted or not.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
You have update a point in a range . Which data structure can be used?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Here, Fenwick Tree(BIT) could be used (alternative can be ordered set or segment trees). Here, constraint on elements of $a$ is $1<=element<=n$ where max value of can be $2\cdot10^5$ . So, we can use an array of n+1 length to store frequency of each element but there is a catch we have to work in a range so make this frequency array a BIT . Now, for index use an array of n+1 elements as a BIT , initialize all elements except 0 with value 1 which represent this value is still present in array. ↵
In each query, use binary search to find where the index prefix sum is equal to given number x . Now update BIT of index -1 where you find $x^{th}$ index . Now use update BIT on frequency array to decrease value found at $x^{th}$ index by 1 . Use binary search again to find median element in frequency BIT .↵
</spoiler>↵
↵
↵
<spoiler summary="Author's Code (C++)">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void update(int i,int val,int n,vector<int> &bit){↵
while(i<=n){↵
bit[i] += val;↵
i += (i & (-i));↵
}↵
}↵
↵
int query(int i,int n,vector<int> &bit){↵
int ans=0;↵
while(i>0){↵
ans += bit[i];↵
i -= (i & (-i));↵
}↵
return ans;↵
}↵
↵
int binary_mid(int val,int n,vector<int> &bit){↵
int ans = INT_MAX;↵
int l = 1 , h = n;↵
while(l<=h){↵
int mid = l + (h - l)/2;↵
if(query(mid,n,bit)>=val){↵
ans = min(ans,mid);↵
h = mid - 1;↵
}↵
else {↵
l = mid +1;↵
}↵
}↵
return ans;↵
}↵
↵
int main(){↵
ios::sync_with_stdio(false); cin.tie(0);↵
↵
int test;cin >> test;↵
while(test--){↵
int n,q; cin>> n >> q;↵
vector<int> v(n+1,0),bit(n+1,0),freq(n+2,0);↵
for(int i=1;i<=n;i++){↵
cin >> v[i];↵
update(i,1,n,bit);↵
update(v[i],1,n,freq);↵
}↵
int size = n;↵
while(q--){↵
int x; cin >> x;↵
int ans = binary_mid(x,n,bit);↵
update(v[ans],-1,n,freq);↵
update(ans,-1,n,bit);↵
size--;↵
int pri = binary_mid((size+1)/2,n,freq);↵
cout << pri << " ";↵
}↵
cout << endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
