Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2) —— Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorial is loading...

Solution(arsijo)


#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
	cin >> n;
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int S = a + b + c + d;
	int Ans = 1;
	for(int i = 2; i <= n; i++)
	{
	    cin >> a >> b >> c >> d;
	    if(a + b + c + d > S)
	    {
	        Ans++;
	    }
	}
	printf("%d\n",Ans);
	return 0;
}

Tutorial is loading...

Solution(arsijo)


#include <bits/stdc++.h>
using namespace std;

long long ar[4];
char c1[4] = {'0', '0', '1', '1'};
char c2[4] = {'0', '1', '0', '1'};

int main() {
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 4; j++){
            if(c1[j] == a[i] && c2[j] == b[i]){
                ar[j]++;
            }
        }
    }
    cout << ar[0] * ar[2] + ar[0] * ar[3] + ar[1] * ar[2] << endl;
    return 0;
}

Tutorial is loading...

Solution(Magolor)


#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int n, L, A[MAXN+5];
int main()
{
	n = rf();
	L = (int)sqrt(n);
	for(rint i = 1, o = n, j; i <= n; i += L)
		for(j = min(i+L-1,n); j >= i; A[j--] = o--);
	for(rint i = 1; i <= n; i++)
		printf("%d%c",A[i],"\n "[i<n]);
	return 0;
}

Tutorial is loading...

Solution(Magolor)


#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int Wu[4096], f[64][64][104], g[4096][104], w[16], m, n, q, E, K, B = 6, L = 63, H = 4032; char _[16];
int main()
{
	m = rf();
	n = rf();
	q = rf();
	generate(w,w+m,rf);
	E = 1<<m;
	for(rint S = 0, j; S < E; S++)
	{
		for(j = 0; j < m; j++)
			S&1<<j?:Wu[S]+=w[j];
		Wu[S] = min(Wu[S],101);
	}
	for(rint i = 1, j, S; i <= n; i++)
	{
		scanf("%s",_+1);
		for(S = 0, j = m; j; j--)
			S = S<<1|(_[j]^'0');
		for(j = 0; j < 64; j++)
			++f[(S&H)>>B][j][Wu[((j^(S&L))|H)&~-E]];
	}
	for(rint S = 0, a, b, j; S < E; S++)
	{
		for(j = 0; j < 64; j++)
			for(a = 0, b = Wu[(((j<<B)^(S&H))|L)&~-E]; b <= 100; a++, b++)
				g[S][b] += f[j][S&L][a];
		partial_sum(g[S],g[S]+101,g[S]);
	}
	for(rint i = 1, j, S; i <= q; i++)
	{
		scanf("%s",_+1);
		for(S = 0, j = m; j; j--)
			S = S<<1|(_[j]^'0');
		printf("%d\n",g[S][rf()]);
	}
	return 0;
}

Tutorial is loading...

Solution(Magolor)


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
//=====Computational Geometry Definitions
struct Vec
{
	int x,y; Vec(){} Vec(int _x, int _y){x=_x,y=_y;} inline Vec operator + (Vec b){return Vec(x+b.x,y+b.y);}
	inline Vec operator - (Vec b){return Vec(x-b.x,y-b.y);} inline Vec operator - (){return Vec(-x,-y);}
	inline ll operator * (Vec b){return (ll)x*b.x+(ll)y*b.y;} inline ll operator % (Vec b){return (ll)x*b.y-(ll)b.x*y;}
	inline ll operator ~ (){return (ll)x*x+(ll)y*y;} inline bool operator < (const Vec &b)const{return x^b.x?x<b.x:y<b.y;}
	inline bool operator ==(Vec b){return x==b.x&&y==b.y;} inline bool operator !=(Vec b){return x^b.x||y^b.y;}
};	typedef Vec Pt; inline bool ToLeft(Vec a, Vec b){return b%a>0;} inline bool Para(Vec a, Vec b){return !(a%b);}
Pt LTL; inline bool cmpltl(Pt a, Pt b){a = a-LTL; b = b-LTL; return Para(a,b) ? ~a<~b : ToLeft(b,a);}
typedef vector<Pt> Poly; Poly A, B, C, D; typedef vector<ll> Str; Str T, S; int n, m; vector<int> nex;
//=====
void CH(Poly &A, Poly &R)
{
	R.push_back(Pt());
	LTL = *min_element(A.begin(),A.end());
	sort(A.begin(),A.end(),cmpltl);
	for(rint i = 0; i < (int)A.size(); i++)
	{
		for(; R.size()>2&&!ToLeft(A[i]-R.back(),R.back()-R[R.size()-2]); )
			R.pop_back();
		R.push_back(A[i]);
	}
	R[0] = R[R.size()-1];
	R.push_back(R[1]);
}
void CTOS(Poly &p, Str &s)
{
	s.push_back(0);
	for(rint i = 1; i < (int)p.size()-1; i++)
	{
		s.push_back(~(p[i]-p[i-1]));
		s.push_back((p[i]-p[i-1])%(p[i+1]-p[i]));
	}
}
void CalNex()
{
	nex.resize(m+1);
	for(rint i = 2, j = 1; i <= m; i++)
	{
		for(; j>1&&S[i]^S[j]; )
			j = nex[j-1]+1;
		j += S[i]==S[j];
		nex[i] = j-1;
	}
}
bool KMP()
{
	for(rint i = 1, j = 1; i <= n; i++)
	{
		for(; j>1&&(j>m||T[i]^S[j]); )
			j = nex[j-1]+1;
		j+=T[i]==S[j]; 
		if(j>m)
			return true;
	}
	return false;
}
int main()
{
	A.resize(rf()); B.resize(rf());
	for(rint i = 0, s = (int)A.size(); i < s; i++)
		A[i].x = rf(), A[i].y = rf();
	CH(A,C);
	CTOS(C,T);
	n = T.size()-1;
	for(rint i = 0, s = (int)B.size(); i < s; i++)
		B[i].x = rf(), B[i].y = rf();
	CH(B,D);
	CTOS(D,S);
	m = S.size()-1;
	for(rint i = 1, s = (int)T.size(); i < s; i++)
		T.push_back(T[i]);
	n <<= 1;
	CalNex();
	puts(KMP()?"YES":"NO");
	return 0;
}

Solution(Kostroma)


#pragma comment(linker, "/STACK:512000000")
#define _CRT_SECURE_NO_WARNINGS
//#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
using li = long long;
using ld = long double;
void solve(bool);
void precalc();
clock_t start;
int main() {
#ifdef AIM
  freopen("/home/alexandero/CLionProjects/ACM/input.txt", "r", stdin);
//freopen("/home/alexandero/CLionProjects/ACM/output.txt", "w", stdout);
//freopen("out.txt", "w", stdout);
#else
  //freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
  start = clock();
  int t = 1;
#ifndef AIM
  cout.sync_with_stdio(0);
  cin.tie(0);
#endif
  cout.precision(20);
  cout << fixed;
//cin >> t;
  precalc();
  while (t--) {
    solve(true);
  }
  cout.flush();

#ifdef AIM1
  while (true) {
solve(false);
}
#endif

#ifdef AIM
  cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif
  return 0;
}

//BE CAREFUL: IS INT REALLY INT?

