Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve(){
int N;
cin>>N;
//note: 1<<X means 2^X
//we put largest coin in first pile
int sum1=(1<<N), sum2=0;
//we put n/2-1 smallest coins in first pile
for (int i=1;i<N/2;i++)
sum1+=(1<<i);
//we put remaining n/2 coins in second pile
for (int i=N/2;i<N;i++)
sum2+=(1<<i);
cout<<sum1-sum2<<endl;
}
int main(){
int t; cin>>t;
while (t--)
solve();
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve(){
int N,K;
cin>>N>>K;
set<int>s;
for (int i=0;i<N;i++){
int a;
cin>>a;
s.insert(a);
}
//if more than K distinct numbers, print -1
if (s.size()>K){
cout<<-1<<endl;
return;
}
cout<<N*K<<endl;
for (int i=0;i<N;i++){
//print the distinct numbers
for (int b:s)
cout<<b<<' ';
//print the extra 1s
for (int j=0;j<K-(int)s.size();j++)
cout<<1<<' ';
}
cout<<endl;
}
int main(){
int t; cin>>t;
while (t--)
solve();
}
1348C — Phoenix and Distribution
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n,k;
cin>>n>>k;
string s;
cin>>s;
sort(s.begin(),s.end());
//if smallest k letters are not all the same, answer is kth smallest letter
if (s[0]!=s[k-1]){
cout<<s[k-1]<<endl;
return;
}
cout<<s[0];
//if remaining letters aren't the same, we append remaining letters to answer
if (s[k]!=s[n-1]){
for (int i=k;i<n;i++)
cout<<s[i];
}
else{
//remaining letters are the same, so we distribute evenly
for (int i=0;i<(n-k+k-1)/k;i++)
cout<<s[n-1];
}
cout<<endl;
}
int main(){
int t; cin>>t;
while (t--)
solve();
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve(){
vector<int>inc;
int N;
cin>>N;
//construct sequence 1, 2, 4, ... while sum <= N
for (int i=1;i<=N;i*=2){
inc.push_back(i);
N-=i;
}
//if sum is not N, we insert and sort
if (N>0){
inc.push_back(N);
sort(inc.begin(),inc.end());
}
cout<<inc.size()-1<<endl;
for (int i=1;i<(int)inc.size();i++)
cout<<inc[i]-inc[i-1]<<' ';
cout<<endl;
}
int main(){
int t; cin>>t;
while (t--)
solve();
}
Tutorial
Tutorial is loading...
Solution
//Solution 1
#include <bits/stdc++.h>
using namespace std;
int N,K;
int a[505],b[505];
bool dp[505][505]; //number of shrubs considered, "extra" red berries
int main(){
cin>>N>>K;
long long totA=0,totB=0;
for (int i=1;i<=N;i++){
cin>>a[i]>>b[i];
totA+=a[i];
totB+=b[i];
}
dp[0][0]=true;
for (int i=1;i<=N;i++){
for (int j=0;j<K;j++){
//leave a[i]%K extra red berries
dp[i][j]=dp[i-1][(j-a[i]%K+K)%K];
for (int l=0;l<=min(K-1,a[i]);l++){
//check if we can leave l extra red berries
if ((a[i]-l)%K+b[i]>=K)
dp[i][j]|=dp[i-1][(j-l+K)%K];
}
}
}
long long ans=0;
for (int i=0;i<K;i++){
if (dp[N][i])
ans=max(ans,(totA+totB-i)/K);
}
cout<<ans<<endl;
}
Tutorial
Tutorial is loading...
Solution 1
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9+7;
int as[200005], bs[200005];
vector<pair<int,int> > start[200005];
int ans[200005];
int where[200005];
int N;
void show(){
for(int i=1;i<=N;i++)
cout<<ans[i]<<' ';
cout<<endl;
}
pair<int,int> st[400005];
int query(int l,int r){
l--;
pair<int,int> res{INF,INF};
for(l+=N,r+=N;l<r;l>>=1,r>>=1){
if(l&1) res=min(res,st[l++]);
if(r&1) res=min(res,st[--r]);
}
return res.second;
}
int main(){
cin>>N;
for(int i=1;i<=N;i++){
cin>>as[i]>>bs[i];
start[as[i]].push_back({bs[i],i});
}
set<pair<int,int> > active;//(right,index)
for(int i=1;i<=N;i++){
active.insert(start[i].begin(),start[i].end());
ans[active.begin()->second]=i;
where[i]=active.begin()->second;
active.erase(active.begin());
}
for(int i=0;i<N;i++){
st[i+N]={as[where[i+1]],i+1};
}
for(int i=N-1;i>0;i--){
st[i]=min(st[i<<1],st[i<<1|1]);
}
for(int i=1;i<=N;i++){
int j=query(i+1,bs[where[i]]);
if(j==INF) continue;
if(as[where[j]]<=i){
cout<<"NO"<<endl;
show();
swap(ans[where[i]],ans[where[j]]);
show();
return 0;
}
}
cout<<"YES"<<endl;
show();
}
Solution 2
#include <bits/stdc++.h>
using namespace std;
int N;
int a[200005],b[200005];
int label[200005]; //the label of the person at i-th position in our perfect matching
int label2[200005]; //which position the i-th person is at
void perfectMatch(){ //finds a perfect matching
deque<pair<pair<int,int>,int>>v;
for (int i=1;i<=N;i++)
v.push_back({{a[i],b[i]},i});
sort(v.begin(),v.end());
multiset<pair<int,int>>mst;
for (int i=1;i<=N;i++){
while ((int)v.size()>0 && v[0].first.first<=i){
mst.insert({v[0].first.second,v[0].second});
v.pop_front();
}
//match person with label to earliest ending interval
label2[i]=mst.begin()->second;
label[mst.begin()->second]=i;
mst.erase(mst.find(*mst.begin()));
}
}
set<int>active;
int vis[200005];
int from[200005];
int ans[200005];
void foundAnother(int node, int nextNode){
vector<int>v;
int cur=node;
//backtracks on cycle to find other ordering
while (cur!=label2[nextNode]){
v.push_back(cur);
cur=from[cur];
}
reverse(v.begin(),v.end());
v.push_back(label2[nextNode]);
reverse(v.begin(),v.end());
cout<<"NO"<<endl;
for (int i=1;i<=N;i++)
cout<<label[i]<<' ';
cout<<endl;
for (int i=1;i<=N;i++)
ans[i]=label[i];
int temp=ans[v.back()];
for (int i=0;i<(int)v.size();i++)
swap(temp,ans[v[i]]);
for (int i=1;i<=N;i++)
cout<<ans[i]<<' ';
cout<<endl;
exit(0);
}
void dfs(int node){
//activates node
vis[node]=1;
queue<int>toRemove;
for (;;){
//binary search for unvisisited neighbor
auto it=active.lower_bound(a[node]);
if (it!=active.end() && *it==label[node]){
toRemove.push(*it);
it++;
}
if (it==active.end() || *it>b[node])
break;
if (vis[label2[*it]]==1) //found cycle (another ordering)
foundAnother(node,*it);
toRemove.push(*it);
if (vis[label2[*it]]==2)
continue;
from[label2[*it]]=node;
dfs(label2[*it]);
}
//removes visited nodes from set
while (!toRemove.empty()){
if (active.count(toRemove.front()))
active.erase(toRemove.front());
toRemove.pop();
}
//deactivates and retire node
vis[node]=2;
}
int main(){
cin>>N;
for (int i=1;i<=N;i++)
cin>>a[i]>>b[i];
perfectMatch();
for (int i=1;i<=N;i++)
active.insert(i);
for (int i=1;i<=N;i++)
if (vis[i]==0)
dfs(i);
cout<<"YES"<<endl;
for (int i=1;i<=N;i++)
cout<<label[i]<<' ';
cout<<endl;
}
Wow! I didn't expect the editorial published so fast.
Yeah, I also didn't expected this fast Editorial! XD
Thanks for the fast editorial!
Video solutions:
Berries pls
Thanks
thanks
Hello, i didn't understand why we insert n-s at last and sort it.Can you explain?
Thanks for making a youtube channel for this.
Thx!
Editorial so early -.-
Wow, it was very good contest. Fast editorial, cool tasks with short conditions. Thanks!
Damn
I feel so stupid after seeing the solution for B
Nice problems man!
Can anyone recommend practice problems for constructive
I really suck at it
I suck at them too. Hate constructive. Downvote the author for making so bad B
Nahh B isn't bad
We just suck XD
Perhaps that mindset is one of the reasons you are hardstuck Specialist. Never blame the problem, only blame yourself for not practicing enough. With this mindset, improving quickly suddenly becomes much easier for anything you do :)
Can u pls explain why we go upto n*k.. I did it that way but not getting how its working
We need to print at least
nnumbers. Printingkof the numbers (if all unique) orcunique numbers andk - c"1"s (or any other digit) (wherecis the number of unique elements) will guarantee that you print all numbers in the input, which is required in the output whatsoever be the insertions you make. The primary goal of constructive problems is to come up with something simple that does the job. You could go all in and actually calculate the sum of first k numbers and then go about trying to solve the problem, but that just makes life a lot lot harder.Sire, I've a doubt in part B. When we store element in set, elements are reordered. So when we output the elements, order may be different than what is in the original array. Since we want to preserve the order, how will it work? Thanks.
you don't need to preserve order. you have set n times: [][][]<- denote set 3 times. let say you need 413 as subsequence. because in each set you have each unique element, you can remove everything from first [] except 4, from second [] remove everything except 1, from last [] remove everything except 3. And, by definition resulting is subsequence, subsequence it's anything you can get by removing elements.
You can think it like this :
Suppose
k=3and the sequence is4 3 4 2So, you need to make a new sequence with period 3 basically.You can make a set with distinct elements from the original sequence and of length 3, like
(2,3,4). Now, you just replace every element with this small sequence. You'll get -(* represents the elements in the original sequence)
No, It was a great problem Just needed to think in another way :/
Why downvote author try to do it.
Instead of blaming the author, you should focus on practising more.
Stop giving advice when you become just become specialist first time. No one asked for it.
Now you are criticising me instead of practising more. That's the reason for your fall. And yes, I become an expert first time with my own potential. And I didn't blame anyone when I was falling. I was seeing my mistakes and was improving them. You should try this too.
WTF retard. You are not expert you are barely specialist. And no one cares for advice unless you are candidate master or above. SO pls gtfo
You too are not eligible to decide the quality of the question, so better you Fuck Off and start practicing.
Please, respect others at least.
are you shit!!!...... suraj_gupta is right..... and i am watching your every comment.... why giving so much hate ....... you were not able to solve problem during contest then it is your problem not of Author.... Around 10000 peoples had solved it... nd you are accussing author for your fault....
The worst people are those who have not very high rating,looking down upon those who have lower rating,but diligent guys
seriously you want to blame him for doing so bad in the contest yourself. That's ridiculous.
In the last contest by dreammoon, the problem div2 C was excellent read its tutorial. It is more like a general way to solve any constructive algo. problem that will help surely. https://codeforces.me/contest/1330/problem/C
Constructing is so hard for me. I haven't been used to it.And I have to admit that I am too scared to solve it LOL.
A very good editorial indeed and how come you guys publish it so fast..?
Secret: I prepare it beforehand :)
Very Good explanation and comments were great at C problem :D Thanks a lot <3
Thanks for ruining ratings with bad problems
You seem to be really asking for trouble, don't ya? Go and watch me on Demon Slayer, you'll learn a thing or two about persistence girl.
- Inosuke Hashihabara, Demon Slayer Corps.I saw demon slayer but left after 3 episodes it's boring
You left before my entry, of course, it must have been boring.
Bruhhhh, this is magic! Great contest and the fastest editorial ever....
In addition:
In problem C we can reduce the time complexity to
O(N)by using arrayint charCount[26];(due to the small alphabet size) instead of explicitstd::sort.p.s. thanks for the fast editorial.
If Anyone needs further information check Count Sort
Video Editorials for today's C and D
C
D
Enjoy watching!
Very nice contest! Problem statements were succinct and the editorial was published so quickly! :)
is it rated ?
Yes,
See the second line of the announcement.
I am just finding your reply's for downvote them xd)):
I think there is an error in solution C.
It should be
returninstead ofcontinue;Thanks, fixed
Can anyone think of a counterexample for this solution to E?
Sum up all the red berries and make as many baskets as possible. There are $$$r$$$ (at most $$$k-1$$$) unused.
Sum up all the blue berries and make as many baskets as possible. There are $$$b$$$ (at most $$$k-1$$$) unused.
This is already almost optimal: there are at most $$$2k-2$$$ unused berries. We can get at most $$$1$$$ basket out of these. Said basket only exists under the following conditions:
This way, we leave as few berries unused as possible.
My code fails on test case 10, and I think it's a problem with the algorithm and not my code. Here's Haskell: 78739086. Here's C++: 78744165
Test:
Your answer : 4
Correct answer : 5
Thanks!
You are almost correct, but you miss some cases.
You might have to find more than one shrub, where the red berries add up to x, and the blue ones add up to y. You are only checking the case where it's a single shrub.
But we can take both kind of berries from one shrub only, isn't it or did i not get you correctly ?
You can only put berries from one shrub into a single bucket (if they're of different colors) but you can use multiple buckets.
For example, in the example above, you can take 5 red, 1 blue from the first shrub, and 3 red 3 blue from the second shrub. The remaining 18 red berries can go into 3 buckets, for a total of 5.
I still dont get it. you aren't using the r and b remaining berries after grouping all the red and blue berries separately.
I think it would be nice to comment my approach to E and the way i thought about it.
Lets say we have some vectors in a plane, lets define a modular plane as a plane such that if we are in $$$[x, y]$$$ then $$$0 \le x,y \lt k$$$, also if the condition doesn't holds then we go to $$$[x\space mod\space k, y\space mod\space k]$$$(a positive modular), we want to see if we are able to choose some of vectors to reach $$$[x, y]$$$ such that $$$x + y \lt k$$$, starting at $$$[r, c]$$$. Also each vector is labeled with a number $$$i$$$, we cant choose two vectors with the same label, there are $$$n$$$ labels at most.
We know that a vector $$$x$$$ coordinate plus its $$$y$$$ coordinate is equal to $$$k$$$(each vector means how many reds we chose and how many blues we chose from a $$$i$$$th shrub). The problem is not easier, but it can help you understand the logic behind the problem and the solution, at least it helped me. Also if you start from $$$[r, c]$$$, you cant reach $$$[x, y]$$$ such that $$$(x+y) \ne (r+c) _{mod \space k}$$$.
What is
randcand what does x and y represent?$$$r$$$ is number of reds modul $$$k$$$ and $$$c$$$ is number of blues modul $$$k$$$, $$$[x,y]$$$ is coordinate of a dot or a vector(coordinates of a vector is the coordinates of the endpoint of the vector when its moved to region)
Woah editorial published very fast! Thanks FieryPhoenix for the contest <3
I didn't expect C to be that simple. Nice problems!
Can anyone explain mass increase from x to 2*x part from D ?
There are $$$x$$$ bacteria. If you split none, mass total will increase by $$$x$$$ that night. If you split all, mass total will increase by $$$2x$$$ that night. So, the mass increase will be between $$$x$$$ and $$$2x$$$ inclusive depending on how you split.
Can we prove that it is possible to acquire all the values in the range $$$[x,2x]$$$?
Let's say there's
xbacteria of massm. Total mass:x * mAt night, it's mass (single bacteria) becomesm + 1. Now, consider if it split before the mass increase. Now, there are2 * xbacteria of massm / 2. At night, the total mass becomes (for one bacteria):m / 2 + 1. The total increase:Final mass - Initial mass: 2 * x * (m / 2 + 1) - x*m = 2 * x. This is only if allxbacteria split. If none split, total increase will bex(as every bacteria mass increases by 1). So, increase will be in the range $$$[x,2x]$$$You make good problems.
I like the format giving solution along side with tutorial is really helpful.otherwise sometimes get stuck with tutorials only.
It is really great that you prepared editorial 6 days ago && published score distribution day before round. Huge thanks for this! (and problems were good as well too)!
I couldn't solve a single question today.
I was totally blank.
But I, cherished the time I used to read each beautiful problem.
And, now this well written editorial and code with comments!
Best contest experience I have had till now !
Kudos to the author for his time and efforts !!
Great to hear, thank you!
Could someone please help me understand why the following claim is true for problem E? The author states "Note that if we know that there are j extra red berries, we can also easily calculate how many extra blue berries there are." How would we calculate the number of extra blueberries from the the number of extra redberries?
If there are $$$t$$$ total berries and $$$r$$$ extra red berries, there will be $$$(t-r)$$$ $$$mod$$$ $$$k$$$ extra blue berries. This is because all the other red berries are already filled in some baskets, and if there are many extra blue berries they can fill their own baskets too.
I get it now. Thank you!
I had to give contest on m2.codeforces.com......codeforces was running very slow.
In Div2-B, why is no solution possible if there are more than k distinct integers?
if there are more than K distinct integers, then there will be at least two subarrays whose sum will be different and they can't be made equal by inserting any numbers from 1 to n
Suppose, n = 2, k = 1 & array = {1,2} why the answer is -1? According to the statement answer can be m = 2, array = {1,2}.
your answer {1,2} has two subarrays of length 1 , {1},{2} , and their sums are 1 and 2 and since they don't satisfy the condition given in the problem , it is incorrect.
and since {1,2} can't be made periodic with period 1 , answer will be -1
below PoIar_ has explained why the answer must be periodic with period k
You want to make an array such that every subarray of length $$$ k $$$ has the same sum.
Let $$$ s $$$ be the sum of the first $$$ k $$$ elements of array $$$ a $$$. You can tell that $$$ a[k+1] = a[1] $$$ so that the subarray from $$$ 1 $$$ to $$$ k $$$ and the subarray from $$$ 2 $$$ to $$$ k+1 $$$ have the same sum $$$s$$$.
With the same idea, you can see that the array must have a period of $$$ k $$$. Thus, once you choose the first $$$ k $$$ elements, you can only repeat them. That's why you can have at most $$$ k $$$ distinct numbers.
The period has to be k so you can't put more than k distinct integers in one period.
can anyone explain what does max(a1,a2,..,ak) means in problem C ?
The largest lexicographically among the strings $$$a_1, a_2, \ldots, a_k$$$.
The maximum among all these strings a1, a2, ..., ak
Author does everything to satisfy participants. Thanks for such a pleasant contest.
I don't understand this. Is the sequence just $$$1,2,2^2,…,2^x$$$ such that $$$1+2+2^2+...+2^x \lt = n$$$?
Also, if you can simply insert $$$n-s$$$, then does the case of $$$-1$$$ never arise?
Yes. Because they are the increase in mass. So the sum must be
s <= nYou can see that we can just wait without splitting to gain every possible integer.
OK, thanks. Still no idea how someone is supposed to come up with this during the contest.
You don't need to use exactly this approach. You could get intermediate value in various ways.
For example, you could at some point decrease number and check is it still possible. To make clear this approach:
It's binary descent. If you always generate all next terms, it works in $$$O(log^2(n))$$$ in terms of the task. In this way you get lexicographically smallest sequence. It's very easy to write using recursion.
My solution was much simpler in understanding, but harder to write. First I get
Example of normal step:
I'm unsure if it even happens to have so long tail, but I don't care.
Example of last step:
Last step proof: if you can't reduce all equal ones in the end, it means that number of them is greater than difference with goal, it means you can reduce them one by one and get goal.
I made this solution in $$$O(log^2(n))$$$ in terms of the task. The only reason why it wasn't $$$O(log(n))$$$, because I was lazy, so I was filling tail of similar numbers after each change. Code: 78742069
Thanks, I will try to understand your approach. By binary descent, I suppose you mean binary search? Or is it different? (Couldn't find anything about binary descent).
Look here https://codeforces.me/blog/entry/76555?#comment-613830
Ah... about binary descent... It's called so when you have some tree of decisions and you descent to some leaf. You can represent all outcomes here as tree like that. Why I said binary? Because either you have binary tree or you can do binary search. Sorry, looks like it's my own name of it :(
And impossible case doesn't exist.
I had a bit different approach. If it was possible to split all bacteria, we will split them.Now how to check this, Consider there were K bacteria and W total mass at some stage, if W + 2*K >=n than we can directly reach n in n-W splits. Else if W + 4*K >=n than we can do it using 2 splits minimum and for every other case we split all of them. Link to my submission
Yes, but make $$$x$$$ as big as possible.
Yes. It is always possible to find a sequence. Easy proof: if you never split your first cell, then after $$$n-1$$$ nights the cell has weight $$$n$$$. (Obviously that is not the shortest sequence)
Editorial is good.
hey guys .. how did you solve problem A ... look over my solution 78745046 dp Solution lol
My solution:
You can divide items into two piles as follows: first stack: $$$2^1, 2^2, \ldots, 2^{\frac{n}{2}-1}, 2^n$$$, second stack: others. This split minimizes the sum difference. This is easy to prove because if one of the piles contains $$$2^n$$$, even if the other contains all the others it would have a smaller amount (because: $$$2^n = 2^1 + 2^2 + \ldots + 2^{n-1} + 1$$$). However, stacks must contain the same number of elements, so it is prudent to add minimal elements to a larger stack ($$$2^1, 2^2, \ldots, 2^{\frac{n}{2}-1}$$$).
And code: 78663445
i think this is the optimal solution good job
this is very funny solution great job .... i think no one solve it using dp there is much easier solution
Judging by the fact that D is rated higher than C despite having a very simple solution with Div2B-ish implementation, (some of) your testers seem to have had similarly over-complicated approaches as me — that makes me feel a little less stupid! Thanks, testers!
Also thanks to Fiery of course, very nice problems!
The editorial has been published very fast, just after the contest. Wow!! The problems were cool..........
what does this mean? how do we know that resultant sequence is even possible?
We have a sequence $$$1, 2, \cdots, 2^x$$$. Note that $$$n-s$$$ does not exceed $$$2^{x+1}$$$. So, inserting $$$n-s$$$ and sorting cannot break the condition: $$$a_i \le a_{i+1} \le 2a_i$$$.
got it. thanks for clarifying
B and D were beautiful! :)
In the solution of Problem
Cif remaining letters aren't the same, we append remaining letters to answerI don't understand why does it works :(
Consider
aaabbbcsplit into 3. We're gonna put all 3as into each split, so our remaining string isbbbc.Dividing evenly gives
ab ab abcwhich won't work. It's easy to tell thatab ab abcisn't as good asa ab abbcbecause the only thing we care about is thatabbc<abc.So we take it to the extreme and throw everything into one, with
abbbcas our answer, so that we push thatcbehind as many lexicographically-lesser characters as possible.someone please explain why one of the test case of DIV.2 b is failing in the codeforces judge while it is running correctly in my local ide the link is:-https://codeforces.me/contest/1348/submission/78736417
Try debugging it using random print statements on codeforces custom test.
There maybe an initialisation error.
First time reading the kind of solution in Div2E. Can someone explain in a possibly detailed manner? I don't get how you can derive the number of extra blue berries from the extra red berries.
Nice, E seems to have no testes against n^4 solution//
There are only $$$O(nk)$$$ total reachable states so optimized $$$n^4$$$ solutions are not actually $$$n^4$$$.
lol, yes, sry
I knew I was stupid after I saw the solution to B. But the solution to C was a facepalm. And to think, I thought the contest was hard. The questions are excellent and well made; they just require us to get a click....
Just 'a click'
Kudos to FieryPhoenix for very interesting problems!
FieryPhoenix Problem: 13348B , My_submission:78741637 For the input : 4 2 (n, k), 2 1 1 2 (n distinct number) My output was : 5 (array length), 1 2 1 2 1 (output array). But it shows wrong. Why?
look the given array is 2 1 1 2 but in your output there is no sub-sequence of that array.. there should be sub-sequence as 2 1 1 2 in the output array.. you can't delete anything from the given array..you can just add numbers in between them.. like the given array is 2 1 1 2 the answer could be : 1 2 1 2 1 2 look at the answer array — you can choose a sub-sequence which is the given array (2 1 1 2) .
so,your answer must contain the given array as a sub-sequence. I hope you got it.How to think for problem like C . I mean seeing min of max() made me think it is binary search over something. Then I thought it being dp .How do we proceed ahead rejecting this ideas and think of case based solution ?
Put aside ideas that doesn't give any approaches for some time span. You have to have some heuristic how long you may think about idea. Revisit ideas.
Personaly, it was obvious that each string has to have letters in sorted order. Because, otherwise we could sort them and string would be smaller. Then I stucked for some time. First good observation for me was: let say string s is answer, then if there some string s' in the list for which some prefix is less than prefix of same length of s, then we can reduce length of s moving letters to s'. Carefully thinking about 'when can we do that', brought me to hypothesis that it's possible only when answer is single letter. Carefullly thinking 'why always single letter' (it's not true) and comparing to samples got me to right list of cases.
My O(N) greedy passed for E: https://codeforces.me/contest/1348/submission/78740802
My logic was this: The final baskets can be divided into two categories: those that are homogenous (i.e have only red or only blue berries) and those that are heterogenous (i.e can have both red and blue berries). The heterogenous baskets are obviously from the same shrub.
Now, we will run two different greedy solutions. In the first solution, we will prioritise making heterogenous baskets. That is, for each i, add (a[i] + b[i])/k to the answer and then leave the remainder for homogenous baskets. With the remainder, I have just prioritised making homogenous A baskets and then made whatever homogenous B baskets are possible at the end.
In the second solution, we will prioritise making homogenous baskets. That is, add (sum of a[i])/k + (sum of b[i])/k to the final answer. Then, find an i such that min(a[i], remainder of a) + min(b[i], remainder of b) >= k. If you find such an i, add 1 to the answer. Otherwise leave as is.
Finally, take the max from both solutions and output it.
Hacked
I think this should fail too: 78774283
the testcases don't seem good...
Hacked. Admittedly, making tests for problem E was very hard because random tests were ineffective, so many of the tests were added through stress testing. As you can imagine, it is very hard to stress against every possible greedy...
yes i see, i just hope no one passed system tests with stuff like this: 78775314
I don't know how complicated it is to find a hack for this one...
Hacked by generating about $$$100,000$$$ random cases with $$$n,k,a,b$$$ in $$$\{1,...,11\}$$$.
It's really hard to find a counter-example for such multi-greedy solutions. In $$$100,000$$$ random cases, usually only $$$1$$$ or $$$2$$$ that program failed. :(
Yep I understand. Great problems though, thanks for the contest.
I used a simpler approach with D,
Observations —
Number of partitions + 1 will always increase each night
so I have to create minimum array possible that sum up to n, which is in increasing order and each element is less than it's max possible at that point which is simple as 2^i as ith night (0 indexed)
now keep maximum possible element fulfilling those condition.
and for actual solution number of partitions each night just take adjacent difference between elements.
My sol — 78714792
Hey! Can you please explain this part (if condition) in your code?
This is the case when we will select maximum possible value for that position i(value = 1<<i) but the next value will be less than that so we equally divide remaining difference between last and second last term
example n = 9 -> ans = [1, 2, 3, 3] , sol = [1, 1, 0]
I am unable to understand div2 C .Can anybody explain it. Thanks in Advance
Editorial is very clear.
Hello!. Can someone tell me why this solution is wrong for E. It fails on test 73
I commented the code so is easy to understand.
What I am trying to do is a dp(i, r) = {maximun number of full_boxes from i to n-1, maximum number of unused blue berries}.
So in each state I try all possible values from [0, k-1] of red berries that I want not to merge with the same shrub (then this one will be merged with r).
At the end the answer should be dp[0][0].first + dp[0][0].second / k
check my submission
Can anyone please explain why the greedy strategy mentioned in problem D works(i.e to take summation till 2powerx and repeat same for n-s) by working I mean proof that it is optimal
There is a typo in problem D. The complexity should be O(nlogn).
$$$n \log n$$$? $$$n$$$ goes up to $$$10^9$$$.
Oh, I didn't read carefully, and thought
nis the length ofinc. Since the length ofincis O(logn), the complexity isO(lognlog(logn))?If you sort using insertion (since we are only adding at most one number), the complexity is still $$$O(logn)$$$ I believe.
I see. Insertion here means insertion sort. Thanks for clarification.
insertion sort isn't nlogn for array of n size? logn(log(logn)) isn't right why?
Insertion sort has complexity O(N^2) in general. But here we construct a sorted array in O(N) and insert (at most) one more value at the end. A single insertion operation is O(N) with respect to the size of the array. And since the size of the array is O(log(N)) with respect to the original n from problem statement, so is the time complexity.
In the solution given we are using sort(inc.begin(),inc.end()) and this sort uses quick sort right? quick sort takes nlogn for size n, so our array length is log(N);
so time complex -> log(N)*log(log(N))
isn't this right??
Sorry, I did not read the code, only the tutorial text.
Yes, you are right: if we use the STL function, then that is the right complexity. And if we use insertion, as suggested in the tutorial (but not implemented in the code), then the complexity is linear. These are 2 independent statements, not conflicting with each other.
For problem E, What is the memoisation approach, if any?
This is my solution 78781631, pretty much the same as the editorial solution except it's memoisation. Be aware this approach TLE'd for me, so I had to optimize a bit.
My solution is a bit different than the one explained in the official editorial.
can you explain why there is no need of memoising the variable 'g' in your code in the dp array?
Explanation
For a given value of x and r, the value of g will always come out to be same.
In other words:
If we know the number of red berries that are being passed on to the
X + 1th shrub, we also know the exact number of blue berries that are being passed along with those red berries. Therefore we do not need to keep track of number of blue berries passed, i.e, we do not need to consider B as another dimension in states of DP.Number of blue berries passed = (Sum of total number of berries in each shrub starting from 1st shrub ending at Xth shrub — Number of red berries R passed onto (X + 1)th shrub) % KI think your codes complexity is O(NK), am I correct? btw thanx for the response, it helped a lot!
No, it's O(N.K^2)
But your DP array is of size O(NK)? could you please explain how?
Oh I got it! thanks for the response!
There's a loop inside each function call f(i, 1, min(a[x] + 1, k)) { }
My submission for problem B is always wa,I'm really disappointed,can anyone help me?https://paste.ubuntu.com/p/9Xftz94CM7/
here
OK,I use the char,which caused non-digits
Why does D have a binary search tag, is there a way to solve this using binary search? Anyone?
Here is a link to my submission: 78773066 I have solved it using binary search.
Suppose at any instance, we have N no of bacteria adding up to a sum S, Then it is clear we can reach the states, with sum = [S+N, S+2*N] from the current instant/stage. This is already explained in the editorial.
We can binary search over this range, at every stage, to find the biggest next state which leads us closest to the destination 'n' and appropriately update the result.
Awesome technique!
I think sum = [N+S, N+2*S], should rather be sum = [N+S, 2*N+S] .
Thanks a lot though!
Assume a state, of sum 3 and no of bacteria 2, then we can can reach the states which have sum in the range [5-7], i.e, [3+2, 3+2*2]
That's right, tho you have written 2*sum rather than 2*no. of bacteria. Was just mentioning to correct it :)
Whoops! apologies for overlooking it twice!! Thanks
This uses the same principle but I am finding the value greedily. Although I have to mention that during contest it would require more thought.
It was a nice set of problems! However, I think that the time limit for problem E was too strict. I understand that a O(nk^2) recursive solution may not be fast enough, but I saw some iterative O(nk^2) solutions getting TLE (including mine).
Yes, I also got TLE on test 33. When I try to use as least as 'long long' as possible, I got AC
Oh, I can't believe it, 1934ms AC after changing that. Thank you!
No offence to problem authors problems were quite elegant but in general I have observed too many constructive algorithm based problem these days. Why the problem setters are focusing on it so much is there any specific reason to include lots of constructive problems in the contest. Or constructive problems are intutive to be prepared. or some other reason exists for this please share your thoughts
No offense taken :) . I am not sure about other problem setters but personally, I did not specifically intend to have many constructive problems. But, the problems in my round covered a diverse range of topics: strings, math, dp and more. The constructive part just happened to come with the problems.
I think constructive algorithms are very closely associated with logical thinking, so learning to solve them increases your problem solving skills. Personally, I quite like constructive problems because they allow you to be more creative (for the most part).
yeah I agree with you problems were really amazing. Even B was very elegant though I solved it too late. But I liked solving B.now I am upsolving other problems.
How we can solve to minimize the length of beautiful array (problem B) if we want to. (In the question ,it was told that we don't need to minimize the length).
The solution for 1348C — Pheonix and Distribution will fail for the case where
k = n. This is because there is no check forn == kin the part below.This will result in out of bounds error/segmentation fault.
The value at the end of the string $$$s[n]$$$ is defined, and is in fact
'\0'. So, this works out.See http://www.cplusplus.com/reference/string/string/operator[]/ for more technical details.
Problem E: Has tag greedy. First line in tutorial: No Obvious Greedy Solution. Is it that complex to implement greedy in it?
There shouldn't be any greedy solutions since the special case where the first shrub has only $$$x$$$ red berries, the second shrub has only $$$K-x$$$ blue berries, and the remaining shrubs have exactly $$$K$$$ berries (of either color) is a knapsack variant.
The greedy tag might be because some ppl might have used a greedy observation to optimize their DP solution.
A different approach for D (binary search):
Claim: If answer is 'd' then you can always find the answer by splitting all bateria till d — 3 days, then on d-2, d-1 you split only m, k bacteria. One can find m, k using binary search. Here is the proof:
(for image 1: note 1st row represent no. of day, 2nd row represents what is the mass after that night night in case all bacterias have been splitted before, 3rd row represent no. of bacteria available to be splitted for next day.)
Here is my submission (Had to upsolve, because in the contest I got confused with the proof for the whole time). Time complexity is O(log(n)) per test case. FieryPhoenix what do you think about this approach.
Obviously the editorial solution is much more creative and definitely elegant :). (but I was nowhere near thinking like that).
You can find $$$m$$$ and $$$k$$$ in constant time too.
Can some one please help me figure out what is wrong with my solution of 1348B? would be great help thanks https://codeforces.me/contest/1348/submission/78743946
Test: #4, time: 234 ms., memory: 160 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER
Checker Log
wrong answer Integer element b[199] equals to -1, violates the range [1, 18] (test case 8)
Like the idea of problem B. (maybe the hardest B problem I have ever met in a div2 conteset)
Thanks for such a high quality contest and the fast turorial! :)
Great solution of problem F!!!
Problem B was the cutest.
Share a Solution in $$$O(nk)$$$ of problem E.
Could you explain how does it work?
First if we pick r red berries and b blue berries from a shrub and use them to fill exactly i baskets ($$$(r+b)MODk=0$$$).
Then if $$$r \geq k$$$ or $$$b \geq k$$$,we can pick k red berries or k blue berries just because they are the same color.So we just need to pick r red and b blue from the same bushes and use them to fill one basket $$$((r+b)=k)$$$.And others can be picked just because they are the same color.
dp[i][j] means considering the first i shrubs if we can pick x red berries (x%k=j) ,y blue berries to fill exactly some baskets((y+x)%k=0).
we can use dp[i][j] to update dp[i+1][c] as follow:
If we pick no berries from the $$$(i+1)_{th}$$$ shrub,then dp[i+1][j]=dp[i][j]
else we must pick exactly k berries from the $$$(i+1)_{th}$$$ shrub.Let's suppose we pick "a" red and "k-a" blue.The following condition must be satisfied :
You can easily find that ,the possible "a"s form an array:[max(1,k-b[i+1]),min(k-1,a[i+1])],in the other words dp[i+1][(j+c)%k](c is in the array) |=dp[i][j].
You can used some ways to achieve it in O(1).Like this :
for an array a[1]...a[n] you want to make a[l]...a[r] both increased by 1.You can do as follow:
a[l]++;
a[r+1]--;
After all the process.Set a[i]=a[i]+a[i-1] for all i (from 2 to n).
Final answer can be worked out according to the dp[n][i].
For A we can see a pattern:2->2, 4-> 2+4, 6->2+4+8... So answer is pow(2,n/2+1)-2
Problems were good. still i was not able to solve even 2 problems.
Nice Contest and Editorial. Thanks Phoenix!
But could someone please help me out with E. I can't really understand what is "_leaving extra berries_" in the editorial? :p
In problem F there is another way to find which friends to swap. When we construct answer greedily for friend i we always take interval with minimal b. So what are intervals with which we can swap i? There is only one possible interval. Interval with second minimal b (if exists). submission
Nice and simple explanation. Thanks!!
In problem F, why do greedy algorithm for an arbitrary valid ordering work?
First we should place friend 1 to somewhere, valid intervals have form [1; x]. Imagine we don't chose one with minimal x, then we should use that interval in future, but then we can swap those two intervals, so solution with using minimal x always exists. For placing friend 2 we can think of intervals with form [1; x] as [2; x] and don't lose anything, and so on. Sorry English.
I got it, thanks!
Can someone explain the O(nk) solution for E ?
Can anyone explain me the binary search solution for Problem-D ???
can anyone explain me why my solution got TLE for 2nd question though i printed n*k which is less than 10^4 letters output.My submission:78696875
More solutions for F:
(When I refer to the "length" of an interval below, I mean the number of unmatched points on it)
First, any interval of length one can be matched greedily. This reduces the problem size by one. Repeating this until no more intervals of length one are left is actually pretty tricky to implement efficiently. Here are two ways:
On every interval, keep two "sentries" at uniformly random distinct positions. This is impossible once the interval has length one, in which case we add it to a queue of length-one intervals. When we find an interval of length one, we match it and shrink all intervals containing that position. This may require relocating "sentries" at this position, which can be done in $$$O(log{n})$$$ per sentry using a Fenwick tree. Since each sentry is expected to have $$$O(\log{n})$$$ relocations, this solution has an expected runtime of $$$O(n\log^2{n})$$$.
For each interval, we store it in a bucket based on the leftmost point it contains that hasn't been matched. We sweep from left to right and match length-one intervals we find. We only need to check the interval in the bucket whose right endpoint is closest. If we do find a length-one interval, all other intervals in the bucket get merged into the next bucket. We also need to take a step backward because a new length-one interval may have been created. We can store the unmatched points in a doubly-linked list to do this efficiently. This solution is $$$O(n\log^2{n})$$$ if buckets are merged small-to-large, or $$$O(n\log{n})$$$ if join-based trees or meldable heaps are used.
Now all intervals have length at least two. Suppose there are at least two valid orderings.
Observe if the greedy algorithm for finding a solution ever has two active intervals with the same right endpoint, taking either will be optimal, so we will get two different solutions. It turns out this must happen if all intervals have length at least two.
There must always be two adjacent (by ID) points such that swapping their intervals creates another solution.
Code:
78842146
78842436
Can someone explain the following approach to D problem ? pigbrain's solution
this one gives a different answer for the test cases. Thank you.
For F problem another greedy initial matching is following: Sort by $$$b_i$$$ in increasing order. Within groups of same $$$b_i$$$ sort by $$$a_i$$$ in increasing order. Now, iterate over this order and for interval $$$i$$$ pick smallest not used value in the interval. I don't know how to prove it shortly. So, perhaps it's wrong.
During this iteration, let say smallest not matched value is $$$v$$$. If you also check for any used values (matched) within interval $$$(a_i, v)$$$ that can be also matched with $$$v$$$ -> this is solution. this pair is exactly what values you may swap. You do this check with segment tree.
Or, at least, it passed tests: 78850901 (code is ugly, just for hacks)
can someone for problem E explain how this TC's correct answer is 4?
4 8 11 5 1 4 1 4 1 6For E, doesn't O(nk^2) time out? Or can CodeForces computers handle ~1.25*10^9 operations in 2 seconds? I thought that modern computers can only handle at most 10^7 ish operations a second. This was my first contest so I'm not really familiar with the website. :P
O(nk^2) is not around 1e9, it's something like 1e8 and well to be honest it's a bit around the edge for 2 seconds, but generally when you see 500, just remember you can usually run it in n^3 if you code tidily.
Oh lol, just realized it's 1e8 can't count. Thanks for the advice though.
Have you ever heard about CPU clock speed? It's measured in Hz. Hertz — is basically something in second. It can be anything. But regarding to clock speed, it is cycles per second.
CPU perform single operation in several cycles, and at the same time, several operations during same cycle. Because of parallelism. It's not that kind of parallelism everyone talking about most of the time, like multiple cores / threads. It's other parallelism: processor split operations into micro operations... In short, all I want to say, that you can't tell time spent on operation. Modern CPUs are very complex.
Instead, lets say in optimistic maner CPU perform single operation in single cycle. This means if CPU is 3GHz, then it does $$$3*10^9$$$ operations per second. I said it's optimistic, but it can be wrong, just because number 1 cycle per operation is arbitrary chosen. You could say 0.5 cycles for operation, it's twice faster. But anyway, it's good approximation of order of magnitude. It's not $$$10^7$$$ or $$$10^8$$$. It's around $$$10^9$$$ because of GHz. Note that some operations are slow, like: sqrt, sin, cos... So, it doesn't work for them the same.
In short, thinking about second as approximately $$$10^9$$$ operations is enough. You can verify by running code. Just keep in mind that compiller can throw off any code that it may predict result, or if result is not used. So, at least print result of computation, and don't make super simple computations.
Thank you! I didn't know about that before. CodeForces doesn't give extra time to Java, right? Do you know the Hz of the CPU for CodeForces?
I don't know. It doesn't add for python and pypy for sure.
Given that the feedback on this tutorial is high, I don't really care if I get negatives for my message. Honestly, the tutorial for E is just terrible. There are many claims without a single proof.
I didn't understand the tutorial after reading it for two hours though I got some clue. I tried to implement the same thing as described in the solution to see what's going on. If you change the condition from $$$(a_i - l)~mod~k + b_i$$$ to $$$(a_i - l)~mod~k + b_i~mod~k$$$, you'll get a wrong answer.
Where that condition comes from? Why do we need to take the $$$mod$$$ of $$$a_i - l$$$ but not of $$$b_i$$$?
Insulting my explanation wasn't called for, please consider asking nicely in the future.
Nevertheless, your question is valid so I will try my best to explain.
Why we don't mod $$$b_i$$$:
Consider the case:
The optimal solution will have one basket contain $$$2$$$ blue berries from the first shrub and $$$1$$$ blue berry from the second shrub, and the second basket will contain $$$3$$$ of the remaining berries from the second shrub.
After processing the first shrub, only $$$dp[1][0]$$$ will be true. When transitioning to the second shrub, one optimal solution leaves $$$0$$$ extra red berries and groups the $$$2$$$ red berries in the second shrub with a blue berry. So, we want to check if $$$l=0$$$ is possible for $$$i=2$$$. A correct solution would return true.
Look at the condition. $$$(2-0)$$$ $$$mod$$$ $$$3$$$ $$$+3$$$ is greater than or equal to $$$3$$$, but $$$(2-0)$$$ $$$mod$$$ $$$3$$$ $$$+(3$$$ $$$mod$$$ $$$3$$$ $$$)$$$ is not. Why? Because for $$$l=0$$$ we can actually group the $$$2$$$ remaining red berries with a blue berry when $$$(b_i \ge 1)$$$, but after modding it doesn't work.
Why we mod $$$a_i - l$$$:
Consider the case:
If we don't mod $$$a_i-l$$$, solution will print $$$2$$$. Why? Because for the second shrub it will say it is allowed for $$$l=0$$$ when it obviously doesn't work. The $$$4$$$ red berries cannot be grouped with blue berries to make some number of full baskets. After leaving $$$l$$$ berries for valid $$$l$$$, all the remaining red berries must be put away.
hi, excuse me, could you please answer my question too? thank you in advance :)
for problem E explain how this TC's correct answer is 4? i can only see 3.....
4 8
11 5
1 4
1 4
1 6
x c y means take x berries of color c from basket y 1. (6 b 4, 2 b 3) 2. (2 b 3, 4 b 2, 2 b 1) 3. (1 r 4, 1 r 3, 1 r 2, 5 r 1) 4. (6 r 1, 2 b 1)
Here's another way of thinking about E:
Suppose we know the number of red berries in heterogeneous baskets modulo $$$k$$$. This determines the number of blue berries in heterogeneous baskets modulo $$$k$$$. Since the number of red berries in homogeneous baskets is a multiple of $$$k$$$, it also determines the number of red berries not in any baskets (we can safely assume this to be less than $$$k$$$ since otherwise we can form another basket). Similarly, we can determine the number of blue berries not in any basket, and thus deduce the number of baskets.
To compute the possible numbers of red berries in heterogeneous baskets modulo $$$k$$$, it suffices to look at each shrub separately and determine the possible numbers of red berries modulo $$$k$$$ in heterogeneous baskets for that shrub. If there is more than one heterogeneous basket for one shrub, we can rearrange the berries to leave at most one heterogeneous. Now we have two cases. If there are no heterogeneous baskets, the number of red berries in those baskets is obviously zero. If there is one heterogeneous basket, let $$$x$$$ be the number of red berries in it and $$$k-x$$$ be the number of blue berries in it. Clearly, $$$0\leq x\leq a_i$$$ and $$$0\leq k-x\leq b_i$$$. Rearranging, we get $$$\max(0,k-b_i)\leq x\leq \min(a_i,k)$$$. These correspond to the transitions for our DP.
Code: 78841831
Bonus: This implementation is actually $$$O(nk+k^2)$$$. (Hint: consider the maximum consecutive sequence of trues in each row).
"If there is more than one heterogeneous basket for one shrub, we can rearrange the berries to leave at most one heterogeneous."
Thank you.
Since some time now, i am seeing a strange pattern in some of cf questions. strangely tough ad hoc which seems just too forced. logics which appear to have been put just to make a question tough more than interesting and learning based . of course some problems are really beautiful and you get to learn, but many like this contest's D are straight out from the first category i mentioned. ofc i may be wrong, just wanted to voice my view.
in problem D, if n=13 output is 1,2,2 but if we follow this approach ,then it goes as, 1->3->7->11 could someone explain it to me? Thx in advance.
your sequence is right upto 7 that is 1 -> 3 -> 7
if you still have doubt feel free to ask
My solution for Problem "E. Phoenix and Berries" 78860291
Let,
DP[X][R]= Number of baskets that can be completely filled using the shrubs indexed fromXtoN — 1(0 based indexing), given that we haveRnumber of red berries to start with.Note that for every shrub, if:-
the total number of berries
a[X] + b[X](both red and blue) in a shrub is greater than or equal toK,and there are both red and blue berries in the shrub.
Then, we'll fill one basket completely, with these
Kberries and pass on the remaining berries to the next shrub. There can be at mostK - 1different ways in which we fill a basket containing both red and blue berries from the same shrub.For example if the
Xth shrub contains 2 red berries and 10 blue berries and K = 4, then the possible combinations are:-(All the combinations with either zero red berries or zero blue berries will be taken care of in the last part)
Whenever, the count of any of these passed on red and blue berries becomes greater than or equal to
K, we immediately fill a basket with it and pass on the remaining (R % K,B % K) berries to the next shrub.Important observation:
It can be observed that if we know the number of red berries that are being passed on to the
X + 1th shrub, we also know the exact number of blue berries that are being passed along with those red berries. Therefore we do not need to keep track of number of blue berries passed, i.e, we do not need to considerBas another dimension in states of DP.Number of blue berries passed = (Sum of total number of berries in each shrub starting from 1st shrub ending at Xth shrub—Number of red berries R passed onto (X + 1)th shrub) % KIf we receive
Rred berries andBblue berries from theXth shrub (passed onto theX + 1th shrub), and the total number of berries in theX + 1th shrub is greater than or equal toK, i.e.,a[X] + b[X] >= K, then we fill exactly 1 basket with these K berries. After selecting a total of K berries (all possible different combinations of red and blue), fromX + 1th shrub, we'll add the remaining red and blue berries toRandBand find modK.The number of red berries
Rand blue berriesBis always stored asR % KandB % K, because if we have at leastKred berries or/andKblue berries, we can completely fill(R / K) + (B / K)baskets.Another Case
If the number of berries in a shrub is less than
K, then we cannot fill a basket completely, using berries, entirely from this particular shrub, therefore we'll have to add the number of red and blue berries in this shrub toRandBrespectively, fillR / KandB / Kbaskets completely, and pass onR % KandB % Kred and blue berries respectively, to the next shrub.We solve the above case even when a[X] + b[X] >= K, to consider the combination :-
and pass on the remaining red and blue berries to the next shrub. :)
We have to find
DP[0][0]your explanation is good but one point i am missing is you said that if in a shrub a[x]+b[x]>=k then we will fill one basket from it and pass the remaining to next shrub , why? why can't i fill more than one basket from the same shrub(of type in which basket is filled with red and blue berries) if i have the chance , why i am filling only 1 basket and passing to next shrub?
I really apreciate your editorial and your effort! If you don't mind, i'm still having some troubles with problem E, it's a little bit hard to digest these operations. I've read carefully the editorial and all the comments and i'm still having troubles with these parts of the code :
"if ((a[i]-k)%K+b[i]>=K) dp[i][j]|=dp[i-1][(j-k+K)%K]; (especially the dp[i — 1][(j — k + k) % k] part)"
dp[i][j]=dp[i-1][(j-a[i]%K+K)%K];
If somebody can give me an explanation with some examples i would be really grateful.
I rewrote some of the variables in the code. Sorry for making it confusing with $$$k$$$ and $$$K$$$.
Essentially, once we determine we can leave $$$l$$$ extra red berries from the $$$i$$$-th shrub, we also have to check whether the state from the previous layer that we want to transition from is true. For some $$$l$$$, if we want to see if we can achieve $$$dp[i][j]$$$, we have to check if $$$dp[i-1][j-l]$$$ is true. But, $$$j-l$$$ might be negative, and since we only care about the value modulo $$$k$$$, we force it to be positive by adding $$$k$$$ then modding.
The second line of the code corresponds to leaving $$$a[i]$$$ modulo $$$k$$$ berries. We can always achieve this by creating full baskets containing only red berries until there aren't enough. The logic of transitioning from the previous dp layer is the same as I described above.
Hope this makes sense!
why is it not possible to leave l red berries if (a[i]-l)%k + b[i] < k. Wouldn't it be possible to combine the (a[i]-l) % k red berries with the j-l red berries already there ?
How is time limit handled on codeforces? Mu solution for problem C had T*N complexity, while solution in editorial had T*N*logN which would not make it in 2 seconds for big enough test set (for example if input would 900 test with string of length 10000 + 100 tests for edge cases). I saw such solution in room, but wasn't quick enough to hack it (with program that would generate 1000 * 10000 test set) and it passed (even though I'm pretty sure that it would take more than 2 seconds). So my question is: is time limit in problem for 1 test, or complete test set? And to add: are there some limitations for hacking (for example time limit for program that is generating input, or number of characters for directly passing input)? Thanks.
Detail explanation for div2 C if anyone need here
My solution for the problem E is greedy and it gave me accepted. To know how it works you can go to this blog: https://codeforces.me/blog/entry/76862
Can you please explain why this is true (or give an appropriate theorem/lemma name)?
Thanks for asking, I added the following explanation to the editorial:
Consider a simpler graph, with only nodes representing positions. We draw a directed edge from node $$$i$$$ to node $$$j$$$ if the friend currently assigned at position $$$i$$$ (from our greedy) can also be assigned to position $$$j$$$. So, if there exists any cycle, we can shift the friends around the cycle to create another valid ordering. If the perfect matching is unique, our graph has to be a DAG.
Now, returning back to the bipartite graph, we see that it is essentially the same. By contracting edges, all position nodes are equivalent to the friend node that is assigned to them (from the greedy). So, following an edge from the left side (position) to the right side (friend) puts us back on the left side (position), and this graph corresponds to the simpler version I explained above.
Please let me know if anything is still unclear.
Now it is clear, thank you.
can someone please explain o(nk) soln for Phoenix and Berries??
Consider solution $$$2$$$ from the editorial. It is clear that valid $$$l$$$ form a contiguous interval, so we can apply prefix sums on each layer to quickly query whether there exists a "true" in some interval.
Some of comments describe it enough, but I'll try to do my best.
First, let's say "problem is tough, let's try solve easier version". Easier version: we don't have shrubs-baskets. So, basket either full of red berries or full of blue berries. In this case, it doesn't matter how many shrubs, and where is one berry and where is another berry. All we need to know how much berries we have. Let $$$C_r$$$ — the number of red berries, and $$$C_b$$$ — number of blue berries, and $$$C$$$ — the number of all berries. Then, maximum filled baskets is
Notice, that maximum potentially unused berries is $$$2*(k-1)$$$ which is at most 1 basket! So, if unused berries is less than $$$k$$$, then we are reached theoretical maximum, because it's equal to case when we can fill basket by any $$$k$$$ berries.
Now, we introduce shrub-basket — one that may take any $$$k$$$ berries from single shrub. I'll call shrub-baskets only those with different berries. Otherwise, you can replace it with full of red berries, or full of blue berries.
We don't know how many shrub-baskets we need, and when. Suppose we know, what then? It will look like magic, but ideas how to come to it is about thinking in the way: how those remaining berries behave if you pick one shrub-basket. Then two... Can sometimes two shrub-basket be replaced by one + full of red?
Let $$$S_r$$$ be the number of red berries in shrub-baskets, and $$$S_b$$$ be the number of blue berries in shrub-baskets. Also let $$$S_r = k\cdot N_r + R_r$$$ be representation of whole part $$$(N_r)$$$ plus remainder $$$(R_r)$$$. Similarly $$$S_b = k\cdot N_b + R_b$$$. And let $$$N$$$ be number of shrub-baskets. This means $$$S_r + S_b = k\cdot N$$$. Now
For remainders to be from zero to $$$k$$$ there are two cases:
I'll use following property:$$$\left\lfloor x-1 \right\rfloor = \left\lfloor x\right\rfloor-1$$$ Which is same as:
And we have two cases:
In both cases we have:
So, the only thing we want to know, is it possible to get $$$R_r$$$ or not. let boolean dp[n][r] be true if and only if it is possible to get remainder r berries in shrub-baskets after first n shrubs. Then, obviously if dp[n][r] is true then dp[n+1][(r+j) mod k] is also true if we can make basket with $$$j$$$ red berries and $$$k-j$$$ blue berries. We can do it if:
Take in account $$$0 \leq j \leq k-1$$$ And corresponding range is
This is $$$O(nk^2)$$$ solution if you iterate across all $$$j$$$. Here is idea to optimize it. First, realize that you set booleans to true many times. What if you would store number instead, and increment it instead of setting it to 1. Then, all non-zero $$$dp[n][r]$$$ numbers represent possible remainder, and zero — impossible. How it helps? Increment by one is not a solution. Idea is that any array you can represent as first element + difference between its elements:
Increment of single value of differences array is corresponding to increment of all the values after corresponding element:
So, idea is: for dp[n] use array of sums to check is it possible to make remainder r, and for dp[n+1] calculate differences. when differences are made, convert it into sums and move to next iteration. Also, don't forget to check that range is not empty, and split it in halves if it overflow $$$k$$$.
Finally, source: 78997658
I'll use "charging argument" (google if you don't know). Suppose we have optimal solution. This means we know which berry we will put into which basket. Consider any shrub-basket (those which has berries of different color, blue berry in particular). If there is another shrub-basket of same shrub, then it has red berry. If we swap blue berry from our basket with red berry from other basket then number of full baskets doesn't change so it is still optimal solution. But in this way we increase amount of red berries in our basket. If we keep going, eventually we may stuck in two cases: no blue berries in our basket left, this means our basket is no longer shrub-basket in my terms; or there is no second shrub-basket of same shrub. So, either we already have single shrub-basket for this shrub, or we decreased number of shrub-baskets. This means, for each shrub, if number of shrub-baskets is greater than one then we can make it to be exactly one. It means, after this operations we have at most one shrub-basket for shrub. And during this operations we don't loose optimality. If initial solution was optimal, then new one is also optimal. It means, that one shrub-basket for shrub is always enough.
I had idea to use only k/x of those with range starting with x. It would be $$$O(n+k^2log(k))$$$ if it work. 79024430 It passed tests but obviously it's wrong so I hacked it.
Looks like I'm finally made legit solution for 1348E - Phoenix and Berries in $$$O(n + k^2)$$$ time and $$$O(k)$$$ memory. Just for fun I was trying to find solution where n can be bigger, and looks I did it. Code: 79055234
Idea of optimization is pretty simple, we want fast check is shrub useful or not. What do I mean by useful? Well, if processing of it does something, then it is useful. Now, just from definition of does something it means that after processing shrub we have more possible remainders. So, task is: determine fast will it increase. We don't care at all how much. So we can ask opposite: when is it useless? Yet again, say "problem is tough, we need something simpler". When it doesn't change if range is exactly one value? (in other words, if we can fill shrub-basket only in single way). If nothing changed, it means that infinite concatenation of our array of booleans after shift by number of red berries picked did overlap completely, and maybe better for understading: their bitwise OR looks same as initial infinite array. This means that it's shift by whole number of periods of our infinite boolean array. And you may find it in linear time. Back to "tough version". We have range of shifts then. So, we need to find is there any value among those shifts that is not whole number of periods of our infinite array. It's done in constant time. So, in the end, we process only those shrubs which will increase number of possible remainders, and in worst case we increase from 0 to k one by one which is k times. Each processing still takes $$$O(k)$$$ so in total with reading of shrubs becomes $$$O(n+k^2)$$$. (:
also look here https://codeforces.me/blog/entry/76555?#comment-614560
thanks
"we do not care about how many extra blue berries we leave because that is uniquely determined by the number of extra red berries." I am not able to get this line from question E, can anyone explain it?
Hi, please see my comment here: https://codeforces.me/blog/entry/76555?#comment-613632
Is there any Testcase for problem D. Pheonix and Science when the answer will be -1 ? If yes, please share.
Answer can never be -1.Because every possible n is reachable, just don't split the bacteria on any day and it will keep on increasing 1,2,3,4.....
Thanks FieryPhoenix for the editorial,
but one thing I don't understand in problem E(Phoenix and Berries) is that according to the editorial we are trying to leave extra l red berries from a[i], and extra means it is not placed in a full basket.
my question is: should not l be <= j ?
because as I see in the solution code that if l > j we are merging some of the l berries with red berries from the i-1 shrubs to maintain j extra berries, and this means that not all l red berries are extra
$$$l$$$ does not have to $$$\le j$$$. When we leave $$$l$$$ extra red berries from shrub $$$i$$$, we merge them with extra red berries from shrub $$$i-1$$$. At this point, if the total number of extra red berries is $$$\ge k$$$, some of the extra red berries may no longer be extra and will form their own basket. So, you can think about those berries being extra temporarily.
Thanks for the explanation
I am new to C++, can someone please tell me what does
int b:sdo? P.S. I read about sets, just can't understand that lineSearch up "foreach loop C++" on Google. Basically, it is an easy way to iterate over a container (such as set or vector for example).
The editorial for D is exquisite, but it is also very confusing, and the editorial must be easy to understand it doesn't matter if it is elegant or not.
Thanks for the tutorial!
There seem to be a little mistake in the first solution for F: "a friend $$$i$$$ such that there also exists some friend $$$j$$$ such that $$$a_{p_j} ≤ p_i \lt p_j ≤ b_{p_i}$$$".
I guess the correct expression should be as follows: $$$a_{p_j} ≤ i \lt j ≤ b_{p_i}$$$.
FieryPhoenix Can you please explain how (t-j)/k gives the total number of completely filled baskets as we are not subtracting extra blueberries?
Another/Easier Approach for Problem C
During the contest , I found it was tougher to come up with the correct approach. So instead this is a brute force solution... (0-based index)
We check if the smallest letter has <k occurences, then simply print the [k-1]th character.
If thats not the case,
We have only 2 Possible Options:
-> Either to fill all A[i] strings with the smallest letter, then append all the remaining characters (s[k......n-1]) to any a[i]. (preferably a[0]).
->Or to simply distribute all the characters evenly in k strings.
Now we make 2 arrays , and store the result of both options. Sort both. Then simply print the Minimum, of the Maximums of both Arrays!
CODE!
can anyone help me in my code.Here is my submission 158595810 1348B - Phoenix and Beauty Instead of inserting the element in array a i have printed them directly
why so ez?