Codeforces Round #844 (Div. 1 + Div. 2)

Hello!

Welcome to the Codeforces Round 844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) that will start on Jan/15/2023 15:05 (Moscow time). It will be a combined rated round for both divisions and open to everyone.

This round is a mirror of VK Cup 2022 Elimination — annual programming championship for Russian-speaking competitors organized by VK. VK Cup started in 2012 and has grown to be a five-track competition in competitive programming, Mobile, ML, Go, and JavaScript.

All the problems are authored and prepared by me. Thanks to KAN, errorgorn, lperovskaya, dario2994, Monogon, Arpa for making this round better.

You will be given 8 problems and 3 hours to solve them.

UPD: Editorial

Congratulations to the winners:

and to maroonrk for getting the only accepted solution to problem H2.

#include <bits/stdc++.h> using namespace std; #define nl '\n' #define sp ' ' #define ll long long #define vi vector<int> #define vl vector<ll> #define vvi vector<vi> #define vvl vector<vl> #define si unordered_set<int> #define sl unordered_set<ll> #define tsi set<int> #define tsl set<ll> #define pii pair<int,int> #define pll pair<ll,ll> #define vpii vector<pii> #define vpll vector<pll> #define tmii map<int,int> #define tmll map<ll,ll> #define mii unordered_map<int,int> #define mll unordered_map<ll,ll> #define pqi priority_queue<int> #define pqig priority_queue<int,vi,less<int>> #define pql priority_queue<ll> #define pqlg priority_queue<ll,vl,less<ll>> #define pqpii priority_queue<pii> #define pqpll priority_queue<pll> #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define yesno(a) cout<<((a)?"YES\n":"NO\n"); #define outrange(x,min,max) ((x)<(min) || (x)>(max)) #define nano (chrono::system_clock::now().time_since_epoch().count()) #define init_rng mt19937 rng(nano) template<typename L,typename R> ostream& operator<<(ostream& out,pair<L,R>& p){ out<<'('<<p.first<<','<<p.second<<')'; return out; } template<typename T> ostream& operator<<(ostream& out,vector<T>& v){ for(auto &i:v) out<<i<<' '; out<<nl; return out; } template<typename K,typename V> ostream& operator<<(ostream& out,map<K,V>& m){ out<<'['; for(auto &[k,v]:m) { out<<k<<':'<<v<<sp; } out<<"]\n"; return out; } template<typename K,typename V> ostream& operator<<(ostream& out,unordered_map<K,V>& m){ out<<'['; for(auto &[k,v]:m) { out<<k<<':'<<v<<sp; } out<<"]\n"; return out; } #ifdef adj8 int dx[8]={1,1,0,-1,-1,-1,0,1}; int dy[8]={0,1,1,1,0,-1,-1,-1}; #endif #ifdef adj4 int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; #endif const int MAX=55; int a[MAX]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; //cin>>t; t=50; while(t--){ int n; n=50;//cin>>n; for(int i=0;i<n;i++){ //cin>>a[i]; a[i]=1+20408160*i; } int count=0; mll m; for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++){ int p=a[i]; int q=a[j]; if((3&(q-p))==2) continue; int k=2; if((q-p)&1) k--; for(;k*k<=q-p;k+=2){ count++; if((q-p)%k) continue; int l=(q-p)/k; if((k+l)&1) continue; ll n=(k+l)>>1; ll x=n*n-q; if(x>=0) m[x]++; } } } if(m.empty()) cout<<1<<nl; else{ ll max=0; for(auto [k,v]:m){ if(v>max) max=v; } max=1+(ll)sqrt(2*max); cout<<max<<nl; } cout<<count<<nl; } }