Tutorial is loading...

**code**

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;cin>>t;
while(t--){
int x,y;cin>>x>>y;
string s;cin>>s;
int u=0,d=0,l=0,r=0;
for(int i=0;i<s.length();i++){
if(s[i]=='U')u++;
else if(s[i]=='R')r++;
else if(s[i]=='D')d++;
else l++;
}
if(x > 0 && r >= x )x = 0;
if(x < 0 && l >= -x )x = 0;
if(y > 0 && u >= y )y = 0;
if(y < 0 && d >= -y )y = 0;
cout<<((!x && !y)?"YES":"NO")<<endl;
}
}
```

Author: Salem_Alwarawreh

Tutorial is loading...

**code**

```
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define fast ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
fast
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
vector<int> a(n);
for(int i=0;i<n;i++)cin>>a[i];
int mx = *max_element(all(a));
if(n * mx < k){
cout << -1 << '\n';
continue;
}
int ans = n+1;
for(int b=0;b<k;b++){
int to = -2;
for(int i=0;i<n-1;i++){
if(a[i] < a[i+1]){
to = i;
break;
}
}
ans = to + 1;
if(to == -2)break;
a[to]++;
}
cout << ans << '\n';
}
}
```

Author: Warawreh

Tutorial is loading...

**code**

```
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 1000000010
const int N = 300010;
int n , m;
int a[N] , b[N] , c[N] , ans[N];
vector< int > g[N];
void solve(){
scanf("%d%d",&n,&m);
for(int i = 1 ;i <= n;i++) g[i].clear();
for(int i = 0 ;i < n;i++)
scanf("%d",&a[i]);
for(int i = 0 ;i < n;i++){
scanf("%d",&b[i]);
if(b[i] != a[i])
g[b[i]].push_back(i);
}
for(int i = 0; i < m;i++){
scanf("%d",&c[i]);
}
int last = -1;
if((int)g[c[m - 1]].size() > 0){
last = g[c[m - 1]].back();
g[c[m - 1]].pop_back();
}
else{
for(int i = 0 ;i < n;i++){
if(b[i] == c[m - 1]){
last = i;
break;
}
}
}
if(last == -1){
puts("NO");
return;
}
ans[m - 1] = last;
for(int i = 0 ;i < m - 1;i++){
if((int)g[c[i]].size() == 0){
ans[i] = last;
}
else{
ans[i] = g[c[i]].back();
g[c[i]].pop_back();
}
}
for(int i = 1;i <= n;i++){
if((int)g[i].size() > 0){
puts("NO");
return;
}
}
puts("YES");
for(int i = 0 ;i < m;i++){
if(i) putchar(' ');
printf("%d",ans[i] + 1);
}
puts("");
}
int main(){
int t;
cin >> t;
while(t--)
solve();
return 0;
}
```

Author: Kilani

Preperation: Warawreh

Tutorial is loading...

**code**

```
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define oo 1000000010
const int N = 1010;
int n , m;
char grid[N][N];
int has[N][2];
void solve(){
scanf("%d%d",&n,&m);
for(int i = 0 ;i <= n;i++) has[i][0] = has[i][1] = -1;
for(int i = 0 ;i < n;i++){
scanf("%s",grid[i]);
for(int j = 0 ;j < n;j++){
if(j == i) continue;
has[i][grid[i][j] - 'a'] = j;
}
}
if(m & 1){
puts("YES");
for(int i = 0 ;i < m + 1;i++){
if(i) putchar(' ');
printf("%d",(i & 1) + 1);
}
puts("");
return;
}
for(int i = 0 ;i < n;i++){
for(int j = i + 1;j < n;j++){
if(grid[i][j] == grid[j][i]){
puts("YES");
for(int k = 0 ;k < m + 1;k++){
if(k) putchar(' ');
printf("%d",(k & 1 ? i + 1 : j + 1));
}
puts("");
return;
}
}
}
for(int i = 0 ;i < n;i++){
for(int j = 0;j < n;j++){
if(i == j) continue;
if(has[j][grid[i][j] - 'a'] == -1) continue;
puts("YES");
int cur = has[j][grid[i][j] - 'a'];
if((m / 2) % 2 == 1){
for(int k = 0 ;k < m + 1;k++){
if(k) putchar(' ');
if(k % 4 == 0)
printf("%d",i + 1);
else if(k % 4 == 2)
printf("%d",cur + 1);
else
printf("%d",j + 1);
}
puts("");
return;
}
printf("%d",j + 1);
for(int k = 0 ;k < m / 2;k++){
if(k & 1) printf(" %d",j + 1); else printf(" %d",cur + 1);
}
for(int k = 0 ;k < m / 2;k++){
if(k & 1) printf(" %d",j + 1); else printf(" %d",i + 1);
}
puts("");
return;
}
}
puts("NO");
return;
}
int main(){
int t;
scanf("%d",&t);
while(t--)
solve();
return 0;
}
```

Author: Kilani

Tutorial is loading...

**code**

```
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define fast ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
fast
int n;
cin>>n;
vector<int> a(n),f(n),cf(n);
vector<pair<int,int>> at(n,{-1,-1});
for(int i=0;i<n;i++){
cin>>a[i];
a[i]--;
f[a[i]]++;
if(at[a[i]].first == -1)at[a[i]] = {i,i};
at[a[i]].second = i;
}
vector<int> dp(n+1);
for(int i=n-1;i>=0;i--){
dp[i] = dp[i+1];
cf[a[i]]++;
if(i == at[a[i]].first)dp[i] = max(dp[i] , dp[at[a[i]].second + 1] + f[a[i]]);
else dp[i] = max(dp[i] , cf[a[i]]);
}
cout << n - dp[0] << '\n';
}
```

Author: Warawreh

Tutorial is loading...

**code**

```
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define oo 1000000010
const int N = 100010;
const int SQ = 500;
int n , x , p;
vector< int > g[N] , cur[N];
char c[N];
int mx;
vector< pair<int,int> > v , v2;
pair< int , char > a , b;
int sz[N];
bool comp(int u,int v){
return (sz[u] < sz[v]);
}
int DFS(int node,int d){
mx = max(mx,d);
cur[d].push_back(node);
sz[node] = 1;
for(int i = 0 ;i < (int)g[node].size();i++)
sz[node] += DFS(g[node][i] , d + 1);
return sz[node];
}
bool dp[SQ][N];
int f[N];
void build_path(int i,int j){
if(i == (int)v2.size())
return;
while(!dp[i + 1][j]){
f[v2[i].first]++;
j -= v2[i].first;
}
build_path(i + 1 , j);
}
int main(){
scanf("%d%d",&n,&x);
a = make_pair(x , 'a');
b = make_pair(n - x , 'b');
if(a > b) swap(a , b);
for(int i = 2 ;i <= n;i++){
scanf("%d",&p);
g[p].push_back(i);
}
DFS(1 , 0);
for(int i = 0 ;i <= mx;i++)
v.push_back(make_pair((int)cur[i].size() , i));
sort(v.begin(),v.end());
for(int i = 0 ;i < (int)v.size();i++){
if(i == 0 || v[i].first != v[i - 1].first)
v2.push_back(make_pair(v[i].first , 1));
else
v2.back().second++;
}
dp[(int)v2.size()][0] = true;
int val , frq;
for(int i = (int)v2.size() - 1;i >= 0;i--){
val = v2[i].first;
frq = v2[i].second;
vector< int > last(val , -1);
for(int j = 0 ;j <= a.first;j++){
if(dp[i + 1][j] == true)
last[j % val] = j;
if(last[j % val] == -1 || ((j - last[j % val]) / val) > frq)
dp[i][j] = false;
else
dp[i][j] = true;
}
}
if(dp[0][a.first]){
build_path(0 , a.first);
for(int i = 1;i <= n;i++) c[i - 1] = b.second;
for(int i = 0 ;i <= mx;i++){
if(f[(int)cur[i].size()] == 0) continue;
f[(int)cur[i].size()]--;
for(int j = 0 ;j < (int)cur[i].size();j++)
c[cur[i][j] - 1] = a.second;
}
printf("%d\n",mx + 1);
c[n] = '\0';
puts(c);
return 0;
}
printf("%d\n",mx + 2);
for(int i = 0 ;i <= mx;i++){
sort(cur[i].begin(),cur[i].end(),comp);
if(a.first < b.first) swap(a , b);
while((int)cur[i].size() > 0 && a.first > 0){
c[cur[i].back() - 1] = a.second;
cur[i].pop_back();
a.first--;
}
while((int)cur[i].size() > 0 && b.first > 0){
c[cur[i].back() - 1] = b.second;
cur[i].pop_back();
b.first--;
}
}
c[n] = '\0';
puts(c);
return 0;
}
```

Author: Kilani

Thank you for the quick editorial

Damn, really fast editorial. Thanks, the problems were great!

Problem C was not so good....

really quick

膜

good problems

wow -__- fast editional

Boring implementation problems (first 4)

really fast,the editorial was ready while system testing

Thank you for the fast editorial

"DELETED"

https://ideone.com/ZpbCHH can someone tell me how is the above code wrong for problem C. I have done almost the same thing as tutorial , the only difference is that tutorial checks that we have enough painter to paint at the end and i check that in the beginning UPDATE : The mistake has been found and corrected

I believe you don't check if the last painter has a color that doesn't appear in b (ie ans=-1) in which case you should say No and you say yes

I have checked that , I have checked that whether Vis[c[m-1]]== false . Vis is true when the no. Appear in the array b.

Thanks for the contest!

D was lengthy :|. Got the idea but can't implement it.

怎么做啊？？？？

B was brute force! C was hard implementation!! Let's see the editorial for D!!!

Thanks for quick editorial and wonderful problems, I got stuck on problem C but during the after-contest discussion with my classmates, I found that it was just hard implementation, while I was thinking of something like DP.

As your senior,I have to point out that you've made A grammer mistake.

As The Principal of your school, I have to point out that you've made a

grammarmistake.Lets laugh together :)

Can someone help me find the error in this solution. I have done exactly as the solution above states.

Link : https://codeforces.com/contest/1481/submission/106601553

hack:

the ans can be

but your output is

`No`

Thankyou so much!

It works for mine, but Im still getting WA

Your code fails to pass this:

thnxs for the testcase

Hey VTifand, Can you tell a counter example for this code 107294260 for Problem C?

Test this:

Hey VTifand Can you please tell where I am going wrong in this solution? 109939615 because it passes all the above test cases that u mentioned in the comments.

Thanks in advance...

thank you so much brother! I found my error thanks...

Can u clear my doubt in problem C editorial, while searching an index in B-array which matches last element in C-array, it is said that a[i] should not equal to b[i].

Problem C was worst in my veiw

I think it was pretty good problem for Div2, because it does not require algorithm but the way you implement your idea into your code. So yeah, I personally enjoyed it

For Prob D, can someone clear my doubt. I had the same idea but was not able to prove one case.

Let's say there are no two nodes that have the same value on the edge. (If

`x`

and`y`

are nodes then they will have value as`a`

and`b`

) and we have`m`

as an even number,I am not able to proof if we don't find two consecutive edges whose values are the same then the answer will always be

`NO`

. I was trying to figure out a case where it's possible.As mentioned in the editorial, for $$$n\geq 3$$$ it's actually always possible to find two consecutive edges that are equal. just consider 3 vertices $$$x$$$, $$$y$$$ and $$$z$$$. Then two of $$$xy$$$ $$$yz$$$ and $$$zx$$$ edges must be equal.

Video solution to problem D: https://youtu.be/U93sCV3I17Y

Please if possible also post a video editorial of C

Thank you! And if you are ever feeling down, know that we all love you (in a brotherly way). :-)

Thank you for the questions and editorial. Much appreciated as a participant

I have a different solution regarding problem D when m is even and there's no cycle with length 2 with the same character (i.e. $$$x \to y = y \to x$$$).

Observation: For every cycle with length 3, there will be always 2 adjacent edges with the same character

Proof: There are 3 edges in the cycle. We put $$$x \to y = a$$$ and $$$y \to z = b$$$. If we put $$$z \to x = a$$$, then $$$x \to y$$$ and $$$z \to x$$$ will have the same characters. Conversely, we can do the same for $$$z \to x = b$$$ and yielding similar result.

Therefore, it is enough to only consider the node permutation $$$1, 2, 3$$$. If $$$m \bmod 3 = 0$$$, then arrange it in such way so the string becomes "abaaba...". If $$$m \bmod 3 = 1$$$, then arrange it in such way so the string becomes "baabaab...". Lastly if $$$m \bmod 3 = 2$$$, then arrange it in such way so the string becomes "aabaabaa...".

The above strategy will work for $$$n \geq 3$$$, and it can be proven that it is impossible for $$$n = 2$$$.

Your solution is more proven and understandable than the solution in editorial! Thank you!

Thanks for quick Editorial! I think Problem D is really ingenious!

Can someone tell me how is this code for problem C giving TLE on pretest 3. I think it's complexity is also O(N).

for problem C, here is my code(python[submission:106605351]), it is showing error on 4th input on test case 2 and, I am unable to look at that input? can someone help me out in my solution? https://codeforces.com/contest/1481/submission/106605351

Thanks a lot,you saved my day,I literally had no idea why my case was failing. And as I debugged this case, boom it got "Accepted". And if you don't mind could you please let me know that how did you get to know about the test case. Once again thanks a lot for helping me a lot.

Can Problem B be done in less than O(n^2)?? using stacks ?? something like rain water trapping ? i wasn't able to code one !!

would appreciate some help, if possible code XD

Consider the algorithm, because the height of each does not exceed 100, and when filling a part of the pit ($$$h_{i-1}\geq h_i<h_{i+1}$$$), it will gradually become a flat ground. Before it becomes flat, there can be no The height of the mountain is more than 100, because if there is a mountain of 100, the stone will either roll into a mountain in front of it or roll to a lower place behind it, and it is impossible to add it to this mountain.

The solution from the tutorial is actually not O(n^2) but O(n^3). Consider the input:

We have to do (100 — 1) * (100 — 1) throwing simulations. Those are O(n). So that solution is O(n^3). (In this case we will need 490149 comparisons to be precise.)

If you want a O(n) solution take a look at my solution. (although one needs to change the vector to doubly linked list to reach O(n) because i use erase alot.)

106632891

(It is not trivial that my solution is O(n) because I don't always increment my index. But every iteration either fills a pit or increases the index. You can't have to fill more than n pits in an array of size n (this can be shown using induction over n) so this is O(n).)

Good problems

Problem D looks like a graph problem

Editorial — Well yes, but actually no!

Can anyone help me to know the case I missed here 106605508

Nevermind it was an issue of colors being 1 ... n and I assumed it as 0 ... n-1. I want to die

Aren't you the guy who writes beautiful explanations?

Your code looks clean. Would be great to know about your thought process.

You have to think that what is important ?.

Important is in this case is that to paint every plank where

`a[i] != b[i]`

.Second thing that is very important is that every painter is coloring some(exactly one) plank.

Let's call the planks that need to painted some color other than

`a[i]`

as bad planks and rest (a[i] == b[i]) as good planks.We need all planks to be good at the end. Next thing is that Assume

`count`

is number of bad planks that wants color`b[i]=k`

then we need atleast`count`

painters that paint color`k`

.If there are more than that and since every painter must paint (they are behaving like spoiled children) they can paint any good or bad plank of color

`k`

(if there exists such plank).Reasoning for this is to divide into three cases.

Case 1 the extra painter is painting a good plank then he is just repainting it and it really doesn't do any harm.

Case 2 the extra painter is painting a bad plank to its correct color but since he is extra that plank was going to be painted to its correct color at some moment , so either he is repainting or painting before its last painting.

Degenerate Case is that there doesn't exist any plank that wants a color that

`m-th`

painter wants then in that case there is no answer. if there doesn't exist a plank that wants a color that`(m-1)th`

or lesser index painter provides then he can color the unwanted color to the same plank the`(m-th)`

last painter is going to paint at last.Assuming there exists an answer then you can be sure that last painter is going to paint or repaint some plank correctly. So any painter that comes at

`(m-1)th`

or lesser index can paint that exact plank since his paint will not remain in the end anyways.It must be clear by now that the last painters of some color

`k`

are to be processed first and other painters of color`k`

are extra and they can paint any plank that`b[i] = k`

(Case 2 or Case 1).Except degenerate case but that can be check by asking "Is there any painting done after this?". A flag variable can help you here.

Iterating from

`mth`

painter to the first helps us a lot. For implementation details check my submission 106614841Could anyone tell me what's the difference between the AC code and this 106549562

For example, $$$px=0$$$ and $$$py=1$$$, the string is $$$\text{UUDD}$$$, your code is wrong.

Code id edited .. the current id is my 1st submission

An error occurred in the $$$x<=0,y>=0$$$ part

It should be

But in the code

RIP .. thanks

that cost me green and -123 T_T

It's hard to understand E's solution! Why when $$$l[a[i]] \neq i$$$, I should move all elements except $$$a[i]$$$?

There are 2 things to do when $$$l_{a_i} \ne i$$$ :

We can either move everything except books with color $$$a_i$$$ so they are next to each other.

Or move book $$$a_i$$$ so it can become next to the other books with color $$$a_i$$$.

Both points are covered in case number 2 and 3.

Can you share intuition behind this:

(note that here we move all books even those after rai)If we keep all books of color $$$a_i$$$ unmoved and there are still books of color $$$a_i$$$ to the left of $$$i$$$ how will we make them adjacent, lets say we have this array $$$[1,2,2,1,1,3]$$$ and $$$i = 4$$$ and we don't want to move the last 2 books of color 1 how could we make all books of color 1 adjacent, simply we say that I will move all books of color 1 to my left then move all books between books of color 1 which is books between $$$i$$$ and $$$n$$$.

So the sequence of moves are move the first book you will get $$$[2,2,1,1,3,1]$$$, then move book with color 3 to get $$$[2,2,1,1,1,3]$$$.

Considering example and trying to dry run

5

1 2 2 1 3

dp[i]: maximum number of books that can be left unmoved if looking at subproblem of books a[i], a[i+1]...a[n-1]

dp[5] = 0 (base case)

start with i=4 (0-indexed):

dp[4] = 1 + dp[4+1] = 1 (scenario 1 from editorial)

dp[3] = max(dp[4], cf) = max(1, 1) = 1 (scanario 2 and 3)

now if dp[3] means the max number of books that can be kept unmoved when solving subproblem [i,n], shouldn't dp[3] be equal to 2. Since the suffix array is {1, 3} and both of them can be left unmoved in this subproblem

Am I interpreting the meaning of dp[i] incorrectly?

When calculating $$$dp_i$$$ we don't treat suffix $$$[i,n]$$$ alone (as a sperate new array) we still take into consider that there is still more books of color 1 that will be processed later.

Could you explain in case 2, why do we even move the books after Rai? I'm a bit confused here.

I think you got the idea. There are two ways to achieve the target.

To do the first way, we make $$$dp[i]=dp[i+1]$$$.

To do the second way, we can do the process as Warawreh says : move all elements except color $$$a[i]$$$ and be ready for the elements $$$a[i]$$$ that is before $$$i$$$ to move to the right.

But when $$$i==l_{a[i]}$$$, we have extra thing to do : just keep all $$$a[i]$$$ ummove and don't need to consider element before, since there are no $$$a[i]$$$s exist before. That is $$$dp[i]=f[a[i]]+dp[r[a[i]]+1]$$$.

"move the book with color $$$a[i]$$$ to join the book behind" — can you elaborate a bit please? And how $$$dp[i] = dp[i+1]$$$ accomplishes that?

The idea is to keep as many of books unmove as possible. That means all others books should be moved. It is obvious that we can arrange those moved book correctly to make the shelf beautiful.

In case no. 3 when we are moving book $$$a_i$$$, shouldn't $$$dp_i = dp_{i+1}+1$$$ instead of $$$dp_{i+1}$$$ because we are moving $$$i^{th}$$$ book also. Moreover, I can't understand why in case 1, $$$dp_i = dp_{r_{a_i}+1}+f_{a_i}$$$. According to my understanding, it should be $$$dp_i = dp_{r_{a_i}+1}+(r_{a_i}-l_{a_i}+1-f_{a_i})$$$ as there are $$$(r_{a_i}-l_{a_i}+1-f_{a_i})$$$ books between first and last instance of book with color $$$a_i$$$. Kindly help me out with this.

We are counting books that are "not" moved

$$$dp_i$$$ which will find for each i themaximum number of books that we can leave unmovedin the suffix $$$[i,n]$$$.You are trying to find the minimum number of moved books, but I am trying to find the maximum #unmoved books.

@Warawreh

So in case when L[a[i]]!=i...then dp[i]=max(dp[i+1],cf[a[i]]+dp[r[a[i]+1]) but u are only considering cf[a[i]](maximum unmoved books from i to n-1)

cf[a[i]]+dp[r[a[i]+1]>=cf[a[i]] as term one is greater. so shouldn't it be like the way i have shown. I am vey confused over this..Please correct me.

Sorry, got it, noob error ;(

In my opinion, dp[i] means if books from 1 to i-1 must be moved, the maximum number of books we can leave unmoved in the suffix [i,n]. So if a book in [1,i-1] has the same color with book i, because it must be moved to the back, all the books except a[i] should be moved in order to make all books colored a[i] next to each other.

The only reason the solution to AB graph (problem D) needs to be O(n^2 + m) is because it takes that O(n^2) to read the input and O(m) to print the solution. Solving the actual problem can be done O(1). See https://codeforces.com/contest/1481/submission/106613756 (which sadly I only got right after the contest had ended).

The trick is that, however big the graph is, you only need look at the first three vertices. Either one of these has the same edge label in both directions, or you can find two consecutive edges in the triangle with the same values. You can then solve the problem using these three vertices as described in the editorial ignoring every other vertex and edge.

This also makes it clear that the only case with no solution is the two vertex case with different edges and an even m.

Can someone help me find the error in this solution. I have done exactly as the solution above states.

Link : https://codeforces.com/contest/1481/submission/106616688

An error occurred in the (mp[1][2]==mp[2][3]&&mp[2][3]==mp[3][1]) part

We should printf("YES\n") first.

Why my submission 106617241 is wrong? please provide me a counter case.

Here is a counter case:

Can you tell a counter example for this code as well https://codeforces.com/contest/1481/submission/106608493

Thanks for the help man.

Can you tell a counter case for this code as well. https://codeforces.com/contest/1481/submission/106676613

Can you tell a counter case for this code as well. https://codeforces.com/contest/1481/submission/106676613

Thank you.

Thanks man

Does in Ques A if the changing position was allowed would the answer be different?

as long as we can delete , changing positions won't make any difference .

What is case 57 of test 3 ?

My logic is same as editorial idk why failing ? code

EDIT:nvm Got it!Btw if there's any way to see a complete test case please comment down!

I'm also wa at case57 test3, have you catch the bug?

i also got it now. 1 3 4

aa b*a bbthis case can cause my faultFailing on the same case, what is different about this case?

{deleted}

We don't need to find x,y,z in problem D because any three node will given us answer , so take first and second and third node and now in a loop 1->2->3->1 there will be atleast two continuous edges which are equal, this will make implementation easy , you can see my submission 106600375

hi there! great contest, although I am still struggling with problem C.

here is my submission: https://codeforces.com/contest/1481/submission/106619632

probably there is some obvious reason why it fails but cannot find it, cannot deduce that also from test cases, anyone could advise? cheers!

Check with this input:

I believe your line

`last_index = colors_later.index(painters[-1])`

is problematic. There is no guarantee that this index will be chosen by any painter, as shown by the input above.Spot on mate! Thanks a lot, this was indeed the problem here.

Cool problemset :3

Using the technique described in this blog, you can improve the time complexity of problem F by a factor of $$$w$$$, where $$$w$$$ is the word size of the machine (usually $$$32$$$ or $$$64$$$).

Instead of using the deque method to solve our 0-K knapsack, we instead decompose our items $$$(a_i, m_i)$$$ into $$$log_2(m_i)$$$ items and perform 0-1 knapsack on those.

Usually, this would add a factor of $$$O(log(n))$$$, but in this case it is provable that the time complexity still remains $$$O(n \sqrt{n})$$$.

The improvement comes from the fact that we can use bitsets for the calculation of the knapsack. Transitions are handled by simple OR functions, and tracing back can be handled by iterating over all new elements of the bitset. This speeds up the dp transitions by $$$O(w)$$$, allowing a complexity of $$$O(\frac{n \sqrt{n}}{w})$$$.

Submission: 106619988

Kilani The given code in this tutorial for 1481C — Fence Painting is giving wrong output for some cases.

For example:

INPUT:

1 2 2 3 5 8 9 8 8

OUTPUT(incorrect):

YES 1 1

Correct OUTPUT: NO

That input is invalid. All colors are in the interval $$$[1, n]$$$.

Can someone tell me which case am I missing in problem C.106619774

Try this:

Thanks for the test case but I resolved it and my code is still failing. 106624257

Can you also provide a counter case for this submission?

106617485 what's the problem with the second test case

$$$k <= 10^9$$$ you're making array of size $$$10^9$$$

Can Anyone Explain me How B is solved And how can I improve my implementation How do I practice ? Please Help!!!!!

Can Anyone Explain me How B is solved And how can I improve my implementation How do I practice ? Please Help!!!!! 1481B][PROBLEM:1481B - New Colony

If you look at the constraints you can place at most 99*99 boulders(worst case) before they start falling into waste collection system. Worst case will be like 100 10^9 1 1 1 1 ...... 100(last height) // n-1 times 1 and last height is 100. So what you can do is code a brute force solution start at 0th index drop the boulder manually traverse till you find the correct position such that h[i]<h[i+1] place it at i (do h[i]++), so for each boulder you need at most O(N) operations to find its correct position and if no position was found which means this boulder will fall into waste collection and all the upcoming boulder will fall too so you can break this loop here and print -1, So overall complexity will be O(No of boulder that can be placed) * O(N) almost equals O(N^3) as No of boulders that can be placed are of order 10^4 in worst case.

Do we have to print the output in a specific order in problem C because when i tried some other order, i got WA in test case 2?

Take care of the order of painters, as if i<j then ith painter will paint before jth comes.Probably you have missed this part.

The editorial for E completely fails to explain the core idea.

The idea is that you can choose any element that you move at the very beginning. Then it becomes obvious that you can add any permutation of the chosen elements to the end of the array of non-chosen elements. So, one necessary condition is that the array of non-chosen elements is beautiful. To understand the DP-transitions, note that the the

ONLYcase where two equal elements can be both inside the chosen and not chosen arrays is if it's at theENDof the array of non chosen elements. So, if it's not the last element, the only way we can add it to the array of not chosen elements is to choose everything before it.Can you please share more insights on this?

watch neal's explanation for this question. It really helped me. https://www.youtube.com/watch?v=pzwQbiT816w

Thank you for the quick editorial! The problems are really great!

can anyone help me with my problem C? 106634920 or maybe some hack samples ? thanks :)

https://codeforces.com/contest/1481/submission/106635785 here, i recoded it with "stack" instead of "vector", and I passed... What happened?

Spoilerin this piece of code you wrote

`i<n`

instead of`i<=n`

whoops my fault... :| thank you so much! o7

I am facing the same problem 109694896. What's wrong? The spoiler's missing

I tried to stress-test your solution and got this test:

Spoilerthe actual answer is "NO" but your solution prints "YES".

hope it helps

Thanks! I immediately find out it should be

`rep(i,1,n+1)if(need[i].size()!=0)ok=false`

since the color is index from 1 to n, not 0 to n-1. This is inconsistency of the index. I am aware that I could have such bugs but unable to find a counterexample. Thank you so much.Exactly the same fault as hehepig. I should use

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

encounting such inconsistent index next time to avoid messing up myself.Yeah, this happens sometimes. In the contest I wrote

`m`

instead of`n`

but it was good that I found out this bug in the contest. solution, wrong, what I changedxD in need of help. What's the fault of that code

106561762 Can anyone spot the bug in my code why it is not accepted?

what if (x!=0 and y==0) or (x==0 and y!=0)

Can you please check my code why it's getting WA problem D

In problem div2-D, what if it says path must form a circle i.e. start and end point are the same and also you can't visit same vertex or edge twice?

Thanks for such a great contest and fast editorials! I love all the interesting problems especially F!

Problem D is exciting but problem E maybe too classic?

And also thanks for the quick and good editotial!

Hey, can you point me to some problems similar to E? I kind of understood the editorial but feeling shaky about how to arrive at the basic intuition

Could anyone help me find my mistake in this code of problem C?

It got WA on 2 but I can't see the exact test data.

Here's the code : 106592765

Thx a lot.

You must have inconsistent index usage. I don't look closely into your code but remind yourself that this problem index is from 1 to n, NOT 0 TO N-1. Probably you miss a particular index, check it.

My solution for C is giving WA I've implemented it same as in editorial Please help me find what's wrong with my solution 106644778

The loop which you were using for the greedy distribution of the painters is going till i=m-1, but you have already given the painter for the last one, thus the loop should go only till i=m-2. I changed that and got your solution accepted. 106646446

But even if i goes to m-1(last painter) it will execute else condition only and assign ans[m-1]=ind which did not change the ans as it is already assigned to ind . Please explain if im missing something

I explained C in my blog https://codeforces.com/blog/entry/87540. I hope you like it.

Your link doesn't work. It redirects to the tutorial of this contest.

I deleted it. but here is my comment https://codeforces.com/blog/entry/87523?#comment-757834

No, it is not necessary that it will execute the else condition. It can execute the if condition too. Consider the case that s[C[m-1]].size() = 1, then it will execute the if condition and then when you are checking the size of the s[C[i]] (after that in which you are setting the 'flag' to zero), it would be empty and thus 'flag' won't be set to zero. But, in reality, you already have painted the last one earlier and thus, s[C[m-1]] shouldn't have been empty and flag should be set to zero. And this case occurs because a painter can paint only one fence and you have already chosen the fence for the C[m-1] when you are finding the value of 'ind'.

Oh I got it now thanks dude

B will be more interesting when h[i]<=10^9.

Then it wouldn't be B :p

Can anyone solve my problem: In problem E, when i is not equal to l[a[i]], we move all the books except for the color a_i, even if it is on the right side of R_a[i]. Why?

The idea behind this is that for example if your original array is 1,2,1,1,1,2,2,2,2,3 you can't say that the numbers that will be unchanged from 3rd number(which is 1 ) to the last one since in this case you need to move the first one and there is no sequence to move the first one to be beside all the other ones (you can read rananjay23 's comment) so you want to have subsequence of numbers such that except for the last color in the subsequence all the colors occurrence (count) in the original array is the same as the subsequence so let's define dp[i] to be the length of the longest subsequence that satisfies that all colors count in the original array is the same as the subsequence except possibly for the last color in the subsequence so if i not equal to l[a[i]] and you considered only the number of colors in the range from i to r[a[i]] + dp[r[a[i]]+1] so in this case your dp[i] won't represent what we want it now will count for subsequences that have number of occurrence not equals to the original number of colors e.x. a=[1,2,2,1,1] so your dp[2]=3 (zero indexed) which is incorrect it should be 2 since you can't take the sequence 2,1,1 but your possible sequences so far are [2] the 2nd 2 or [1,1] the 2nd and 3rd 1 and the longest of them is [1,1] so dp[2]=2

Problem D can be solve using dfs + random(for even m). It's my code: https://pastebin.com/29jv66h3

I am getting WA in div2-D. Can someone help me find the error in this solution? Submission Link

https://codeforces.com/contest/1481/submission/106664046 can someone help me with my approach on C problem. its showing wa on test case 376 in test 2. the need map stores the index in which we need to repaint. the sb map stores a index of every element in b array. the count array is for checking we have enough painters of that color that we need. UPDATE : found the mistake

In problem E , I failed to understand through editorial completely , so i came up with following thought process while upsolving (might be same as editorial):

Note that answer is $$$n-sum$$$ , where $$$sum$$$ is largest subsequence of the array similar to $$$1,1,1,1,1,4,4,4,4,4,5,5,5,5$$$ . Important thing to note here is except the last color ($$$5$$$ here) , count of all other colors in subsequence must be equal to count in the original array.

For example if array was of the form : $$$1,1,2,1,1,3,1,4,4,4,4,4,5,5,5,5$$$ , then we cannot choose $$$1,1,1,1,4,4,4,4$$$ because $$$1$$$ is not the last element in subsequence and we haven't taken all of it's occurrences.

Once we have chosen the largest subsequence such that all similar colors in subsequence is consecutive and except last color in subsequence all other color count in subsequence is equal to that in original array , we can see that we can move all other colors greedily to the end of the subsequence .

For example if array was $$$1,1,2,1,1,3,1,4,4,4,7,4,4,5,5,5,5,2$$$ . Then we can choose $$$1,1,1,1,1,4,4,4,4,4,5,5,5,5,2$$$ as largest subsequence , then we can move the $$$2$$$( at 3rd position),$$$3$$$ (at 6th position) , $$$7$$$ (at 11th position) to the end of the subsequence and thus final arrangement will be $$$1,1,1,1,1,4,4,4,4,4,5,5,5,5,2,2,3,7$$$ .

For implementation while iterating we can keep track of largest such subsequence ending with $$$a[i]$$$ and also largest subseqeunce such that all colors in subsequence have count equal to that in original array (even the last color) .

Code is very short for this problem . submission

I think I understood your idea, but could you help me figure out the implementation please? I didn't understand the submission you posted.

you can try to see how code works line by line (i.e dry run) by taking samples in question and in my comment .

I have heard that B can be solved in O(n).Does anyone know how to solve B in O(n) using stack?

106663413 Can anyone please point out the error in this code for problem D?

Its been hours since I am trying to debug this code but its not getting an AC.

I haven't solved this problem yet, but I think this input is a counter case:

Your code outputs

`1 2 1`

which I believe corresponds to a non-palindromic string`'ab'`

?Yes, I understood that what was the error in it, if (m/2) was odd so I was trying to print aabbaabbaa..... and so on and the last 2 letters would be 'aa' but through my code the last 2 letters were not coming out as 'aa' always, I just had to print d2+1 in place of d+1 at the last line, thanks for pointing out the error.

Can someone please help me find the error in my submission for the problem C. TIA Here is my submission

and the shiitiest implementation of the year award goes to problem C. congrats Kilani

Why if M / 2 is even we cannot write out the vertices in the order x -> y -> z -> y -> x? (Task D).

Of course, we can. Problem was in my code. Sorry :(

My Submission for C is exactly the same as editorial. Why am I getting WA at test 2? Pls help.

Can someone please help me understand why my solution for problem B is WA? I'm placing boulders until there is no i that satisfies a[i]<a[i+1] in the array. I tried many test cases which I can do a dry run of but couldn't find where am I going wrong. My Submission

https://codeforces.com/contest/1481/submission/106907738

can anyone tell me whats wrong in the code it is giving wrong answer on test 3.

D

problem E was just amazing !!!

So for the problem E, why if i != l(ai) cant you just leave all ai unmoved and move only those between i and r(ai) same as if i = l(ai) and add dp(r(ai) + 1)?

If you can read Chinese，I'd like to recommend my blog

For problem C, why do you choose $$$b_x \not= a_x$$$? Wouldn't this solution still work if $$$b_x = a_x$$$ as long as $$$b_x = c_m$$$?

Thanks!

Can someone help with this: https://codeforces.com/contest/1481/submission/107022262

I did almost same explained in tutorial, but there is something wrong with my code, it doesn't pass all test cases, it stuck on test case 59 or 3rd set. It shows, that output string isn't a palindrome. Any help effort is appreciated.

Thank you!!

https://ideone.com/hOl1eG

Can anybody tell me the mistake in this solution for problem D. I am getting the following error in test case 3

wrong output format Expected integer, but "YES" found (test case 59)Problem E — Can anyone tell me how to get the answer in 4 moves for the following input? 8 6 6 1 6 3 1 8 8 10, AC program outputs 4.

1: move first 8 to end, 6 6 1 6 3 1 8 8 10 8

2: move 10 to end, 6 6 1 6 3 1 8 8 8 10

3: move first 1 to end, 6 6 6 3 1 8 8 8 10 1

4: move the other 1 to end, 6 6 6 3 8 8 8 10 1 1

Problem B is a good problem but the solution to it is quite bad

Kilani In problem F, when ans == mx + 2, why do you sort the vertex by its size as a subtree out of greed ? Can you explain it

Why does problem A always has to be observant one? Don't have new ideas?????????????????????????????????????????????????????????????????????????????????????