Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### vovuh's blog

By vovuh, history, 21 month(s) ago, All problems were proposed by Mikhail MikeMirzayanov Mirzayanov.

1283A - Minutes Before the New Year

Tutorial
Solution

1283B - Candies Division

Tutorial
Solution

Tutorial
Solution

1283D - Christmas Trees

Tutorial
Solution

1283E - New Year Parties

Tutorial
Solution

1283F - DIY Garland

Tutorial
Solution Tutorial of Codeforces Round #611 (Div. 3) 611, Comments (92)
 » Very cool problem set, except weak C pretests :(.
•  » » Amen
 » 21 month(s) ago, # | ← Rev. 2 →   I found a $O(n)$ solution for C that's I think quite easy to both code and understand. We keep everyone who hasn't received a gift in a sorted vector and do the same for the ones that haven't gifted ($rec$ and $give$). We can construct them in linear time as the input already gives us the second ordered vector and the first one can be constructed using a boolean array that says whether the $ith$ person has already been gifted. Now we just iterate these two vectors at the same time, and if in the $ith$ position we find that $rec[i]==give[i]$ we do $swap(give[i], give[i-1])$ (if $i=0$ swap with $i+1$). It's easy to prove it by induction, as the case where $n=2$ is trivial and if you already have a correct array with size $n-1$, $n > 2$, if the $nth$ term is already matched to a different index we don't need to do anything, else we will swap it with it's predecessor and our matching is still valid, as we know we aren't matching it's predecessor with itself as the vector is ordered and $rec[n]==give[n]$. My code: 67844246
•  » » Nice solution. Thanks
•  » » I managed to do not exactly the same but yeah it was something like this. But became overconfident when the pretests passed. Could have applied the logic in the end. But fortunately my solution got hacked.
•  » » thnx bro
•  » » brilliant,thank you very much for this solution
•  » » hello,I wonder why that we need to swap(give[i],give[i-1]) can be correct,if we meet rec[i]==give[i],why it is wrong every time we meet that situation we swap (give[i],give)
•  » » » I know i'm late but, when rec[i] == give[i] happens and we simply assign it without swapping then it means that ith person is giving his gift to himself, which is forbidden.arr[give[i]] = rec[i]
•  » » Thanks...Nice solution, nicely explained and make more sense than the editorial....
•  » » Great approach. Thanks a lot.
 » D and E are good problems for Div3 contestants.Thank you Vovuh for this amazing year!
•  » » Explain E?
 » 21 month(s) ago, # | ← Rev. 2 →   why does using unordered_map give tle whereas using map my answer got accepted..(I am using BFS in D )
•  » » In the worst case, unordered_map runs in linear time. It's risky.
•  » » » so, when do we use umap and map.
•  » » » » You should use unordered map with custom hash function, otherwise don't use it. Use map or coordinate compression.
•  » » » » » Hi Where can I learn coordinate compression from. Can someone provide me with a link.
•  » » » » » How to do that hash function?
•  » » It is because of the complexity for unordered_map can be O(n). But for a map it is always O(logn).
•  » » This generally happens when there are collisions due to which the worst case time complexity of an unordered map is O(n). Problem setters generally make the test cases in such a way that collisions will happen and your solution will time out. Either you can use map or write your own customized hash function.
•  » » Consider this link. It explains how an unordered_map works, and how it is probable to be hacked with a TLE verdict, and how it can be prevented by a custom hash. It also includes one custom_hash, but you can always feel free to write one of your own :P
 » Thank you vovuh for cool amazing contest. My first problem solved in codeforce contest.
 » 21 month(s) ago, # | ← Rev. 3 →   Got it 1283C I am new to CP. Can anyone explain whats wrong in this approach ?It is given that the data provided is such that always some solution will exist. So what we do is we just order the edges with next greater element and largest one with smallest. like if we have 2 1 0 0 0lets iterate till 3 (numbered 1 to 5) then check next greater element who doesn't have any gift , and give it to him. So we give it to 4 then we get to 4 and give his give to 5 and when we get to 5 we give it to smallest that is 3. Whats wrong here? We will get following answer :-2 1 4 5 3and for knowing who have any gift i created an array r[i] such that for r[f[i]] = 0 if he have not recieved and r[f[i]] = 1 if he has
 » For problem C, i found a solution which is easier to both think and code, the time complexity is O(nlogn), here's my solution :67860783Let's assume the input array and the output array is a[i].Since the answer is a permutation with n distinct integers, and we can only put numbers in postions where in the input a[i] is equal to 0, so firstly i want to know what numbers i can use to put in these positions, you can use std::set to do that.And then we can iterate from the last element to the first element, if the current element is equal to 0, we just put the smallest element we can use(your_set_name.begin()) in this positon, and erase it.After that, you may obtain the correct answer, or there is only one postion i where a[i] is equal i, that's because when we iterate it, we put the element from the last to the first in increasing order, which is decreasing order from the first to the last, so if postion i satisfies a[i] == i, it must be a[i] > ion his left side element he put in, and a[i] < i on his right side element he put in, so there's at most one postion is not correct. At last, we just need to swap the number in this positon i with any postion which was 0 in the input except position i, after the swap, you get the correct answer.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   I took the same approach but I tried to simplify and just took next greater element. But it was wrong approach as 2 0 1 5 3 0 would give 2 4 1 5 3 0 from my solution. I wish i did as u did , and didn't try to oversimplify things
•  » » » yep, that's why you have to make sure the number you put in should be in decreasing order, that's more simple to implement it.
•  » » I did exactly the same and thought it in the same way but see my foolishness, after even analyzing that there will be a case in which there is one position of i which will satisfy a[i]==i , I didn't check the array again. And eventually I paid the price, my solution got hacked. Here's what I did. Used simple marked array to mark the already existing numbers and then put the numbers which are not present in the array, let's say absent array. Then I sorted it in the increasing order. Then simply iterate through the input array and check if there's an element whose value is zero then I picked the maximum number from the absent array and place it there.67826491
•  » » Can you give a proof that why there will be atmost one a[i]=i
 » My solution of C: find all chains. How? Beginnings of chains are people who doesn't receive gifts. To find ending: just traverse it until chain ends. When you have $s_i,e_i$ — start and end of chains, you just need to connect $e_i$ with $s_{i+1}$, and you're done.
 » For C, I tried a randomized approach. I tried to randomly assign values, not already present in the array, at the vacant positions until a valid solution is found. This approach has a success probability of about 36% (link).Link: 67832203However, I don't know why, but the same code received TLE when I submitted it in Pypy2, because of which I ended up spending more than 1 hour for this problem :(Link to the TLEd Pypy submission: 67817623
•  » » i tried a randomized approach independently haha just now..and got AC as well
 » My solution of E: lets construct both answers.Construction of maximum. Sort all people using counting sort of $O(n\,\log(n))$ sort. Make array $b_i$ — how many people will have coordinate $i$ — result of construction. Iterate over sorted list of people. Assign each friend to lowest unused position he may achieve. Count all used positions. This is maximum. Why? If there is some friend that may move to unused coordinate to the left, it will not decrease number of used cells. It may increase but not decrease. (google charging argument)Construction of minimum. $cnt_i$ — how many friends living in coordinate $i$. Make array $b_i$ — how many people will have coordinate $i$ — result of construction. Iterate over $i$ from $1$ to $n$. If $b_{i-1} > 0$ or $b_i > 0$ then assign $cnt_i$ to corresponding coordinate. Otherwise, assign to $i+1$ coordinate. This is minimum. Why? (not rigorous) Well, we move 'leftmost' friends to the 'rightmost' and merge all that may come in same place. Then we do same untill all friends processed.
•  » » Could you please elaborate the minimum construction?
•  » » » You move all friends from coordinate i to single coordinate. It's never better to move one friend from i to j, and another friend from i to k. So we consider friends in groups by their initial cooridnate. Next, we decide where we move whole group from i. $b_i$ is resulting distribution of friends after move. So, algorithm is greedy. Two cases for each i: if there is already neighbor where we can move -> move into it. Otherwise move to the right, in otherwords "make new home".
 » C has a much easier approach using deque data structure. Insert the positions in deque which are not pointed by anyone. And now put values on place of zero by checking first and last element in deque. Here's my code: https://codeforces.com/contest/1283/submission/67862320
•  » » i tried almost the same solution as you but i didn’t check the cnt<2 condition and got hacked after contest :/ But nice solution
 » As i think map is better than unordered_map. Give me example where Unordered_map is better than map..!
 » Any help for problem m F
•  » » For Problem F, we can think of the tree as rooted at the lamp connected to the power grid. We first notice that the first number in the input array must be the root. We can then maintain a list of all the "leaf" nodes (those that never appear in the input array, i.e. those nodes that are never the "main lamp" for any wire). Then, because the parent of largest leaf node would have appeared earlier in the input, we can match the smallest unprocessed leaf to the last number in the input array, remove the leaf, then update the list of unprocessed leaves (if necessary), and do this repeatedly.Consider the sample input: 6 3 6 3 1 5 The first number in this input array is $3$, so $3$ is the root of our tree.We know that every node (except the root) has exactly one parent, and some number of children nodes, so we can start by maintaining a degree array, which is equal to 1 (for the connection to the parent) plus x, if the node appears in the input array $x$ times (it is the parent of $x$ nodes). For the given input, the degree array will then be: 1: 2 2: 1 3: 3 4: 1 5: 2 6: 2 We note that the degree of $3$ is one more than the true degree, because $3$ has no parent. So, we decrement $1$ from the degree of $3$.From our degree array, we can look for all nodes with a degree of $1$, which will be our unprocessed leaf nodes, in this case [2, 4]. This can be effectively maintained using a priority_queue or other such data structures.Now, we iterate backward through the input array to match each leaf to its parent. We process all the leaves in sorted order, because the parent of a lighter leaf would appear later in the input.The last number in our input array is $5$, so the parent of $2$ (the smallest unprocessed leaf) is $5$. Now we remove $1$ from the degree of $2$, and one from the degree of $5$, and add an edge in our final output between $2$ and $5$. We do not need to consider the node $2$ anymore. For node $5$, it has now become a new leaf (its degree is now $1$) so we push it into our priority_queue for processing.Now, the smallest leaf is $4$, so we can look at the next item in the input array (going backwards), which is $1$. We add an edge in our output between $4$ and $1$. We decrement the degree of $1$ and $4$, and as the degree of $1$ now also becomes $1$, we push it to our leaf priority_queue. We do not need to consider the node $4$ anymore.We repeat this process until we have processed all leaf nodes (we need to be careful not to process $3$, as it is the root), and then output our answer.
•  » » » thanks for your solution nice method~
•  » » » In what case will F have no answer? when to print -1?
•  » » » » There is always an answer (:
 » Easy solution for C. https://codeforces.com/contest/1283/submission/67815280 just map thing
 » My solution for F. You can observe that you can make the more important link's main as the parent of the less important link's main. Thus we iterate through the array and make the next number as the child of the first number. Else, if we can't do that, that is the next number in the array is already used, we can make the biggest number available as its child. This comes from the fact that a power of 2 is bigger than all other powers of 2's less than itself. Otherwise, if there is no number left to assign, then we say that such an arrangement is not possible.
 » Good round, thanks to organizers :)
»

can any one tell me that how is my code wrong if it is same as editorial solution...? please tell me i couldn't understand this.

# include

using namespace std;

int main() { long int tc; cin>>tc; while(tc--) { long long int n,k,i,j; cin>>n>>k; if(n<=k) cout<<n<<endl; else { if(n%k==0) cout<<n<<endl; else { j = (n%k-(k/2)); if(j>0) i = n — j; else i = n;

cout<<i<<endl;
}
}

}
return 0;

}

 » D was nice problem
•  » » Can You Please Explain the Solution of D ?
 » Ez solution for E https://codeforces.com/contest/1283/submission/67867801
•  » »
 » Could anyone help out on why is my solution getting a TLE for Problem D ? (https://codeforces.com/contest/1283/submission/67857488)
•  » » are you sure that m reaches 0. your m-- is inside if condition.
 » wrong answer The value of nf_7 should be equal to f_7my solution 67869058 for C is failing 2nd test case with this error can someone explain me this.
 » very easy solution for E. https://codeforces.com/contest/1283/submission/67869665 just map thing..!
•  » » Can you explain the solution?
•  » » https://codeforces.com/contest/1283/submission/82440699 just array thing! XD
 » My approach for problem C:First, I store all the node with indegree equals to 0, which I call list of starting node, iterate all of these nodes, at each node $v$, just go to next node unless you can't, assuming now you are on node $u$, connect $u$ with the node after $v$ in the list of starting node. My submission Problem E is exactly greedy approach, but the provided implementation is quite hard, my implementation is just greedy and lay each person at greedy position, afterward count the number of positions which were occupied. My submission
 » 21 month(s) ago, # | ← Rev. 4 →   how does the solution of new year parties work? can anybody explain in simple terms? in maximization case?
 » To weak C pretests.
 » 21 month(s) ago, # | ← Rev. 4 →   Can someone tell me what's wrong with my solution to the problem C? First I collected all points s.t. a[i] = 0 and i does not give gift to anyone. Then I rotated the array. For all other points, I simply printed it as it. Here is the link https://codeforces.com/contest/1283/submission/67874440
 » 21 month(s) ago, # | ← Rev. 2 →   My DP solution for E,both subtasks are similar,sort the array,now however we move the people,the final positions should be sorted too,there are only 3 states possible.Try them all! https://codeforces.com/contest/1283/submission/67875164The code is almost same for both subtasks(change min to max) # SAY-NO-TO-GREEDY
 » Please explain problem E :/
 » 21 month(s) ago, # | ← Rev. 2 →   Hi guys, am getting WA on test case 44 for problem Dcan someone please identify my mistakeMY Approach:- am using visited (map) to mark all unavailable points, and in the pair ( pair) am storing point x in first part of pair and in second part of pair 1 for forward movement and 0 for backward movement then i take points one by one and according to the movement type i check is the movement of the point i just selected possible or not , e.g if the point that i took out of queue is forward based then i check is it possible to take the point after this using the visited map if possible then push the next point to queue and c is a queue used to store the corresponding distance of the point in queue 'v' , took c separately so as to make code more readableplease help me find my mistakemy_solutionThanks in Advance
»

# include <math.h>

using namespace std;

int main() {

int n,x;

cin>>n;

vectorv;

vectora;

vectorv3;

for(int i=0;i<n;i++){

cin>>x;

if(x!=0) a.push_back(x);

v.push_back(x);

}

//int ans = {2,4,5};

for(int j=1;j<=n;j++){

int flag = 1;

for(int i=0;i<3;i++){

cout<<j<<" "<<a[i]<<endl;

if(j == a[i]){

flag = 0;

break; }

}

if(flag == 1){

cout<<"mc"<<endl;

v3.push_back(j); }

}

for(int i=0;i<v.size();i++){

if(v[i] == 0 && v3[i] != i){

v[i] = v3[i];

}

}

for(int i=0;i<v.size();i++){

cout<<v[i]<<"  ";

}

return 0; }

 » 21 month(s) ago, # | ← Rev. 2 →   Can anyone please tell me what is wrong in this code for PROBLEM-1283B~~~~~ - 1. — 1. — ~~~~~ Your code here... ~~~~~int main() { ll t,i; cin>>t; while(t--) { ll n,k; cin>>n>>k; if(n
•  » » n=5, k = 4 your answer is 6, it should be 5
 » I've got a very good solution to Problem D using Binary Search :O
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   Can you explain your solution to me please?
•  » » turkoarias What was your approach? Can you please elucidate?
 » Can somebody explain his solution of C, how to consider permutation as a graph?
 » Hi,guys,I want to know the reason of get WA on problem C in my solution. Order the list of unreceiver from greater to less,if the size of the list is odd,swap the mid one and the mid one + 1,and output them,if now position is zero,output the previous list by order. But I get WA in test 12,i don't know why...,hope someone could give me an example. Very thanks.
 » i dont clearly understand that how should we choose the first tree-posotion from which the multisource bfs should start.
 » While solving problem 1283C - Friends and Gifts, a vey weird thing happened. When i submit my solution 68002964 in pypy , it says wrong answer on testcase 5, but when i submit the same code in python 68003409, it becomes accepted. Does anybody have any idea as to why it might be happening?
 » vovuh Thanks for great contest :)when you will write a tutorial for problem F 1283F - DIY Garland
 » 21 month(s) ago, # | ← Rev. 2 →   (F) why does this O(n^2) solution work?
•  » » It looks like it is $O(n^2)$ but actually it is $O(n)$ since each element is visited at most once by both $i$ and $cur$ leading to $2n$ operations.
 » 21 month(s) ago, # | ← Rev. 2 →   O(n) solution for C: https://codeforces.com/contest/1283/submission/67981767Algo: 1) Keep a boolean array for received and a array for gift-to index (which is the input basically). 2) Iterate through gift-to array. If you find a zero, iterate in reverse through the received array. If you find a false ie that person hasnt send a gift break. 3) if the indexes of both loops are not equal simply assign and push the index in the assigned vector. 4) But if the indexes are equal we have to either of both things either or both of which is possible. * Swap from the assigned vector. But what if the assigned vector is empty? [This is exactly why my initial solution got hacked :( ] * Iterate through boolean array using a temporary index initialized at current index. Find another index that hasn't gifted and assign. Then reset that index to the current index.
 » If you want a problem D Video tutorial: https://www.youtube.com/watch?v=mb9two5KApU
 » editorial of F reminds me Half-life 3)
 » The problem F is simply just decode the given Prüfer code.
 » Can anyone explain B problem?, I couldn't get it.
 » Soon...? It's been a month already.
 » #include #define ll long long int #define N 100009 #define M 1000000007 #define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--) #define po pop_back #define pb push_back #define lb lower_bound #define ub upper_bound #define ibs ios_base::sync_with_stdio(false) #define cti cin.tie(0) #define cot cout.tie(0) using namespace std;//coded by abhijay mitra #define watch(x) cout << (#x) << " is " << (x) << endl int main() { ibs;cti;int n;cin>>n;std::vector v(n+1,0);std::vector b(n+1,0); std::vector c; for (int i = 1; i <=n; ++i) { cin>>v[i];b[v[i]]=1; } for (int i = 1; i < n+1; ++i) { if(b[i]==0)c.pb(i); } for (int i = 1; i < n+1; ++i) { if(v[i]!=0)cout<
 » Someone please explain dp solution for E.
