Codeforces Round #462 Editorial

№	Пользователь	Рейтинг
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

№	Пользователь	Вклад
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

Hi, all!

This is not Tommyr7, but the impostor behind the round again (guess who I am? :P). The statements are written by me. Thank you, everyone, and hope you've all enjoyed the round!

Any feedback on problems and tutorials are welcome — we look forward to doing even better in the future!

Here are some of the detailed tutorials!

Tutorials

934A - A Compatible Pair

Author quailty / Preparation quailty / Tutorial quailty

Tutorial

Solution (quailty)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=(1LL<<60)-1;
ll a[55],b[55];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld",&b[i]);
    ll res=INF;
    for(int i=1;i<=n;i++)
    {
        ll now=-INF;
        for(int j=1;j<=n;j++)if(j!=i)
            for(int k=1;k<=m;k++)
                now=max(now,a[j]*b[k]);
        res=min(res,now);
    }
    printf("%lld\n",res);
    return 0;
}

934B - A Prosperous Lot

Author Tommyr7 / Preparation cyand1317 / Tutorial cyand1317

Tutorial

Solution (Tommyr7)

#include <bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
	scanf("%d",&k);
	if (k>36) printf("%d\n",-1);
	else
	{
		while (k>0)
		{
			if (k>=2)
			{
				printf("%d",8);
				k-=2;
			} else
			{
				printf("%d",9);
				k-=1;
			}
		}
		printf("\n");
	}
	return 0;
}

933A - A Twisty Movement

Author visitWorld / Preparation visitWorld / Tutorial visitWorld

Tutorial

Solution (visitWorld)

#include <bits/stdc++.h>

#define rep(i, x, y) for (int i = (x), _ = (y); i < _; ++i)
#define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define bin(x) (1 << (x))
#define SZ(x) int((x).size())

using namespace std;
typedef pair<int, int> pii;
typedef vector<int> Vi;
typedef long long ll;

template<typename T> inline bool upmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }
template<typename T> inline bool upmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }

const int MAX_N = 2005;

int pre[MAX_N][2], suf[MAX_N][2];
int g[MAX_N][MAX_N][2][2];
int w[MAX_N], N;

int main() {
	scanf("%d", &N);
	rep (i, 0, N) { scanf("%d", &w[i]); w[i]--; }
	rep (i, 0, N) {
		if (i) memcpy(pre[i], pre[i - 1], sizeof pre[i]);
		down (j, 2, w[i]) upmax(pre[i][j], pre[i][w[i]] + 1);
	}
	down (i, N, 0) {
		if (i < N - 1) memcpy(suf[i], suf[i + 1], sizeof suf[i]);
		rep (j, 0, w[i] + 1) upmax(suf[i][j], suf[i][w[i]] + 1);
	}
	int ans = pre[N - 1][1];
	rep (i, 0, N) {
		rep (a, 0, w[i] + 1) rep (b, w[i], 2) {
			g[i][i][a][b] = 1;
		}
	}
	rep (l, 1, N) rep (i, 0, N - l) {
		int j = i + l;
		rep (l, 0, 2) rep (a, 0, 2 - l) {
			int b = a + l;
			g[i][j][a][b] = max((a < 1 ? g[i][j][a + 1][b] : 0), (b ? g[i][j][a][b - 1] : 0));
			upmax(g[i][j][a][b], g[i + 1][j][a][b] + (b == w[i]));
			upmax(g[i][j][a][b], g[i][j - 1][a][b] + (a == w[j]));
			upmax(ans, (i ? pre[i - 1][a] : 0) + g[i][j][a][b] + (j < N - 1 ? suf[j + 1][b] : 0));
		}
	}
	printf("%d\n", ans);
	return 0;
}

933B - A Determined Cleanup

Author Tommyr7 / Preparation cyand1317 / Tutorial cyand1317

Tutorial

Solution (Tommyr7)

#include <bits/stdc++.h>
using namespace std;
long long p;
int k;
int cnt=0;
int ans[107];
int get()
{
	int x=p%k;
	if (x<0) x+=k;
	return x%k;
}
int main()
{
	scanf("%lld%d",&p,&k);
	while (p!=0)
	{
		++cnt;
		ans[cnt]=get();
		p-=get();
		p/=(-k);
	}
	printf("%d\n",cnt);
	for (int i=1;i<=cnt;i++)
		printf("%d ",ans[i]);
	printf("\n");
	return 0;
}

