Problem A: find missing space

Really excited for this contest. Don't know why.(◠‿◠)

as a tester, I can assure that problemset is perfectly balanced , all problems are interesting and I recommend to read all the problems

As a participant, I will appreciate the work of authors and testers. Thank you for the contest!

As a !non-Tester, I tried to solve problems and give proper feedback. glhf

As an author, I wish all <1600 participants getting their free expert this round!

this is gonna be my first contest! wahoo!

Как одна из тестировщиц раунда хочу сказать, что задачи интересны и приятны. Желаю всем участникам удачи и удовольствия от раунда!

As a participant, I will achieve a 4 long streak of losing rating in div3

it's not related to this blog :

can some one give me the list or easy to medium problems for DP to kickstart my learning ( like any difficulty wise or something ) for beginner level to medium and you can share any resources or suggestions ....

Thanks in advance!

Really excited for this contest. Looking forward to becoming a pupil soon:)

How can we be a tester? Plz don't downvote.

As a non tester....... how to be tester? (I thought only purple+ can test).

hope to become an expert

Give me contribution

How to hack a solution during contest?

yayyy my first contest!! let's so how it goes

Please provide hints and proofs for the problems along with editorials

It helps in upsolving and understanding concepts for beginners instead of directly jumping to solutions :)

This is my first round in Codeforces. I really want to get more ratings.

hoping for 160 + Delta. feels like mission impossible... xD

I'll try my best, wish me luck

glhf

Hope everyone after this contest will change color:)

I've participated in more than 5 rated contests and my rating is <1900 why I'm not in the official standings table?

is there anyone else who did not read the problem C properly and just guessed the solution from sample test cases?

did g and f leak? Sudden increase in submissions for both

When can you submit in practice?

How to do G2?

Thanks a ton for such a contest. Getting to Expert in style :)

Is G2 based on the fact like finding all unique GPs of common ratio upto 30 then doing some trick(no idea) to find GPs of ratio greater than 30 also using the GPs of common ratio upto 30?

Div.3: The contest where you can literally ask WolframAlpha to solve C, without reading description at all

Finally Expert this time.

Such a great contest, really loved it, Problem F was the nicest and cute problem!

As a pupil I'm becoming a newbie

What was the logic in problem C? I guessed from the test cases.

I saw problem E before in codechef but with minimum difference prob

int n;
    cin>>n;
    vector<ll>v(n);
    map<ll,int>mp;
    for(int i=0;i<n;i++){
        cin>>v[i];
        mp[v[i]]++;
    }
    vector<ll>t;
    for(auto& m:mp){
        t.pb(m.ff);
    }
    v = t;
    sort(all(v));
    ll ct = 0;
    for(ll r=2;r<=1e3;r++){
        for(int j=0;j<n;j++){
            if(mp[v[j]*r]>0 && mp[v[j]*r*r]>0){
                ct+=(mp[v[j]]*mp[v[j]*r]*(mp[v[j]*r*r]));
            }
        }
    }
    for(auto& m:mp){
        if(m.ss>=3){
            ct+=(m.ss)*(m.ss-1)*(m.ss-2);
        }
    }
    cout<<ct<<endl;

Why TLE?

Problem G1 :

when I use vector freq((int)1e6 + 1);

I got TLE

after replace it with int freq[(int)1e6+1];

I got Acc

How can this happens?? If I use array by luck I got Acc!! it's bad tests

A: If a[i]+i-1<=t we can choose the i-th video.

B: First we can choose (i, j) where a[i]*a[j] is the maximum product and remove all other elements. We sort all non-zero elements in a[i] and consider the maximum non-zero product. If there's less than 2 non-zero elements, the answer is 0. If there's 2 non-zero elements, the maximum non-zero product is their product. Otherwise, there must be 2 elements with same sign, and their product will be positive. We need to pick 2 elements with same sign and maximum absolute value to get the maximum product.

C: The answer is (n+1)^2+1 (by looking at examples), but how to prove it? Well, if we change the size of a cinnabon roll from n-1 to n, we need to add 2*n+2 chocolate outside, add 1 chocolate and remove 2 chocolate inside, so we have ans(n)=ans(n-1)+(2*n+1). Therefore we can get answer by induction.

D: First if i>1 and a[i]=n, we have b[i]=(b[i-1]+n)%n=b[i-1], so b[i] cannot be a permutaion, then we have a[1]=n. If n is odd, (n+1)/2 is integer, then we have b[1]=a[1]%n=0, b[n]=(1+2+...+n)%n=(n*(n+1)/2)%n=0, so b[i] cannot be a permutaion. If n is even, let a={n, n-1, 2, n-3, 4, n-5, ...}, then b={0, n-1, 1, n-2, 2, n-3, ...} is a permutaion.

E: If n is odd there's no solution. If there's any char c that there are more than n/2 occurences of c, there's no solution because by the piegonhole principle, there are n/2 pairs of symmetric positions and there are more than n/2 occurences of c, so there must be a pair of positions occupied by c. Otherwise, solution must exist. To calculate the minimum number of operations, let's see what can we do in one operation: For something like ..a..b..|..b..a.. (where '|' denotes the axis of symmetry), we can swap (ba) to turn it into ..a..b..|..a..b.. and remove 2 bad pairs; for something like ..a..b..|..b..c, we can swap (bc) to turn it into ..a..b..|..c..b and remove 1 bad pair. In other words, we can remove 2 different bad pairs or 1 bad pair in one operation. So we can calculate the number of bad pairs of chars from 'a' to 'z' and then we can get the answer.

