Codeforces Round 746 Div 2 Editorial Solutions A - D

Gamer Hermose

One day, Ahmed_Hossam went to Hemose and said "Let's solve a gym contest!". Hemose didn't want to do that, as he was playing Valorant, so he came up with a problem and told it to Ahmed to distract him. Sadly, Ahmed can't solve it... Could you help him?

There is an Agent in Valorant, and he has n weapons. The i-th weapon has a damage value ai and the Agent will face an enemy whose health value is H

The Agent will perform one or more moves until the enemy dies.

In one move, he will choose a weapon and decrease the enemy's health by its damage value. The enemy will die when his health will become less than or equal to 0. However, not everything is so easy: the Agent can't choose the same weapon for 2 times in a row.

What is the minimum number of times that the Agent will need to use the weapons to kill the enemy?

Input

Each test contains multiple test cases. The first line contains the number of test cases t$t$ (1≤t≤105). Description of the test cases follows.

The first line of each test case contains two integers n and H (2≤n≤103,1≤H≤109) — the number of available weapons and the initial health value of the enemy.

The second line of each test case contains n integers a1,a2,…,an(1≤ai≤109)— the damage values of the weapons.

It's guaranteed that the sum of n over all test cases doesn't exceed 2⋅105

Output

For each test case, print a single integer — the minimum number of times that the Agent will have to use the weapons to kill the enemy.

Example

input

Copy

3
2 4
3 7
2 6
4 2
3 11
2 1 7

output

Copy

1
2
3

Note

In the first test case, the Agent can use the second weapon, making health value of the enemy equal to 4−7=−3. −3≤0 so the enemy is dead, and using weapon 1 time was enough.

In the second test case, the Agent can use the first weapon first, and then the second one. After this, the health of enemy will drop to 6−4−2=0, meaning he would be killed after using weapons 2 times.

In the third test case, the Agent can use the weapons in order (third, first, third), decreasing the health value of enemy to 11−7−2−7=−5 after using the weapons 3 times. Note that we can't kill the enemy by using the third weapon twice, as even though 11−7−7<0, it's not allowed to use the same weapon twice in a row.

 Program Code

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ll long long int

#define dbg(a,b,c) cout<<a<<"  "<<b<<"  "<<c<<endl;

#define mem(a,b) memset(a,b,sizeof(a))

#define endl "\n"

#define INF 1e18

#define w(t) cin>>t;while(t--)

#define kill(a) {cout<<a<<endl;continue;}

#define pi  2 * acos(0.0)

int t,ans=0,tot=0,kk=0;

const int mxn=2e5+10,mod=1e9+7;

 

signed main()

{

    

    w(t)

    {

        ll n,m,a,b,c,d,e,i,j,k,sm=0,sm1=0,cn=0,cn1=0,mx=-1e9,mn=1e9;

        string s,ss,sr,sa;

        bool f=false,ff=true;

        cin>>n>>m;

        ll ar[n];

        for(i=0;i<n;i++)cin>>ar[i];

        sort(ar,ar+n,greater<ll>());

        sm=ar[0]+ar[1];

        cn=m/sm;cn1=cn;

        cn*=2;

        m-=(cn1*sm);

        if(m>0)

        {

            cn++;

            m-=ar[0];

            if(m>0)cn++;

        }

        cout<<cn<<endl;

    }

}

Hermose Shopping

Hemose was shopping with his friends Samez, AhmedZ, AshrafEzz, TheSawan and O_E in Germany. As you know, Hemose and his friends are problem solvers, so they are very clever. Therefore, they will go to all discount markets in Germany.

Hemose has an array of n integers. He wants Samez to sort the array in the non-decreasing order. Since it would be a too easy problem for Samez, Hemose allows Samez to use only the following operation:

• Choose indices i and j such that 1≤i,j≤n, and |i−j|≥x.Then, swap elements ai and aj
  

Can you tell Samez if there's a way to sort the array in the non-decreasing order by using the operation written above some finite number of times (possibly 0$0$)?

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤105). Description of the test cases follows.

