№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Идея: Vladosiya, разработка: Vladosiya

Разбор

Решение

def solve():
    n = int(input())
    s = input()
    cnt = set()
    for i in range(1, n):
        cnt.add(s[i - 1] + s[i])
    print(len(cnt))


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

1833B - Восстанови погоду

Идея: myav, разработка: myav

Разбор

Решение

#include<bits/stdc++.h>
using namespace std;
void  solve(){
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>>a(n);
    vector<int>b(n), ans(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].first;
        a[i].second = i;
    }
    for(auto &i : b) cin >> i;
    sort(b.begin(), b.end());
    sort(a.begin(), a.end());

    for(int i = 0; i < n; i++){
        ans[a[i].second] = b[i];
    }
    for(auto &i : ans) cout << i << ' ';
    cout << endl;
}
int main(){
    int t;
    cin >> t;
    while(t--) solve();
}

1833C - Влад строит красивый массив

Идея: Vladosiya, разработка: Vladosiya

Разбор

Решение

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()

1833D - Перевертыш

Идея: Gornak40, разработка: Aris

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back



void solve() {
    int n; cin >> n;
    vector<int> p(n);
    for (auto &e : p) cin >> e;

    int r = 0;
    for (int i = 0; i < n; ++i) {
        if (p[min(n-1, r+1)] <= p[min(n-1, i+1)]) {
            r = i;
        }
    }
    vector<int> ans;
    for (int i = r + 1; i < n; ++i) ans.eb(p[i]);
    ans.eb(p[r]);
    for (int i = r-1; i >= 0; --i) {
        if (p[i] > p[0]) {
            ans.eb(p[i]);
        } else {
            for (int j = 0; j <= i; ++j) {
                ans.eb(p[j]);
            }
            break;
        }
    }
    for (auto e : ans) cout << e << ' ';
    cout << endl;
}

int main() {
    int t;
    cin >> t;

    forn(tt, t) {
        solve();
    }
}

1833E - Хороводы

Идея: MikeMirzayanov, Vladosiya, разработка: senjougaharin

Разбор

Решение

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long ll;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<set<int>> g(n);
    vector<set<int>> neighbours(n);
    vector<int> d(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i]--;
        g[i].insert(a[i]);
        g[a[i]].insert(i);
    }
    for (int i = 0; i < n; ++i) {
        d[i] = g[i].size();
    }
    int bamboos = 0, cycles = 0;
    vector<bool> vis(n);
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            queue<int> q;
            q.push(i);
            vis[i] = true;
            vector<int> component = {i};
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v: g[u]) {
                    if (!vis[v]) {
                        vis[v] = true;
                        q.push(v);
                        component.push_back(v);
                    }
                }
            }
            bool bamboo = false;
            for (int j: component) {
                if (d[j] == 1) {
                    bamboo = true;
                    break;
                }
            }
            if (bamboo) {
                bamboos++;
            } else {
                cycles++;
            }
        }
    }
    cout << cycles + min(bamboos, 1) << ' ' << cycles + bamboos << '\n';
}

int main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        solve();
    }
}

1833F - Ира и фламенко

Идея: Gornak40, разработка: Gornak40

Разбор

Решение

/*
         `)
        _ \
      (( }/  ,_
      )))__ /
     (((---'
       \ '
        )|____.---- )
       / \ `       (
      / ' \ `      )
     /  '  \  `   /
    /   '       _/
   /   _!____.-'
  /_.-'/    \
     |`_    |`_
*/
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> ipair;

const int MAXN = 200200;
const int MAXK = MAXN;
const int MOD = 1000000007;

inline int add(int a, int b) {
	return (a + b >= MOD ? a + b - MOD : a + b);
}

inline int mul(int a, int b) {
	return 1LL * a * b % MOD;
}

int n, m, k;
int arr[MAXN], brr[MAXN], cnt[MAXK];

void build() {
	sort(arr, arr + n);
	memcpy(brr, arr, sizeof(int) * n);
	k = unique(arr, arr + n) - arr;
	for (int j = 0; j < k; ++j)
		cnt[j] = upper_bound(brr, brr + n, arr[j]) - lower_bound(brr, brr + n, arr[j]);
}

