### vovuh's blog

By vovuh, history, 13 months 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

• +51

 » 13 months ago, # |   +6 Very cool problem set, except weak C pretests :(.
•  » » 13 months ago, # ^ |   0 Amen
 » 13 months ago, # | ← Rev. 2 →   +8 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
•  » » 13 months ago, # ^ |   +1 Nice solution. Thanks
•  » » 13 months ago, # ^ |   0 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.
•  » » 13 months ago, # ^ |   +1 thnx bro
•  » » 13 months ago, # ^ |   +1 brilliant,thank you very much for this solution
•  » » 12 months ago, # ^ |   0 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[1])
•  » » » 6 months ago, # ^ |   0 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]
•  » » 7 months ago, # ^ |   0 Thanks...Nice solution, nicely explained and make more sense than the editorial....
 » 13 months ago, # |   +20 D and E are good problems for Div3 contestants.Thank you Vovuh for this amazing year!
•  » » 12 months ago, # ^ |   0 Explain E?
 » 13 months ago, # | ← Rev. 2 →   +3 why does using unordered_map give tle whereas using map my answer got accepted..(I am using BFS in D )
•  » » 13 months ago, # ^ |   +7 In the worst case, unordered_map runs in linear time. It's risky.
•  » » » 13 months ago, # ^ |   0 so, when do we use umap and map.
•  » » » » 13 months ago, # ^ |   0 You should use unordered map with custom hash function, otherwise don't use it. Use map or coordinate compression.
•  » » » » » 13 months ago, # ^ |   0 Hi Where can I learn coordinate compression from. Can someone provide me with a link.
•  » » » » » 2 months ago, # ^ |   0 How to do that hash function?
•  » » 13 months ago, # ^ |   0 It is because of the complexity for unordered_map can be O(n). But for a map it is always O(logn).
•  » » 13 months ago, # ^ |   0 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.
•  » » 13 months ago, # ^ |   0 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
 » 13 months ago, # |   +3 Thank you vovuh for cool amazing contest. My first problem solved in codeforce contest.
 » 13 months ago, # | ← Rev. 3 →   0 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
 » 13 months ago, # |   +1 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.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +1 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
•  » » » 13 months ago, # ^ |   0 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.
•  » » 13 months ago, # ^ |   0 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
•  » » 6 months ago, # ^ |   0 Can you give a proof that why there will be atmost one a[i]=i
 » 13 months ago, # |   +9 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.
 » 13 months ago, # |   0 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
•  » » 5 weeks ago, # ^ |   0 i tried a randomized approach independently haha just now..and got AC as well
 » 13 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   0 Could you please elaborate the minimum construction?
•  » » » 6 months ago, # ^ |   0 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".
 » 13 months ago, # |   +8 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
•  » » 13 months ago, # ^ |   0 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
 » 13 months ago, # |   0 As i think map is better than unordered_map. Give me example where Unordered_map is better than map..!
 » 13 months ago, # |   0 Any help for problem m F
•  » » 13 months ago, # ^ |   +15 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.
•  » » » 13 months ago, # ^ |   0 thanks for your solution nice method~
•  » » » 13 months ago, # ^ |   0 In what case will F have no answer? when to print -1?
•  » » » » 12 months ago, # ^ |   0 There is always an answer (:
 » 13 months ago, # |   0 Easy solution for C. https://codeforces.com/contest/1283/submission/67815280 just map thing
 » 13 months ago, # |   0 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.
 » 13 months ago, # |   0 Good round, thanks to organizers :)
»
13 months ago, # |
0

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;

}

 » 13 months ago, # |   0 D was nice problem
•  » » 12 months ago, # ^ |   0 Can You Please Explain the Solution of D ?
 » 13 months ago, # |   0 Ez solution for E https://codeforces.com/contest/1283/submission/67867801
•  » » 7 months ago, # ^ |   0
 » 13 months ago, # |   0 Could anyone help out on why is my solution getting a TLE for Problem D ? (https://codeforces.com/contest/1283/submission/67857488)
•  » » 13 months ago, # ^ |   0 are you sure that m reaches 0. your m-- is inside if condition.
 » 13 months ago, # |   0 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.
 » 13 months ago, # |   0 very easy solution for E. https://codeforces.com/contest/1283/submission/67869665 just map thing..!
•  » » 13 months ago, # ^ |   0 Can you explain the solution?
•  » » 7 months ago, # ^ |   0 https://codeforces.com/contest/1283/submission/82440699 just array thing! XD
 » 13 months ago, # |   +3 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
 » 13 months ago, # | ← Rev. 4 →   0 how does the solution of new year parties work? can anybody explain in simple terms? in maximization case?
 » 13 months ago, # |   0 To weak C pretests.
 » 13 months ago, # | ← Rev. 4 →   0 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
 » 13 months ago, # | ← Rev. 2 →   -7 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
 » 13 months ago, # |   -8 Please explain problem E :/
 » 13 months ago, # | ← Rev. 2 →   0 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
»
13 months ago, # |
-18

# 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[3] = {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; }

 » 13 months ago, # | ← Rev. 2 →   0 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
•  » » 13 months ago, # ^ |   0 n=5, k = 4 your answer is 6, it should be 5
 » 13 months ago, # |   0 I've got a very good solution to Problem D using Binary Search :O
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Can you explain your solution to me please?
•  » » 6 months ago, # ^ |   0 turkoarias What was your approach? Can you please elucidate?
 » 13 months ago, # |   0 Can somebody explain his solution of C, how to consider permutation as a graph?
 » 13 months ago, # |   0 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.
 » 13 months ago, # |   -8 i dont clearly understand that how should we choose the first tree-posotion from which the multisource bfs should start.
 » 13 months ago, # |   0 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?
 » 13 months ago, # |   +9 vovuh Thanks for great contest :)when you will write a tutorial for problem F 1283F - DIY Garland
 » 13 months ago, # | ← Rev. 2 →   0 (F) why does this O(n^2) solution work?
•  » » 12 months ago, # ^ |   0 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.
 » 12 months ago, # | ← Rev. 2 →   0 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.
 » 12 months ago, # |   0 If you want a problem D Video tutorial: https://www.youtube.com/watch?v=mb9two5KApU
 » 12 months ago, # |   +8 editorial of F reminds me Half-life 3)
 » 12 months ago, # |   +3 The problem F is simply just decode the given Prüfer code.
 » 12 months ago, # |   0 Can anyone explain B problem?, I couldn't get it.
 » 12 months ago, # |   0 Soon...? It's been a month already.
 » 11 months ago, # |   0 #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<
 » 8 months ago, # |   0 Someone please explain dp solution for E.
•  » » 7 months ago, # ^ |   0 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
»
7 months ago, # |
0

//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[0]==unrecer[0]){
result[ungiver.back()-1]=unrecer[0];
result[ungiver[0]-1]=unrecer[1];
break;
}
result[ungiver.back()-1]=unrecer[1];
result[ungiver[0]-1]=unrecer[0];
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;`

}

 » 7 months ago, # |   0 Cool contest
 » 6 months ago, # |   0 Can anyone help me to analyze the time complexity for D. How is it O(nlogn) as mentioned in the editorial
 » 4 months ago, # | ← Rev. 2 →   0 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.
 » 8 days ago, # |   0 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?