Codeforces Round #699 (Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

(Input#4, TestCase #2) 24 24 19 19 19 17 24 7 12 15 11 23 3 11 1 20 10 23 24 1 23 18 23 17 3 7 19 11 19 17 24 7 12 15 11 13 3 11 1 20 10 23 24 1 23 18 23 1 12 7 22 15 3 20 22 11 18 9 10 21 11 2 13 12 10 12 16 11 16 16 12 16 11 1

Comments (153)

Show archived | Write comment?

borgar02

4 years ago, # |

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

→ Reply

HimanshuG

← Rev. 3 →

-64

Problem C was not so good....

Nanako

really quick

inszva

4 years ago, # ^ |

-9

膜

E404_Not_Found

-11

wow -__- fast editional

FatihSolak

← Rev. 2 →

-67

Boring implementation problems (first 4)

lory1608

-15

really fast,the editorial was ready while system testing

DeMen100ns

-86

"DELETED"

dhruv7888

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

bcollet

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.

raysk

Thanks for the contest!

roshan_mehta

-27

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

kassutta

-25

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

qinyihao

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.

huayucaiji

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

euler_3

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

ashish_kumarsoni

Lets laugh together :)

99Harsh

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

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

H8_8Q

+12

hack:

the ans can be

Yes
1 1

but your output is No

Thankyou so much!

Dan4Life

It works for mine, but Im still getting WA

VTifand

Your code fails to pass this:

thnxs for the testcase

sameesevas

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

Test this:

pb_18

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...

code_warrior

-35

Problem C was worst in my veiw

dorjderem

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

ankurverma1994

-6

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.

yuhoooo

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.

kartik8800

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

Please if possible also post a video editorial of C

vioalbert

← Rev. 4 →

+38

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$$$.

antitu

-10

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

JackF

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

utkarshgarg1

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).

Spaniard

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://mirror.codeforces.com/contest/1481/submission/106605351

sirius

Answer:
YES
22 22 22 22 22 2 22 22 22 22 22 22 10 23 22 22 22 22 22 22 22 22 22 22

Problems_AB

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.

sar_1

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.

tlin

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

1
100 10000
1 1 1 ... 1 1 100

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).)

-senshi-

Problem D looks like a graph problem
Editorial — Well yes, but actually no!

rav.gupta

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

Vik

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 106614841

Abdo_Naser

Could anyone tell me what's the difference between the AC code and this 106549562

Samsara_soul

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

if (cnt['L'] >= -x && cnt['U'] >= y)

But in the code

if (cnt['L'] >= -x && cnt['U'] >= -y)

onglu1

+74

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

Warawreh

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.

darknight0409

+17

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

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?

+15

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.

123thunderbuddie

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.

move book with color $$$a[i]$$$ to join the book behind.
keep book with color $$$a[i]$$$ ummove and guarantee $$$a[i]$$$ is the first book on the shelf.

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]$$$.

Legend_of_Azkaban

"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.

Dragnoid99

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.

+13

We are counting books that are "not" moved

$$$dp_i$$$ which will find for each i the maximum number of books that we can leave unmoved in 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.

Sorry, got it, noob error ;(

triccsr

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.

aberent

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://mirror.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.

polar_eagle

Link : https://mirror.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.

rifatrraazz

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://mirror.codeforces.com/contest/1481/submission/106608493

Thanks for the help man.

foxface_ap

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

Thanks man

shubhanshushekharp

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

rananjay23

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

SarthakBansal

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!

yogeshnarang

Failing on the same case, what is different about this case?

gupta_nitin

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

maciaas

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

here is my submission: https://mirror.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.

generic_placeholder_name

+10

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

madhavmittal

-21

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]$$$.

umanggupta1975

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

Himanshusprinto

106617485 what's the problem with the second test case

Satoru

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

ijxjdjd

+61

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 ONLY case where two equal elements can be both inside the chosen and not chosen arrays is if it's at the END of 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.

sadhwanyash66

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

REOI

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

hehepig

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

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

kitsune

Spoiler

in this piece of code you wrote i<n instead of i<=n

for (int i=1; i<n; i++) {
	if (s[i].size()>0) {
		puts("NO");
		return;
	}
}

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

Night_L

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:

the 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 changed

xD in need of help. What's the fault of that code

akcodes

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)

_manvirag

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

Shantanu

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?

wsyhb

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

Gemini7X

Problem D is exciting but problem E maybe too classic?

And also thanks for the quick and good editotial!

anotherTry

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

zzn_nzz

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.

isamad0201

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

Dipesh_DK

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://mirror.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://mirror.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

Ajmain_Abir

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

+16

Then it wouldn't be B :p

shao0320

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?

MohamedK

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

vitkishloh228

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

PsychoPirate

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

hei_sen_berg

https://mirror.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

+11

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 .

D_Coder_03

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:

1
3 2
*ab
b*a
ab*

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.

igorwwylson

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 :(

dedsec_29

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

hurt_FOR_heart

problem E was just amazing !!!

Vanjanja

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

DL-POWER

Can someone help with this: https://mirror.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!!

saurabhldg

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)

soda_bottle

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.

rushtowest

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

Killer250104

3 years ago, # |

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

adityagamer

2 years ago, # |

For question C: Can somebody find error in my code. https://mirror.codeforces.com/contest/1481/submission/158748611

I am assigning last painter to a correct fence. Then I have made req, which stores for each color, which fence needs to be repainted(YES i have excluded the last painter one). Then for each painter if this color needs to be assigned then color that node otherwise color the fence which last painter will paint. If no fence needs to be repainted at last, then answer is YES

MASTERB4APRIL

15 months ago, # |

allah hayou ageed

Gyanpapi

3 weeks ago, # |

https://mirror.codeforces.com/contest/1481/submission/288751901

NEED QUICCKKK HELPPP whats causing runtime rror here?
FENCE PAINTING PROBLEM--

Kilani's blog