The first line of each test case contains two integers n and x (1≤x≤n≤105)

The second line of each test case contains n integers a1,a2,...,an (1≤ai≤109).

It is guaranteed that the sum of n over all test cases doesn't exceed 2⋅105.

Output

For each test case, you should output a single string.

If Samez can sort the array in non-decreasing order using the operation written above, output "YES" (without quotes). Otherwise, output "NO" (without quotes).

You can print each letter of "YES" and "NO" in any case (upper or lower).

Example

input

Copy

4
3 3
3 2 1
4 3
1 2 3 4
5 2
5 1 2 3 4
5 4
1 2 3 4 4

output

Copy

NO
YES
YES
YES

Note

In the first test case, you can't do any operations.

In the second test case, the array is already sorted.

In the third test case, you can do the operations as follows:

• [5,1,2,3,4], swap(a1,a3)
  
• [2,1,5,3,4], swap(a2,a5)
  
• [2,4,5,3,1] swap(a2,a4)
  
• [2,3,5,4,1], swap(a1,a5)
  
• [1,3,5,4,2], swap(a2,a5)
  
• [1,2,5,4,3], swap(a3,a5)
  
• [1,2,3,4,5]
  

(Here swap(ai,aj) refers to swapping elements at positions i, j).

Program Code

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int > pii;

const int N = 1e5+10;

 

pii a[N];

int b[N];

int n, x;

 

int finda(int x) {

    return lower_bound(b, b+n, x) - b;

}

 

int findb(int x) {

    return upper_bound(b, b+n, x) - b;

}

 

int main() {

    int T;

    scanf("%d", &T);

 

    while(T -- ) {

        scanf("%d%d", &n, &x);

        for(int i = 0; i < n; i++) scanf("%d", &a[i].first), a[i].second = i;

 

        sort(a, a+n);

 

        for(int i = 0; i < n; i++) b[i] = a[i].first;

 

        int flag = 1;

        for(int i = 0; flag && i < n; i++) {

            int idx = a[i].second;

            int aa = finda(a[i].first), bb = findb(a[i].first) - 1;

            if(aa <= idx && idx <= bb) continue;

            if(idx >= x || n-1-idx >= x) continue;

            flag = 0;

        }

        if(flag) puts("YES");

        else puts("NO");

    }

    return 0;

}

 

Bakery and Partitioning

Bakry faced a problem, but since he's lazy to solve it, he asks for your help.

You are given a tree of n nodes, the i-th node has value ai assigned to it for each i from 1 to n. As a reminder, a tree on n nodes is a connected graph with n−1edges.

You want to delete at least 1, but at most k−1 edges from the tree, so that the following condition would hold:

• For every connected component calculate the bitwise XOR of the values of the nodes in it. Then, these values have to be the same for all connected components.

Is it possible to achieve this condition?

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤5⋅104). Description of the test cases follows.

The first line of each test case contains two integers n and k (2≤k≤n≤105).

The second line of each test case contains n$n$ integers a1,a2,...,an (1≤ai≤109).

The i-th of the next n−1 lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), which means that there's an edge between nodes ui and vi.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of n over all test cases doesn't exceed 2⋅105.

Output

For each test case, you should output a single string. If you can delete the edges according to the conditions written above, output "YES" (without quotes). Otherwise, output "NO" (without quotes).

You can print each letter of "YES" and "NO" in any case (upper or lower).

Example

input

Copy

5
2 2
1 3
1 2
5 5
3 3 3 3 3
1 2
2 3
1 4
4 5
5 2
1 7 2 3 5
1 2
2 3
1 4
4 5
5 3
1 6 4 1 2
1 2
2 3
1 4
4 5
3 3
1 7 4
1 2
2 3

output

Copy

NO
YES
NO
YES
NO

Note

It can be shown that the objection is not achievable for first, third, and fifth test cases.

In the second test case, you can just remove all the edges. There will be 5 connected components, each containing only one node with value 3, so the bitwise XORs will be 3 for all of them.

In the fourth test case, this is the tree:.

You can remove an edge (4,5)

The bitwise XOR of the first component will be, a1⊕a2⊕a3⊕a4=1⊕6⊕4⊕1=2 ( )⊕ denotes the bitwise XOR).

The bitwise XOR of the second component will be, a5=2.

Program Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define nl '\n'

vector<vector<int>> g;

vector<ll> a;

ll all;

int k;

ll dfs2(int v, int par, int bad, bool& good, ll val) {

    ll res = a[v];

    for(int ne : g[v]) {

        if(ne == par || ne == bad) {

            continue;

        }

        res ^= dfs2(ne, v, bad, good, val);

    }

    ll rest = all;

    if(rest == res && res == val) {

        if(par != -1 && k >= 3) {

            good = true;

        }

    }

    return res;

}

ll dfs(int v, int par, bool& good) {

    ll res = a[v];

    vector<ll> vec;

    for(int ne: g[v]) {

        if(ne == par) {

            continue;

        }

        vec.push_back(dfs(ne, v, good));

        res ^= vec.back();

    }

    ll rest = all ^ res;

    if((rest == res)) {

        if(par != -1) {

            good = true;

        }

    }

    else if((res == all) && (rest == 0)) {

        if(par != -1) {

            bool good2 = false;

            dfs2(0, -1, v, good2, res);

            if(good2) {

                good = true;

            }

        }

    }

    return res;

}

void solve() {

    int n;

    cin >> n >> k;

    g.clear();

    a.clear();

    a.resize(n);

    all = 0;

    g.resize(n);

    set<int> ss;

    for(int i = 0; i < n; i++) {

        cin >> a[i];

        all ^= a[i];

        ss.insert(a[i]);

    }

    for(int i = 0; i < n - 1; i++) {

        int u, v;

        cin >> u >> v;

        u--, v--;

        g[u].push_back(v);

        g[v].push_back(u);

    }

    bool ok = false;

    dfs(0, -1, ok);

    cout << (ok ? "Yes" : "No") << nl;

}

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    int t;

    cin >> t;

    while(t--) {

        solve();

    }

    return 0;

}

Hermose in  ICPC

This is an interactive problem!

In the last regional contest Hemose, ZeyadKhattab and YahiaSherif — members of the team Carpe Diem — did not qualify to ICPC because of some unknown reasons. Hemose was very sad and had a bad day after the contest, but ZeyadKhattab is very wise and knows Hemose very well, and does not want to see him sad.

Zeyad knows that Hemose loves tree problems, so he gave him a tree problem with a very special device.

Hemose has a weighted tree with n nodes and n−1 edges. Unfortunately, Hemose doesn't remember the weights of edges.

Let's define Dist(u,v)for u≠v as the greatest common divisor of the weights of all edges on the path from node u to node v.

Hemose has a special device. Hemose can give the device a set of nodes, and the device will return the largest Dist between any two nodes from the set. More formally, if Hemose gives the device a set S of nodes, the device will return the largest value of Dist(u,v) over all pairs (u,v) with u, v ∈ S and u≠v

Hemose can use this Device at most 12 times, and wants to find any two distinct nodes a, b, such that Dist(a,b) is maximum possible. Can you help him?

Interaction

Begin the interaction from reading a single integer n (2≤n≤103) — the number of nodes in the tree.

Next, read n−1 lines.

The i-th of the next n−1 lines contains two integers ui and vi (1≤ui,vi≤n, ui≠vi), which means that there's an edge between nodes ui and vi

It's guaranteed that weights of edges were ≤109.

It is guaranteed that the given graph is a tree.

Now you may begin asking queries. To ask a query about a set of k$k$ nodes v1,v2,…,vk(2≤k≤n, 1≤vi≤n, all vi are distinct), output:

? k v1 v2 …$\dots$ vk

You will then receive an integer x, the largest Dist(vi,vj) over 1≤i,j≤k with i≠j

When you have found a and b (1≤a,b≤n)$)$, a≠b) such that Dist(a,b) is the maximum possible, print the answer in the following format:

! a b

Outputting answer doesn't count towards the limit of 12 queries.

If there are several pairs (a,b) with the same largest Dist(a,b), you can output any.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

Example

input

Copy

6
1 2
2 3
2 4
1 5
5 6

10

2

10

output

Copy

? 6 1 2 3 4 5 6

? 3 3 1 5

? 2 1 2

! 1 2

Note

The tree in the first sample:

Program Code

#include<bits/stdc++.h>

using namespace std;

#define task "sol"

#define lb lower_bound

#define ub upper_bound

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define zs(v) ((int)(v).size())

#define BIT(x, i) (((x) >> (i)) & 1)

#define CNTBIT __builtin_popcountll

#define ALL(v) (v).begin(),(v).end()

//#define endl '\n'

typedef long double ld;

typedef long long ll;

typedef pair<int, int> pii;

const int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};

const int dxx[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dyy[8]={0, 1, 1, 1, 0, -1, -1, -1};

const ll mod = 1000000007; /// 998244353

const ll base = 331;

const int N=3005;

pii e[N];

int n;

int cnt=0;

int numE;

vector<int> dsk[N];

int query(vector<int> &res)

{

    cnt++;

    assert(cnt<=12);

    cout<<"? "<<zs(res)<<' ';

    for (int i:res) cout<<i<<' ';

    cout<<endl;

    int x;

    cin>>x;

    return x;

}

int query(int l, int r)

{

    assert(l<=r);

    vector<int> res;

    for (int i=l;i<=r;++i)

    {

        res.pb(e[i].fi);

        res.pb(e[i].se);

    }

    sort(ALL(res));

    res.resize(unique(ALL(res))-res.begin());

    return query(res);

}

void dnc(int l, int r, int ans)

{

    int mid=(l+r)>>1;

    if (l<=0||r>n-1||l>r) return;

    if (l==r)

    {

        if (cnt<12) assert(ans==query(l,l));

        cout<<"! "<<e[l].fi<<' '<<e[l].se<<endl;

        exit(0);

    }

    int res=query(l,mid);

    if (res==ans)

    {

        dnc(l,mid,ans);

    }

    else

    {

        dnc(mid+1,r,ans);

    }

    assert(1==0);

}

void dfs(int u, int pre)

{

    for (int v:dsk[u]) if (v!=pre)

    {

        e[++numE]=mp(u,v);

        dfs(v,u);

    }

}

void solve()

{

    cin>>n;

    for (int i=1;i<=n-1;++i)

    {

        int u,v;

        cin>>u>>v;

        dsk[u].pb(v);

        dsk[v].pb(u);

    }

    dfs(1,1);

    vector<int> vec;

    for (int i=1;i<=n;++i) vec.pb(i);

    int ans=query(vec);

    dnc(1,n-1,ans);

}

int main()

{

    ios_base::sync_with_stdio(0); cin.tie(0);

    solve();

}

Links

Codeforces Round 745 Div 2 Editorial

More about Codeforces Round 746 Div 2

Codeforces organizes many contests out of which one is this Codeforces rounds to improve coding skills and get a higher coding knowledge. Codeforces Round 746 Div 2 was too a great round to test our coding skills. This round was held on  Sunday, October 3, 2021 at 20:05UTC+5.5. This round will be rated for coders with rating upto 2100. A total of 6 problems are given which needs to be solved in 2 hours 15 minutes.  

The first problem that is Gamer Hermose was cakewalk it was so simple that in 5 minutes we had more that four thousand successful submissions. Problem B was too a great deal of simplicity but it took a bit of time to understand what to do in the problem. Problem C was medium level and was a good question of logic for the average coders and for best coders it was just too simple. Problem D was good to go but the question was quite difficult to guess what algorithm would be required. Problem E1 was quite simple and many successful submissions were made. Problem E2 and F were the testing the skills of top coders and average coders just kept guessing what algorithms to use.

The contest was a great success and every body enjoyed it truly. Just practice more questions and go ahead in building a streak of code and get better everyday. Happy coding journey ahead.