933C - A Colourful Prospect

Author quailty / Preparation quailty / Tutorial quailty

Tutorial

Solution (quailty)

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

typedef long double db;
const db eps=1e-12;

struct Point
{
    db x,y;
    Point(){}
    Point(db _x,db _y):x(_x),y(_y){}
    Point operator + (const Point &t)const
    {
        return Point(x+t.x,y+t.y);
    }
    Point operator - (const Point &t)const
    {
        return Point(x-t.x,y-t.y);
    }
    Point operator * (const db &t)const
    {
        return Point(x*t,y*t);
    }
    Point operator / (const db &t)const
    {
        return Point(x/t,y/t);
    }
    bool operator < (const Point &t)const
    {
        return fabs(x-t.x)<eps ? y<t.y : x<t.x;
    }
    bool operator == (const Point &t)const
    {
        return fabs(x-t.x)<eps && fabs(y-t.y)<eps;
    }
    db len()const
    {
        return sqrt(x*x+y*y);
    }
    Point rot90()const
    {
        return Point(-y,x);
    }
};

struct Circle
{
    Point o;
    db r;
    Circle(){}
    Circle(Point _o,db _r):o(_o),r(_r){}
    friend vector<Point> operator & (const Circle &c1,const Circle &c2)
    {
        db d=(c1.o-c2.o).len();
        if(d>c1.r+c2.r+eps || d<fabs(c1.r-c2.r)-eps)
            return vector<Point>();
        db dt=(c1.r*c1.r-c2.r*c2.r)/d,d1=(d+dt)/2;
        Point dir=(c2.o-c1.o)/d,pcrs=c1.o+dir*d1;
        dt=sqrt(max(0.0L,c1.r*c1.r-d1*d1)),dir=dir.rot90();
        return vector<Point>{pcrs+dir*dt,pcrs-dir*dt};
    }
}p[5];

struct DSU
{
    int fa[5];
    void init(int n)
    {
        for(int i=1;i<=n;i++)
            fa[i]=i;
    }
    int find(int x)
    {
        return fa[x]==x ? x : fa[x]=find(fa[x]);
    }
    void merge(int x,int y)
    {
        x=find(x),y=find(y);
        if(x!=y)fa[x]=y;
    }
}dsu;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        cin>>p[i].o.x>>p[i].o.y>>p[i].r;
    vector<Point> all;
    dsu.init(n);
    int e=0;
    for(int i=1;i<=n;i++)
    {
        vector<Point> pat;
        for(int j=1;j<=n;j++)if(i!=j)
        {
            vector<Point> tmp=p[i]&p[j];
            if(!tmp.empty())dsu.merge(i,j);
            for(int k=0;k<(int)tmp.size();k++)
                all.push_back(tmp[k]),pat.push_back(tmp[k]);
        }
        sort(pat.begin(),pat.end());
        e+=unique(pat.begin(),pat.end())-pat.begin();
    }
    sort(all.begin(),all.end());
    int v=unique(all.begin(),all.end())-all.begin(),c=0;
    for(int i=1;i<=n;i++)
        c+=(dsu.find(i)==i);
    cout<<e-v+c+1<<endl;
    return 0;
}

Solution (cyand1317)

#include <cmath>
#include <cstdio>
#include <algorithm>

static const int MAXN = 3;
static const double EPS = 1e-9;

static int n;
static int x[MAXN], y[MAXN], r[MAXN];

// -2: internally separate
// -1: internally tangent
//  0: intersecting
// +1: externally tangent
// +2: externally separate
static int g[MAXN][MAXN];
// Number of points passed by all three circles
static int conc;

inline int rel(int a, int b)
{
    int dssq = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]),
        dfsq = (r[a] - r[b]) * (r[a] - r[b]),
        smsq = (r[a] + r[b]) * (r[a] + r[b]);

    if (dssq < dfsq) return -2;
    else if (dssq == dfsq) return -1;
    else if (dssq < smsq) return 0;
    else if (dssq == smsq) return +1;
    else return +2;
}

