Contest link : https://codeforces.com/gym/102942

Announcement link : https://codeforces.com/blog/entry/87209

Finally, The round is over smoothly :) We hope everyone had fun and enjoyed the contest!

Screencast by AnandOza (start 10 minutes after the end of the contest).

Video Editorial by Bojack_human. He is a new youtuber. So, please support him (:

A. Directional Move

**Tutorial**

There have $$$4$$$ sides. Side-0(East), side-1(South), side-2(West), side-3(North).

- If we found '1', we have to move left, just decrement the side value. But for 'side-0', we have to move 'side-3'.
- Otherwise we found '0', we have to move right, just increment the side value. But for 'side-3', we have to move 'side-0'.

Clearly, final side will be the answer.

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
int main()
{
int test,n;
cin>>test;
while(test--){
string side="ESWN",p;
cin>>n>>p;
ll idx=0;
for(ll i=0;i<n;i++){
if(p[i]=='0') idx++;
else idx--;
if(idx==-1) idx=3;
else if(idx==4) idx=0;
}
cout<<side[idx]<<endl;
}
return 0;
}
```

**Tester Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define PSB push_back
#define ll long long
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
constexpr ll mod = 1e9 + 7;
const ll N=3e5+5;
int main(){
FastIO
int test;
cin>>test;
while(test--){
ll cnt=0,n;
string s;
cin>>n>>s;
for(ll i=0;i<n;i++){
if(s[i]=='0') cnt++;
else cnt--;
}
cnt%=4;
if(cnt<0) cnt+=4;
if(!cnt) cout<<"E"<<endl;
else if(cnt==1) cout<<"S"<<endl;
else if(cnt==2) cout<<"W"<<endl;
else cout<<"N"<<endl;
}
return 0;
}
```

B. Make All Odd

**Tutorial**

There are two cases.

Case 1: There have only even number. In this case answer is "-1". Cause for making the even number odd by adding another number, we need a odd number (we can make even number odd by only adding a odd number with that even number)

case 2: In this case there must have a odd number. Then for every even number, we can add a odd number with the target even number. And make every even number odd by one operation. Thus number of even number = minimum operation to make all odd.

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define PSB push_back
#define ll long long
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
constexpr ll mod = 1e9 + 7;
const ll N=3e6+5;
int main(){
FastIO
int test;
cin>>test;
while(test--){
int n;
cin>>n;
vector<int> a(n);
int cnt=0; bool ck=false;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]%2) ck=true;
else cnt++;
}
if(!ck) cout<<"-1"<<endl;
else cout<<cnt<<endl;
}
return 0;
}
```

C. Team

**Tutorial**

A Team can be formed by two ways. By one student Or by two students.

Way 1: For Those students skill at least k, every student can form a team.

Way 2: Firstly take the student of maximum skill. Then take the student with minimum skill, as if (1st student skill + 2nd student skill)$$$ \geq k$$$. And Both students were not included in any team before.

Continue this case to form as much team as possible.

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define PSB push_back
#define ll long long
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
constexpr ll mod = 1e9 + 7;
const ll N=3e6+5;
int main(){
FastIO
int test;
cin>>test;
while(test--){
int n,k,team=0;
cin>>n>>k;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end());
for(ll l=0,r=n-1;l<=r; ){
if(a[r]>=k){
++team; --r;
}
else if(a[r]+a[l]>=k && l!=r){
++team; ++l; --r;
}
else l++;
}
cout<<team<<endl;
}
return 0;
}
```

**Tester Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define PSB push_back
#define ll long long
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
constexpr ll mod = 1e9 + 7;
const ll N=3e6+5;
int main(){
FastIO
int test;
cin>>test;
while(test--){
int n,m,a;
cin>>n>>m;
multiset<ll> st;
for(ll i=0;i<n;i++){
cin>>a;
st.insert(a);
}
ll ans=0;
for(ll i=n-1;i>=0;i--){
ll bal=*st.rbegin();
st.erase(--st.end());
if(bal>=m){
ans++; continue;
}
ll baki=m-bal;
auto xx=st.lower_bound(baki);
if(xx==st.end()) break;
st.erase(xx);
ans++;
if(st.size()==0) break;
}
cout<<ans<<endl;
}
return 0;
}
```

D. XOR Game

**Tutorial**

For any two integers a, b. The maximum xor value is $$$(a+b)$$$. It can be found when there have not any common bit between 'a' and 'b'.

Case 1: If Alice chosen two integer, produce the maximum xor value. Then Alice must be win.

Case 2: In this case there must have some common bit between 'a' and 'b'. Then Bob can easily win, by choose two integer 'c' and 'd', where $$$(c \oplus d)$$$ = (a | b).

And it is proven that if have some common bit between 'a' and 'b' then (a | b) must be greater than ($$$a \oplus b$$$).

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define PSB push_back
#define ll long long
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
constexpr ll mod = 1e9 + 7;
const ll N=3e5+5;
int main(){
FastIO
int test;
cin>>test;
while(test--){
int a,b;
cin>>a>>b;
if((a^b)==(a+b)) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}
```

