104802A - Submission Bait Writer: wuhudsm
We use two pointers to solve this problem.
Set $$$l=1$$$ and $$$r=n$$$ initially.
- If $$$a_l=a_r$$$,
l++,r--; - If $$$a_l<a_r$$$,split $$$a_r$$$ into $$$a_r-a_l$$$ and $$$a_l$$$,
r--; - If $$$a_l>a_r$$$,split $$$a_l$$$ into $$$a_r$$$ and $$$a_l-a_r$$$,
l++;
When $$$l \geq r$$$,the process ends.
104802B - Snowy Bus Writer: pavlekn
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$$$.
104802C - Nafis and Strings Writer: BF_OF_Priety
\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 Writer: Ashutosh.Singh
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 Writer: Ashutosh.Singh
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.
104802F - Nafis and Mex Writer: BF_OF_Priety
\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}
104802G - Che Forest Writer: pavlekn
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 'a' to '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;
}