inline void get_intersections(int a, int b, double ix[2], double iy[2])
{
    double angle = atan2(y[b] - y[a], x[b] - x[a]);
    double ds = sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
    double delta = acos((ds * ds + r[a] * r[a] - r[b] * r[b]) / (2.0 * r[a] * ds));
    ix[0] = x[a] + r[a] * cos(angle + delta);
    iy[0] = y[a] + r[a] * sin(angle + delta);
    ix[1] = x[a] + r[a] * cos(angle - delta);
    iy[1] = y[a] + r[a] * sin(angle - delta);
}

inline bool on_circle(int a, double x0, double y0)
{
    return fabs((x[a] - x0) * (x[a] - x0) + (y[a] - y0) * (y[a] - y0) - r[a] * r[a]) <= EPS;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);

    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
            g[i][j] = g[j][i] = rel(i, j);

    conc = 0;
    if (n == 3) {
        for (int i = 0; i < 2; ++i) {
            for (int j = i + 1; j < 3; ++j) if (g[i][j] >= -1 && g[i][j] <= +1) {
                int k = 3 - i - j;
                double ix[2], iy[2];
                get_intersections(i, j, ix, iy);
                if (on_circle(k, ix[0], iy[0])) ++conc;
                if (on_circle(k, ix[1], iy[1]) && g[i][j] == 0) ++conc;
                break;
            }
            if (conc != 0) break;
        }
    }

    if (n == 1) {
        puts("2");
    } else if (n == 2) {
        puts(g[0][1] == 0 ? "4" : "3");
    } else if (n == 3) {
        int x[3] = { g[0][1], g[0][2], g[1][2] };
        std::sort(x, x + 3);
        if (x[0] == -2) {
            printf("%d\n", 4 + (x[1] == 0) + (x[2] == 0));
        } else if (x[0] == -1) {
            if (x[1] == -1) {
                printf("%d\n", x[2] == -1 ? 4 : (6 - x[2]));
            } else {
                switch (x[1] * 10 + x[2]) {
                    case 00: printf("%d\n", 7 - conc); break;
                    case 01: puts("6"); break;
                    case 02: puts("5"); break;
                    case 11: case 12: case 22: puts("4"); break;
                    default: puts("> <");
                }
            }
        } else if (x[0] >= +1) {
            puts(x[0] == +1 && x[2] == +1 ? "5" : "4");
        } else {    // x[0] == 0
            switch (x[1] * 10 + x[2]) {
                case 00: printf("%d\n", 8 - conc); break;
                case 01: printf("%d\n", 7 - conc); break;
                case 02: puts("6"); break;
                case 11: puts("6"); break;
                case 12: puts("5"); break;
                case 22: puts("5"); break;
                default: puts("> <");
            }
        }
    } else puts("> <");

    return 0;
}

933D - A Creative Cutout

Author skywalkert / Preparation skywalkert / Tutorial skywalkert

Tutorial

Solution (skywalkert)

#include <bits/stdc++.h>
typedef long long LL;
const int mod = (int)1e9 + 7, inv2 = (mod + 1) / 2, inv3 = (mod + 1) / 3, inv5 = (mod * 2 + 1) / 5, inv7 = (mod + 1) / 7;
const int inv6 = (LL)inv2 * inv3 % mod, inv30 = (LL)inv5 * inv6 % mod, inv42 = (LL)inv6 * inv7 % mod;
const int coeff[4][8] = {
{0, 1}, // sum(b^0) = n
{0, inv6, inv2, inv3}, // sum(b^2) = 1/6 n + 1/2 n^2 + 1/3 n^3
{0, mod - inv30, 0, inv3, inv2, inv5}, // sum(b^4) = -1/30 n + 1/3 n^3 + 1/2 n^4 + 1/5 n^5
{0, inv42, 0, mod - inv6, 0, inv2, inv2, inv7} // sum(b^6) = 1/42 n - 1/6 n^3 + 1/2 n^5 + 1/2 n^6 + 1/7 n^7
};
LL n;
int f[4], g[4], ans;
int main() {
	scanf("%lld", &n);
	int nn = n % mod;
	f[0] = nn * (nn + 1LL) % mod * (nn + 2) % mod;
	f[1] = (3LL * nn + 4) % mod;
	f[2] = mod - 3LL * (nn + 2) % mod;
	f[3] = 2;
	for(int x = 0; (LL)x * x <= n; ++x) {
		LL rem = n - (LL)x * x;
		int yLim = (int)ceil(sqrtl(rem));
		for( ; (LL)yLim * yLim <= rem; ++yLim);
		for( ; (LL)yLim * yLim > rem; --yLim);
		int sum = 0, x2 = (LL)x * x % mod, x4 = (LL)x2 * x2 % mod, x6 = (LL)x2 * x4 % mod;
		g[0] = (f[0] + (LL)f[1] * x2 + (LL)f[2] * x4 + (LL)f[3] * x6) % mod;
		g[1] = (f[1] + 2LL * f[2] * x2 + 3LL * f[3] * x4) % mod;
		g[2] = (f[2] + 3LL * f[3] * x2) % mod;
		g[3] = f[3];
		for(int i = 0; i < 4; ++i) {
			int tmp = 0;
			for(int j = i << 1 | 1; j >= 0; --j)
				tmp = ((LL)tmp * yLim + coeff[i][j]) % mod;
			sum = (sum + (LL)g[i] * (tmp << 1 | !i)) % mod;
		}
		x && (sum <<= 1) >= mod && (sum -= mod);
		(ans += sum) >= mod && (ans -= mod);
	}
	ans = (LL)ans * inv6 % mod;
	printf("%d\n", ans);
	return 0;
}

