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
Damn, really fast editorial. Thanks, the problems were great!
Problem C was not so good....
really quick
膜
wow -__- fast editional
Boring implementation problems (first 4)
really fast,the editorial was ready while system testing
"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 grammar mistake.
Lets laugh together :)
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
hack:
the ans can be
but your output is
NoThankyou 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...
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
xandyare nodes then they will have value asaandb) and we havemas 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
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://mirror.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).)
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
countis number of bad planks that wants colorb[i]=kthen we need atleastcountpainters that paint colork.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-thpainter wants then in that case there is no answer. if there doesn't exist a plank that wants a color that(m-1)thor 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)thor 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
kare to be processed first and other painters of colorkare extra and they can paint any plank thatb[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
mthpainter 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
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 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 ;(
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://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.
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/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://mirror.codeforces.com/contest/1481/submission/106608493
Thanks for the help man.
Can you tell a counter case for this code as well. https://mirror.codeforces.com/contest/1481/submission/106676613
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!
Failing on the same case, what is different about this case?
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://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.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
106617485 what's the problem with the second test case
$$$k <= 10^9$$$ you're making array of size $$$10^9$$$
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.
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://mirror.codeforces.com/contest/1481/submission/106635785 here, i recoded it with "stack" instead of "vector", and I passed... What happened?
in this piece of code you wrote
i<ninstead ofi<=nwhoops 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:
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=falsesince 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
minstead ofnbut 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.
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://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
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://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
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 .
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 1which 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.
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 :(
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
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
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!!
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
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
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
allah hayou ageed
https://mirror.codeforces.com/contest/1481/submission/288751901
NEED QUICCKKK HELPPP whats causing runtime rror here?
FENCE PAINTING PROBLEM--