template<typename T>
T binpow(T q, T w, T mod) {
  if (!w)
    return 1 % mod;
  if (w & 1)
    return q * 1LL * binpow(q, w - 1, mod) % mod;
  return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
  while (w) {
    q %= w;
    swap(q, w);
  }
  return q;
}
template<typename T>
T lcm(T q, T w) {
  return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& vec) {
  sort(all(vec));
  vec.erase(unique(all(vec)), vec.end());
}

template<typename T>
void relax_min(T& cur, T val) {
  cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
  cur = max(cur, val);
}

void precalc() {

}

#define int li
//const li mod = 1000000007;
//using ull = unsigned long long;

struct Point {
  int x, y;
  Point() {}
  Point(int x, int y) : x(x), y(y) {}
  Point operator - (const Point& ot) const {
    return Point(x - ot.x, y - ot.y);
  }
  int operator * (const Point& ot) const {
    return x * ot.y - y * ot.x;
  }
  void scan() {
    cin >> x >> y;
  }
  bool operator < (const Point& ot) const {
    return make_pair(x, y) < make_pair(ot.x, ot.y);
  }
  int sqr_len() const {
    return x * x + y * y;
  }
  long double get_len() const {
    return sqrtl(sqr_len());
  }
  int operator % (const Point& ot) const {
    return x * ot.x + y * ot.y;
  }
};

struct Polygon {
  vector<Point> hull;
  Polygon(int n) {
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
      points[i].scan();
    }
    sort(all(points));
    vector<Point> up, down;
    for (auto& pt : points) {
      while (up.size() > 1 && (up[up.size() - 2] - up.back()) * (pt - up.back()) >= 0) {
        up.pop_back();
      }
      up.push_back(pt);
      while (down.size() > 1 && (down[down.size() - 2] - down.back()) * (pt - down.back()) <= 0) {
        down.pop_back();
      }
      down.push_back(pt);
    }
    hull = up;
    for (int i = (int)down.size() - 2; i > 0; --i) {
      hull.push_back(down[i]);
    }
  }
  int sqr_len(int pos) const {
    return (hull[(pos + 1) % hull.size()] - hull[pos]).sqr_len();
  }
  int size() const {
    return (int)hull.size();
  }
  long double get_angle(int pos) const {
    auto a = hull[(pos + 1) % hull.size()] - hull[pos], b = hull[(pos + hull.size() - 1) % hull.size()] - hull[pos];
    long double co = (a % b) / a.get_len() / b.get_len();
    return co;
  }
};

void solve(bool read) {
  vector<Polygon> polys;
  int n[2];
  cin >> n[0] >> n[1];
  for (int i = 0; i < 2; ++i) {
    polys.emplace_back(n[i]);
  }
  if (polys[0].size() != polys[1].size()) {
    cout << "NO\n";
    return;
  }
  vector<long double> all_lens;
  int m = polys[0].size();
  for (int i = 0; i < m; ++i) {
    all_lens.push_back(polys[0].sqr_len(i));
    all_lens.push_back(polys[0].get_angle(i));
  }
  all_lens.push_back(-1);
  for (int j = 0; j < 2; ++j) {
    for (int i = 0; i < m; ++i) {
      all_lens.push_back(polys[1].sqr_len(i));
      all_lens.push_back(polys[1].get_angle(i));
    }
  }
  /*for (int x : all_lens) {
    cout << x << " ";
  }
  cout << "\n";*/
  vector<int> p(all_lens.size());
  for (int i = 1; i < p.size(); ++i) {
    int j = p[i - 1];
    while (j > 0 && all_lens[i] != all_lens[j]) {
      j = p[j - 1];
    }
    if (all_lens[i] == all_lens[j]) {
      ++j;
    }
    p[i] = j;
    if (p[i] == 2 * m) {
      cout << "YES\n";
      return;
    }
  }
  cout << "NO\n";

}

Tutorial is loading...

Solution(Magolor,optimized by arsijo)


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned int
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
bitset<100000032> _b; int n; uint A, B, C, D, Ans;
inline uint f(int p){
    return((A*p+B)*p+C)*p+D;
}
inline int cnt(int p, int n){
    int r=0;
    for(;n/=p;r+=n);
    return r;
}
inline auto b(int i)->decltype(_b[0]){
    return _b[(i&1)&&(i%6!=3)?i/6<<1|((i%6)>1):0];
}
inline auto b2(int i)->decltype(_b[0]){
    return _b[i/6<<1|1];
}
inline auto b3(int i)->decltype(_b[0]){
    return _b[i/6<<1];
}

int main()
{
    n = rf();
    A = rf();
    B = rf();
    C = rf();
    D = rf();
    _b[0] = 1;
    Ans = cnt(2,n)*f(2)+cnt(3,n)*f(3);
    for(rint i = 5, j, z, c, w; i <= n; i += 4){
        if(!b2(i))
        {
            Ans += cnt(i,n)*f(i);
            if(i <= 20000){
                w = i + i;
                c = w % 6;
                z = (i * i) % 6;
                if(c == 0){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w){
                            b3(j) = 1;
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w){
                            b2(j) = 1;
                        }
                    }
                }else if(c == 2){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w){
                            b3(j) = 1;
                            j += w + w;
                            if(j <= n){
                                b2(j) = 1;
                            }
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w + w){
                            b2(j) = 1;
                            j += w;
                            if(j <= n){
                                b3(j) = 1;
                            }
                        }
                    }
                }else if(c == 4){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w + w){
                            b3(j) = 1;
                            j += w;
                            if(j <= n){
                                b2(j) = 1;
                            }
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w){
                            b2(j) = 1;
                            j += w + w;
                            if(j <= n){
                                b3(j) = 1;
                            }
                        }
                    }
                }
            }
        }
        i += 2;
        if(i <= n && !b3(i))
        {
            Ans += cnt(i,n)*f(i);
            if(i <= 20000){
                w = i + i;
                c = w % 6;
                z = (i * i) % 6;
                if(c == 0){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w){
                            b3(j) = 1;
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w){
                            b2(j) = 1;
                        }
                    }
                }else if(c == 2){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w){
                            b3(j) = 1;
                            j += w + w;
                            if(j <= n){
                                b2(j) = 1;
                            }
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w + w){
                            b2(j) = 1;
                            j += w;
                            if(j <= n){
                                b3(j) = 1;
                            }
                        }
                    }
                }else if(c == 4){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w + w){
                            b3(j) = 1;
                            j += w;
                            if(j <= n){
                                b2(j) = 1;
                            }
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w){
                            b2(j) = 1;
                            j += w + w;
                            if(j <= n){
                                b3(j) = 1;
                            }
                        }
                    }
                }
            }
        }
    }
    printf("%u\n",Ans);
    return 0;
}

Solution(000000)


#include <bits/stdc++.h>

using namespace std;
typedef unsigned int ll;
const ll maxn=4e8;
const ll maxp=sqrt(maxn)+10;
ll f[4][maxp],g[4][maxp];
ll n,m,A,B,C,D,ans,res,tmp,rt;

ll p1(ll x){
    ll y=x+1; if (x%2==0) x/=2; else y/=2;
    return x*y;
}
ll p2(ll x){
    long long y=x+1,z=x*2+1;
    if (x%2==0) x/=2; else y/=2;
    if (z%3==0) z/=3; else if (x%3==0) x/=3; else y/=3;
    return (ll)x*y*z;
}
ll p3(ll x){
    ll y=p1(x);
    return y*y;
}
bool is_prime(ll x){
    for (ll i=2;i*i<=x;i++) if (x%i==0) return false;
    return true;
}

