vovuh's blog

Codeforces Round #611 (Div. 3) Editorial
By vovuh, history, 5 years ago, In English

All problems were proposed by Mikhail MikeMirzayanov Mirzayanov.

1283A - Minutes Before the New Year

Tutorial
Solution

1283B - Candies Division

Tutorial
Solution

1283C - Friends and Gifts

Tutorial
Solution

1283D - Christmas Trees

Tutorial
Solution

1283E - New Year Parties

Tutorial
Solution

1283F - DIY Garland

Tutorial
Solution
  • Vote: I like it
  • +51
  • Vote: I do not like it

Comments Comments (62)
| Write comment?
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

D and E are good problems for Div3 contestants.

Thank you Vovuh for this amazing year!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    In the worst case, unordered_map runs in linear time. It's risky.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so, when do we use umap and map.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should use unordered map with custom hash function, otherwise don't use it. Use map or coordinate compression.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hi Where can I learn coordinate compression from. Can someone provide me with a link.

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please elaborate the minimum construction?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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".

      → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As i think map is better than unordered_map. Give me example where Unordered_map is better than map..!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any help for problem m F

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Easy solution for C. https://codeforces.net/contest/1283/submission/67815280 just map thing

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good round, thanks to organizers :)

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To weak C pretests.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Can you/anyone explain the state transition in the code?

    Edit: You are trying to apply all operations on all elements -1,0,1 and picking the best out of all..such that after an option on ai and an (i+1) they are placed one after the other then increase the ans by 1.

    dp(l,t1)=  1+dp(l+1,t2)  if (a1+t1)<(a2+t2)

    else
    dp (l+1,t1) = dp(l+1,t2) if(a1+t1)>=(a2+t2) for all t={-1,0,1}..

    → Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Please explain problem E :/

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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;

} `~~~~~` ``

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

vovuh Thanks for great contest :)

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

editorial of F reminds me Half-life 3)

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
#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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone please explain dp solution for E.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply