If you are unable to view the problems, then click here once to get access to the contest and then access the problems.
A. Har Ghar Tiranga
Problem Author: AdC_AB2
In the year (say $$$y$$$) we celebrate $$$(y-1946)^{th}$$$ independence day
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout << n-1946 << endl;
}
}
B. Mafia in IITM
Problem Author: anmol73
Anmol starts at the origin $$$(0,0)$$$ initially. Let his position after $$$k$$$ $$$(k < n)$$$ moves be $$$(x,y)$$$ and his final position be $$$(X,Y)$$$ . Since his distance from origin always increases, exactly one of $$$|x|$$$ or $$$|y|$$$ increases by $$$1$$$ unit after every move. Initially his distance from $$$(0,0) = 0$$$. Since, his distance increases by exactly $$$1$$$ unit after every move, after $$$n$$$ moves, his distance from $$$(0,0) = n$$$, i.e. his coordinates of his final position follows the relation $$$|X| + |Y| = n$$$. It can be seen that this is a square centred at the origin. The number of points in such a square $$$= 4 \cdot n$$$. ($$$n-1$$$ in every quadrant and $$$4$$$ on the coordinate axes).
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout << 4*n << endl;
}
}
C. Seating Arrangement
Problem Author: Mantra7
The seats that can be occupied by the teams are seat 1, (1+2), (1+2+3) and so on. We can use a loop and check if the seat is available, updating the seat accordingly inside the loop, and incrementing the answer by one if the current seat number is less than or equal to n, otherwise, break out of the loop.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int capacity=0, i=0;
while(capacity+(i+1) <= n)
{
i++;
capacity += i;
}
cout << i << endl;
}
}
D. Ma-Shau's conjecture
Problem Author: Shaun0510
The question states that we have a function which generates the newer terms of the sequence.
Now if n is odd the next term in sequence is 3*n+3. Now note that this new term is for sure a multiple of 3.
If n is even we see that next term is n/2. This can only reduce a number of the form 2k to k.
So if k has any prime number other than 2 as it's factor then the new term in the sequence gets a multiple of 3 which will never be destroyed.
By destroyed I mean that the function n to n/2 destroys powers of 2. But if power of 3 is present or in general any other prime then it doesn't vanish out here.
So for powers of 2 this is a terminating sequence. For others it non terminating.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
while(n%2==0)
n/=2;
if(n == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
E. Long Time No C
Problem Author: ShruthiK
If string is palindrome, we know answer is $$$1$$$.
If string is not palindrome, then you can notice that string will consist characters $$$a$$$ and $$$b$$$ both.
We will choose a subsequence such that all $$$a$$$ are present in it. This subsequence is a palindrome.
What will be left after removal of all $$$a$$$ will be all $$$b$$$. In next move, we choose whole string. So we can do it in $$$2$$$ moves.
#include <bits/stdc++.h>
using namespace std;
bool ispal(string s)
{
for(int i=0; i<s.size()/2; i++)
{
if(s[i]!=s[s.size()-1-i])
return false;
}
return true;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
if(ispal(s))
cout << "1" << endl; //remove the whole string in a single move
else
cout << "2" << endl; //remove the subsequence with all a's first, then remove the subsequence with all b's
}
}
F. Mysterious Power
Problem Author: anmol73
Here the main observation is that if Abhinav needs $$$k$$$ coins, where $$$k$$$ is even, he needs only $$$k/2$$$ coins, and by using his mysterious power, he can get another $$$k/2$$$ coins. Similarly, if $$$k$$$ is odd, Abhinav needs $$$\frac{p-1}{2}$$$ coins which, by using his mysterious power, becomes $$$p-1$$$ coins, then Abhinav can take $$$1$$$ coin as a loan from the bank. This way, Abhinav can achieve the minimum number of coins he needs to take as a loan from the bank.
To achieve this, we will go in the reverse direction, i.e. at each step:
- We will check if $$$k$$$ is odd, then we will add $$$1$$$ in our answer; else, we won't add anything to the answer.
- We will divide current $$$k$$$ by $$$2$$$.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n, ans=0;
cin>>n;
int n1=n;
while(n) //count number of set bits in n
{
ans += n%2;
n /= 2;
}
cout << ans << endl;
}
}
G. Chair Trouble
Problem Author: sapta0506
The idea in this problem is to keep only one red chair from a contiguous subsegment of the arrangement containing $$$\geq$$$ 1 red chair, while the blue chairs will always be present in the final arrangement. Note that the chairs are arranged in circular order, so if $$$s[n-1]$$$ and $$$s[0]$$$ both are $$$R$$$, then they'll form such a contiguous subsegment.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
stack<char> st;
string s;
cin>>s;
st.push(s[0]);
for(int i=1;i<n;i++)
{
if(s[i]=='R')
{
if(st.top()!='R') st.push(s[i]);
}
else st.push(s[i]);
}
if(s[0]=='R'&&st.top()=='R'&&st.size()>1)cout<<st.size()-1<<endl;
else cout<<st.size()<<endl;
}
}
H. Guavas
Problem Author: s.tharun_dyanish
Assume the initial line is a queue with people indexed from $$$1$$$ to $$$N$$$. If a person gets a $$$good$$$ guava then remove him from the queue, if he gets a $$$bad$$$ one remove him from the front of the queue and put him at the back. We maintain an array for the time at which each index leaves the queue (he gets a $$$good$$$ guava), which is essentially the index of the guava he gets in the given string of $$$good$$$ ($$$G$$$) and $$$bad$$$ ($$$B$$$) guavas. Essentially we simulate the process of the queue itself starting from the first guava and coming out if the guavas get over or if the queue becomes empty (all the people are served).
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int m,n;
cin>>m>>n;
string guavas;
cin>>guavas;
int query_count;
cin>>query_count;
int arr[query_count];
for(int i=0; i<query_count; i++)
cin>>arr[i];
queue<int> q;
for(int i=0; i<n; i++)
{
q.push(i);
}
vector<int> b(n,-1);
for(int i=0;i<=m-1;i++)
{
if(q.empty())
{
break;
}
if(guavas[i]=='G')
{
b[q.front()]=i+1;
q.pop();
}
else
{
q.push(q.front());
q.pop();
}
}
for(int i=0;i<=query_count-1;i++)
{
cout<<b[arr[i]-1]<<endl;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
solve();
return 0;
}
I. Sum It Thrice!
Problem Author: code.bee
It is obvious that $$$k$$$ must be $$$\leq n$$$, since sums of digits (i.e. $$$k_1, k_2, k_3$$$) must be non-negative. So, $$$k\leq 10^9$$$. Now, \begin{itemize} \item $$$max(k_1) = 9 \cdot 9 = 81$$$, for $$$k=999999999$$$ \item $$$max(k_2) = 7+9 = 16$$$, when $$$k_1 = 79$$$ \item $$$max(k_3) = 9$$$, when $$$k_2 = 9$$$ \end{itemize} Therefore, $$$max(k_1+k_2+k_3)=106$$$. This means it's enough to search just in the 106-spanning left neighbourhood of the number $$$n$$$, viz. $$$[max(0, n-106), n]$$$ (max of zero and $$$n-106$$$ to be taken, since $$$n$$$ may be smaller than 106, and we don't want out of bound solutions).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define sz(a) (ll)a.size()
const ll mod=1000000007;
const ll N=200005;
ll func(ll x)
{
ll val=0;
while(x)
{
val+=x%10;
x/=10;
}
return val;
}
void solv()
{
ll n;
cin>>n;
vector<ll> ans_vec;
for(ll i=max(0ll,n-100); i<=n; i++)
{
ll f = func(i);
ll ff = func(f);
ll fff = func(ff);
if(i+f+ff+fff == n)
ans_vec.push_back(i);
}
cout << sz(ans_vec) << endl;
if(sz(ans_vec))
{
for(ll i=0; i<sz(ans_vec); i++)
cout << ans_vec[i] << " ";
cout << endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll tc=1;
cin>>tc;
for(ll cc=1;cc<=tc;cc++)
{
solv();
}
return 0;
}
J. Guess the Age
Problem Author: code.bee
Suppose the number $$$A$$$ is in base $$$k$$$. So, in decimal base, it will have a value of $$$(A){10}=\sum{i=1}^{n} a_{n-i} \cdot k^{i-1}$$$. Now, according to the question's requirement:
$$$(k-1)$$$ divides $$$\sum_{i=1}^{n} a_{n-i} \cdot k^{i-1}$$$
$$$\Rightarrow$$$ $$$m$$$ divides $$$\sum_{i=1}^{n} a_{n-i} \cdot(1+m)^{i-1}$$$, where $$$m=(k-1)$$$
$$$\Rightarrow m$$$ divides $$$\sum_{i=1}^n a_{n-i}$$$
$$$\Rightarrow m$$$ divides $$$\sum_{i=1}^n a_{i}$$$, i.e. the sum of the digits of $$$A$$$
Also, such $$$k$$$ must be $$$>max{\forall a_i}$$$, else the digits won't be defined. So, we just have to store all the divisors (i.e. all such $$$m$$$'s) of $$$S = \sum_{i=1}^n a_{i}$$$ which are $$$\geq max{\forall a_i}$$$. This can be done in $$$O(\sqrt{S})$$$ time-complexity. Even in the worst case, it will undergo at most $$$\sim 10^5$$$ iterations, taking no more $$$1$$$ seconds to execute.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void solve()
{
int n;
cin >> n;
int a[n];
int64_t sum = 0;
int m = INT_MIN;
for(int i = 0; i<n; i++)
{
cin >> a[i];
sum += a[i];
m = max(m,a[i]);
}
set<int> s;
int count = 0;
for(int i = 1; i*i<=sum; i++)
{
if(sum % i == 0)
{
if(i == sum/i)
{
if(i >= m)
s.insert(i+1);
}
else
{
if(i >= m)
s.insert(i+1);
if(sum/i >= m)
s.insert(sum/i+1);
}
}
}
cout << s.size() << "\n";
for(auto &val : s) cout << val << " ";
cout << "\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--)
{
solve();
}
}
K. Preferential Queue
Problem Author: Jigly_Puff
Find the maximum possible value of index 'i' (i<x) according to the given condition and subtract this index from the rest to get the new indices after it's rotation
Obviously if there is no one in front of Jigyasa with height greater than or equal to $$$k$$$ in the queue then the answer must be 0.
Let us consider the more interesting case when there exists atleast one $$$i < x$$$ such that $$$h_i \geq k$$$. Let at any time the state of the queue is such that the most recent removal operation was done on the person who's index in the original queue was $$$pos$$$ (Consider zero indexing). Hence, the $$$i^{th}$$$ person in the original queue has an effective position of $$$i - pos$$$ in the new queue (Assuming $$$i > pos$$$ and 0-based indexing). Now the condition required to be valid to apply a Removal operation on index $$$i$$$ would be $$$x - i \geq i - pos$$$.
We could solve the following problem by maintaining two pointers, one pointing to the last index that required a removal operation and one pointing to a possible future candidate for the removal operation. Let us call these variables $$$pos$$$ and $$$curr$$$ respectively. We can initialise $$$pos$$$ and $$$curr$$$ each to -1 and iterate over all i from 0 to $$$x$$$, updating $$$curr = i$$$ everytime we find an $$$i$$$ that satisfies the given conditions (i.e. $$$h_i >= k$$$ and $$$x - i >= i - pos$$$). and updating $$$pos = curr$$$, $$$curr = i$$$ and incrementing our total counter everytime we find that $$$h_i >= k$$$ but $$$x - i < i - pos$$$.
We can detect whether an answer exists or not by running an initial for loop which checks the condition $$$x - i >= i - pos$$$ for all $$$i$$$ from 0 to $$$x - 1$$$ such that $$$h_i >= k$$$. If this isn't satisfied then no such sequence of operations exist.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define sz(a) (ll)a.size()
const ll mod=1000000007;
const ll N=200005;
ll solv()
{
ll n,k,x;
cin>>n>>k>>x;
vector<ll> a(n+1);
vector<ll> b;
for(ll i=1; i<=n; i++)
{
cin>>a[i];
if(a[i]>=k)
b.push_back(i);
}
ll lftmost_k = b[0];
ll lft_el = 1;
ll mov=0;
while(1)
{
lftmost_k = *lower_bound(b.begin(),b.end(),lft_el);
if(lftmost_k == x)
return mov;
/* y - lft <= x - y - 1
2*y <= (x + lft - 1)
y <= (x + lft -1)/2 */
ll max_allowed = (lft_el+x-1)/2;
auto itr = upper_bound(b.begin(),b.end(),max_allowed);
if(itr == b.begin())
return -1;
itr--;
if(*itr < lft_el)
return -1;
mov++;
lft_el = *itr + 1;
}
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll tc=1;
cin>>tc;
for(ll cc=1;cc<=tc;cc++)
{
cout << solv() << endl;
}
return 0;
}
L. Yet another GCD problem
Problem Author: Mantra7
Let's consider the array $$$A$$$ to have elements $$$a_1, a_2, \ldots, a_n$$$. Let's call the GCD of all elements in the array to be $$$gcd$$$.
The answer will be 0 if and only if all elements in the array are equal.
If the answer is 1 for a given array, then $$$gcd$$$ must be present in that array. If $$$gcd$$$ is not present in the array, then no matter what proper subsequence we perform a move on, there will be an element that is not equal to $$$gcd$$$.
Let's say $$$gcd$$$ is present in the array. If we can make all elements of the array to be equal to $$$gcd$$$ in 1 move, then there must exist an $$$n-1$$$ length subsequence whose GCD = $$$gcd$$$ and the array element not present in that subsequence must be $$$gcd$$$ itself.
Let's explore 2 cases:
Array has $$$gcd$$$ present in it and more than 1 move is required: In this case, we can make all elements of the array equal in 2 moves. For move $$$#1$$$, choose an $$$(n-1)$$$ length subsequence with $$$gcd$$$ present in this subsequence. For move $$$#2$$$, choose a subsequence containing both $$$gcd$$$ and the element left out in the first move's subsequence. Can you see why this will work? :)
Array does not have $$$gcd$$$ present in it: We saw that to reduce the array to all equal elements in a single move, we need to have $$$1$$$ occurence of $$$gcd$$$ in the array, and the GCD of the remaining elements must be equal to $$$gcd$$$. Hence, if the array is equalizable in 2 moves, we need to produce an occurence of $$$gcd$$$ in 1 move. If there exists an $$$(n-1)$$$ length subsequence in the array whose GCD is $$$gcd$$$, then we can perform move $$$#1$$$ on this subsequence. Now, we'll have all but one elements of the array to be $$$gcd$$$ and one element to be something else. Can you find out what we have to do here? :)
To calculate GCD of all $$$(n-1)$$$ size subsequences, we can maintain 2 arrays — prefixGCD & suffixGCD. prefixGCD[i] stores the GCD of the first $$$i$$$ elements of the array. suffixGCD[i] stores $$$GCD(a_i, a_{i+1}, \ldots, a_n)$$$
No! For any array, we can make all elements equal in $$$3$$$ moves.
- Move 1: Choose the subsequence $$$[a_1, a_2, \ldots, a_{n-1}]$$$ and make all these elements to $$$GCD(a_1, a_2, \ldots, a_{n-1})$$$.
- Move 2: Choose the subarray $$$[a_{n-1}, a_{n}]$$$ and make these to elements to $$$GCD(GCD(a_1, a_2, \ldots, a_{n-1}), a_n) = GCD(a_!, a_2, \ldots, a_n) = gcd$$$.
- Move 3: Choose the subarray $$$[a_1, a_2, \ldots, a_{n-1}]$$$ and make these to elements to $$$gcd$$$.
If $$$n = 2$$$ and $$$a_1 \neq a_2$$$, then the array elements can never be made equal.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define sz(a) (ll)a.size()
const ll mod=1000000007;
const ll N=200005;
ll solv()
{
ll n;
cin>>n;
vector<ll> a(n);
for(ll i=0; i<n; i++)
{
cin>>a[i];
}
//Corner case
if(n==1)
return 0;
if(n==2)
{
if(a[0]==a[1])
return 0;
else
return -1;
}
//Evaluating GCD of array & freq[GCD]
ll gcd = a[0];
for(ll i=1; i<n; i++)
{
gcd = __gcd(gcd, a[i]);
}
ll gcd_count = 0;
for(ll i=0; i<n; i++)
{
if(a[i] == gcd)
gcd_count++;
}
if(gcd_count == n) // All elements are equal already
{
return 0;
}
else if(gcd_count > 1) // > 1 occurence of gcd in array
{
return 1;
}
else if(gcd_count == 1) // 1 occurence; check if GCD of remaining elements = gcd
{
ll rest_gcd;
if(a[0] == gcd)
rest_gcd = a[1];
else
rest_gcd = a[0];
for(ll i=0; i<n; i++)
{
if(a[i] != gcd)
{
rest_gcd = __gcd(rest_gcd, a[i]);
}
}
if(rest_gcd == gcd)
return 1;
else
return 2;
}
//Check if we can find n-1 size subsequence such that their GCD = array gcd
vector<ll> pref_gcd(n,a[0]);
for(ll i=1; i<n; i++)
pref_gcd[i] = __gcd(pref_gcd[i-1],a[i]);
vector<ll> suff_gcd(n,a[n-1]);
for(ll i=n-2; i>=0; i--)
suff_gcd[i] = __gcd(suff_gcd[i+1],a[i]);
bool flag = false; //flag = true if we can find n-1 elements in the array such that GCD of those elements = gcd
if(pref_gcd[n-2]==gcd || suff_gcd[1]==gcd)
flag = true;
for(ll i=1; i<n-1; i++)
{
if(__gcd(pref_gcd[i-1],suff_gcd[i+1])==gcd)
{
flag = true;
break;
}
}
if(flag)
return 2;
else
return 3;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll tc=1;
cin>>tc;
for(ll cc=1;cc<=tc;cc++)
{
cout << solv() << endl;
}
return 0;
}
M. Optimal Journey
Problem Author: AdC_AB2
We can process the tower sequence from left to right. When we are at the $$$i^{th}$$$ tower, we'll have the optimal sequence of moves from towers $$$1$$$ to $$$i-1$$$.
Let's call the move $$$[$$$tower $$$i-1$$$ to tower $$$i]$$$ to be $$$m_1$$$. Now, we check if we can merge the latest move (move on top of stack) with $$$m_1$$$. If that works, we form the merged move $$$m_2$$$ and pop the topmost move from the stack. We repeat this process until we can't do a merge.
Once we can't do a merge, we'll have the optimal sequence of moves from towers $$$1$$$ to $$$i$$$. We can now move on to process tower $$$i+1$$$.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define sz(a) (ll)a.size()
const ll mod=1000000007;
const ll N=200005;
bool collision(vector<ll> &a, ll i, ll j, ll k)
{
if((a[k]-a[i])*(j-i) >= (a[j]-a[i])*(k-i))
return false;
return true;
}
double slope(vector<ll> &a, ll i, ll j)
{
return fabs((double)(a[j]-a[i])/(j-i));
}
void solv()
{
ll n;
cin>>n;
vector<ll> a(n);
for(ll i=0; i<n; i++)
{
cin>>a[i];
}
vector<ll> s; //serves as a stack here
s.push_back(0);
s.push_back(1);
for(ll i=2; i<n; i++)
{
while(s.size()>=2)
{
if(!collision(a,s[s.size()-2],s.back(),i))
{
s.pop_back();
}
else
break;
}
s.push_back(i);
}
double ans = slope(a,s[0],s[1]);
for(ll i=2; i<s.size(); i++)
ans = max(ans, slope(a, s[i], s[i-1]));
cout << fixed << setprecision(7) << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll tc=1;
cin>>tc;
for(ll cc=1;cc<=tc;cc++)
{
solv();
}
return 0;
}
N. Crash Bandicoot
Problem Author: ShruthiK
What happens when you start with column with height $$$x$$$?
If frequency of height $$$x$$$ is $$$freq[x]$$$ then how many moves can be done?
If we start on a column with height $$$x$$$ then all other columns' height will decrease by 1. So for us to do next "Jump" move, there should be another column of height $$$x$$$ so that it can become $$$x-1$$$ after doing "Attack" move.
Let $$$freq[x]$$$ store initial frequency of columns with height $$$x$$$. So following happens if you start on column with height $$$x$$$,
- "Attack" — Now there are $$$freq[x]-1$$$ columns left with height $$$x-1$$$
- "Jump" — You can jump to any 1 of them
- "Attack" — Now there are $$$freq[x]-2$$$ columns left with height $$$x-2$$$
- ...
Crash can initially jump to any column, so we will calculate total Wumpa fruits collected for each initial column and maximum of those would be the answer.
Crash will be able to make $$$x+1$$$ total "Attack" moves and make $$$x$$$ "Jump" moves.
Example: Attack, Jump($$$x$$$ to $$$x-1$$$), Attack, Jump($$$x-1$$$ to $$$x-2$$$), ..., Jump($$$1$$$ to $$$0$$$), Attack.
$$$[2, 2, 2] -> [2, 1, 1] -> [1, 1, 0] -> [0, 0, 0]$$$
All elements less than $$$x+1$$$ will become $$$0$$$ and others will decrease by $$$x+1$$$. We can maintain count of all elements less than or equal to $$$x$$$ in an array $$$lessCnt[x]$$$ and similarly sum in an array $$$lessSum[x]$$$. So final number of Wumpa fruits collected becomes,
$$$Total fruits = lessSum[x+1] + (n - lessCnt[x+1]) \cdot (x+1)$$$
Crash will be able to make $$$freq[x]$$$ "Attack" moves and $$$freq[x]-1$$$ "Jump" moves.
Example: Attack, Jump($$$x$$$ to $$$x-1$$$), Attack, Jump($$$x-1$$$ to $$$x-2$$$), ..., Jump($$$x-freq[x]+2$$$ to $$$x-freq[x]+1$$$), Attack.
$$$[4, 4, 4] -> [4, 3, 3] -> [3, 3, 2] -> [2, 2, 2]$$$
All elements less than $$$freq[x]$$$ will become $$$0$$$ and all others elements except $$$x$$$ will decrease by $$$freq[x]$$$. But $$$x$$$ will decrease by $$$freq[x] - 1$$$ as you can see by above sequence of "Attack" and "Jump" moves. So final number of Wumpa fruits collected becomes,
$$$Total fruits = lessSum[freq[x]] + (n - lessCnt[freq[x]] - freq[x]) \cdot freq[x] + (freq[x]-1)\cdot freq[x]$$$
= $$$lessSum[freq[x]] + (n - lessCnt[freq[x]]) \cdot freq[x] -freq[x]$$$
This case will be similar to $$$case 1$$$ if there is some element $$$y<x$$$ in the initial array as it will become $$$0$$$ and crash will be able to do another "Attack" move after jumping there which makes total $$$x+1$$$ "Attack" moves.
$$$[2, 3, 3, 3] -> [1, 3, 2, 2] -> [0, 2, 2, 1] -> [0, 1, 1, 1] -> [0, 0, 0, 0]$$$
But if $$$x$$$ is the minimum element then it will be similar to $$$case 2$$$ as he won't be able to do one extra "Attack" and total $$$x=freq[x]$$$ "Attack" move can be done.
LessCnt and LessSum can be counted in one iteration of the frequency array similar to prefix sum. And we can get number of fruits collected for each initial column in O(1). So total time complexity is O(10000) per test case.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define sz(a) (int)a.size()
const ll mod=1000000007;
const ll N=200005;
void solv()
{
ll n;
cin>>n;
vector<ll> h(n), f(10001), cum_cnt(10001), cum_sum(10001);
ll mini=mod;
for(int i=0; i<n; i++)
{
cin>>h[i];
f[h[i]]++;
mini = min(mini, h[i]);
}
if(n==1) // Corner case
{
cout << 0 << endl;
return;
}
for(int i=1;i<=10000;i++)
{
cum_sum[i]=cum_sum[i-1]+f[i]*i; //cum_sum[i] = sum of all elements <= i
cum_cnt[i]=cum_cnt[i-1]+f[i]; //cum_cnt[i] = number of elements <= i
}
ll ans=0;
for(int i=0;i<=10000;i++)
{
if(f[i]==0) continue;
ll temp=0, mov=0; //mov = number of moves we can do if we start on a crate of height i
if((i > f[i]) || (i==f[i] && i==mini))
{
mov = f[i];
temp += cum_sum[mov];
temp += (n-cum_cnt[mov])*mov;
temp -= f[i];
}
else
{
mov = i+1;
temp += cum_sum[mov];
temp += (n-cum_cnt[mov])*mov;
}
ans = max(ans, temp);
}
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll tc=1;
cin>>tc;
for(ll cc=1;cc<=tc;cc++)
{
solv();
}
return 0;
}
O. Quantitative Trading
Problem Author: AdC_AB2
First crucial observation we can make is that since we are allowed to have negative money and negative position, we can always buy or sell a share on all days.
For any particular query let's say day i and price p, we can buy all the shares sold at a price lower than p and sell all the shares sold at a price higher than p till day i.
Let us say we are able to calculate the following quantities for every possible query
- $$$x_1$$$ — number of shares sold at a price lower than p till day i
- $$$x_2$$$ — sum of prices of all shares sold a price lower than p till day i
- $$$x_3$$$ — total sum of prices of all shares sold till day i
Thus we know,
- total number of shares sold till day i are i,
- $$$i-x_1$$$ shares would be sold at a price higher than or equal to p till day i (considering the price equal to p case here)
- $$$x_3-x_2$$$ would be the sum of the prices of all the shares sold till day i
So total profit that we would have is, (till day i)
= (Sum of prices of shares sold — Price at we will buy shares sold from IT dept * Number of Shares sold) + (Price at we will sell shares bought from IT dept * Number of Shares bought — Sum of prices of shares bought)
= $$$(x_3-x_2-p*(i-x_1)) + (p*x_1-x_2)$$$
Now all that is left to be done is calculating the values $$$x_1$$$, $$$x_2$$$ and $$$x_3$$$ for each query.
We can update the process day by day and answer the queries for that particular date. For this we can sort all the queries and answer the queries after every day is over.
To find $$$x_3$$$ is simple, we store a variable and increment the value of the variable with the value of the share that day
For computing $$$x_1$$$, we can use an ordered multiset. Every day we will insert the value of the current share in the multiset. Then for all the queries that particular day we will figure out the number of items in the list smaller than the given value.
Since we do not have a simple ordered multiset implementation, we instead use an ordered set of pairs, with the second value in the pair representation which occurrence of the current value we are at, thus all entries in the ordered pair will always be unique.
For computing $$$x_2$$$, we can a segment tree. Let's say we had smaller constraints such that $$$p_i$$$ was small (~2e5). Then we could have considered a segment tree over the prices of the stocks. And once we get a stock with price $$$p_i$$$ on day i, we increment the $$$p_i^{th}$$$ index in the segment tree by $$$p_i$$$. Then while answering a query we can take the sum of the all the indices from 0 to $$$p_i$$$ in the segment tree and this will give us the sum of all the elements smaller than p.
But unfortunately, $$$p_i$$$ can go up to 1e9. Thus we cannot directly use such an array. But instead we can use a standard technique of compressing co-ordinates. Since we can have at max 2e5 distinct values for the stock prices, since we only have at max 2e5 days, we can map each of the distinct price of the stocks to a smaller value (say by sorting the stock vector, applying the std::unique function and mapping each of these distinct values to its index instead). Thus for each query, first we can check the stock price just smaller than price p using the ordered set that we already made earlier. Now this price will be mapped to some value $$$m_{p_i}$$$ as described earlier. Then calculating the sum from index i to index $$$m_{p_i}$$$ will give us $$$x_3$$$.
Thus we can calculate the total profit.
#include<bits/stdc++.h>
using namespace std;
using namespace chrono;
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define precision(a) {cout << setprecision(a) << fixed;}
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<ld> vld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef set<int> si;
typedef set<ll> sll;
typedef set<pll> spll;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<ll,ll>> vpll;
typedef tuple<ll,ll,ll> tll;
typedef vector<tll> vtll;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<pll,null_type,less<pll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ll t[800000]={0};
void build(ll a[], ll v, ll tl, ll tr) {
if (tl == tr) {
t[v] = a[tl];
} else {
ll tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = t[v*2] + t[v*2+1];
}
}
ll sum(ll v, ll tl, ll tr, ll l, ll r) {
if (l > r)
return 0;
if (l == tl && r == tr) {
return t[v];
}
ll tm = (tl + tr) / 2;
return sum(v*2, tl, tm, l, min(r, tm))
+ sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}
void update(ll v, ll tl, ll tr, ll pos, ll new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
ll tm = (tl + tr) / 2;
if (pos <= tm)
update(v*2, tl, tm, pos, new_val);
else
update(v*2+1, tm+1, tr, pos, new_val);
t[v] = t[v*2] + t[v*2+1];
}
}
void solve()
{
ll n;
cin>>n;
ll a[n];
sll s;
for(ll i=0;i<n;i++)
{
cin>>a[i];
s.insert(a[i]);
}
s.insert(0);
mll ptoi, itop;
ll c=0;
for(auto i:s)
{
ptoi[i]=c;
itop[c]=i;
c++;
}
ll arr[c]={0};
build(arr,1,0,c-1);
ll q;
cin>>q;
pair<pll,ll> pq[q];
for(ll i=0;i<q;i++)
{
cin>>pq[i].ff.ff>>pq[i].ff.ss;
pq[i].ff.ff--;
pq[i].ss=i;
}
sort(pq,pq+q);
ll ans[q]={0};
ordered_set prices;
mll cnt;
ll sumsofar=0;
ll cntsofar=0;
ll l=0;
for(ll i=0;i<q;i++)
{
for(int j=l;j<=pq[i].ff.ff;j++)
{
prices.insert({a[j],cnt[a[j]]});
cnt[a[j]]++;
sumsofar+=a[j];
cntsofar++;
update(1,0,c-1,ptoi[a[j]],cnt[a[j]]*a[j]);
}
l=pq[i].ff.ff+1;
ll price = pq[i].ff.ss;
auto it = s.upper_bound(price);
it--;
ll ind = ptoi[*it];
ll sumless = sum(1,0,c-1,0,ind);
ll summore = sumsofar-sumless;
ll cntless = prices.order_of_key({*it,1e9});
ll cntmore = cntsofar - cntless;
ans[pq[i].ss] = -sumless + cntless*price + summore - cntmore*price;
}
for(ll i=0;i<q;i++)
{
cout<<ans[i]<<"\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}