**Tester Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
int main()
{
int test;
cin>>test;
read:
while(test--){
ll a,b;
cin>>a>>b;
while(a && b){
if(a%2 && b%2){
cout<<"Yes"<<endl;
goto read;
}
a/=2;
b/=2;
}
cout<<"No"<<endl;
}
return 0;
}
```

E. Password

**Tutorial**

We can solve it by dynamic programming.

If some digit sequence already in decreasing order then answer is always "0".

We can write the transition of dp states like this:

$$$dp[i][digit]$$$ $$$ = \; $$$number of non-decreasing sequences end at $$$i$$$ and $$$s[i]=digit$$$.

Initially, all $$$dp[0][i]$$$ states are "1" $$$\; (1 \leq i \leq 9)$$$.

Case of ($$$s[i]$$$ = "-") :

$$$\qquad$$$ We can set any digit $$$(1-9)$$$ here. For this case ,

$$$\qquad\quad$$$ $$$dp[i][digit] = dp[i-1][1] + dp[i-1][2] + \dots + dp[i-1][digit]$$$.Case of ($$$s[i]$$$ = '1' to '9') :

$$$\qquad$$$ Then we must keep $$$s[i]$$$ as it is. For this case ,

$$$\qquad\quad$$$ $$$dp[i][s_i] = dp[i−1][1] + dp[i−1][2] + \dots + dp[i−1][s_i]$$$.

$$$\qquad$$$ For calculation help of the next states we can take the "Cumulative sums" $$$— dp[i][digit]$$$ += $$$d[i][digit−1]$$$ , $$$(2 \leq digit \leq 9)$$$

The final answer is $$$dp[len][9]$$$.

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
char s[N];
long long dp[N][10];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test;
cin>>test;
while(test--){
int i,j,l,n;
cin >>n>> s+1;
l=strlen(s+1);
for(int i=0;i<=l;i++)
for(int j=0;j<=10;j++)
dp[i][j]=0;
for(i=1;i<10;i++) dp[0][i]=1;
for(i=1;i<=l;i++)
{
if(s[i] >= '1' && s[i] <= '9')dp[i][s[i]-'0']=dp[i-1][s[i]-'0'];
else
{
for(j=1;j<10;j++)dp[i][j]=dp[i-1][j];
}
for(j=2;j<10;j++)
{
dp[i][j]+=dp[i][j-1];
dp[i][j]%=mod;
}
}
cout << dp[l][9]<<endl;
}
return 0;
}
```

**Tester Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
int main()
{
int test,n;
cin>>test;
read:
while(test--){
string s;
cin>>n>>s;
s='1'+s+'9';
ll mod=1000000007LL,ans=1LL;
for(ll i=0,j;i<(ll)s.size()-1;){
for(j=i+1;j<(ll)s.size();j++)
if(s[j]!='-') break;
if(s[j]<s[i]){
cout<<0<<endl;
goto read;
}
ll diff=s[j]-s[i];
ll d[10];
for(ll k=0;k<10;k++) d[k]=1LL;
for(ll k=i+1;k<j;k++){
for(ll l=diff-1;l>=0;l--){
d[l]+=d[l+1];
d[l]%=mod;
}
}
ans*=d[0];
ans%=mod;
i=j;
}
cout<<ans<<endl;
}
return 0;
}
```

**Tester Solution 2**

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
const int mx=1e6+5;
int Pow(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*1LL*a)%mod;
a=(a*1LL*a)%mod;
b>>=1;
}return res;
}
int f[mx];
inline int mul(int a,int b){return (a*1LL*b)%mod;}
inline int ncr(int n,int k){
return mul(f[n],Pow(mul(f[k],f[n-k]),mod-2));
}
int main(){
f[0]=1;
for(int i=1;i<mx;i++){
f[i]=(f[i-1]*1LL*i)%mod;
}
int test;
cin>>test;
read:
while(test--){
int ans=1,n;
string s; cin>>n>>s; s="1"+s+"9"; n=s.size();
for(int i=0,l=-1;i<n;i++){
if(s[i]>='0' && s[i]<='9'){
if(l==-1){
l=i;
continue;
}
int a=s[l]-'0',b=s[i]-'0',k=b-a;
if(k<0){
cout<<0<<endl;
goto read;
}
int len=i-l-1;
if(len==0){
l=i;
continue;
}
// cout<<len<<' '<<k<<' '<<i<<endl;
int aa=0;
for(int K=0;K<=k;K++){
aa+=ncr(len+K-1,K);
if(aa>=mod)aa-=mod;
}
ans=mul(ans,aa);
l=i;
}
}cout<<ans<<endl;
}
return 0;
}
```

