first comment

206652299

what's wrong in this code?

Much simpler solution for F just uses sorting and queue. Count the frequency of each element and use sliding window of size $$$m$$$ on the sorted frequencies. You can keep track of the product of the frequencies in the window using simple modulo math. If at any time you are holding $$$m$$$ consecutive elements (simpler definition of magnificent dance) inside your window, you add this product to the answer.

A greedy idea for G:

Consider a node X that is the parent of m leaves

if m>2: The solution does not exist

if m=2: Two leaves and X form a branch

if m=1: Only one leaf (called Y) Move Y up 1 node (set parent of Y is also the parent of X, so that X and Y are siblings)

Repeat the process until reaching the root, which can be solved by DFS or BFS

An O(n) Solution for D: 206614690

In G, it is sufficient to just cut edges leading to subtrees with a size that is a multiple of 3, which leads to a very clean solution. Of course, some basic check for validity is also needed, such as making sure the correct number of edges were removed and that there is a proper amount of nodes.

A greedy solution for G which works in O(NlogN):

First root the tree(Take 1 to be the root) using dfs. For creating a branch, consider the leaf node at maximum depth. For this I used a priority_queue of pair<int,int> and then extract the node with maximum depth. For this to be in a branch, this node along with its parent has to be in the branch. Now for the 3rd node, if the parent has another child which is not part of another branch then take it otherwise take the parent of the parent as the third node. Now if the parent of the node at maximum depth has more than 1 other child(apart from the max depth node) then a solution to this problem does not exist i.e. output -1. Also if any of the nodes i.e. either the parent of a node or the case in which parent of parent of node is considered and that node is already part of another branch, then the solution does not exist i.e. output -1. Rest is the implementation and processing part which is there in this solution:

206591154

My simple greedy approach for G using degree and dfs: https://codeforces.net/contest/1833/submission/206667701

For G , I calculated the diameter of the tree and performed a simple dfs from one of the leaf nodes of the diameter , here is the code : 206572278

An O(n) solution for D is here: 206665067

On the problem G, I just try to go DFS on a tree, for a vertex u and vertex v is a direct child of u and if v is already searched, I'll check if the size of subtree at vertex v would add to the size of subtree at vertex u so that the size of subtree at u is still less than or equal to 3, if yes, I merge these two vertex in DSU, otherwise the edge connect u and v will be cut. After the DFS, I check all the component in DSU if the size of all of them is equal to 3.

But I dont really know how to prove this greedy solution, I just feels like to do it and it got Accepted

This is my solution: 206610493

Solution for probelm F giving WA in TC-4. please help me to find out.Link

In the editorial of problem F, the definition of prefix product should be $$$p_i=c_{1}\cdot c_{2}\dots c_{i}$$$ or $$$p_i=c_{i}\cdot p_{i-1}$$$, Please fix it, thanks.

I have another question about this part: if $$$p_{i}=0$$$, $$$p_{i+m}=0$$$ at the same time, but there is actually no zero in the interval $$$[i,i+m]$$$, this way of calculation may be wrong.

Example: $$$n=6$$$, $$$m=3$$$, $$$c=[1,0,1,1,2,1]$$$, now $$$i=3$$$, we found that $$$p_3=0$$$ and $$$p_6=0$$$ but actually $$$c_3\cdot c_4\cdot c_5\cdot c_6=2$$$, so this is incorrect.

If there are other special properties that make this never happen please point it out to me, thank you.

Finally became cyan :)

How is the output for the 4-th test in problem D the maximal permutation you can achieve? isn't the correct answer when l=2 and r=6?

yeah i understood no need to reply

In the C question solution what does .split() do?

def solve(): n = int(input()) a = [int(x) for x in input().split()] a.sort() if a[0] % 2 == 1: print("YES") return for i in range(n): if a[i] % 2 == 1: print("NO") return print("YES")

t = int(input()) for _ in range(t): solve()

I made a video editorial for this contest's first 5 problems, i.e. A to E. It has Hindi commentary so if you know Hindi then you can consider watching this video. Video Editorial Link — https://youtu.be/rXj5okWOy4k

Please give your valuable feedbacks in the comment section :)

.

Honestly I don't really understand what's the purpose of proposing something like problem D in division 3, which I think should be more educational, since beginner coders are the target audience here. What this problem is suppose to teach? Really anything, it's just heavy implementation and corner cases. I got the O(n) solution by myself something like 30 min after the contest and implemented the day after, just for the sake of doing it, being aware this is not worth from the educational point of view.

Does someone understand the solution for problem E in the editorial?? My approach was that each cycle greater than 2 had to be a separate dancing group so the last and the first person could connect. In the editorial code, it ignores these cycles of length > 2 now that it only takes in account the leafs(nodes with degree==1) in the graph. It only counts cycles when there are no leafs. Probably I have not seen an observation or something.

Can someone please explain me this solution:)?

Oh man, got super close on F, just needed to debug my prefix product code when the timer ran out

I can't understand the meaning of problem E, can someone translate it into formal statement? Thank you very much!

