We use two pointers to solve this problem.
Set $$$l=1$$$ and $$$r=n$$$ initially.
\begin{itemize} \item If $$$a_l=a_r$$$, \t{l++,r-}\t{-;}
\item if $$$a_l<a_r$$$,split $$$a_r$$$ into $$$a_r-a_l$$$ and $$$a_l$$$, \t{r-}\t{-;}
\item if $$$a_l>a_r$$$,split $$$a_l$$$ into $$$a_r$$$ and $$$a_l-a_r$$$, \t{l+}\t{+;}
\end{itemize}
When $$$l \geq r$$$,the process ends.
Let $$$M$$$ be the initial mass of the bus with all passengers: $$$M = w + \sum_{i = 1}^{n}{m_i}$$$. Let $$$F$$$ be the total force of the pushers, initially, $$$F=0$$$.
Imagine getting out the $$$i$$$-th passenger out of the bus, then $$$M$$$ is decreased by $$$m_i$$$, while $$$F$$$ is increased by $$$f_i$$$. Hence, $$$M - F$$$ is decreased by $$$m_i + f_i$$$. Clearly, we want to make $$$F \ge M$$$, i.e. $$$M - F \le 0$$$.
Therefore, that lead us to the greedy approach: let us sort passengers by $$$m_i + f_i$$$ in descending order and start getting the passengers out of the bus, one by one, according to their order, until the bus is able to be moved, i.e. $$$F \ge M$$$.
\bf{Hint 1} : What's the minimum frequency of the most frequent character of a decimal string?
\bf{Hint 2} : What's the minimum size of $$$LCS$$$ between two strings of length $$$K$$$ required to make a string of size $$$19k/10$$$?
We can observe one thing that as there are only \t{10} possible different characters in a string of length $$$K$$$ then it's obvious that the frequency of the most frequent character in it is $$$\ge K/10$$$ , let's assume that character is \t{0} in the first string that we observe.All we need to solve this problem is finding a $$$LCS$$$ of size atleast $$$K/10$$$ between two strings.So we already have a string where there are $$$K/10$$$ \t{0}s.Now let's observe any other \t{9} strings where the most frequent characters suppose are : \t{1} \t{2} \dots \t{9} . Notice that we are assuming that there are no same characters among the first $$$10$$$ observed strings' most frequent characters co-incidentally. If there are duplicates we already have our answer. Assuming there are no duplicates in the first \t{10} observed strings, it is guaranteed the most frequent character appearing in the $$$11th$$$ string must have appeared before as there are \t{10} possible characters only.Then we have our answer , we will construct our answer by merging two strings with same most frequent character.It's basically the \bf{pigeonhole} principle like if we have \t{10} types of chocolates in \t{11} boxes , there has to be duplicates.So we prove that \t{11} strings are enough to generate an answer , so we always have an answer as we have \t{20} decimal strings
Time complexity of optimal implementation of this problem : $$$O(20 * K)$$$ , although there are $$$O(20^2 * K)$$$ solutions which may also pass which takes advantage of the fact that there has to be a pair of strings which have \bf{LCS} of length >= $$$K/10$$$
\begin{lstlisting}
include<bits/stdc++.h>
using namespace std; typedef int ll;
define pb push_back
define pf push_front
int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int k; cin>>k; vector v; string s; vector adj[10];//to store indices of string where a particular character is most frequent for(int i=1;i<=20;i++){ cin>>s; v.push_back(s); } int l=-1; int r=-1; char aa='Z'; for(int i=0;i<=19;i++){ ll m[10]={};//character frequency array for(auto u : v[i]){ int kk=u-'0'; m[kk]++; } ll best=0; ll yy=-1; for(char xx='0';xx<='9';xx++){ ll xx1=xx-'0'; if(m[xx1]>best){ best=m[xx1]; ll pal=xx-'0'; yy=pal; } } adj[yy].push_back(i); if(adj[yy].size()==2){ aa='0'; aa+=yy; l=adj[yy][0]; r=adj[yy][1]; break; } } deque v2,v3;//used for storing indices of LCS of two optimal strings string ans=""; //string merging process starts ll kk=-1; for(auto u : v[l]){ kk++; if(u==aa) v2.pb(kk); } v2.pf(-1); kk=-1; for(auto u : v[r]){ kk++; if(u==aa) v3.pb(kk);
}
v3.pf(-1);
for(ll aa1=1;aa1<=k/10;aa1++){
for(ll bb=v2[aa1-1]+1;bb<=v2[aa1]-1;bb++){
ans+=v[l][bb];
}
for(ll bb=v3[aa1-1]+1;bb<=v3[aa1]-1;bb++){
ans+=v[r][bb];
}
ans+=aa;
}
for(ll aa1=v2[k/10]+1;aa1<=(k)-1;aa1++) ans+=v[l][aa1];
for(ll aa1=v3[k/10]+1;aa1<=(k)-1;aa1++) ans+=v[r][aa1];
cout<<ans<<endl;} \end{lstlisting}
104802D - Rudraksh's Sleepiness
First, let's find the minimum number of the stops Rudraksh will make. There are 4 different cases. Let's say the school coordinates are $$$(x, y)$$$.
$$$1)$$$ The manhattan distance of $$$(x,y)$$$ from $$$(0,0)$$$ (means $$$x+y$$$) is itself a prime number. So we can directly jump to the school, making only one-stop.
$$$2)$$$ If the $$$x+y-2$$$ is a prime number so we should first travel distance 2 i.e any of {(1,1),(0,2),(2,0)} as per the school coordinates, and then the next stop will be the school coordinate.
$$$3)$$$ If the $$$x+y$$$ is even, then as per Goldbach Conjecture, it can be written as the sum of two prime numbers. So the stops can be determined based on that prime numbers.
$$$4)$$$ If the $$$x+y$$$ is odd, then we may move to some coordinate whose Manhattan distance is odd and that is prime (for simplicity we can use 3), too. Now this became a similar problem to type $$$3$$$.
For identifying the exact stops, you can iterate over every prime number.
104802E - Anuj's Longest Subarray
For each index $$$i$$$, $$$a_i$$$ should be the greater than or equal to the $$$k^{th}$$$ maximum element in the subarray. So, to make the subarray longest, $$$a_i$$$ should be as least as possible therefore,it should be $$$x^{th}$$$ maximum $$$(x \leq k)$$$, where $$$x$$$ should be the maximum possible value.
If $$$a_i$$$ is $$$x^{th}$$$ maximum in the subarray $$$a[l...r]$$$, then there are $$$x-1$$$ elements greater than $$$a_i$$$. Suppose there are $$$p$$$ $$$(0 \leq p \leq k-1)$$$ elements from $$$l$$$ to $$$i-1$$$, that are greater than $$$a_i$$$, then there will be $$$(x-1)-p$$$ elements greater than $$$a_i$$$ in $$$i+1$$$ to $$$r$$$ (all elements are distinct) .As $$$k \leq 10$$$, therfore for every index $$$i$$$, we can find the minimum $$$l$$$ and maximum $$$r$$$ for every $$$p$$$, and find the maximum of $$$(r-l+1)$$$, which will be our answer.
For implementing, we can use set or ordered set (policy-based data structure), and can start inserting the index of elements from $$$n$$$ to $$$1$$$, after every insertion, we can iterate $$$k$$$ indices in the set in both directions — previous the current element's index in set and after the current element's index in set.
See code for detailed implementation.
\bf{hint 1} : Maximum possible score of a subsequence is $$$n$$$ as in an array of size $$$n$$$ $$$\rm{mex}$$$ can't be greater than $$$n$$$
\bf{hint 2} : Calculating number of subsequences where $$$score$$$ is $$$i$$$ for each $$$0 \le i \le n$$$ is enough
First let's calculate for each $$$0 \le i \le n$$$ the number of subsequences where score is $$$i$$$.How to calculate that?Well when is mex of a subsequence a positive integer $$$i$$$?How does the subsequence look like?In that subsequence there can be arbitrary integers greater than $$$i$$$ ,no appearance of $$$i$$$ and every integer from \t{0} to $$$i-1$$$ is present in the subsequence each arbitrary number of times.So if $$$f_i$$$ is the value of number of subsequences where $$$mex$$$ is $$$i$$$ , $$$f_i$$$ : $$$ 2^X * (2^{a_0}-1) * (2^{a_1}-1) * (2^{a_2}-1)* \dots * (2^{a_{i-1}}-1)$$$ where $$$X$$$ is count of elements greater than $$$i$$$ and $$$a_j$$$ is count for j in the array.If subsequence count for some $$$i$$$ crosses $$$K$$$ we minimise it to $$$K$$$.In case of \t{0} : $$$f_0$$$ = $$$2^y$$$ where $$$y$$$ is count of elements greater than \t{0}. But we subtract \t{1} from that count as we are considering \bf{non-empty} subsequences only. Now when we pick and arrange $$$K$$$ subsequences it's obvious that we have to pick $$$(k+1)/2$$$ subsequences with \bf{minimum} scores and $$$k/2$$$ subsequences with \bf{maximum} scores. As the range of possible \bf{scores} is very low $$$[0 \dots n]$$$ we just iterate greedily from the beginning of the range to add scores of \bf{odd} indices and after that we iterate from the end greedily to subtract the scores of \bf{even} indices.
Time complexity of optimal implementation of this solution : $$$O(N)$$$
\begin{lstlisting}
include<bits/stdc++.h>
using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll t=1; cin>>t; ll m[100002];//subsequence count array ll m2[100002]={};//frequency array ll fact[100002];//array for storing values of 2^i for(int j=1;j<=t;j++){ ll n,k; cin>>n>>k; ll i,x; vector v; fact[0]=1; m2[0]=0; for(i=1;i<=n;i++){ m2[i]=0; fact[i]=fact[i-1]; fact[i]*=2; fact[i]=min(fact[i],k+1); } ll sum=0; for(i=1;i<=n;i++){ cin>>x; if(x<=n) m2[x]++; } sum=n; ll dal=1; for(ll i=0;i<=n;i++){ m[i]=dal; sum-=m2[i]; m[i]*=fact[sum]; if(i==0) m[i]-=1; m[i]=min(m[i],k); dal*=(fact[m2[i]]-1); dal=min(dal,k+1); } ll ans=0; ll jh=(k+1)/2; // odd ll jk=k/2; // even for(i=0;i<=n;i++){ ll kk=min(m[i],jh); ans+=(i*kk); jh-=kk; m[i]-=kk; } for(i=n;i>=0;i-=1){ ll kk=min(m[i],jk); ans-=(i*kk); jk-=kk; m[i]-=kk; } cout<<ans<<endl; } }
\end{lstlisting}
Let $$$p$$$ be the number of times we move a character to the front of the string, and $$$q$$$~--- the number of times we move a character to the back. Then, $$$p=\lceil{k/2}\rceil$$$, $$$q=\lfloor{k/2}\rfloor$$$.
Clearly, the first $$$p$$$ characters of the answer must be $$$p$$$ minimal characters of $$$s$$$. Moreover, amongst all $$$p$$$-th minimal characters, we should pick characters in the order from the back of the string to the front.
Now, we are left with the remaining string $$$t$$$ of length $$$k - p$$$ and with $$$q$$$ second-type operations to do. We can assume that the tail of the answer~--- the last $$$q$$$ characters are sorted in lexicographically increasing order, as we can move characters to the tail in order from smallest to largest. So, we only need to minimize the middle part~--- characters that we are not moving anywhere, since the tail can be restored in a single way afterwards.
Thus, the greedy approach should work once again:
Let's greedily pick up the answer, trying to put the lexicographically smallest character in each position, as long as we skipping, i.e. moving to the tail, at most $$$q$$$ characters. In order to do that efficiently, we can precalculate the next occurrence of every character from \t{a}' to\t{z}' for every index of $$$t$$$.
For more detail, look at the solution code.
Some solutions depends on some library and I pasted them into the solutions. In that case, main logic is at the lower side of the code.
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t>0){
t--;
long long n;
cin >> n;
deque<long long> dq;
for(long long i=0;i<n;i++){
long long x;
cin >> x;
dq.push_back(x);
}
long long res=0;
while(dq.size()>=2){
long long pre=dq.front();dq.pop_front();
long long bac=dq.back();dq.pop_back();
if(pre==bac){continue;}
if(pre<bac){
res++;
dq.push_back(bac-pre);
}
else{
res++;
dq.push_front(pre-bac);
}
}
cout << res << "\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
using pl=pair<long long,long long>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t>0){
t--;
long long n,m;
cin >> n >> m;
vector<long long> a(n);
for(auto &nx : a){cin >> nx;}
vector<long long> b(n);
for(auto &nx : b){cin >> nx;}
vector<long long> eff;
for(long long i=0;i<n;i++){
m+=a[i];
eff.push_back(a[i]+b[i]);
}
sort(eff.begin(),eff.end());
reverse(eff.begin(),eff.end());
long long res=-1;
for(long long i=0;i<n;i++){
m-=eff[i];
if(m<=0){res=i+1;break;}
}
cout << res << "\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
std::random_device seed_gen;
std::mt19937_64 engine(seed_gen());
int k;
cin >> k;
vector<string> s(20);
vector<vector<int>> bk(20,vector<int>(10,0));
for(int i=0;i<20;i++){
cin >> s[i];
for(int j=0;j<k;j++){
bk[i][s[i][j]-'0']++;
}
}
vector<pair<int,int>> vp;
for(int i=0;i<20;i++){
for(int j=i+1;j<20;j++){
vp.push_back({i,j});
}
}
shuffle(vp.begin(),vp.end(),engine);
vector<int> p={0,1,2,3,4,5,6,7,8,9};
for(auto &nx : vp){
int i=nx.first;
int j=nx.second;
shuffle(p.begin(),p.end(),engine);
for(auto &tg : p){
if(min(bk[i][tg],bk[j][tg])>=(k/10)){
string res;
int p=0,q=0;
while(p<k && q<k){
if(s[i][p]-'0' != tg){
res.push_back(s[i][p]);
p++;
continue;
}
if(s[j][q]-'0' != tg){
res.push_back(s[j][q]);
q++;
continue;
}
res.push_back(s[i][p]);
p++;q++;
}
while(p<k){res.push_back(s[i][p]);p++;}
while(q<k){res.push_back(s[j][q]);q++;}
while(res.size()<(k/10)*19){
res.push_back('0'+(engine()%10));
}
cout << res << "\n";
return 0;
}
}
}
return 0;
}
// factorize
// https://judge.yosupo.jp/problem/factorize
#include<bits/stdc++.h>
using namespace std;
// https://hitonanode.github.io/cplib-cpp/number/binary_gcd.hpp.html
template <typename Int> Int binary_gcd(Int x_, Int y_) {
unsigned long long x = x_ < 0 ? -x_ : x_, y = y_ < 0 ? -y_ : y_;
if (!x or !y) return x + y;
int n = __builtin_ctzll(x), m = __builtin_ctzll(y);
x >>= n, y >>= m;
while (x != y) {
if (x > y) {
x = (x - y) >> __builtin_ctzll(x - y);
} else {
y = (y - x) >> __builtin_ctzll(y - x);
}
}
return x << (n > m ? m : n);
}
struct factorizer{
long long smlrng;
vector<long long> lpf;
vector<long long> plis;
// init
// https://37zigen.com/linear-sieve/
factorizer(long long smlrng_){
smlrng = smlrng_;
lpf.resize(smlrng+1);
fill(lpf.begin(),lpf.end(),0);
plis.clear();
for(long long i=2;i<=smlrng;i++){
if(lpf[i]==0){
lpf[i]=i;
plis.push_back(i);
}
for(auto &p : plis){
if(p*i > smlrng || p>lpf[i]){break;}
lpf[p*i]=p;
}
}
}
vector<long long> tinyplis = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
long long mulmn(long long a,long long b,long long n){
__int128 c128=a;
c128*=b;
return ((long long)(c128%n));
}
long long powmn(long long a,long long b,long long n){
long long res=1;
while(b>0){
if(b&1ll){
res=mulmn(res,a,n);
}
a=mulmn(a,a,n);
b/=2;
}
return res;
}
bool isprime(long long n){
if(n<=1){return false;}
if(n<=smlrng){return (n==lpf[n]);}
for(auto &p : tinyplis){
if(n%p==0){return false;}
}
// from now, n should be odd
// https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
vector<long long> a={2,7,61};
if(n>=(1ll<<32)){
a = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
}
long long s=__builtin_ctzll(n-1);
long long d=((n-1)>>s);
for(auto &ca : a){
if(powmn(ca,d,n)==1){continue;}
bool cp=true;
for(long long r=0;r<s;r++){
if(powmn(ca,(1ll<<r)*d,n)==(n-1)){cp=false;break;}
}
if(cp){return false;}
}
return true;
}
long long ffrho(long long n){
long long m=(1ll<<((64-__builtin_clzll(n))/8));
for(long long c=1;;c++){
auto f = [&](long long v){ return (mulmn(v,v,n)+c)%n; } ;
long long x,y=2,r=1,q=1,g=1,ys;
while(g==1){
x=y;
for(long long i=0;i<r;i++){
y=f(y);
}
long long k=0;
while(k<r && g==1){
ys=y;
for(long long i=0;i<min(m,r-k);i++){
y=f(y);
q=mulmn(q,abs(x-y),n);
}
g=binary_gcd(q,n);
k+=m;
}
r<<=1;
}
if(g==n){
g=1;
while(g==1){
ys=f(ys);
g=binary_gcd(abs(x-ys),n);
}
}
if(g<n){
if(isprime(g)){return g;}
else if(isprime(n/g)){return (n/g);}
return ffrho(g);
}
}
}
// https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
vector<long long> factorize(long long n){
vector<long long> res;
for(auto &p : tinyplis){
while(n%p==0){
n/=p;
res.push_back(p);
}
}
while(n>1){
if(isprime(n)){res.push_back(n);break;}
long long cf=ffrho(n);
while(n%cf==0){
n/=cf;
res.push_back(cf);
}
}
sort(res.begin(),res.end());
return res;
}
};
vector<int> gb(int x,factorizer &fz){
for(int i=2;i<=x-i;i++){
if(fz.isprime(i) && fz.isprime(x-i)){
return {i,x-i};
}
}
return {-1,-1};
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
factorizer fz(10000005);
int t;
cin >> t;
while(t>0){
t--;
int x,y;
cin >> x >> y;
if(fz.isprime(x+y)){
cout << 1 << "\n";
cout << x << " " << y << "\n";
continue;
}
else if(fz.isprime(x+y-2)){
cout << 2 << "\n";
cout << 1 << " " << 1 << "\n";
cout << x << " " << y << "\n";
continue;
}
else if((x+y)%2==0){
vector<int> v=gb(x+y,fz);
cout << v.size() << "\n";
int s=0;
for(auto &nx : v){
s+=nx;
cout << min(x,s) << " " << max(0,s-x) << "\n";
}
}
else{
vector<int> v=gb(x+y-3,fz);
v.push_back(3);
cout << v.size() << "\n";
int s=0;
for(auto &nx : v){
s+=nx;
cout << min(x,s) << " " << max(0,s-x) << "\n";
}
}
}
return 0;
}
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using pi=pair<int,int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t>0){
t--;
int n,k;
cin >> n >> k;
vector<int> inv(n);
for(int i=0;i<n;i++){
int p;
cin >> p;
p--;
inv[p]=i;
}
set<pi> st;
for(int i=0;i<k+5;i++){
st.insert({-1,1e9+i});
st.insert({n,1e9+i});
}
vector<int> res(n,0);
for(int i=n-1;i>=0;i--){
auto ifw=st.lower_bound({inv[i],i});
auto ibk=ifw;ibk--;
vector<int> pf,pb;
for(int i=0;i<k;i++){
pf.push_back((*ifw).first);ifw++;
pb.push_back((*ibk).first);ibk--;
}
// for(auto &nx : pf){cout << nx << " ";}cout << "\n";
// for(auto &nx : pb){cout << nx << " ";}cout << "\n";
for(int p=0;p<k;p++){
int q=k-1-p;
res[inv[i]]=max(res[inv[i]],pf[p]-pb[q]-1);
}
st.insert({inv[i],i});
}
for(int i=0;i<n;i++){
if(i){cout << " ";}
cout << res[i];
}cout << "\n";
}
return 0;
}
#include<bits/stdc++.h>
#include <algorithm>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <vector>
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
using namespace std;
using namespace atcoder;
long long big=2e9;
long long op(long long a,long long b){
return min(a*b,big);
}
long long e(){
return 1;
}
long long power(long long a,long long b){
long long res=e();
while(b>0){
if(b&1ll){
res=op(res,a);
}
a=op(a,a);
b/=2;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t>0){
t--;
long long n,k;
cin >> n >> k;
long long gtn=0;
vector<long long> bk(n+1,0);
for(long long i=0;i<n;i++){
long long a;
cin >> a;
if(a>n){gtn++;}
else{bk[a]++;}
}
vector<long long> ini(n+2);
for(long long i=0;i<=n;i++){
ini[i]=power(2,bk[i]);
}
ini[n+1]=power(2,gtn);
segtree<long long,op,e> seg(ini);
vector<long long> cnt(n+1);
for(long long i=0;i<=n;i++){
seg.set(i,1); // not contain
cnt[i]=seg.all_prod();
seg.set(i,power(2,bk[i])-1); // at least 1
}
cnt[0]--; // remove empty set
long long pre=(k+1)/2;
long long suf=k-pre;
long long res=0;
for(long long i=0;i<=n;i++){
long long del=min(pre,cnt[i]);
pre-=del;
res+=del*i;
}
for(long long i=n;i>=0;i--){
long long del=min(suf,cnt[i]);
suf-=del;
res-=del*i;
}
// for(auto &nx : cnt){
// cout << nx << " ";
// }cout << "\n";
cout << res << "\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t>0){
t--;
int n,k;
cin >> n >> k;
string s;
cin >> s;
int fw=(k+1)/2;
int bc=k/2;
int md=n-fw-bc;
string pre,mid,suf;
for(char c='a';c<='z';c++){
for(int i=n-1;i>=0;i--){
if(pre.size()<fw && s[i]==c){
pre.push_back(s[i]);
s[i]='*';
}
}
}
string ns;
for(auto &nx : s){
if(nx!='*'){ns.push_back(nx);}
}
int l=ns.size();
vector<vector<int>> mem(l+1);
vector<int> bk(26,1e9);
mem[l]=bk;
for(int i=l-1;i>=0;i--){
bk[ns[i]-'a']=i;
mem[i]=bk;
}
int pt=0;
while(mid.size()<md){
// cerr << mid << " " << pt << "\n";
for(int i=0;i<26;i++){
// cerr << pt << " " << i << " " << ((int)mid.size())+(l-mem[pt][i]) << "\n";
if(((int)mid.size())+(l-mem[pt][i]) >= md){
mid.push_back(ns[mem[pt][i]]);
ns[mem[pt][i]]='*';
pt=mem[pt][i]+1;
break;
}
}
}
for(auto &nx : ns){
if(nx!='*'){
suf.push_back(nx);
}
}
sort(suf.begin(),suf.end());
cout << pre+mid+suf << "\n";
}
return 0;
}