F. Offer

**Tutorial**

we can solve this problem by two pointer idea.

Every time, we fixed one left and right point and store the current frequency of every unique element between the left to right subsegment inclusively. And for those cases after buying all element between left to right subsegment inclusively, cost is not more than k, we have to find the maximum value of $$$(right-left+1)$$$.

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define PSB push_back
#define ll long long
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
constexpr ll mod = 1e9 + 7;
const ll N=1e6+5;
int n, k;
int a[N], curf[N];
int main(){
FastIO
int test;
cin>>test;
while(test--){
cin>>n>>k;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i],curf[a[i]]=0;
int cost = 0, ans = 0;
int l = 0;
for(int r = 0; r < n; r++)
{
if(curf[a[r]] == 0)
cost += a[r];
curf[a[r]]++;
while(cost > k)
{
curf[a[l]]--;
if(curf[a[l]] == 0)
cost -= a[l];
l++;
}
ans = max(ans, r - l + 1);
}
cout<<ans<<endl;
}
return 0;
}
```

**Tester Solution**

```
//Author: AnandRaj doubleux
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test() int t;cin>>t;while(t--)
#define all(v) v.begin(),v.end()
#define prinp(p) cout<<p.first<<" "<<p.second<<endl
#define prinv(V) for(auto v:V) cout<<v<<" ";cout<<endl
#define take(V,f,n) for(int in=f;in<f+n;in++) cin>>V[in]
#define what(x) cerr<<#x<<" = "<<x<<endl
#define KStest() int t,t1;cin>>t;t1=t;while(t--)
#define KScout cout<<"Case #"<<t1-t<<": "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7,MAX = 1e6+5;
const ll INF = 1e18+5;
int main()
{
int test;
cin>>test;
while(test--){
int n,k;
cin>>n>>k;
vi A(n);
take(A,0,n);
int ans = 0;
int low = 0,high = n;
while(low<=high)
{
int mid = low + (high-low)/2;
bool can = false;
ll sum = 0;
vi M(MAX);
for(int i = 0;i<mid;i++)
{
M[A[i]]++;
if(M[A[i]]==1) sum+=A[i];
}
if(sum<=k)
{
ans = mid;
low = mid+1;
}
else
{
for(int i=mid;i<n;i++)
{
M[A[i-mid]]--;
if(M[A[i-mid]]==0) sum -= A[i-mid];
M[A[i]]++;
if(M[A[i]]==1) sum += A[i];
if(sum<=k) can=true;
}
if(can)
{
ans = mid;
low = mid+1;
}
else high = mid-1;
}
}
cout<<ans<<endl;
}
}
```

-If have any more query, then please comment.

thanks for this contest and hope for more contest like this.

Rudro25 what can be the difficulty of problems E and F?

My guess: E(1400-1500) and F(1500-1600)

Great round. For D, if x and y have no common bits then answer is NO else YES. So this will also work

this will also work!

Both are same!

a + b = (a | b) + (a & b)

thank you for this . I came up with the same logic , but didn't know how to proceed with bit manipulations.

So used the basic method to calculate every bit by n%2 and check whether both of them are 1 or not

My method is quite different then the others.First I mapped the position of each set bits in $$$a$$$ and $$$b$$$.If both $$$a$$$ and $$$b$$$ has a common position set bit then the bit is off(basic xor).Then I traverse the map and if any second value is $$$0$$$ then ans is $$$YES$$$.Otherwise $$$NO$$$.

Spoiler...

Thanks for the round and quick editorial

welcome sir!

Thanks for the round waiting for the next one

welcome sir! i will try (:

Hoping to solve upto D in div2 contest also some day. btw thanks for this contest and hope for more contest like this.

welcome sir :D i will try soon for the next one.

Welcome, Sir! Hope to see you next time also

Nicely done, thanks for the contest!

Thank you sir, for the support.

orzE was really a good problem for learning dp, thanks for the round.

welcome sir!

We can also solve E with combinatorics. Combination with repetition to be exact. Suppose the string is like, 1----5. We can place any digit from this, {1,2,3,4,5} set in increasing order in 4 place between 1 and 5.

Let,

`n = number of place to fill.`

`m = size of the set.`

Possible ways will be`(n+m-1) Choose n`

.For practice: https://codeforces.com/contest/1288/problem/C

I thought on similar lines but wasn't able to get my code working as intended. I'd appreciate it if anyone out here could look into the following submission.

Link: https://ideone.com/U8cjmP

Try checking the validity of the result explicitly.

The problem is with the size of your fac array which is 100005 but according to the problem n<=10^6 which makes n+k-1<=100009(and it is less than 100005).

I changed 100005 to 100020 and it got Accepted

Silly me! Thank you so much!

are you sure about this? I submitted the same code after changing it to

`int fac[100020];`

and still got WA at test 4. Did you change anything else?You are running the first for loop (inside int main function) only upto 100005, change it to 100020 too.

Of course, should have known that. Thank you very much.

Thanks for the formula, I got stuck at this and couldn't find this formula. Can you please provide me an explanation or a link where this formula can be find? Thanks for the given problem too.

Stars and bars

Imagine you need to fill a sequence of integers of size $$$10$$$ using only $$$1$$$, $$$2$$$, or $$$3$$$ so that the sequence is non-decreasing. As they are non-decreasing, all $$$1$$$'s have to appear in front of all $$$2$$$'s and so on, so we don't need to care about the order of these integers and we need only the number of occurences of each $$$1$$$, $$$2$$$, and $$$3$$$. Thus, we need to find number of solution of: $$$count_1 + count_2 + count_3 = 10$$$, with $$$count_0, count_1, count_2 \geq 0$$$.

Thank you for the explanation and the link. I got it.

Check this out: https://www.youtube.com/watch?v=4_je4mXUCGA Hope it will be helpful. I learned it from Coursera. Someone uploaded the video in YouTube too.

Thanks for the help.

Consider this example:

1 — — — 6

In this we have to fill 3 places and to fill those 3 places we have 6 elements. Now observe that

we only need to choose the elementswith which we want to fill the gaps.We don't need to decide the order as that is fixed.I got the idea in the contest but was unable to find the formula for that. which hijibijee provided.

Thancs for the formula :)...was thinking of this approach but couldn't remember the formula

I also tried to solve it with combinatorics. 105596767 This is the code it's failing test case 4. So can you help? if you find something. Thanks in advance.

Your solution will fail for (n+m-1) > 10e5 cases. Calculate factorials up to 10e6.

check this comment: https://codeforces.com/blog/entry/87253?#comment-754156

Ok Done :)

can you please explain the formula.how m+n-1

Thanks for the contest, had fun doing it!

Welcome sir!

Please make the submissions public, or atleast the testcases. It helps a lot in debugging silly mistakes.

I already told this secondthread sir. May be he will open soon , if possible sir.

Could anyone explain F in a more detailed way? It would be much appreciated.

It's just 2 pointer approach, we can keep on increasing our right pointer while maintaining frequency and cost, until the cost becomes greater than k. At this point we can start incrementing our left pointer and decreasing the cost. The number of elements will right-left+1. Now we keep on repeating the prcoess.

CodeIf in problem D, we were asked to maximize the score of Bob, how will we solve it ?

I think You can iterate from the highest to lowest bit, and try to set it, if possible.

The contest was great! Although I had come up with a similar idea as editorial, I had a hard time proving D during contest. I still can't wrap around why case 2 always is true. Could anyone please explain?

Hope This comment helps you.

Indeed, thank you so much!

Nice Contest..problem set was really good.

Thank you bhai :D

Very nice contest! Want more! Especially thanks for the good E task.

Thank you sir!

The F can also be solved using the bit + binary lifting technique.

But isn't it overkill?

can you please add more test cases? bacause it is just checking with one test case and getting accepted?

so now i don't even know whether my solution is correct or not?

You have the permission to see only 1 test case, sir. May be it's the 'gym' contest rule.

For C, why is the following approach incorrect? Answer is at least equal to elements >=k. Now put other elements in a list and sort it. Now iterate over every element, for every a[i], use lower_bound() on k-a[i] in range [i, list.size()] to find if such element exists. If it does, mark it used and increment answer. Why does this give a WA?

Codecan you please provide the code by spoiler! no permission to see other submission :(

Sure! My bad

Failed test case: 1 10 5 1 3 2 1 4 3 4 2 3 1

Expected: 4 but found 6.

May be the problem is — When you find a pos by lower_bound it can be also used before but you not checked that. may be you can use set and remove every used element then you can use lower_bound easily.

Ah right, I think the problem exactly is what you pointed out, I should definitely be removing those used values from my list. Thanks! Orz

Let's consider a variation of problem F. Now in the subsegment [l,r] instead of making the cost of all repeating elements in that subsegment zero if we were allowed to take only one of the repeating elements in that subsegment and make its cost equal to zero. Rest all the conditions remain same as mentioned in the problem F. Then can someone please provide an insight on how we could have solved it.

Hello , Thanks for this Contest . Can you Please Update the Settings so that we can we view all the test case , My Code for F gave wrong answer on test case 3 but I cannot access that test case . Thanks .

secondthread sir told that's may be impossible sir. but you can provide your code, i can check that by using polygon which on failed (:

Can you tell why my top down dp giving the memory limit exceed ??for problem E

We need more contests like this. Contests like today's destroy us and you pick us up. Thanks for organizing this man!

True

So, my understanding of the solution of $$$D$$$ is as follows:

If $$$a$$$ and $$$b$$$ are given such that there are

nocommon bits between them, the answer is $$$NO$$$, because there are no 2 integers $$$1 \leq c \leq a,$$$ $$$1 \leq d \leq b$$$ s.t. their xor will be strictly greater than the xor between $$$a$$$ and $$$b$$$.If $$$a$$$ and $$$b$$$ are given such that there

arecommon bits between them, the answer is $$$YES$$$, because we canalwaysfind 2 integers $$$1 \leq c \leq a,$$$ $$$1 \leq d \leq b$$$ s.t. their xor will be strictly greater than the xor between $$$a$$$ and $$$b$$$.But I don't understand why this should always be true (i.e. for 2 integers $$$a$$$ and $$$b$$$ s.t. there

arecommon bits between them, why is it that we can always find 2 integers $$$1 \leq c \leq a,$$$ $$$1 \leq d \leq b$$$ whichdon'thave common bits between them, s.t. their xor will always be strictly greater than the xor of $$$a$$$ and $$$b$$$), can anyone please provide a more detailed explanation of this or a proof?Edit: deleted some erroneous stuff I thought was correct..; also, thanks a lot @doubleux, that last paragraph (especially) really made it very clear and obvious that the "strategy" for the solution of $$$D$$$ would always work.

Notice, that the maximum Xor between any two numbers is always less than their sum, the maximum arising when no two bits are common.

Thus, if no bits are common, Xor of a and b is a+b, which is maximum that you can get using numbers less than them. Therefore no pair possible in this case.

If the do have common bits, a Xor b will be 0 at that position. Now choose c same as a, while for d, change the bit at common position as 0. This will make that bit 1 in their bitwise Xor, thus making it larger.

I used the same logic and approach in F but got TLE, why Python why :'-)

Problem F submission

Great tasks tho!

Rudro25 Can you please explain the tutorial for problem-A more clearly? It is not making any sense. [forgot to add that the problems were interesting!! ;) ]

Thanks

Why I am getting WA in problem E:

106721306

I used the chorus property.

`a^b=c -> a^c=b`

so`(c^d = (a^b)+somenum) -> (c^((a^b)+somenum)=d)`

And did`1<=somenum<=10`

. But why +10 was enough I don't understand. can open my eyes?this is my submission.107902945

IGNORE