inline void push(stack<ipair> &S, int x) {
	S.emplace(x, mul(x, S.empty() ? 1 : S.top().second));
}

int solve() {
	if (k < m) return 0;
	stack<ipair> S1, S2;
	for (int j = 0; j < m; ++j)
		push(S1, cnt[j]);
	int ans = 0;
	for (int j = m; j <= k; ++j) {
		if (arr[j - 1] - arr[j - m] == m - 1)
			ans = add(ans, mul(S1.empty() ? 1 : S1.top().second, S2.empty() ? 1 : S2.top().second));
		if (S2.empty()) {
			for (; !S1.empty(); S1.pop())
				push(S2, S1.top().first);
		}
		S2.pop();
		push(S1, cnt[j]);
	}
	return ans;
}

int main() {
	int t; cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 0; i < n; ++i)
			cin >> arr[i];
		build();
		cout << solve() << endl;
	}
}

1833G - Ксюша и шиншилла

Идея: Gornak40, разработка: Gornak40

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> ipair;

const int MAXN = 200200;

int n;
vector<ipair> gr[MAXN];
vector<int> res;
queue<int> qu;
int par[MAXN], ipar[MAXN], deg[MAXN], hard[MAXN];

void init() {
	res.clear();
	while (!qu.empty()) qu.pop();
	memset(deg, 0, sizeof(int) * n);
	memset(hard, 0, sizeof(int) * n);
	for (int v = 0; v < n; ++v)
		gr[v].clear();
}

void dfs(int v, int p, int ip) {
	par[v] = p;
	ipar[v] = ip;
	for (auto [u, i]: gr[v]) {
		if (u == p) continue;
		dfs(u, v, i);
		++deg[v];
		hard[v] += (deg[u] > 0);
	}
}

void build() {
	dfs(0, -1, -1);
}

bool rempar(int v) {
	int u = par[v];
	if (u == -1) return true;
	par[v] = -1;
	res.push_back(ipar[v]);
	--deg[u], --hard[u];
	if (deg[u]) {
		if (!hard[u]) qu.push(u);
		return true;
	}
	if (par[u] == -1) return false;
	--hard[par[u]];
	if (!hard[par[u]]) qu.push(par[u]);
	return true;
}

bool solve() {
	if (n % 3) return false;
	for (int v = 0; v < n; ++v)
		if (!hard[v] && deg[v]) qu.push(v);
	while (!qu.empty()) {
		int v = qu.front(); qu.pop();
		if (deg[v] > 2) return false;
		if (deg[v] == 2) {
			if (!rempar(v)) return false;
		} else if (deg[v] == 1) {
			if (par[v] == -1) return false;
			for (auto [u, i]: gr[par[v]]) {
				if (u == par[par[v]] || u == v || par[u] == -1) continue;
				if (!deg[u]) return false;
				res.push_back(i);
				par[u] = -1;
			}
			if (!rempar(par[v])) return false;
		}
	}
	return true;
}

int main() {
	int t; cin >> t;
	while (t--) {
		cin >> n, init();
		for (int i = 1; i < n; ++i) {
			int v, u; cin >> v >> u, --v, --u;
			gr[v].emplace_back(u, i);
			gr[u].emplace_back(v, i);
		}
		build();
		if (!solve()) {
			cout << -1 << endl;
			continue;
		}
		cout << res.size() << endl;
		for (int id: res)
			cout << id << ' ';
		cout << endl;
	}
}

define S second

using namespace std; typedef long long ll; typedef vector vi; typedef pair<int, int> pi;

bool dfs(int node,vector&visit,vector&parent,vector<unordered_set> adj){ visit[node]=true; bool cycle=false; for(auto i:adj[node]){ if(!visit[i]){ parent[i]=node; cycle=dfs(i,visit,parent,adj); } else if(i!=parent[node])cycle=true; } return cycle; }