ll solve(ll n)
{
    ll i,j,rt,o[4];
    for (m=1;m*m<=n;m++) {
        f[0][m]=(n/m-1);
        f[1][m]=(p1(n/m)-1)*C;
        f[2][m]=(p2(n/m)-1)*B;
        f[3][m]=(p3(n/m)-1)*A;
    }
    for (i=1;i<=m;i++) {
        g[0][i]=(i-1);
        g[1][i]=(p1(i)-1)*C;
        g[2][i]=(p2(i)-1)*B;
        g[3][i]=(p3(i)-1)*A;
    }
    for (i=2;i<=m;i++) {
        if (g[0][i]==g[0][i-1]) continue;
        o[0]=1; for (int w=1;w<4;w++) o[w]=o[w-1]*i;
        for (j=1;j<=min(m-1,n/i/i);j++)
            for (int w=0;w<4;w++)
                if (i*j<m) f[w][j]-=o[w]*(f[w][i*j]-g[w][i-1]);
                else f[w][j]-=o[w]*(g[w][n/i/j]-g[w][i-1]);
        for (j=m;j>=i*i;j--)
            for (int w=0;w<4;w++)
                g[w][j]-=o[w]*(g[w][j/i]-g[w][i-1]);
    }
    for (int i=1;i<=m+1;i++) f[0][i]*=D,g[0][i]*=D;
    rt=0;
    for (ll i=1;n/i>m;i++) {
        for (int w=0;w<4;w++) rt+=(f[w][i]-g[w][m]);
        //cout<<"H"<<rt<<endl;
    }
    return rt;
}

int main()
{
    //freopen("input.txt","r",stdin);
    ll n; cin >> n >> A >> B >> C >> D;
    ans=solve(n);
    for (ll i=2;i<=m;i++){
        if (is_prime(i)){
            res=A*i*i*i+B*i*i+C*i+D; tmp=n;
            while (tmp){
                ans+=res*(tmp/i);
                tmp/=i;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Tutorial is loading...

Solution(arsijo)


#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5 + 10;

bool black[MAX]; // is it vertex black now
vector<int> vec[MAX]; // main edges
bool old_black[MAX]; // to remember the tree before block

const int MAX_BLOCK_SIZE = 600;

int t[MAX], v[MAX]; // queries

bool used[MAX]; // is in mini-tree
vector<pair<pair<int, int>, int> > v2[MAX]; // mini-tree edges (son, number of white vertices, dist)
int push[MAX]; // push of the i-th vertex in mini-tree
bool clear[MAX]; // do we need to clear first

void dfs_1(int pos, int prev = -1, int white = 0, int dist = 0){
    if(used[pos]){
        if(prev != -1){
            v2[prev].push_back(make_pair(make_pair(pos, white), dist));
        }
        for(int a : vec[pos]){
            dfs_1(a, pos, 0, 0);
        }
    }else{
        if(!black[pos]){
            white++;
        }
        for(int a : vec[pos]){
            dfs_1(a, prev, white, dist + 1);
        }
    }
}

void make_1(int pos){
    if(!black[pos]){
        black[pos] = true;
        return;
    }
    push[pos]++;
    for(auto a : v2[pos]){
        if(a.first.second + 1 <= push[pos]){
            make_1(a.first.first);
        }
    }
}

void make_2(int pos){
    black[pos] = false;
    push[pos] = 0;
    clear[pos] = true;
    for(auto &a : v2[pos]){
        a.first.second = a.second;
        make_2(a.first.first);
    }
}

void dfs_2(int pos, int p = 0, bool cl = false){
    if(used[pos]){
        p = push[pos];
        cl |= clear[pos];
    }else{
        black[pos] = old_black[pos];
        if(cl){
            black[pos] = false;
        }
        if(!black[pos] && p){
            black[pos] = true;
            p--;
        }
    }
    for(int a : vec[pos]){
        dfs_2(a, p, cl);
    }
}

int main(){
    ios_base::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for(int i = 2; i <= n; i++){
        int a;
        cin >> a;
        vec[a].push_back(i);
    }
    for(int i = 1; i <= q; i++){
        cin >> t[i] >> v[i];
    }
    int root = 1;
    for(int i = 1; i <= q; i += MAX_BLOCK_SIZE){
        for(int j = 1; j <= n; j++){
            used[j] = false;
            v2[j].clear();
            old_black[j] = black[j];
            push[j] = 0;
            clear[j] = false;
        }
        for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){
            used[v[i + j]] = true;
        }
        dfs_1(root);
        for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){
            int t = ::t[i + j];
            int v = ::v[i + j];
            if(t == 1){
                make_1(v);
            }else if(t == 2){
                make_2(v);
            }else{
                cout << (black[v] ? "black" : "white") << "\n";
            }
        }
        dfs_2(root);
    }
    return 0;
}

Tutorial is loading...

Solution(Magolor)


#include <bits/stdc++.h>
using namespace std;
#define MAXN 200000
#define MOD 998244353
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int n, m, q, B, C, T, fac[MAXN+5], efac[MAXN+5], Ans[MAXN+5], A[MAXN+5], t[MAXN+5], c[MAXN+5];
int mp[MAXN+5], rv[480], h[480][100032], _init[MAXN+5], d[105][100032]; bitset<100032> b[480];
typedef pair<int,int> pii; pii S[MAXN+5]; struct QU{int u,l,r,k,i;}Q[MAXN+5];
inline bool cmpi(const QU &a, const QU &b)
{
	return a.i<b.i;
}
inline bool cmpm(const QU &a, const QU &b)
{
	return a.u^b.u?a.u<b.u:a.u&1?a.r<b.r:a.r>b.r;
}
//fastpow
inline int fxp(int s, int n=MOD-2){int a=1;for(;n;n&1?a=1ll*a*s%MOD:0,s=1ll*s*s%MOD,n>>=1);return a;}
inline void Init(int k)
{
	if(_init[k]) return;
	_init[k] = ++C;
	int *D = d[C], s = 1ll*m*k%MOD;
	D[0] = 1;
	for(rint i = 1; i <= n; i++)
		D[i] = 1ll*D[i-1]*(s+i)%MOD;
}
inline int dxp(int a, int b)
{
	return 1ll*fac[a]*efac[a-b]%MOD;
}
inline int DXP(int k, int l)
{
	return d[_init[k]][l];	
}
void insert(int x)
{
	--h[t[x]][c[x]++];
	++h[t[x]][c[x]];
	S[++T] = pii(t[x],c[x]);
}
void erase(int x)
{
	--h[t[x]][c[x]--];
	++h[t[x]][c[x]];
	S[++T] = pii(t[x],c[x]);
}
inline int calc(int k)
{
	int _ = T; T = 0;
	for(rint i = 1; i <= _; i++)
		if(!b[S[i].first][S[i].second]&&h[S[i].first][S[i].second])
			S[++T] = S[i], b[S[i].first][S[i].second] = 1;
	int Ans = 1;
	for(rint i = 1; i <= T; i++)
	{
		b[S[i].first][S[i].second] = 0;
		Ans = 1ll*Ans*fxp(dxp(rv[S[i].first]+k,S[i].second),h[S[i].first][S[i].second])%MOD;
	}
	return Ans;
}
int main()
{
	n = MAXN;
	for(rint i = fac[0] = 1; i <= n; i++)
		fac[i] = 1ll*i*fac[i-1]%MOD;
	efac[n] = fxp(fac[n]);
	for(rint i = n; i; i--)
		efac[i-1] = 1ll*i*efac[i]%MOD;
	n = rf();
	m = rf();
	q = rf();
	B = n/sqrt(q*2/3)+1;
	for(rint i = 1; i <= n; i++)
		++t[A[i]=rf()];
	for(rint i = 1, c = 0; i <= n; i++)
		mp[t[A[i]]]?:rv[mp[t[A[i]]]=++c]=t[A[i]];
	for(rint i = 1; i <= m; i++)
		t[i] = mp[t[i]];
	for(rint i = 1, l, r, k; i <= q; i++)
	{
		l = rf();
		r = rf();
		k = rf();
		Init(k);
		Q[i] = {~-l/B,l,r,k,i};
	}
	sort(Q+1,Q+q+1,cmpm);
	for(rint i = 1; i <= n; i++)
		++h[t[A[i]]][0];
	for(rint i = 1, l = 1, r = 0; i <= q; i++)
	{
		for(; l > Q[i].l; insert(A[--l]));
		for(; r < Q[i].r; insert(A[++r]));
		for(; l < Q[i].l; erase(A[l++]));
		for(; r > Q[i].r; erase(A[r--]));
		Ans[Q[i].i] = calc(Q[i].k);
	}
	sort(Q+1,Q+q+1,cmpi);
	for(rint i = 1; i <= q; i++)
		printf("%d\n",1ll*DXP(Q[i].k,n-(Q[i].r-Q[i].l+1))*Ans[i]%MOD);
	return 0;
}

Solution(Kostroma)


#pragma comment(linker, "/STACK:512000000")
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(__attribute__((unused)) bool);
void precalc();
clock_t start;
#define FILENAME ""

int main() {
#ifdef AIM
    string s = FILENAME;
//    assert(!s.empty());
    freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);
  //freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);
#else
//    freopen(FILENAME ".in", "r", stdin);
//    freopen(FILENAME ".out", "w", stdout);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
#ifndef AIM
    cout.sync_with_stdio(0);
    cin.tie(0);
#endif
  precalc();
    cout.precision(10);
    cout << fixed;
    //cin >> t;
    int testNum = 1;
    while (t--) {
        //cout << "Case #" << testNum++ << ": ";
        solve(true);
    }
    cout.flush();
#ifdef AIM1
    while (true) {
      solve(false);
  }
#endif

#ifdef AIM
    cout.flush();
    auto end = clock();

    usleep(10000);
    print_stats(end - start);
    usleep(10000);
#endif

    return 0;
}

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}