F: Let ecc[i]=max(1<=j<=n)(dist(i, j)), then the cost of the tree rooted at i is k*ecc[i], and the cost of moving root from 1 to i is c*dist(1, i), so the answer is k*ecc[i]-c*dist(1, i). We can calculate dist(1, i) by BFS, and to find ecc[i] we can find a diameter of the tree, if (u, v) is a diameter, then ecc[i]=max(dist(u, i), dist(v, i)).

G1: The number of good triples where b==1 is sum(cnt[t]*(cnt[t]-1)*(cnt[t]-2)) where t iterate over all values of a[i], so we assume b>=2 for other good triples. For each possible value of k, we can see the maximum possible value of b is not greater than sqrt(a[k]), so the contribution of k is sum(cnt[a[k]/b]*cnt[a[k]/(b*b)]) where 1<=b, b*b<=k. The complexity is O(n*sqrt(A)).

G2: To optimize the solution of G1, we can see that if a[k]/(b*b) is integer, let c=a[k]/(b*b), we have a[k]=b*b*c, then we have b<=cbrt(a[k]) or c<=cbrt(a[k]), so we can find all possible combinations of (b, c) in O(cbrt(a[k])). We can solve the problem in O(n*cbrt(A)) using Hashmap or O(n*log(n)*cbrt(A)) using Treemap for checking cnt[t].

global arrays >>>> unordered_map<int, int, custom_hash> :(

deleted

Can someone explain why my solution to G1 is timing out? https://codeforces.net/contest/1822/submission/203347556

Basically I check all possibilities for the middle element. For each distinct element a, I go through all factors x of a and add up (# of a/x)*(# of a)*(# of xa). This should take O(120n) since each number in [1, 10^6] has <=120 factors, which should pass; however, it TLEs. Can someone help? Thank you.

Problem statement C was very hard to understand. At least for me.

Небольшие заметки о том, как решать все задачи из этого контеста с ссылками на исходники на C++.

Скопипастил то, что Slamur написал в Telegram-канал:

Could someone explain problem D?

I want to ask why the problem G1 my code's time complexity is (2e5*ln1e6) , but I get several times Time Limit Exceed? Can someone help？Thank you very much! This is my code:

#pragma GCC optmize(3)
#pragma GCC optmize(2)
#pragma GCC optmize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1000010,mod=1e9+7;
int a[N],n;
long long c[N];
int b[200010];
void solve()
{
	cin>>n;
	int mx=0;
	for (int i=1;i<=n;i++)
	{
		cin>>b[i];
		c[b[i]]=-1;
		a[b[i]]++;
		mx=max(mx,b[i]);
	}
	long long ans=0;
	for (int i=1;i<=n;i++)
	{
		long long res=0;
		if (c[b[i]]!=-1)
		{
			ans+=c[b[i]];
			continue;
		}
		if (a[b[i]]>=3)
			res=res+(a[b[i]]-1)*(a[b[i]]-2);
		for (int j=2;j<=mx/b[i];j++)
			if (b[i]%j==0)
				res=res+a[b[i]/j]*a[b[i]*j];
		ans+=res;	
		c[b[i]]=res;			
	}
	for (int i=1;i<=n;i++)
		a[b[i]]=0;
	cout<<ans<<'\n';
}
signed main()
{
	cin.tie(0)->sync_with_stdio(false);
	int t=1;
	cin>>t;
	while (t--)
		solve();
}

hacked :(

What is the expected rating of problem E?

• What is the expected rating of problem E?
• What is mostly rating range of problem E in Div 3?
• What is mostly rating range of problem D in div2?

Wonderful div3 round,i learned new things this round.Thanks to problemsetters!

Any hint or idea for problem D ?

Why does G1 has to have so tight constraints I submitted it in python and got that question hacked. Please make it fair for all languages. Atleast try to make in python and c++ many beginners use python.

A rated round should not have had problem F. Its a blatant copy of the general standard problem of finding max distance of a node from each node of a tree. https://cses.fi/problemset/task/1132.

I highly doubt setters were unaware of this since its literally in cses. Please unrate the round in the future before pulling such schenanigans. Contest is not meant to copypaste submission and modify 2- 3 lines to get AC. (I say this as someone who got the problem in under 4 mins due to this exact reason)

Could please someone explain why this submission of G2 TLE's

My current rating is 401. I've submitted solution of 5 problems of Codeforces Round #867 (Div.3), and all submissions was accepted. a This is my 2nd contest, but still my rating is not increased. Can anyone tell why?

To be honest ,I still do not understand Problem C,but just by observing the test cases,I came out to the solution

Is there anyone like me who like Div 2 rounds more than the Div 3 ones?

I'm new in contestant in Codeforces. I wanna clear that is Codeforces Round 867 (Div. 3) was a rated contest? I solved two problem(A & C) but my rating/rank is looks like that...

This is the first time ever I solve a div3 F instantly. I can't believe that there was a time when I struggle to solve div3 E. It feels pretty amazing

no way,i think e is harder than f and g1 XD

Hello friends, I have uploaded the video editorial of this contest from A to F. Editorial. If want, You can watch it!!!

I feel like problem C and D are just "guess correct solution" problems / see pattern. Is this kind of problems okey for you guys?