int main() { int t; cin >> t; while (t--) { ll n; cin >> n; vector<unordered_set> adj(n+1); vector a(n); for (int i = 0; i < n; ++i){ int num; cin>>num; adj[num].insert(i+1); adj[i+1].insert(num); } vector visit(n+1,false); vector parent(n+1,-1);

int countCycles=0,countNormal=0; for(int i=1;i<=n;++i){ if(!visit[i]){ if(dfs(i,visit,parent,adj))++countCycles; else ++countNormal; } } if(countNormal)cout<<countCycles+1<<' '; else cout<<countCycles<<' '; cout<<countCycles+countNormal<<endl; } return 0;

}

define sz(x) x.size()

template void READ(datatype arr[],int n){ For(i,n) cin>>arr[i]; } void READ() {} template<typename datatype, typename... Args> void READ(datatype& data, Args&... rest) { cin >> data; READ(rest...); }

void WRITE(){}//cout<<"";} template<typename datatype, typename... Args> void WRITE(datatype variable, Args... rest){ cout<<variable; WRITE(rest...); } int cinInt(){int a;cin>>a;return a;}

int n, o, e, mo, me, arr[2*10^5+5]; bool negORzero; void solve(){ cin>>n; o=e=negORzero=0; mo=me=10^9; READ(arr,n); for(int i=0; i<n; i++){ if(arr[i]<=0){negORzero=1;} else if(arr[i] & 1){ o++;mo=min(arr[i],mo); } else{ e++;me=min(me,arr[i]); } } cout<< (!negORzero && o==n || e==n || mo<me ? "YES" : "NO") <<'\n'; }