template<typename T>
void relax_min(T& cur, T val) {
    cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
    cur = max(cur, val);
}

void precalc() {
}

#define int li
const int mod = 998244353;

struct Query {
  int l, r, id;
};

vector<int> res;
vector<int> a;
int n;

int TIMER = 0;
const int C = 200500;
int used[C];
int cur_cnt[C];
int rev[C];
map<int, vector<int>> down;
vector<int> init;

void kill(vector<Query>& all_q, int block_size, int k) {
  vector<vector<Query>> by_block(n / block_size + 1);
  for (auto& cur_q : all_q) {
    by_block[cur_q.l / block_size].push_back(cur_q);
  }
  for (int i = 0; i < by_block.size(); ++i) {
    ++TIMER;
    auto& q = by_block[i];
    sort(all(q), [&] (const Query& o1, const Query& o2) {
      return o1.r < o2.r;
    });
    int cur_l = min(n, (i + 1) * block_size);
    int cur_r = cur_l;
    int cur_prod = 1;

    auto add_item = [&] (int val) {
      if (used[val] != TIMER) {
        used[val] = TIMER;
        cur_cnt[val] = 0;
      }
      int cur_k = k + init[val];
      ++cur_cnt[val];
        cur_prod = cur_prod * (cur_k - cur_cnt[val] + 1) % mod;
    };
    auto remove_item = [&] (int val) {
      int cur_k = k + init[val];
        cur_prod = cur_prod * rev[cur_k - cur_cnt[val] + 1] % mod;
      --cur_cnt[val];
    };

    for (auto& cur_q : q) {
      while (cur_r < cur_q.r) {
        add_item(a[cur_r++]);
      }
      while (cur_l > cur_q.l) {
        add_item(a[--cur_l]);
      }
      while (cur_r > cur_q.r) {
        remove_item(a[--cur_r]);
      }
      while (cur_l < cur_q.l) {
        remove_item(a[cur_l++]);
      }
        res[cur_q.id] = cur_prod * down[k][n - cur_q.r + cur_q.l] % mod;
    }
  }
}

void solve(__attribute__((unused)) bool read) {
  for (int i = 1; i < C; ++i) {
    rev[i] = binpow(i, mod - 2, mod);
  }
  int m, Q;
  //read = false;
  if (read) {
    cin >> n >> m >> Q;
  } else {
    n = 50000;
    m = 100000;
    Q = 50000;
  }
  a.resize(n);
  init.assign(m, 0);
  for (int i = 0; i < n; ++i) {
    if (read) {
      cin >> a[i];
      --a[i];
    } else {
      a[i] = rand() % m;
    }
    ++init[a[i]];
  }
  map<int, vector<Query>> q;
  for (int i = 0; i < Q; ++i) {
    int l, r, k;
    if (read) {
      cin >> l >> r >> k;
    } else {
      do {
        l = rand() % n + 1;
        r = rand() % n + 1;
      } while (l > r);
      k = rand() % 100;
    }
    --l;
    q[k].push_back({l, r, i});
    down[k] = vector<int>();
  }
  res.assign(Q, 0);
  for (auto& item : down) {
    int init_val = (item.first * m) % mod;
    auto& vec = item.second;
    vec.assign(n + 1, 1);
    for (int i = 1; i < vec.size(); ++i) {
      vec[i] = vec[i - 1] * (init_val + i) % mod;
    }
  }
  for (auto& item : q) {
    int k = item.first;
    auto& cur_q = item.second;
    int block_size = std::max((int)(n / sqrt((int)cur_q.size())), 1LL);
    kill(cur_q, block_size, k);
  }

  for (int i = 0; i < Q; ++i) {
    cout << res[i] << "\n";
  }

}

Bonus Problem

It is the previous D1E and its standard solution is hacked. Can you solve it?

Bonus problem

//v1 and v2 are the two convex hulls. if(sz(v1) != sz(v2)) NO; n = sz(v1) for(int k = 0; k < n; k++) //v1[0] will coincide with v2[k] { bool can = true; for(int i = 0; i < n; i++) { p11 = v1[i], p12 = v1[(i+1)%n], p13 = v1[(i+2)%n] p21 = v2[(i+k)%n], p22 = v2[(i+1+k)%n], p23 = v2[(i+2+k)%n] //Congruency check if(dist(p11,p12)!=dist(p21,p22) || dist(p12,p13)!=dist(p22,p23) || dist(p11,p13)!=dist(p21,p23)) { can = false; break; } } if(can) YES; } Otherwise: NO;