Solution (demon1999)

#include <bits/stdc++.h>


using namespace std;

#define re return
#define sz(a) (int)a.size()
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define re return
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define bend(a) a.begin(),a.end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long double ld;
typedef unsigned long long ull;
const ll mod = int(1e9) + 7;

ll n, sum1, sum2, sum3, sum4, ans;
vector<ll> cp;

ll mdd(ll c) {
	c %= mod;
	if (c < 0) c += mod;
	re c;
}

ll pow1(ll k, ll st) {
	ll ans = 1;
	while (st) {
		if (st & 1) ans = mdd(ans * k);
		k = mdd(k * k);
		st >>= 1;
	}
	re ans;
}

ll get_sum(ll n) {
	n %= mod;
	n += mod;
	n %= mod;
	re (n * (n + 1) / 2LL) % mod;
}

ll get_cnt(ll a) {
	a = mdd(a);
	re mdd(mdd(2LL * mdd(a * a) * a) - mdd(3LL * mdd(a * a) * mdd(n + 2)) + mdd(mdd(a) * mdd(3LL * n + 4)) + mdd(n) * mdd(mdd(mdd(n) * mdd(n)) + 3LL * n + 2LL));
}

int main() {
	iostream::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (ll k = 1; k * k <= n; k++) {
		ll c = mdd(k * k);
		cp.push_back(k * k);
		sum1 = mdd(sum1 + c);
		sum2 = mdd(sum2 + mdd(c * c));
		sum3 = mdd(sum3 + mdd(mdd(c * c) * c));
		sum4 = mdd(sum4 + get_cnt(c));
		//cout << sum4 << "\n";
	}
	ans = mdd(get_cnt(1) + 4LL * sum4);
	ll k1 = 2, k2 = mdd(-3LL * (n + 2)), k3 = mdd(3LL * n + 4);
	for (ll a = 0; ; a++){
		while (sz(cp) && cp.back() + (a+1LL) * (a + 1LL) > n) {
			ll c = mdd(cp.back() + a * a);
			sum1 = mdd(sum1 - c);
			sum2 = mdd(sum2 - mdd(c * c));
			sum3 = mdd(sum3 - mdd(mdd(c * c) * c));
			sum4 = mdd(sum4 - mdd(get_cnt(c)));
			cp.pop_back();
			continue;
		}		
		if (sz(cp) == 0) break;
		ll k = mdd(2LL * a + 1), ksq = mdd(k * k), ktr = mdd(ksq * k);
		//cout << sum4 << "\n";
		sum4 = mdd(sum4 + mdd(ll(sz(cp)) * mdd(k1 * ktr + k2 * ksq + k3 * k)) +
			   mdd(sum1 * mdd(2LL * k * k2 + 3LL * k1 * ksq)) +
			   mdd(sum2 * mdd(3LL * k * k1)));
		//cout << sum4 << "\n";
		ans = mdd(ans + 4LL * sum4);
		sum3 = mdd(sum3 + mdd(ll(sz(cp)) * ktr) + mdd(sum2 * 3LL * k) + mdd(ksq * 3LL * sum1));
		sum2 = mdd(sum2 + mdd(ll(sz(cp)) * ksq) + mdd(2LL * sum1 * k));
		sum1 = mdd(sum1 + mdd(ll(sz(cp)) * k));
		//cout << sum3 << " " << sum2 << " " << sum1 << "\n";
	}
	//cout << ans /6<< "\n";
	ans = mdd(ans * pow1(6, mod - 2));
	cout << ans;
}