•  » » idk tho i think i have a better solution https://codeforces.com/contest/1283/submission/82440699 sorry in advance if you don't find that good enough
»

//my solution for problem c

# include <bits/stdc++.h>

using namespace std;

int main() {
int n,temp; cin>>n;

int result[n];
set<int> re;
vector<int> ungiver;

for(int i=0;i<n;i++){
cin>>temp;
if(temp==0){
ungiver.push_back(i+1);
continue;
}
result[i]=temp;
re.insert(temp);
}

vector<int> unrecer;

for(int i=1;i<=n;i++)
if(re.find(i)==re.end())
unrecer.push_back(i);

while(!ungiver.empty()){
if(ungiver.size()==2){
if(ungiver.back()==unrecer.back()||ungiver==unrecer){
result[ungiver.back()-1]=unrecer;
result[ungiver-1]=unrecer;
break;
}
result[ungiver.back()-1]=unrecer;
result[ungiver-1]=unrecer;
break;
}

if(ungiver.back()!=unrecer.back()){
result[ungiver.back()-1]=unrecer.back();
ungiver.pop_back();
unrecer.pop_back();
continue;
}
result[ungiver.back()-1]=unrecer[unrecer.size()-2];
ungiver.pop_back();
unrecer.erase(unrecer.begin()+unrecer.size()-2);
}

for(int v:result)
cout<<v<<" ";

return 0;`

}

 » Cool contest
 » Can anyone help me to analyze the time complexity for D. How is it O(nlogn) as mentioned in the editorial
 » 12 months ago, # | ← Rev. 2 →   Is F something which is already known? It is almost like the Prufer correspondence proof for n^(n-1) rooted labelled trees on n vertices.
 » For problem D, why do i get TLE for this soluion using set https://codeforces.com/problemset/submission/1283/103887402, but get AC for this one using map https://codeforces.com/problemset/submission/1283/103885753. Can someone please help me?
 » C has more easy solution. I used two pointer method. firstly, I fixed the point where a[i] = 0, && i is missing. set l = 0, r = vector.sz — 1. now iterate through the array. when a[i] = 0 && f[i] = 0, then pick v[l] if v[l] != i. otherwise pick v[r]. now again iterate through the array and put the remaining value. my submission