Comments (112)

Show archived | Write comment?

codeRaider

6 years ago, # |

← Rev. 2 →

+13

Can someone explain the technique used to hash the convex hull in this solution? http://codeforces.me/contest/1017/submission/41357754

for (int i = 0; i < pA.n; ++i) {
		dA.len[i] = length(pA.p[i + 1] - pA.p[i]);
		dA.rot[i] = angle(pA.p[i + 2] - pA.p[i + 1], pA.p[i + 1] - pA.p[i]);
		hA += log(dA.len[i] * 233.0 + dA.rot[i]);
	}

→ Reply

gyjian

6 years ago, # ^ |

← Rev. 3 →

Just because I didn't come up with the idea of doubling the sequence of A (dA) and running KMP...

At first I thought of multiplying all of these lengths and angles. However, this is obviously incorrect; considering that the multiplication of these numbers can be very large, I used logarithm to convert multiplications into additions.

In this solution len[i] is the i-th length and rot[i] is the i-th angle (rotation), and these two numbers are correlated. I thought that it's hard that hashes log(len+rot) collide (this implements the multiplication of (len[i]*233+rot[i])), so... that's my solution.

More specifically, if the two convex hulls don't match, there must be some pairs of data (length, rotation) differ. While pair (length, rotation) changes, hash value (len*233+rot) changes.

Now I'm working on implementation without doubles :-)

Can someone prove why for a unique permutation of hash values (len[i]*233+rot[i])), only one polygon is possible?

Suppose W, X, Y, Z are hash values of a particular quadrilateral, then prove that there cannot be a quadrilateral with hash values Y, X, W, Z.

aangairbender

So here is my solution without doubles. It uses another hash function but works as well. 41434197 I just have such struct:

struct localDesc
{
    long long d1, d2;
    long long dot, sqr2;
};

And then this hash function:

long long gH(localDesc p)
{
    return p.d1 * 113 + p.d2 * 89 + p.dot * 173 + p.sqr2 * 199;
}

Where

d1,d2 — lengths of two consecutive edges of a convex hull
dot — dot product of these edges (casted to vectors)
sqr2 — doubled square of triangle built from these edges.

Works pretty good.

Magolor

-8

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).

cookiedoth

+16

Problem F can be solved by precalc answer for n, which are divided by X, where X ~ 200000.

mango_lassi

← Rev. 4 →

That is how I did it (41368570). I was very surprised when the other solution in my room wasn't this, since I thought the memory limit was way tighter than it was :P

yat0pp

for problem C, why does L=⌊√n⌋ always work? I eventually used that result but only from intuition and writing examples in the paper.. Does L=⌈√n⌉ not work?

nevermind, got it!

surfer007

Can you explain the solution , I did not get what the editorial said.

nmc

Can you explain it to me?

This theorem states that any permutation of a sequence with at least (x-1)^2+1 distinct elements have an increasing/decreasing subsequence of length x. Take any input n and find maximum x such that (x-1)^2+1 <= n, you'll find that ⌊√n⌋ always works. So, just assume LIS (could be LDS) to be ⌊√n⌋ and build the permutation in such a way that minimizes LDS, this lead to the small increasing chunks construction and thus to LDS=n/⌊√n⌋.

I am not able to get the part where you say "⌊√n⌋ will always work". Please be more verbose about it.

These are the questions I have in mind for your second statement : 1. Take any input n , this is perhaps the length of the permutation, If I am correct ? 2. How will I find the maximum x such that (x-1)^2+1 <= n ? 3. How does the conclusion '⌊√n⌋ always works' is related to the previous findings related to x. Should x be ⌊√n⌋ ?

I am not able to figure out the concept as whole, little hints might help.

yes
just try every x=1...+inf . You will see that the maximum x you can use is sqrt(n). Take n=9, for example, (3-1)^2+1 <= 9 is valid (x=3), but (4-1)^2+1 <= 9 is not (as with any other x>3).
yes, x=⌊√n⌋

If any permutation we make has an increasing or decreasing subsequence of size x (from the theorem) and you have found x=⌊√n⌋, then you know that any permutation you build will have either LIS=⌊√n⌋ or LDS=⌊√n⌋. So just assume one, LIS for example, and make the permutation in such a way that LDS is also minimal.

Sorry if I can't make it more clear.

If LIS is ⌊√n⌋ and we make little chunks of it , as shown in the editorial for example 22 , then LDS would be n/ ⌊√n⌋ . If I am correct ? The question was a very intuitive one , if someone who did not know the theorem already

ivan100sic

+24

Another approach for problem F: 41353364

Find all the primes up to $\text{[math]}$ and then, using those primes, run the sieve in blocks of size M (here M = 8·2²⁰). Even without using bitsets, you can achieve under 1MB of memory usage without sacrificing much of the speed.

aryanc403

Another approach for problem D : 41362569
I converted 01 string in binary.
There are atmax 2ⁿ (4096) distinct 01 strings stored count of all of them in an array.
Whenever a query is made I first checked this String is already processed.
If no then calculated answers for all values of K in O(n * 2ⁿ)
Worst case Time Complexity O(n * 4ⁿ) ~ (Edit) (2e8).

GreenGrape

+14

That's 2e8 actually :D

Thanks. Updated.

goagain

I don't like the question F to limit my memory use. in fact, I get the answer quickly, but I spent all of my time until the contest end. If we match for algorithm, why limit others?

mouse_wireless

There is also a O(2^(2N)) solution for D which worked for the given constraints (perhaps even better than the provided solution?), by simply pre-calculating all (s,t) wu results.

Checkout my comment above. Sol : 41362569 Extra n in complexity is included to account for time taken to match two strings. I didn't pre processed but evaluted when only needed.

Cain

You code may be faster if you replace map with binary search and sort.

I haven't used map. I'm using array with index as no. as val. So there is no need to sort it also.

kanishk779

4 years ago, # ^ |

aryanc403 I have also done the same thing but I get TLE, can you tell how to improve it. I precalculate the result for all (s,t) pairs 84729180 .

retired.old.cake

its never supposed to be. At least i can't pass........

My first submission should be a WA (by simply mistake) but not a TLE

never_giveup

Solution for G?

teja349

+19

I was thinking of a HLD solution
initialize all nodes with -1.
query 1, add 1 to that node
query 2. make value of all nodes in the subtree -1.Also if query 3 on this node gives non negative value, add -1*(ans to query 3)-1 to the node
query 3. find max non empty suffix sum from that element to root. if negative , white otherwise black.

Can someone validate??

Deemo

It's correct

peach

query 3. find max non empty suffix sum from that element to root. if negative , white otherwise black.

Does this mean that you take all positive values on the chains up to root?

I would like to understand the HLD solution.

bocity

Could someone tell me why we should maintain segment-tree like this: mx[v] = max(mx[v<<1^1], sm[v<<1^1] + mx[v<<1]);? This bothered me for a day.

I think I see. This can help to maintain max suffix sum.

Jungarr1k

How do you make values of all nodes in subtree of a vertex in HLD?

HLD is also a Euler tour.

Don't understand you. As I assume, HLD is a set of paths with a data structure built on each. What does it have to do with Euler tour? Elaborate pls.

Check Here

Wow. Thanks!

Zeus726

Tnx for the great contest Magolor