933E - A Preponderant Reunion

Author skywalkert / Preparation skywalkert / Tutorial skywalkert

Tutorial

Solution (skywalkert)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = (int)3e5 + 3;
int n, a[maxn], cnt, p[maxn], m, out[maxn];
LL f[maxn];
bool v[maxn];
int descension(int pos) {
	int dt = min(a[pos], a[pos + 1]);
	if(dt)
		out[++m] = pos;
	a[pos] -= dt;
	a[pos + 1] -= dt;
	return dt;
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		LL odd = f[max(i - 2, 0)] + a[i], even = f[max(i - 3, 0)] + max(a[i - 1], a[i]);
		f[i] = min(odd, even);
		v[i] = f[i] != odd;
	}
	// a[n + 1] = 0;
	LL ans = min(f[n - 1], f[n]);
	// printf("%lld\n", ans);
	for(int i = n - (ans == f[n - 1]); i > 0; i -= 2 + v[i])
		p[++cnt] = i;
	reverse(p + 1, p + cnt + 1);
	for(int i = 1; i <= cnt; ++i) {
		int pre = p[i - 1], cur = p[i], ctr = 0;
		if(v[cur])
			ctr += descension(cur - 1);
		ctr += descension(pre + 1);
		ctr += descension(cur);
		assert(ctr == f[cur] - f[pre]);
	}
	printf("%d\n", m);
	for(int i = 1; i <= m; ++i)
		printf("%d\n", out[i]);
	return 0;
}

Thank you everyone!

Happy Valentine's Day and happy Lunar New Year!

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

Показать архивные | Написать комментарий?

Tommyr7

7 лет назад, # |

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

→ Ответить

mango_lassi

7 лет назад, # ^ |

← Rev. 2 →

-59

Please don't make problems that require either using python or programming your own BigInt class, It's unfair for people who exclusively program c++. I don't see any need for the bounds in div1B to be so large.

Or maybe I should just finally learn python...

Edit: I was wrong, the problem is definitely solvable with just long long. I'll do more research before complaining next time.

Um_nik

+56

What? 35233893

rotavirus

← Rev. 3 →

+24

do you think all these guys used their own BigInt class?

jqdai0815

+103

Feedback: Terrible pretests for D and terrible spj for E.

skywalkert

+42

Oops... Sorry for the inconvenience. T_T

+25

What is spj?

And I don't really think that pretests should be that strong. Yes, input is bigger than MOD, so you should be careful.

quailty

+27

He means the checker. It is a pity that he operated on zeros and didn't pass pretests in problem E.

+22

Ehem. It is written in bold that each operation should be on positive numbers.

+38

Yes you are right. Maybe he is just too nervous with the end of the contest approaching :)

I_LOVE_METSUKA

Terrible nickname.

Igorjan94

← Rev. 5 →

+19

Python2: 35268543

[igorjan@archlinux]$ du -b B.py
44	B.py

Perl: 35270787

[igorjan@archlinux]$ du -b B.pl
38	B.pl

0x_________x0

+13

python2 [42 bytes] : 35283953

SrO

Oh! It's so easy in python! Here is my C++ code: 35239158 (charlieshu is also me)

int n;

int main()
{
	cin>>n;
	if(n>36)OVER("-1");
	for(int i=0;i<n/2;i++)cout<<8;
	if(n%2)cout<<4;
	cout<<endl;
	return 0;
}

alexyz

+16

div1C: find all intersections -> build graph -> count edges and vertices -> F = 2 + E — V . Am I right?

Partially correct, think about three single circles.

