Very cool problem set, except weak C pretests :(.

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

D and E are good problems for Div3 contestants.

Thank you Vovuh for this amazing year!

why does using unordered_map give tle whereas using map my answer got accepted..(I am using BFS in D )

Thank you vovuh for cool amazing contest. My first problem solved in codeforce contest.

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 0

lets 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 3

and 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 :67860783

Let'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.

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: 67832203

However, 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

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.

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.net/contest/1283/submission/67862320

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

Easy solution for C. https://codeforces.net/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 :)

Ez solution for E https://codeforces.net/contest/1283/submission/67867801

very easy solution for E. https://codeforces.net/contest/1283/submission/67869665 just map thing..!

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

To weak C pretests.

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.net/contest/1283/submission/67875164

The code is almost same for both subtasks(change min to max)

# SAY-NO-TO-GREEDY

Please explain problem E :/

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<k) { ll val1=k/2; n=min(n,val1); cout<<n<<endl; } else {ll rem=n%k; ll val=k/2; if(rem!=0) rem-=val;

cout<<n-rem<<endl;
}

}

return 0;

} `~~~~~` ``

I've got a very good solution to Problem D using Binary Search :O

Can somebody explain his solution of C, how to consider permutation as a graph?

vovuh Thanks for great contest :)

when you will write a tutorial for problem F 1283F - DIY Garland

(F) why does this O(n^2) solution work?

editorial of F reminds me Half-life 3)

The problem F is simply just decode the given Prüfer code.

Soon...? It's been a month already.

#include <bits/stdc++.h>
#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<int> v(n+1,0);std::vector<bool> b(n+1,0);
    std::vector<int> 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<<v[i];
        else{
            if(c.back()!=i){cout<<c.back();c.pop_back();}
            else{cout<<c[0];c.erase(c.begin());}
        }
        cout<<" ";
    }
    return 0;   
}

Got hacked for a test case C

Someone please explain dp solution for E.

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.

excuse me.I think admin's code is not right with this test: 8 8 10 5 10 9 2 9 3 Problem E:New Year Parties