how to solve G ?!

is it a HLD problem ?

Bekh

Could somebody point out to me why this 41374761 gives TLE? Isn't its complexity: (2^n * (2^n + 100) + q * n)?

Your soln — 41375264 . I have replaced n with 15 . It gives AC because Time take to compare i with constant (15) is less that variabe(n)

Thank you. But shouldn't such complexity pass easily in 2 seconds? what's the difference between my solution and 41356297 The 2 codes are almost identical. Edit: Also seems like it only passed by luck. I resubmitted the exact code you got AC with (with replacement of variable (n) with 15) and I got TLE 41377553

As I have mentioned in my comments above. Time complexity is O(n * 4ⁿ). For n=12. This is around 2e8. Hence It just passes TL. There are some highly optimised solns with this time complexity which takes around 500 ms.

brdy

No, it shouldn't. It is actually living on the edge.

But if you used bitmasks/BITSET I think you can cut down runtime dramatically.

I did use bitmasks. What confuses me the most is that after the contest I got inspired by this 41356297 submission and my 41374761 submission are almost identical except for maybe using vectors instead of arrays. but the AC solution passes in 1300 ms and mine can't run below 2s :/ I really can't spot the difference between the 2 codes.

Try to only run the dp when necessary (whenever you encounter a new mask) and keep track of whichs masks you've seen. It should now cut it to something like a bit over 1 second.

I've seen that in other solutions but it's really bothering me how the AC solution 41356297 — which I almost copied — still runs in below 1.3s without having to do that. What's the key for the quick runtime there?

Speedups/observation:

Arrays vs Vectors (arrays faster)

Array Indexing:

Basically if you look at his code all of the index sizes are increasing order. This actually can run way faster (something with memory access)

It seems making V a global variable (outside of main) is a big speedup, not sure why though.

UPD1: http://codeforces.me/contest/1017/submission/41379154

Got it to pass by using more arrays instead of vectors, increasing index, and making 'v' a global variable.

This is still far from 1200 ms though.

UPD2: Found the culprit. You use endl instead of '\n' which is slower becaus it does extra stuff.

Your code is actually way faster lol: http://codeforces.me/contest/1017/submission/41379280

Thank you very much for your effort. Much appreciated and noted these things down! never using endl; again! :D

thenymphsofdelphi

You can use #define endl '\n' for that.

neal

It's because you use cout << ... << endl;.

endl is a newline and a flush; it's the same as cout << ... << '\n' << flush;. In other words, your code is attempting to write to disk 500,000 times, which is not going to finish in 2 seconds.

Waw, thanks so much!

shrubb

In C, why is $\text{[math]}$ minimal for a given LIS = L?

Because you can order the array in L chunks. Depending on if the elements within the chunk are increasing or decreasing, the i'th element of some chunk will be strictly less then or greater than the i'th element of the next chunk.

So if LIS or LDS is L (amount of chunks), the other N/L (size of chunk)

Example: 1 2 3 4 5 6, L = 2

{4 5 6 } {1 2 3}

4 > 1, 5 > 2, 6 > 3, so it can be clear LDS = 2

4 < 5 < 6, and 1 < 2 < 3 so the LIS = 3

+21

Thanks, the algorithm is clear (I solved the problem exactly this way), but I actually asked a different question. I was wondering how to prove that one cannot construct a permutation with $\text{[math]}$ .

-10

Oh, I am sorry for restating the obvious.

Here it is:

([x] is a sequence of x increasing numbers)

LDS is the amount of chunks [LIS][LIS][LIS]...[< LIS]

As you can see, the amount of chunks is the LDS, and here the amount of chunks is (amount of [LIS] chunks) + 1

Amount of [LIS] chunks is "how many LIS fit into N" which is floor(N/LIS), and we also add 1 to include the smaller leftover chunk.

Among the integers, floor(x)+1 = ceil(x)

So it's ceil(N/LIS).

Now imagine it is a perfect square. Then rounding doesn't matter.

Hope this helps.

oToToT

I think that what he need is a proof of the optimality, but you just provide an algorithm and calculate the [LIS]+[LDS] without proving that this algorithm is optimal.

neutron-byte

Assume a permutation with $\text{[math]}$ exists. Assign pairs $\text{[math]}$ to all elements such that a_i denotes the length of a LIS and b_i denotes the length of a LDS ending at position i. It follows that all pairs must be different (why?) and we have

$\text{[math]}$

as well as

$\text{[math]}$ .

Thus, there are less than $\text{[math]}$ pairs and two of them must be equal by pigeonhole principle. Contradiction.

Note: This is the same proof idea used in Erdős–Szekeres theorem.

This is brilliant. Can't thank you enough!

Harolinch

and (how, why) $\text{[math]}$ always work ?

This problem basically simplifies to a much easier problem because A*B = N (you must use all elements 1 to N).

So imagine you have a number N and you want to minimize A + B where A*B = N.

Actually in this case A = B = sqrt(N).

For example:

A,B values for 16

(1,16) (2,8) (4, 4)

The best A,B is in the "middle" of the factors, which is sqrtN.

how you convert the problem from A + B to A × B ?

We want to minimize (A+B) so that A*B = n.

So for 16, the minimum A+B = 8, because we have A = 4, B = 4, and 4*4 = 16.

yes, why ?!!

https://codeforces.me/blog/entry/61061?#comment-450032

Look at the problem discussion. I'm sorry but I can't say much more than "drawing it out".

You will notice that if you split it into K blocks (with increasing values between blocks) you will notice a LIS is contained within block while LDS is contained across the blocks. (or other way around, either is fine)

7 8 9 ||| 4 5 6 ||| 1 2 3

thanks so much, now i understand somehow

Why A*B=N ?

I can’t get it.(sad)

wallcrawler

Actually, since we have to minimize L + ceil(n/L) (L = length of the LIS)
So, we have to minimize f(x) = x + ceil(n/x) or simply minimize x + n/x
Find out it's minima point by differentiation of f(x)
On solving we get x = sqrt(n).

We want to make a permutation of size N, so we can use divide our answer into A increasing blocks of size B. A*B must equal N to use every single numbers from 1 to N.

Antoine

In problem C, how does Dilworth's theorem relate to LIS and LDS in a permutation?

CazadorDivino

I have the same question!

Trying to understand the relationship between LIS and LDS with Dilwort's theorem I found this paper (http://math.mit.edu/~cb_lee/18.318/lecture8.pdf).

Theorem (Dilworth 1950): Let P be a poset. Then there exists an an-tichain A and a chain decomposition C satisfying |C|=|A|.

Someone can explain the relationship between the theorem, LIS and LDS?

What is an an-tichain A and what is chain decomposition , sounds greek to , can some one please care to explain , if they are related to problem c.

caa_tomsk

I think I got it.

Let's assume that we are given some permutation of numbers 1 ... N.

Then let's define a relation

i«j

as "i is smaller than j and it occurs earlier in the given ordering".

Then we apply the Dilworth theorem in terms of this relation. A longest antichain corresponds to the longest decreasing subsequence. If LDS has length L then by the theorem statement we know that the partially ordered set cannot be partitioned into fewer than L chains. Chanis correspond to increasing subsequences and thus LIS cannot be shorter than ceil(N/L).

We are supposed to come up with the construction algorithm and the Dilworth theorem helps prove that it matches the lower bound for LDS+LIS.

IMO this problem was more difficult than its score! :\

strelizia_smurf

+25

Problem C

Looking at Erdos lap number the other day and came through this theorem.

https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem Edros Theorem says any permutation of n^2 + 1 distinct numbers has a increasing/decreasing sub sequence of n+1.

Ne0n

+12

And one more solution for D: 41376803 It has O(2²ⁿ + q * n) complexity and the most interesting part — it doesn't use that k is relatively small.

First, as in mouse_wireless's solution, we want to count Wu value for all possible masks and create a vector pre_w containing pairs (Wuvalue, mask). Then we sort this vector in increasing order and now we are ready to another precalc)

For each possible string t we build a vector based on pre_v: we just change mask to ( $\text{[math]}$ ), which will represent s string needed to get this mask. Now we have to iterate over new vector once again to do following: we will change second value in every pair (ex-mask and ex-( $\text{[math]}$ )) to number of string in S, for which Wuvalue doesn't exceed current Wuvalue (in current pair). We can do this by simple dp.

Now, for answering a query, all we need is binary search a vector related to given t. It is the part which has a O(q * n) complexity.

Unfortunately, during the contest I got TL4 with this solution beacause of slow IO. Thanks to SHAMPINION, who advised me to add two stirngs of code, which make IO faster and after that the solution passed in 1.7 s.

OMGTallMonster

I had a similar solution to D, with two differences:

1) Rather than sort the list of (Wuvalue, mask) tuples, it's actually possible to use a Dijkstra-like approach to save a sorting step. This is only a minor speedup though, since computing this list only needs to be done once.

2) Rather than use binary search, I sorted the queries by k and then iterated in order of increasing Wuvalue's and k's. This saves quite a bit of memory, since you don't have to memoize the results.

AC in 607ms! 41379365

mohamedeltair

In problem E, I have understood that after getting the hulls of the 2 engines, we will represent each hull using a string of edge lengths and angles. After this, Double one of the two strings, and then check that the string which is not doubled exists in the doubled string.

Edge lengths would not change between 2 isomorphic hulls, but angles could change. So, how to normalize angles of the two hulls such that their KMP matching becomes rotation invariant?

EDIT: Never mind, I got it.

ivanzuki

+43

For problem E, Magolor's solution differs from Kostroma's solution in this input:

Output should be "No", since reflection is not allowed.

+36

For 1017E - The Supersonic Rocket, many of the accepted submissions (around one-third?) actually fail on this test case:

I wrote up a detailed explanation of what's going on in this post: https://codeforces.me/blog/entry/61086

Can we add this case to the practice version of the problem?

EDIT: Looks like ivanzuki above has the same idea and I was a bit slow. That's what I get for writing a long post :)

Fuko_Ibuki

For problem D,I use O(q × 2ⁿ) "solution" and passed it.
my code:http://codeforces.me/contest/1017/submission/41379865

quachtridat

Can you explain your solution please? And also I cannot view the code and I don't know why.

Now you can read it.

Nisiyama_Suzune

+29

I think that Problem F can also be dealt with easily should one know about the technique of Extended Eratosthenes Sieve.

That is, we can even solve the problem for n ≤ 10¹¹ without the memory limit. :)

My code: 41366266

By the way, Problem E can also be done by finding the minimal string rotation of two convex hulls and compare them with brute force.

Log_out

Please briefly explained problem B.

Do you understand the problem statement? Let everyone know and we may have further explanation.

Yes but I couldn't understand the solution in tutorial.

Let me explain an intuitive and naive solution this way.

There are some notes:

The bitwise OR operator (assume it is A | B = C) will make the result become 1 if A or B is 1 or both A and B are 1.

There must be a pair of two elements with two different values at two different places to form a change (i.e. swap) that changes the "appearance" of the binary number. In another word, a change (or swap) consists of two different elements.

Look at these two binary numbers:

A = 0011
B = 0101

Notice that, in each column of the representation of the two numbers above, if you make a pair of one element from number A and one from B, you will have these "vertical" pairs: 00, 01, 10, 11 (assigning names p00, p01, p10, p11)

The first digit in each pair comes from A, and the second digit in each pair comes from B.

Because the problem is about swapping two different elements in A so that it makes change when OR is done, in each pair above, the first digit will be the one which is swapped with another first digit in another pair, and the second digit will stay still.

Also by the notes, when we make a change (i.e. a swap of two different elements in A), the one digit we take has to be different from the other digit we take to perform the swap, otherwise the swap become nonsensical because no any elements are changed. In another word, for a pair of positions, there must be a pair of different elements in A, or both A and B. So we can say that the swap for these p make sense:

p00 with p10

p00 with p11

p01 with p10

p01 with p11

p10 with p00

p10 with p01

p11 with p00

p11 with p01

Notice that we have to put each p vertically in actual representation.

Look more closely at such pairings above, by notes again, we notice something redundant in some pairs:

p00 with p10 (OK: OR = 01 before & 10 after swap)

p00 with p11 (OK: OR = 01 before & 11 after swap)

p01 with p10 (OK: OR = 11 before & 10 after swap)

p01 with p11 (NO: OR = 11 both before & after swap -> no change)

p10 with p00 (OK: Same as the first one)

p10 with p01 (OK: Same as the third one)

p11 with p00 (OK: Same as the second one)

p11 with p01 (NO: Same as the fourth one)

Now that we get these pairs left and they are OK:

Therefore the result as shown by the tutorial writer.

I hope this would help you.

Sorry for my English because this may not such a long explanation like this.

Thanks for your very good explanation ....

consecutivelimit

+40

I came up with the solution of A~G but I made mistakes in my segment tree and failed to pass G...

My solution of problem D~G:

Let f(i, s, k) be how many $\text{[math]}$ can be gotten by changing s[i, n) with a cost not greater than k.

When k < 0, f(i, s, k) = 0, otherwise:

f(n, s, k) is the count of s in S;

When i < n, $\text{[math]}$ .

The answer of a question is f(0, t, k).

Complexity: O(2ⁿnk).

The problem is equivalent to checking if two point sets' convex hull is the same by shifting and rotating one of them.

If two convex hulls' size are different, the answer is NO. Otherwise, let k be their size, and number the points of each convex hull 0, 1, ..., k - 1 clockwise. Let P_i be point i in the first convex hull and Q_i be point j in the second convex hull.

Enumerate which point Q_i is corresponding to point P₀, and check if for each j = 0, 1, ..., k - 1:

$\text{[math]}$ $\text{[math]}$

The answer is YES if and only if there is an i satisfying this condition.

To avoid floating point operations, we use

instead of $\lvert P_{i}P_j\rvert$ and $\text{[math]}$ , among them P_i(x_i, y_i). The absolute value of these numbers are not greater than 2 × 10¹⁶, we can use 64-bit integer to store them.

I use string hash to solve it. Initialize the prefix and suffix hash value of sequence

$\text{[math]}$ $\text{[math]}$ $\text{[math]}$ $\text{[math]}$

Then checking one i costs O(1) time.

After calculating the convex hulls, the complexity is O(n). The total complexity is $\text{[math]}$ .

Let P = {p₁, p₂, ...} be the prime set(p_i < p_i + 1). The answer is

When $p\le\sqrt{n}$, we can calculate $\text{[math]}$ by brute force.