Actually my tutorial is finished but it needs to be posted by the sleeping poster :(

cwy

Why is div1C = gym100200C ?

+11

iloveUtaha

For Div1 C, it should be 3 if n=2 and two circles are neither intersect nor tangent

Thank you for pointing out. I will fix it later.

Svlad_Cjelli

+49

The tutorial isn't up for Div1A, and the code looks quite complicated. Here's a much simpler way:

Let's say we flipped a segment and found the best subsequence. It will look something like this: 11111122222222

Suppose we unflip the segment. Now the sequence looks like this: 1111222211112222

That is, it will be composed of 4 regions, made of 1s,2s,1s,2s. So the problem reduces to simply figuring out the longest subsequence of such form in the original sequence, no flipping necessary.

This can easily be done with a single O(N) traversal of the sequence. At each point, keep 4 values: the longest sequence of 1s, the longest sequence of 1s2s, the longest sequence of 1s2s1s, and finally the longest sequence of 1s2s1s2s.

EDIT: The editorial is up and they put this solution in it. Still, strange that they would use the complicated N^2 solution as the sample.

vacuous

You Miss out cases like

111111122112211221122222221111

Here answer should be 18. It can be found if you twist from 7 index(0-based) to end.

Running it through my solution, I'm getting an answer of 24, so I think you're missing something. Flipping 7 index to the end does work for that (the only things missing from the increasing subsequence are the 3 pairs of 11 in the middle).

kushwah_1

Thanks nice explanation it worked for me

I_D0nt_Kn0w

Sir , I still didn't get why are we finding the longest subsequence of type 1s,2s,1s,2s in your solution.. Plz explain.

Because when you flip the middle segment of 2s and 1s, you get a sequence of 1s followed by 2s, which is what you want.

abcd40404

Is there still a O(n) solution if the sequence has more values(1,2,3,4,5...)?

Yes, your intuition is almost right.

In fact, a previous version limits 1 ≤ a_i ≤ 5 and the author has tested a O(5³n) solution :P

If in that case, we need to find out the longest subsequence of 1s5s4s3s2s1s5s, am I right?

Partially correct. There may be several cases such as 1-2-4-3-2-4-5.

Thanks a lot, and Happy lunar New Year!

pk842

Thanks a lot!

ghoshsai5000

For the benefit of all beginners, here's my O(nm) solution for Div 2 A.

http://codeforces.net/contest/934/submission/35280443

My idea was to find all products, find the maximum product A[i]B[j] in one O(nm) scan.

Then, find the maximum without that particular A[i], in another O(nm) scan.

The best A can do is hide at most one element and A has to hide the element that contributes to the greatest product.

https://github.com/MathProgrammer/CodeForces/blob/master/Explanations/Explanations%2019/A%20Compatipble%20Pair%20Explanation.txt

kalra_aman

This is exactly what I thought of except that I missed some corner cases and got WA :P. Nice approach !

Thank you !

Div 2- C/ Div-1 A:

I am unable to understand this case for which my solution is failing. The editorial is not yet there. Can anyone explain how is the answer to pretest 3 is 116. Many thanks :)

http://codeforces.net/contest/934/submission/35263594

Your answer of 13 is way too low.

My guess is that you interpreted "subsequence" to mean "subarray". The difference is that a subsequence doesn't have to be contiguous.

For example, 1 2 3 4 is a subsequence of 1 5 2 5 3 5 4.

Ah got it. Thanks. I read it wrong, my bad. Thanks for the help :)

oorjaMe