Hello, I am newbie here Can anyone tell me why my code falling 206856992. The problem is C.

What does "bamboos" mean in the tutorial for problem E?

nice contest

A simpler solution of G is 206896718

I am getting TLE exceeded on testcase 6 in question no. 2. While i think it is in the time limit. Can anyone help me out please? https://codeforces.net/contest/1833/submission/206588962

I don't understand the 3rd method/solution for problem F. I am talking about this part:

"We will use the idea of building a queue on two stacks, but we will support prefix products modulo in these stacks. Time complexity is O(n) and we don't use that the module is prime."

I would appreciate if anybody could explain this part in more detail.

Could you please explain examples in problem D:

4
4 3 2 1

why can't we just reverse segment with length 1 (without changing anything), and use empty prefix and suffix?

or

5
2 3 1 5 4

why can't we invert the first two elements [2,3] so it is 3 2 1 5 4 and then swap empty prefix and suffix [5,4] so it is 5 4 3 2 1 ?

feeling really stuck here, please help

Hey!

I'm trying to find a test case that makes my submission give WA on problem G.

Currently, I'm getting WA on TC 158:

Here is my submission: https://codeforces.net/contest/1833/submission/207332694

Can anybody explain stack and queue sulution of problem F with more detail?

I am unable to understand the idea behind the code

they don't even give answer to comments

Can 2nd question can be solved in Log(n)time

Can someone please check what's wrong with my solution? https://codeforces.net/contest/1833/submission/209606714

Why my solution is getting the runtime error for problem F?

210284741

I didn't get last part of tutorial of problem F, where possible approaches to calculate c[i] * c[i + 1] * ... * c[i + m]. In my solution, which got WA4, I tried to create prefix products p, so that p[i] contains product of amounts of occurrences of distinct values that appear till position i in sorted array a. The answer if magnificent dance for level a[i] exists, would be p[last occurrence of a[i] + m — 1 in sorted array a] / p[last occurrence of a[i] — 1 in sorted array a]. But because of overflows, the code got WA4

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll mod = 1e9+7;

ll count(unordered_map<ll, int> &arr, int l, int r) {
    ll i, rtn=1;
    for(i=l; i<=r; i++) {
        rtn = rtn%(ll)(1e9+7)*arr[i]%(ll)(1e9+7);
    }
    return rtn%(ll)(1e9+7);
}

ll power(ll a, ll b)
{
    ll res=1;
    
    while(b) {
        if(b&1)
            res=((res%mod)*(a%mod))%mod;

        a=(a*a)%mod;
        b/=2;
    }
    
    return res%mod;
}

int main() {
    
    int t, m, n, i, l, r;
    ll ans, store;

    unordered_map<ll, int> cnt;
    vector<ll> cpyA; 
    
    cin >> t;
    
    while(t--) {
    
       
        ans = 0;

        cin >> n >> m;
        
        ll a[n];
        
        for(i=0; i<n; i++) {
            cin >> a[i];
            cnt[a[i]]++;
            if(cnt[a[i]] <= 1)
                cpyA.push_back(a[i]);
        }
        
        sort(cpyA.begin(), cpyA.end());
        
        l = 0; r = m-1;
        store = count(cnt, cpyA[0], cpyA[m-1])%(ll)(1e9+7);
        while(r < cpyA.size()) {
            if(cpyA[r]-cpyA[l] < m) {
                ans = ans%(ll)(1e9+7)+store%(ll)(1e9+7);
            }
            r++;
            if(r < cpyA.size())
                store = ((store%(ll)(1e9+7)*power(cnt[cpyA[l]], 1e9+5)%(ll)(1e9+7))%(ll)(1e9+7))*cnt[cpyA[r]]%(ll)(1e9+7);
            l++;
        }
        
        cnt.clear();
        cpyA.clear();
        
        cout << ans%(ll)(1e9+7) << endl;

    }
    
    return 0;
    
}

my solution is much simpler than the solution of $$$G$$$ in editorial: hint : isn't it optimal to put the vertex into a component which has the smallest degree currently?

Can anyone suggest a problem, that is similar to problem F, but with these conditions:

• exactly A (instead of m) students participate in the dance;
• levels of every two dancers have an absolute difference strictly less than B (instead of m);
• levels of all dancers are pairwise distinct;

Basically the same problem, but without this claim:

A dance [x1,x2,…,xm] is called magnificent if there exists such a non-negative integer d that [x1−d,x2−d,…,xm−d] forms a permutation.

D can be solved in $$$O(n)$$$, why constraints are for $$$O(n^2)$$$

My submission

problem E statement in case you don't want to spoil the problem :

there are n people dancing in a dancing floor each person can hold the hand of 2 persons at most.

in order for the dance to be a good dance it's shape must be a circle, a circle can be formed with 2 persons or more ,

now each person remembers only one dancing partner and he don't remember if there was a second dancer with them or not. your task is to find the minimum and the maximum possible dancing circles that were good in that night by deciding weather there was a second partner for each person and if there was then who was it