Thank you everyone for your participation. Do vote under the Feedback section, and feel free to give your review of the problems in the comments.
Idea: TimeWarp101
Editorial: TimeWarp101
Is it a good idea to have consecutive B
's?
If you space out all the B
's, how many regions do you have to place the R
's into?
What is the best way of placing the R
's into $$$b+1$$$ regions such that the maximum number of R
's in a region is minimum?
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n,r,b;
cin>>n>>r>>b;
int p=r/(b+1),q=r%(b+1);
for(int i=0;i<q;i++) cout<<string(p+1,'R')<<'B';
for(int i=q;i<b;i++) cout<<string(p,'R')<<'B';
cout<<string(p,'R');
cout<<endl;
}
return 0;
}
t = int(input())
for i in range(t):
n, r, b = map(int, input().split())
p = r % (b + 1)
y = ""
for j in range(int(r / (b + 1))):
y = y + "R"
ans = ""
for i in range(b + 1):
if i > 0:
ans = ans + "B"
ans = ans + y
if p > 0:
ans = ans + "R"
p = p - 1
print(ans)
Idea: Newtech66
Editorial: Newtech66
Let's say you don't ever pick a bit. How many times will it get flipped?
If you do pick a bit once at some point, it will get flipped $$$1$$$ less time overall.
To get the lexicographically largest string, you need to make bits $$$1$$$ starting from the left. What is the minimum number of times you have to select a bit to ensure it gets flipped, or stays the same?
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n,k;
cin>>n>>k;
string s;
cin>>s;
vector<int> f(n,0);
int tmpk=k;
for(int i=0;i<n && tmpk>0;i++)
{
if(k%2==s[i]-'0')
{
f[i]=1;
tmpk--;
}
}
f[n-1]+=tmpk;
for(int i=0;i<n;i++)
{
if((k-f[i])%2==1) s[i]='1'-(s[i]-'0');
}
cout<<s<<endl;
for(auto& e:f) cout<<e<<" ";
cout<<endl;
}
return 0;
}
t = int(input())
for i in range(t):
n, k = map(int, input().split())
kc = k
s = input()
f = [0] * n
ans = ""
for i in range(n):
if k == 0:
break
if kc % 2 == 1 and s[i] == '1':
f[i] = f[i] + 1
k = k - 1
elif kc % 2 == 0 and s[i] == '0':
f[i] = f[i] + 1
k = k - 1
f[n - 1] = f[n - 1] + k
for i in range(n):
flip = kc - f[i]
if flip % 2 == 0:
ans = ans + s[i]
else:
if s[i] == '1':
ans = ans + '0'
else:
ans = ans + '1'
print(ans)
for i in range(n):
print(f[i], end = ' ')
print()
Idea: Newtech66
Editorial: Newtech66
Try to analyze the cost of each operation separately. Is there some linearity you can exploit?
Try to make greedy decisions. Can we say that it is always better to move right whenever possible?
Let's say you fix the final position of your capital. Now think about Hint 2.
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol inf=1e18+8;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n;
lol a,b;
cin>>n>>a>>b;
vector<lol> x(n+1),p(n+1);
x[0]=0;
for(int i=1;i<=n;i++) cin>>x[i];
partial_sum(x.begin(),x.end(),p.begin());
lol ans=inf;
for(int i=0;i<=n;i++)
{
ans=min(ans,(a+b)*(x[i]-x[0])+b*(p[n]-p[i]-(n-i)*x[i]));
}
cout<<ans<<endl;
}
return 0;
}
Idea: Newtech66
Editorial: Newtech66
Is there any way to tell how many $$$1$$$s were in $$$A$$$?
Can you tell what $$$a_n$$$ was by looking at just $$$c_n$$$?
Try to simulate removing each $$$B_i$$$ starting from $$$B_n$$$.
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n;
cin>>n;
vector<lol> v(n);
for(auto& e:v) cin>>e;
int k=accumulate(v.begin(),v.end(),0ll)/n;
vector<int> b(n),ans(n,0);
int lf=n-k;
for(int i=lf;i<n;i++) b[i]=n-1;
for(int i=n-1;i>=0 && lf<=i;i--)
{
int cur=v[i]-(b[i]-i);
if(cur==i+1) ans[i]=1;
else if(cur==1)
{
ans[i]=0;
lf--;
b[lf]=i-1;
}
}
for(auto& e:ans) cout<<e<<" ";
cout<<endl;
}
return 0;
}
Try to solve this problem if it is possible for invalid $$$C$$$ to be given as input. This was the original version of the problem, but testers struggled a lot with it. The solution to this is still used in the validator.
Idea: Newtech66
Editorial: TimeWarp101
Can the MEX ever be $$$> 2$$$?
For the MEX to be $$$0$$$, the AND of the walk should be $$$> 0$$$. This implies that some bit is on for all the edges of the walk. How can you check this efficiently?
Make $$$30$$$ graphs, with each graph only containing edges where the $$$i$$$-th bit is on. You can use disjoint sets on these graphs to solve the above problem.
When MEX is $$$1$$$, we know $$$0$$$ exists in the sequence. We need to avoid $$$1$$$ and jump from some other number to $$$0$$$. We need to get rid of the $$$0$$$-th bit while some other bit stays on to ensure we don't get $$$1$$$ in our sequence. This basically means that we need to walk to a node which has an even edge and ensure our AND so far is $$$> 1$$$. Travelling through the even edge would guarantee that our answer is $$$1$$$.
Again, make $$$29$$$ graphs, with each graph only containing edges where the $$$0$$$-th and $$$i$$$-th ($$$i\geq 1$$$) bits are on. Use disjoint sets on these graphs. For each vertex you can note if it is adjacent to an even edge and then store this information in the disjoint set data structure.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
struct dsu {
vi d;
dsu(int n) : d(n, -1) {}
int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);}
void join(int x, int y) {
x = find(x), y = find(y);
if(x == y) return;
if(d[x] > d[y]) swap(x, y);
d[x] += d[y]; d[y] = x;
}
bool is_joined(int x, int y) {
return find(x) == find(y);
}
};
int32_t main() {
fastio;
int n, m; cin >> n >> m;
vector<tuple<int, int, int>> edges;
rep(i, m) {
int u, v, w; cin >> u >> v >> w;
edges.eb(--u, --v, w);
}
vector<dsu> zero(30, n), one(30, n);
rep(j, 30) {
for(auto& [u, v, w]: edges) if(w >> j & 1) {
zero[j].join(u, v);
}
}
vb even(n);
rep1(j, 29) {
for(auto& [u, v, w]: edges) if((w >> j & 1)) {
one[j].join(u, v);
}
vb vis(n);
for(auto& [u, v, w]: edges) if(!(w & 1)) {
vis[one[j].find(u)] = 1;
vis[one[j].find(v)] = 1;
}
rep(i, n) if(vis[one[j].find(i)]) even[i] = 1;
}
auto check = [&](int u, int v) -> int {
rep(j, 30) if(zero[j].is_joined(u, v)) return 0;
if(even[u]) return 1;
rep1(j, 29) if(one[j].is_joined(u, v)) return 1;
return 2;
};
int q; cin >> q;
while(q--) {
int u, v; cin >> u >> v; --u, --v;
cout << check(u, v) << endl;
}
}
Try to solve this problem if the queries were for longest walk instead.
1659F - Tree and Permutation Game
Idea: Newtech66
Editorial: Newtech66
Bench0310 has written another proof for the solution to this problem here and here. Many thanks to him!
Notice that as long as there are $$$\geq 3$$$ elements not in their correct place, Alice can always put at least $$$1$$$ element into the correct place.
Intuitively, Alice should win if the tree is "big enough", because Bob won't be able to reach some places quickly enough. How to define this sense of "big enough"?
Try to solve this problem on a line graph.
It is actually possible to force a sequence of moves to get the $$$2$$$ remaining elements onto the diameter of the tree. Given this, use the answer to Hint 3.
Prove that Alice always wins on trees with diameter $$$\geq 3$$$.
A tree of diameter $$$2$$$ is a star graph. This case has a number of edge cases. This time, try to look at permutation cycles. Can you define some kind of invariant?
#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
pair<int,int> dfs(int u,const vector<vector<int>>& g,int p=-1) //returns {node with max dist,max dist}
{
pair<int,int> res{u,0};
int mx=0;
for(auto v:g[u])
{
if(v==p) continue;
pair<int,int> cur=dfs(v,g,u);
cur.second++;
if(mx<cur.second)
{
res=cur;
mx=cur.second;
}
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
int n,x;
cin>>n>>x;
vector<vector<int>> g(n+1);
vector<int> p(n+1),deg(n+1,0);
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
deg[u]++,deg[v]++;
}
for(int i=1;i<=n;i++)
{
cin>>p[i];
}
//find diameter of tree with 2 DFSes
int diam=dfs(dfs(1,g).first,g).second;
//if diam>=3, Alice always wins
//if diam=1, n=2, have to check if p=[1,2]
//otherwise we have a star graph and cases follow
if(diam>=3) cout<<"Alice";
else if(diam==1) cout<<((p[1]==1)?"Alice":"Bob");
else
{
//we need to check if we have already won or can win in the first move
//this is possible if the permutation is already sorted
//or if there are two marked elements and the chip is on neither of them
vector<int> marked;
for(int i=1;i<=n;i++)
{
if(p[i]!=i) marked.push_back(i);
}
if((int)marked.size()==0)
{
cout<<"Alice";
}else if((int)marked.size()==2 && (x!=marked[0] && x!=marked[1]))
{
cout<<"Alice";
}else
{
//we haven't won yet and it is not possible to win in one move
//cases follow
//first find center, it will have deg>1
int center;
for(int i=1;i<=n;i++)
{
if(deg[i]>1)
{
center=i;
break;
}
}
//is chip on center?
bool chiponcenter=(x==center);
//is center marked?
bool centerismarked=(find(marked.begin(),marked.end(),x)!=marked.end());
//list the cycles
vector<int> vis(n+1,false);
vector<vector<int> > cycles;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
int j=i;
cycles.push_back({j});
vis[j]=true;
while(!vis[p[j]])
{
cycles.back().push_back(p[j]);
vis[p[j]]=true;
j=p[j];
}
}
//min number of swaps
int swapcnt=0;
for(auto& cycle:cycles) swapcnt+=(int)cycle.size()-1;
//parity
int parity=(swapcnt+!chiponcenter)%2;
//cases
if(!centerismarked) cout<<(parity?"Alice":"Bob");
else if(chiponcenter && centerismarked) cout<<"Bob";
else //chip not on center and center is marked
{
//need to check if we can unmark center on first move
//it is impossible if x is on p[center] (since we need to move p[center] to get center
//to the right place, but p[center] is blocked)
bool cannotunmarkcenter=(p[center]==x);
if(cannotunmarkcenter) cout<<"Bob";
else cout<<(parity?"Alice":"Bob");
}
}
}
cout<<endl;
}
return 0;
}
Writing for the ones I solved:
I spent more time on problem B than problems A, C, D combined, although that's mostly my fault.
I think the time you spend on each problem just depends on you, not on the problem's quality. I spent more time on A, than on B or C. Also, I do not get why you say B's implementation was hairy, I didn't have any problems implementing it and the idea was easy to get.
I agree that the idea was very simple. For me personally, I overcomplicated the implementation and ended up falling in a lot of traps. I knew that it was mostly my fault, but I saw that others had similar experiences, so I thought it would be fairly reasonable to bring it up.
Who tf asked?
i asked.
For the problem D, I have the same solution as you. It is pretty hard to explain, because it is a result of making several observations.
The first thing I noticed is that the first number is the (0-indexed) position of the first zero in the original array; n means that there is no zero. That is because we either have a zero there (which will never be replaced) or a one (which will be replaced as soon as we encounter a zero). After thinking for a while, I was able to extend this logic to "if $$$A_i = 1$$$, then $$$C_i$$$ is the 0-indexed position of the i-th zero in $$$A$$$". That's because we will replace 1 with 0 as soon as we find the i-th zero, but no sooner since we first have to set the first (i-1) elements to 0. From this, we infer the first rule: if $$$A_i = 1$$$, then $$$A_{C_i} = 0$$$.
Now what about the case when $$$A_i = 0$$$? Well, if there aren't any 1's before it in A, then (and only then) $$$C_i = 0$$$. Otherwise, it will become a 1 on the i-th step, because it will be the last sorted element. And after that, it will become a 0 again when we add the i-th zero. That means that $$$C_i = Z_i - i$$$, where $$$Z_i$$$ is the position of the i-th zero. Thus, if $$$A_i = 0$$$ and $$$C_i \neq 0$$$, then $$$Z_i = C_i + i => A_{C_i + i}$$$ = 0.
One last thing we need to observe is that after we encounter the first non-zero $$$C_j$$$, we always know $$$A_i$$$ before processing it, because we know the position of the (i-1)-st zero and there is at least one 1 before this point.
How do you prove that this is sufficient?
Essentially, we learn the position of every zero in the array. On all the other positions there can only be ones. So there is only one solution, and we find it.
How can you say that "at all other positions, there can only be ones"?
Because there isn't a zero, and the only other option is one.
Good explanation. Breaking it up into the core "observations" is a good way to put it.
Thank you problem writers for problem B. I enjoyed solving it. Made me get my brain to work for the first time.
I remember seeing blogposts that said A’s are too ad-hocish and if you are new to CP and have no math competitions background you can’t really solve them. And some even suggested that first problems should be more about implementation than about math observations. But yesterday’s A was about pigeonhole principle and outputting such string. So basic math (you may even not know what pigeonhole principle is but you understand it intuitively) plus implementation. However people complained that A is too hard. So may I ask what the hell is going on?
Here is an equivalent version of this rounds problem A that is rated 1500.
https://codeforces.net/problemset/problem/746/D
I suspect the authors were heavily inspired from this problem. So what you are saying is that the rating for problem A should be 1500?
Oh so that why I got WA on A, I'm suck at string problem as usual
And I got the exact idea for B quickly but I outsmarted myself lol
nice problems to training my weak brain.
And i've been struggled on B for more than 30min :)
For Problem D, We can also iterate from left to right in C and determine indexes of 0 in A.
Video Solution : Problem A-D
In the implementation of E, this line seems redundant:
rep1(j, 29) if(one[j].is_joined(u, v)) return 1;
Becauserep(j, 30) if(zero[j].is_joined(u, v)) return 0;
is easier to satisfy than the above.So nice problems for div2.I love them,especially D and E.
Solution for the challenge of problem D:
First, we can check if the sum of values in $$$C$$$ is divisible by $$$n$$$, if not, then the array is invalid. Now, lets just solve the problem considering the array is valid, and later check if the resulting sequence produced by our algorithm can make the array $$$C$$$ or not. The goal is now to solve the reverse problem — we have the array $$$A$$$ and need to create the sums-array $$$C$$$ from it.
I'll assume one-based indexing from here on. Consider finding the sum of ones for an index $$$i$$$ in the array $$$A$$$.
First of all, we check its contribution in the first $$$i - 1$$$ iterations. Until then, $$$A[i]$$$ will remain unchanged, so, if $$$A[i] = 1$$$, then $$$C[i] = (i - 1)$$$, else $$$C[i] = 0$$$.
From iteration $$$i$$$ onwards, $$$A[i]$$$ will also get sorted along with the previous elements. The $$$i^{th}$$$ value in the sorted sequence can only be $$$0$$$ if there are atleast $$$i$$$ zeros in the sequence. So, we need to find the index $$$j$$$ such that $$$A[j]$$$ is the $$$i^{th}$$$ zero in the sequence. We can do this by storing all zero value indexes in a separate array.
From iteration $$$i$$$ and until before the $$$i^{th}$$$ zero has been found, the value of $$$A[i]$$$ will be one. If it is found at index $$$j$$$, then the contribution to $$$C[i]$$$ will be $$$(j - i)$$$. (If $$$i$$$ zeros do not exist in the sequence, then the contribution to $$$C[i]$$$ will be $$$(n + 1 - i)$$$.
So, for each element, $$$C[i] = (i - 1) + (j - i)$$$ if $$$A[i] = 1$$$, and $$$C[i] = (j - i)$$$ otherwise.
It is actually possible to solve it without solving the reverse problem. The solution requires minimal additional casework. But good job.
You can submit your solution for the reverse problem here :P
If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
Can't find a counter test case for my 153997173 of problem D ticket(s) : https://cfstress.com/status/5235 https://cfstress.com/status/5222
You've already used the website to infer that your code runs fine on thousands of small testcases, but only fails on bigger test cases on CF
What's the most popular reason for that? Integer Overflows.
Avoid using fancy stuff such as accumulate, without reading the documentation first
I leave it up to you to figure out why do we need to handle overflows.
Thanks.
Hi guys, I have some wonders and hope to seek for explanations! In problem D:
Submission 1: I use set and get AC -> complexity O(???) (I'm still confused about this)
Submission 2: I use deque and get TLE -> I expect the complexity would be O(NlogN) So I hope you guys will point out for me where did I do wrong.
Sorry for my bad clarifications! Thanks in advance!
I have known why my code got TLE! Thanks!
If any one can help me finding test case for problem D which fails my submission https://codeforces.net/contest/1659/submission/153997173 it will be really helpful it passes almost all smaller test cases it is failing on when n is huge, thanks in advance.(sorry for my bad english)
Edit: no need, found the bug.
Can someone help me figure out why my solution for A is WA'ing?
153898766
Your code fails for the below test case: Input: 12 10 2 Output: RRRRBRRRRBRR Expected Output: RRRRBRRRBRRR According to your code 10 is begin split into 3 parts i.e., 4, 4, 2 whereas optimal division is 4, 3, 3 So we need to split the parts such that Max valued part — Min valued part is as small as possible!
My solution for reference — 153908138
Why does this matter, both have a maximum of 4?
You can look at the testing details, the failed test isn't that long. Your solution uses too many R's in the beginning, which leads to a large cluster of B's in the end.
Can someone explain how to solve problem C, I having hard time following tutorial!
In solution of D, paragraph 5, every case after "Otherwise" word is very ambiguous. Can someone explain with correct grammar please?
Now consider the last element in array A
i think i solve C in another greedy way. here it is. code
the key is to see change location as saving money for further conquer. so every iteration i compare how much to change location(c2) and how much i can save(c1). if c1 < c2, that means worthless to change. otherwise, let's do change. though it get AC, i'm curious about this greedy correctness.
hope for some help
In problem B, why is it correct to add all remaining moves to the last element? What if the number of remaining moves is odd? I just cant figure out how to prove the remaining number be even.
The remaining number can be odd and it may make the last element go from 1 to 0, but since we want lexicographically maximum, its better to have the earlier element maximum, and then use the remaining moves on last.
can anyone please tell the DP approach of problem C
Define $$$dp_i$$$ to be the minimum cost to conquer all kingdoms upto the $$$i$$$-th one and end with your capital there. The base case is $$$dp_0=0$$$. The transition is
This can be implemented naively in $$$\mathcal{O}(n^2)$$$ time.
However, rewriting it as
allows you to use the convex hull trick. The line to insert is given by $$$y=mx+c$$$ with $$$m=-bx_j$$$ and $$$c=dp_j + b \cdot (jx_j-p_j) - a \cdot x_j$$$. The set is evaluated at the point $$$x=i$$$.
The answer is given by
Thus the time complexity becomes $$$\mathcal{O}(n\log{n})$$$.
Can someone please tell the approach to solve this question through dp. I am trying through dp but it is getting TLE in Test Case 5 .
my dp code is
ll dp[100002];
long long solve(int i ,int i2){
long long cost =0;
if(i>n)return cost;
if(dp[i2] != -1)return dp[i2];
}