When $\text{[math]}$ , $\text{[math]}$ , so now we need to calculate $\text{[math]}$ .

Consider Eratosthenes sieve, let f(n, m, k) be the sum of k-th power of the rest numbers after deleting all p_ix (i ≤ m, $\text{[math]}$ , x > 1) from 2, 3, ..., n, while 0 ≤ k ≤ 3.

Obviously, $\text{[math]}$ , it can be calculated in O(1) time.

If p_m² > n, f(n, m, k) = f(n, m - 1, k).

Else, $\text{[math]}$ , $\text{[math]}$ .

Then we can get the sum of k-th power of the primes in $\text{[math]}$ , it's $\text{[math]}$ (p_m² > n). Summing $\text{[math]}$ up and we can get the answer.

Because the first parameter is always $\text{[math]}$ , $\text{[math]}$ , and p_m² ≤ n, the time complexity of calculating f is $\text{[math]}$ . Scrolling the array can optimize the memory.

Time complexity: $\text{[math]}$ .

Memory complexity: $\text{[math]}$ .

Let f(v) be how many operations 1 are operated on vertex v, then f(v) = max{f(p_v) - 1, 0} + c(v), c(v) is the count of direct operation on v, i.e. "1 v".

If f(v) > 0, v is black, otherwise v is white.

We can use heavy-light decomposition and segment tree to maintain f. Consider a chain 0 - 1 - 2 - ... - n, if the status of 1, 2, ..., n is known, f(n) can be described as a function of f(0): f(n) = max{f(0) + a, b}. When using segment tree to maintain the heavy-light decomposition, each node storages the a, b of its interval. Then for an operation "3 v", we can query the value of f(v) in $\text{[math]}$ time.

For single vertex v (leaves of the segment tree), at first its a = - 1, b = 0. After an opeartion "1 v", increases its a, b by 1.

After an operation "2 v", decreases v's a, b by f(v) (current value), and restore the subtree v (not contain v) to a = - 1, b = 0. Because the value of f(v) is increasing before restoring, this algorithm is correct.

Complexity: $\text{[math]}$ .

UPD: H can be solved simply by Mo's algorithm, but I didn't open this problem at all...

nimom

What is Dilworth's Theorem? How do I learn it? Do I need to know anything else before learning it?

https://www.youtube.com/watch?v=S8mXDhGs_pg It's from Codechef's Indian Programming Camp 2016. This might help you learn it if you want to start from scratch.

Ezio07

This helped to understand the actual explanation of the approach used. Thanks.

Afifii

← Rev. 5 →

+11

Another simple way to check convex hull isomorphism in problem E is to simply check the relations between consecutive triplets of points (as if you are checking triangles congruency). In this way, angles will be implicitly considered.

This code is not O(N^2), because matches between triplets cannot be dense, and the inner loop will not take so long before it breaks. However, I couldn't formally prove it.

Edit: From the reply of Kostroma
This code is O(N*M), where M is the maximal number of equal edges in a convex polygon, which can't be that big due to the constrains on the coordinates.

Here is my accepted submission: 41392476

actually the convex hull with integer points will only have $\text{[math]}$ in size, so the complexity of checking the same would be O(C)

di_z

I am really interested in this conclusion. Could you provide proof or more detail about it?

I learned it from a competitive programming camp.

I couldn't memorize the proof well, but it's just something like every adjacent edges won't be colinear, so there won't be too much points on the convex hull.

p.s. why downvoting me...

dalex

-31

This code IS n^2. It's just weak tests.

Kostroma

Wanna give a test or just unproven cock-a-rats? I believe it works in O(n·M), where M is maximal number of equal edges in a convex polygon, which can't be that big with these constraints on coordinates surely.

bazsi700

Maybe I'm misunderstanding his solution, but IMO if the two polygons are the same, except one vertex, then it will have O(N^2) running time.

I think that almost all iterations of the outer loop will be short, because there can't be many long equal parts in two convex polygons with vertices in integer points.

In my understanding, his solution checks if the triangles created by 3 adjacent vertices are coincident.

If that's what it does, then by having the same polygon twice, just moving 1 vertex by a little, the inner loops running times will be 1,2,3,...,n which summed is O(N^2).

If the two polygons are the same (except for maybe one side), the inner loop will NOT be O(n) for all the iterations of the outer loop.

Because if the two polygons look similar when v1[0] corresponds to (coincides with) v2[0], it doesn't mean that they will look similar when v1[0] correspond to v2[1].

The only exception is when the two polygons are somehow close to regular polygons, as many matches will occur no matter how you rotate the polygon's vector. In this case the code will really be O(N^2). However, you cannot have a regular polygon with many sides given the constrains of the problem.

C051N3

Can anyone explain the solution of problem D in the editorial? I solve D with another solution, but didn't understand the provided solution. Why f[S1][S2][j], and what is it going to do with g[S][k]?

DucPro

The complexity in F is just too BS. Setting the limit of N to just 1e8 would make a lot of us see that this complexity works, but 3e8 just makes alot of people says: It's not gonna pass.

Vatinkriv

I think problem G can be solved by using Segment Tree Beats. This is my solution: https://codeforces.me/problemset/submission/1017/41447852

vivukhue

Can you tell me what pii lz[N<<1] do ?

you can search info about it before asking me

each node in my segment tree doesn't maintain the value of 1 range. A node has value if only if its range is a position

newStartNotSure

Could somebody point out to me why this gives TLE? https://codeforces.me/contest/1017/submission/41443492

xproxmess

Failing G on test 6, but can't seem to find my bug. Could someone help? Thanks in advance!

http://codeforces.me/contest/1017/submission/41515637

UPD: Accepted.

AbdelRahmanEmara

In div2C: I want to answer why sqrt(n) will always work: I won't talk about the statement that: if lis = L then optimal lds = n/L (1) Because it has been proved severel ways. But lets for now believe the above statement(1) and use it. We know that secret_number = lis + lds = lis + n/lis. Then we have secret_number as a pure function in lis. Now we want rewrite as f(lis) = lis + n/lis Know we want to minimize the above function. In other words we need the optimal lis that minimizes f(lis). And here some calculus will answer us : differentating a function is equavelent to getting its slope of tangent to the function curve wrt to its independent variable(lis), we may notice that when a tangent to a curve is parallel to x-axis at some point x then: at this x the function is at a peek (minimum or maximum). So we set the function derivative to zero (slope is 0 when tangent is parallel to x-axis) and solve for Lis, the obtained lis is the one that minimzes the function. F'(lis) = 1 + n / (lis^2) Setting f'(lis) = 0 ===> lis = sqrt(n).

ale

In problem E, the first official solution fails on this case:

which is actually test case #55 in the judge system (so weird).

The solution outputs YES, when the answer is NO.

This is due to all cross products of consecutive sides being the same (1 or -1), and the sequences of sides' square length are 2,1,2,1 and 1,2,1,2 respectively. So when we duplicate the second-one (without losing generality), we get 1,2,1,2,1,2,1,2 and it can be seen that it contains the first-one as a substring (starting on position 2).

I think this is because of the use of the cross product. I think dot product should be used instead, because it will characterize the angle between two consecutive sides of the hull better than the cross product, which is in fact characterizing the area of the triangle.

Magolor's blog

Bonus Problem