My solution for "A Prosperous Lot" : 54 bytes. can we have a look at Tester Solution please. n=int(input()) print(["8"*(n//2)+"9"*(n%2),-1][n>36])

nikich340

-8

Not the best idea in E task. Complicated geometry that required special knowledges — it is not for 2-hour contest :(

sak3t

-9

Where is Div2D ? Edit: Sorry.

sudhakarshah

Can someone explain me div2 C?

Here is my approach. Ask me if you have any doubt.

nanzy

Can someone explain another solution for problem

xish

for Problem C, my solution is to regard each a[i] as the position changes from 1 to 2. That means, we calculate all 1's before i and all 2's after i, so we can get all maxium length through a[i] in O(n).

Then we do the reverse, we can regard the reverse section [L, R], only L < i < R will affect a[i]'s max length, and i split the section into two parts, [L, i) and (i, R]. For section [L, i] after reverse, we can minus all 1 and plus all 2 in the section. And for (i, R], it's simmilar but we plus all 1 and minus all 2.

Also, these two section are distinct, so we can get max L and R, sepeartely. Therefor the whole algorithm is in O(n^2)

noob__coder

Can someone explain to me why my solution for problem C in JAVA is giving TLE in large value of n. I am using similar approch as sak3t described in this comment. I see that c++ solution easily passes whereas Java is having a hard time.

Ideally it should pass the time limit easily. I don't find any bug in your submission. Probably it is some high Java intensive problem in your code.
PS: Try to optimize the code more. Like you don't need to store dp[i][j][k], as we need data for only dp[0][j][k] and dp[i][n - 1][k]. Notice, 0 and n - 1 constants. You can have this data in two linear arrays rather than one 2D array.

Thanks for the response. Check this solution. I thought that indexing may be an issue, so tried this way. And this amazing result :P

Woah, I had no idea, this can affect time taken by approximately 10 times.

Can anyone please provide beginner friendly explanation of Div2 E?

rohank196196

Can someone help me with my solution of DIV2 C. http://codeforces.net/contest/934/submission/35292502

a_adel

In Problem A i just sorted the 2 arrays and the answer was the mutliplication of a[n-2]*b[m-1]

i skipped the max of tommy and get the max of banban * the max of tommy after deleting the it's first max and i got WA on test 10 any help please

Policarpo

Your code fail for this simple test:
3 3
-7 1 5
-7 1 5

so what should be the result 5 or 49

The correct answer is 25

oToToT

How could I get the intersection of two circle, my previous method didn't provide enough precision.

I can't get the main idea behind quailty's method.

Could someone explain it for me?

cz_xuyixuan

For Div.1 D, there's a terrible mistake in the tutorial which almost drove me mad this morning and took me hours to realize what was wrong.

That polynomial of L mentioned in the tutorial appeared to be $\text{[math]}$ ,

but the correct polynomial seems to be $\text{[math]}$ .

Please fix it as soon as possible!

cuizhuyefei

Thanks so much! I also wasted a great deal of time on it.

Ha! You found a blind spot! The mistaken polynomial was from my draft paper (and I used to wrong profoundly...) but the standard solution uses the appropriate polynomial :P

The tutorial was fixed just now. Please wait for a while and refresh the page :)

Okay, thanks a lot. By the way, despite that accidental mistake, Div.1 D was really a wonderful and challenging problem :).

CodingKnight

Many thanks Codeforces for the interesting problems.

RE: 933C - A Colourful Prospect

Is there an explanation that the solution to test #115

0 0 1

0 3 2

4 0 3

is 5 not 4?

It seems that C1 = (0,0,1) is tangent to C2 = (0,3,2) at point P12 = (0,1), and is tangent to C3 = (4,0,3) at point P13 = (1,0). And, that C2 and C3 are not tangent and do not intersect. Therefore, the number of regions should be 4 not 5.

Thanks in advance for explaining.

Best wishes.

An update: A further analysis of the test case revealed that C2 and C3 are tangent at P23 = (8/5,9/5). Therefore, the area surrounded by the three arcs on C1, C2 and C3 extending between each pair of P12, P13, and P23 constitutes the fifth region.

Thanks again and best wishes.

harshit15

can anyone please explain the approach behind div2A? I am not getting why do we need to print the minimum of maximums and not the 2nd maximum?

+10

Please note tutorial for 933E has been revised for better understanding. Hope it will be helpful :)

sgrey

For div2 E can anyone explain why is my algorithm wrong? Code

if n==1 , ans=2 ; if n==2 , ans=3 (two circle,universal region) , for every pair of circles intersecting:ans++ if n==3 , ans=4 (three circle,universal region), for every pair of circles intersecting: ans++. if all three intersects, ans++.

I cannot understand what is wrong with this algorithm? TIA.

You can use GeoGebra for reasoning. Here is test 14.

akashsingh_

Can anyone please explain the question "A twisty movement" DIV2 C with this test case n=12: 1 2 1 2 1 2 1 2 1 2 Length of the Longest subsequence after the reversal is 8! Can anyone please tell [l,r] which need to flip to get this answer

cyand1317

Flipping [10, 11] gives 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2.

Mooncrater

5 лет назад, # |

-10

For 933 A, do not read the editorial's solution. It's, in simple words, bad. Use Um_nik's solution as well. Easy to understand.

Tricopter

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

How would you solve D1d's bonus? Sorry for necroposting but I can't find it anywhere.

Unnamed-Cube

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

I think it's similar to https://www.spoj.com/problems/DIVCNT1/

The solution uses Stern-Brocot Tree.