int main() { boost; int t; cin>>t; //READ(t); while(t--){ solve(); } return 0; }

#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; }

Комментарии (115)

Написать комментарий?

weaersedf

11 месяцев назад, # |

-52

first comment

→ Ответить

tallapallimurali987

← Rev. 2 →

206652299

what's wrong in this code?

RecursiveCo

11 месяцев назад, # ^ |

+14

total_num /= ma[cur_ele]; is wrong.

Unlike with addition/multiplication, you can't naively perform "division modulo 1e9+7" with the / operator. Instead you should multiply by the modular inverse of ma[cur_ele] (which is a way to perform division with modulo). To calculate the modular inverse of a number x, you can do x to the power of modulo-2 using a fast exponentiation function. More information can be found online.

TxRahul

8 месяцев назад, # ^ |

can be solved using segment tree as well

nonrice

← Rev. 5 →

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.

Scyther_07

Did the same. (Although didn't have enough time to solve during contest)

IMMORTAL1941

Your solution doesn't work for

k=6, m=3

1 8 16 30 31 32

You are right... now that I look at my code I am so surprised it got accept... your case isn't even unusual or anything. It is beyond me why a similar one is not in the official test set. I am remove my submission so to not confuse anyone.

Bberabi11

← Rev. 3 →

Is this related to the presented algorithm or the implementation?

I implemented the same idea in my solution and it works for this case. It also gets AC on the judge. Was this test case added to the tests after the contest?

Is there a general reason why this greedy approach with sliding window would fail?

My submission is here: https://codeforces.com/contest/1833/submission/206977596

The idea was correct. It helped me understand the editorial's solution. The problem was with the shared code. His sliding window wasn't checking if all the elements inside the window were consecutive.

While implementing I was referring to his code and couldn't understand how he was doing consecutive checks. So I tried using test cases that weren't consecutive beforehand and it failed but the same test case got the correct answer when tested on the editorial's solution.

About your code. You are checking if the elements between the left and right pointers are consecutive in the else statement of while loop. So you are maintaining consecutiveness.

It makes sense, thanks for clarifying!

yashesh_07

10 месяцев назад, # ^ |

https://codeforces.com/contest/1833/submission/210284741

Why my solution is giving runtime error for problem F? I have the same idea.

ctrller

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

Xiyy

207336476 what's wrong in this code? Please.

Check this test case:

1-2 2-3 2-4

I assume that you forgot the case when there is only the root left after running DFS

Oh,yes! b（￣▽￣）d　 Thanks

anshshah91

An O(n) Solution for D: 206614690

An O(n) solution which is quite short: Submission

Nice

71IQ

An O(n) solution which is even shorter: 206718901

Great! (I like the way you defined "FOR".)

It's stolen, but thanks

+29

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.

AKMalice

Thanks for the idea! just implemented it : 206740622

Indra_Morningstar

nice idea, was here for editorial , but seeing your comment , tried to solve on my own and ended up solving 1800 problem , thanks!

4 checks in dfs 1. if node is 1 , return 1; 2. if total nodes of subtree including current node is < 3 then return count of nodes including current node. 3. if total nodes of subtree including current node is == 3 add edge in cuts, return 0 (i.e. remove the subtree including current node from parent node calculations). 4. else make flag = true, if flag is true print -1.

implementation : https://codeforces.com/contest/1833/submission/209181115

rdjava9

D, E and F were nice. Thanks.

Mitansh_k01

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

ND_

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

not_ahmed_hamed

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

rumman_sust

It's late but still wanted to share my two cent on your solution approach. To be honest, you can take any leaf node. No need to pick the diameter. That's because any leaf node would be one of the end of a branch. Once you make a cut, the next node would either become a leaf node or it would form a single branch(eg. next node is the middle node of a branch and it has only two children). I have modified your solution slightly and it passed: 218094662

Nice solution

_pk_

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

f_in_the_chat

Here's my O(n) solution to D:

FortuneWillWinICPC

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

zoro500

My solution is similar to this idea but did not use dsu just stored the candidate edges to be removed

this is the solution: 206535400

n1k1450

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

prod /= c[k];

This is incorrect. You should multiply prod by the inverse of c[k] instead and to find the inverse you would need binary exponentiation. Refer this Binary exponentiation.

Dude, still got the same problem! :( Here's the submission

Bruh! You must keep all variables in 64bit, int would lead to overflow.

ethico

Good contest

wsc2008qwq

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.

saurabh_kadian

Since $$$b$$$ (the unique and sorted array) and $$$c$$$ (their frequencies in $$$a$$$) is derived from $$$a$$$ (the original array), there is no way of having a number occurring in $$$a$$$ and having frequency $$$0$$$.

Finally became cyan :)

Iova

:/ not anymore

Ab bol... Ab bol na mc

a1abay

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

notshashwat

206709921 Memory limit exceeded G submission with dfs recurssive, greedily checking for 2 children for a cut to be made

Can someone suggest how can I solve this

nicktohzy

Try using an explicit stack/queue instead of recursion on the call stack?

Thank you for setting this contest for us. I would like to suggest that the description for problem E would be clearer if you include the statement that "Each person participated in exactly one round dance".

If this statement were not true (ie each person can participate in multiple dances and remembers one neighbor from one of their dances), then the problem description would still fit (but I believe it's unsolvable)

bitthal04

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()

fishy15

It splits a string into a list of tokens separated by whitespace. More info can be found here.

Got it thanks

itzzRaghav

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

B_Consistent

give comment in hindi too

dhairysheel.21910784

-8

Denondi

For problem E, I believe the solution's usage of "vector<set> neighbours(n);" isn't necessary.

FlyingElephant

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.

defiler123

I wouldn't consider 30 lines solution heavy implementation... and if you came up with a more implementation-ugly solution (which seems to be in your case) than the model solution, then that alone teaches you that you can come up with a more elegant solution, so what is the issue here?

What I meant is that my main goal so far Is learning new things and, implementation apart, this problem does not teach anything at all. This is not exactly the kind of problem I would expect in a division 3. Am I wrong stating this?

pedrosorio

It teaches you how to think about and handle corner cases :)

Also, it is not "implementation heavy" at all, about 15 lines of Python.

juancs

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:)?

If in a particular component every node has exactly two neighbors, it signifies the formation of a cycle. In this case, you should consider it as a round dance. Conversely, if at least one node only has a single neighbor (referred to as a bamboo in the editorial), this indicates two possible outcomes: you can either close a cycle by treating this deficiency as a wildcard, or you can link it to other bamboos to create a larger round dance. This is how I understand it, and I hope my interpretation is helpful.

I understand why there is a cycle when in a component every node has exactly 2 neighbours. But let's say I have 1->2->3->4->2. In this case the code will mark it as a bamboo, and in my intuition, this should be marked as a separate dance now that there is a cycle greater than 2. I thought it separated in 2. cycle : 2->3->4->2 AND bamboo : 1. But in the code I see the code only counting the node with degree equal to 1. Maybe I am really confused, not sure This is the code from the editorial that I am talking about. It seems weird that it only cares about the nodes with degree equal to 1 bool bamboo = false; for (int j: component) { if (d[j] == 1) { bamboo = true; break; } }

If someone could explain this to me, I would appreciate it.

This scenario isn't possible because '2' represents a person who is part of a round dance and, as such, can only have a maximum of two neighbors.

Thanks, you're right. It even says it in the comments, I guess I mis read it.

rmz

2 месяца назад, # ^ |

i dont get it , im struggling to understand why its not a valid test case

If we look the input as an adjacency list, then we will have a graph with n edges. This graph has the property (1) each node as an outdegree exactly 1. And in the resulting graph(Round dance), each node must have degree exactly 2

If we look the previous test case I stated: 1->2->3->4->2 Node 2 has 3 neighbors, meaning that we could not build a round dance.

This means all nodes in a |cycle| > 2 will have a degree == 2. Given this, we will only be left with |cycles| > 2 and bamboos. Cycles with size 2 does not follows the propery that each node has degree == 2, so it is taken as a normal edge.

Let me know if you need more help.

i got all of it except the test case part , i'm saying why cant we do 1->2->3->4->2 in 2 rounds

first round 1->2->3->4

second round 2->4->2

1->2->3->4->2 is not a valid test case node 2 would be neighbor with node 1, 2, and 4 The problem states that each node must have exactly 2 neighbors. The statement says each person remembers only 1 neighbor, meaning that the starting graph must be a subset of the ending graph

thanks for your efforts , i get it now

No problem, any other doubt or question is welcome

SystemTesting

ummm, you can think it in a better approach.... we will store the the graph in a adjacency list. Then we can just run a dfs for every unvisited node(1-n) and if it gets visited we will mark it as visited. So the number of times the dfs has run is the max count, and while running the dfs we will also check if the graph has cycle, if it has cycle we will increase minimum value by 1, and at last we will just check if maximum is greater than minimum, if it is then we can increase minimum by 1, because the total maximum count will make another cycle. You can see the solution to get a clear idea 207292218

codesniper99

Hi, can someone help me with D question For this input:

1
12
2 3 4 5 6 7 8 9 10 11 12 1 4

why is answer output

12 1 11 10 9 8 7 6 5 4 3 2

Shouldnt we want to move the 9 to the first position? By doing so we ensure that our final array will start with a 9 and will be lexicographically maximum?

instead answer moves 12 to start which makes number begin with a 1 then a 2 which would be less than a 9??

Please help I dont understand

According to the problem, a permutation 'a' is considered lexicographically greater than permutation 'b' if there's an 'i' (where 1≤i≤n) such that a[j] equals b[j] for 1≤j<i, and a[i] is greater than b[i]. Thus, in this context, 12 is superior to 9.

EDIT: Example 7 may have misled you. However, since the operations described must be applied exactly once, the initial 10 couldn't have remained untouched.

oh got it, thanks

AW_Flister

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

cwxcai

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

Mrinall

Given an undirected graph where each node has a maximum of two neighbors, find the maximal and minimal number of connected components the graph can have while still fulfilling the initial condition (each node must have a maximum of two neighbors).

Very clear, thank you！

AshishLikePanner

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

what's the meaning of "even" and "odd" in your code? it's too complicated.

juneharold

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

stas_sl

I would call them also "chains", basically just a sequence of connected nodes a — b — c — d ...

Ahmed_Ashraf_f

nice contest

aniketabhiraj2004

A simpler solution of G is 206896718

nikolatesla999001

Thanks! Now I can understand.

HelloFromUnknown

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.com/contest/1833/submission/206588962

adibur6

The main problem with your code is this line. while(cnt[ind]) ind++;
This loop runs for some test cases, like the following:

Spoiler

1
10 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

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.

nikitakuchinisme

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?

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

I believe you're getting the 2nd step wrong. You can't arbitrarily choose prefix and suffix after reversing a segment. If you choose to reverse the segment p[l,r] then you have to choose segments p[1,l-1] and p[r+1,n] to swap.

In the example you provided with the array [2,3,1,5,4], if you choose to reverse the segment [2,3], you should also swap the segments [ ] (empty segment before 2) and [1,5,4] (segment after 3). Following these steps, the resulting array would be [1,5,4,3,2].

oh, i finally got it, thanks a lot!

cftryharder

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.com/contest/1833/submission/207332694

Try this one.

Test case

Thank you!

I got AC. The main issue is that I was tracking the leaves wrong. I was not accounting the degree of the nodes that I've was pushing to the queue.

I ended up also doing a random input generator :/, because I just checked this comment.

Chinu7445

I did the similar code for problem E of this, but I got TLE. The only difference is I applied DFS instead of BFS in my code.

include

define rep(i, a, b) for (int i = a; i < b; ++i)

define PB push_back

define F first

carolinux

In Python, the following code TLE's for F. If I uncomment the sorting of the list it passes. What's going on? Am I hitting some bad case with the set() function?

def solve(n_orig, m, a):
    #a.sort() # this is somehow necessary?
    cnt = Counter(a)
    sk = sorted(list(set(a)))
    n = len(sk)
    #... correct code after that #

369

in problem B if in array b the minimum element is 11 for array a = [1,3,3,5,9] then is sorting array b efficient?

Sabamak

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

I am unable to understand the idea behind the code

why write tutorial when you fail to clear the concept

shitty editorial... can't understand a thing

This is shit

they don't even give answer to comments

"They" don't have time to reply to everyone.

suyasho786

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

yeyeyey1

bro has -10^9 temperature ☠️☠️☠️☠️☠️☠️☠️☠️

10 месяцев назад, # |

I have done the following solution for G.

I have created a map that will store that whether a edge has been broken or not. So I have started a DFS from the vertex 1 and go till I have found a broken able edge or not.

By broken able edge I mean whether I found two single degree children for the node or a node that is parent of a single node only which is having a degree 1. So using this thing in mind I tried to find if the generated graph is the required one or not, for that I checked if the components that are formed this way is containing 3 nodes only or not. if it is not then -1 will be the answer else I will check which of the edges are in the broken state so print them thinking them as my answer. I am not able to get sure that the solution I will be forming is the unique one which the question is asking. The submitted code: submission

34z12000

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

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

210284741

sr_saad

9 месяцев назад, # |

Can anyone tell me what's the problem here?

include<bits/stdc++.h>

using namespace std;

define boost ios_base::sync_with_stdio(false);cin.tie(NULL);

define ll long long int

define undefined -1

define pie 3.141592653589793

define For(i,n) for(int i=0;i<n;i++)

define For_(i,v,n) for(int i=v;i<n;i++)

define vfind(v,i) find(v.begin(), v.end(), i);

define viint vector::iterator

define vii2int(v,i) i — v.begin()

Arnur2937

8 месяцев назад, # |

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

Penguin1729

4 месяца назад, # |

4 месяца назад, # ^ |

Can someone tell why I am getting memory limit exceeded?

BF_OF_Priety

3 месяца назад, # |

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?

AnishchukT

3 недели назад, # |

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.

Блог пользователя Vladosiya

include

include

include

include

include

include

include

include

include

define rep(i, a, b) for (int i = a; i < b; ++i)

define PB push_back

define F first

define S second

include<bits/stdc++.h>

define boost ios_base::sync_with_stdio(false);cin.tie(NULL);

define ll long long int

define undefined -1

define pie 3.141592653589793

define For(i,n) for(int i=0;i<n;i++)

define For_(i,v,n) for(int i=v;i<n;i++)

define vfind(v,i) find(v.begin(), v.end(), i);

define viint vector::iterator

define vii2int(v,i) i — v.begin()

define sz(x) x.size()