Codeforces Round #631 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

Tutorial is loading...

author's code:

#include<cstdio>
const int MAX_V = 201;
bool achieve[MAX_V];
void solve() {
    int n, x;
    scanf("%d%d", &n, &x);
    for(int i = 1; i <= n + x; i++) {
        achieve[i] = false;
    }
    for(int i = 1; i <= n; i++) {
        int ranking;
        scanf("%d", &ranking);
        achieve[ranking] = true;
    }
    for(int k = n + x; k > 0; k--) {
        int v = 0;
        for(int i = 1; i <= k; i++) {
            if(!achieve[i]) v++;
        }
        if(v <= x) {
            printf("%d\n", k);
            return;
        }
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

Tutorial is loading...

author's code

#include<cstdio>
const int SIZE = 200000;
int p[SIZE];
int ans[SIZE][2];
int ans_cnt;
bool judge(int a[], int n){
    static int used[SIZE+1];
    for(int i = 1; i <= n; i++) used[i] = 0;
    for(int i = 0; i < n; i++) used[a[i]] = 1;
    for(int i = 1; i <= n; i++) {
        if(!used[i]) return 0;
    }
    return 1;
}
bool judge(int len1, int n){
    return judge(p, len1) && judge(p + len1, n - len1);
}
int main() {
    int t = 0;
    scanf("%d", &t);
    while(t--) {
        ans_cnt = 0;
        int n;
        scanf("%d", &n);
        int ma=0;
        for(int i = 0; i < n; i++) {
            scanf("%d", &p[i]);
            if(ma < p[i]) ma = p[i];
        }
        if(judge(n - ma,n)) {
            ans[ans_cnt][0] = n - ma;
            ans[ans_cnt++][1] = ma;
        }
        if(ma * 2 != n && judge(ma,n)) {
            ans[ans_cnt][0] = ma;
            ans[ans_cnt++][1] = n - ma;
        }
        printf("%d\n", ans_cnt);
        for(int i = 0; i < ans_cnt; i++) {
            printf("%d %d\n", ans[i][0], ans[i][1]);
        }
    }
    return 0;
}

Tutorial is loading...

author's code

#include<bits/stdc++.h>
const int SIZE = 100002;
int len[SIZE];
long long suffix_sum[SIZE];
void err() {puts("-1");}
void solve() {
    int N, M;
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++) {
        scanf("%d", &len[i]);
        if(len[i] + i - 1 > N) {
            err();
            return;
        }
    }
    for(int i = M; i > 0; i--) {
        suffix_sum[i] = suffix_sum[i + 1] + len[i];
    }
    if(suffix_sum[1] < N) {
        err();
        return;
    }
    for(int i = 1; i <= M; i++) {
        printf("%lld", std::max((long long)i, N - suffix_sum[i] + 1));
        if(i < M) putchar(' ');
        else puts("");
    }
}
int main() {
    solve();
    return 0;
}

Tutorial is loading...

UPD: onthefloor provides proof for what I mention here.

author's code

#include<bits/stdc++.h>
void solve(){
    int d, m;
    scanf("%d%d",&d, &m);
    long long answer=1;
    for(int i = 0; i < 30; i++) {
        if(d < (1 << i)) break;
        answer = answer * (std::min((1 << (i+1)) - 1, d) - (1 << i) + 2) % m;
    }
    answer--;
    if(answer < 0) answer += m;
    printf("%lld\n",answer);
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        solve();
    }
}

Tutorial is loading...

a super simple solution which is differet to this blog provided by Swistakk.

author's code (from bottom to top with min heap)

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 1<<20;
int INF = 1000000001;
pair<int, int> a[SIZE];
int final_v[SIZE];
bool used[SIZE];
int h, g;
void pull(int id) {
    while(a[id] > min(a[id<<1], a[(id<<1)|1])) {
        if(a[id<<1] < a[(id << 1) | 1]) {
            swap(a[id<<1], a[id]);
            id <<= 1;
        }
        else {
            swap(a[(id<<1)|1], a[id]);
            id = (id << 1) | 1;
        }
        if(id >= (1 << h)) return;
    }
}
void solve() {
    scanf("%d%d", &h, &g);
    long long an = 0;
    for(int i = 1; i < (1 << h); i++) {
        used[i] = 0;
        scanf("%d", &a[i].first);
        a[i].second = i;
        final_v[i] = 0;
    }
    h--;
    for(int lv = h - 1; lv >= 0; lv--) {
        int ll = 1 << lv;
        int rr = 1 << (lv + 1);
        for(int i = ll; i < rr; i++) {
            pair<int, int> tmp = a[i];
            int bot = i << (h - lv);
            a[i] = a[bot];
            a[bot] = make_pair(INF, 0);
            pull(i);
            if(lv < g) {
                int need_mi = max(final_v[i * 2], final_v[i * 2 + 1]);
                while(a[i].first < need_mi) {
                    a[i] = make_pair(INF, 0);
                    pull(i);
                }
                an += final_v[i] = a[i].first;
                used[a[i].second] = 1;
                a[i] = tmp;
                pull(i);
            }
            else {
                a[bot] = tmp;
            }
        }
    }
    printf("%lld\n", an);
    bool first_time = true;
    for(int i = (1 << (h + 1)) - 1; i > 0; i--) {
        if(!used[i]) {
            if(!first_time) printf(" ");
            else first_time = false;
            printf("%d", i);
        }
    }
    puts("");
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

isaf27's code(from bottom to top with sorted array)

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

//defines
typedef long long ll;
typedef long double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define prev _prev
#define y0 _y0
#define kill _kill

//permanent constants
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int alf = 26;
const int dig = 10;
const int two = 2;
const int th = 3;
const ll prost = 239;
const ll btc = 30;
const ld eps = 1e-8;
const ll INF = (ll)(1e18 + 239);
const int BIG = (int)(1e9 + 239);
const int MOD = 1e9 + 7; //

//random
mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count());

//constants
const int M = (int)(2e5 + 239);
const int N = (int)(2e3 + 239);
const int L = 20;
const int T = (1 << 20) + 239;
const int B = 500;
const int X = 35;
const int T2 = 2 * T;

int h, g, a[T2], n;
bool mark[T];
int id[T], buf[T], timer;

bool cmp(int i, int j)
{
    return (a[i] < a[j]);
}

int pos;

void dfs_write(int p)
{
    id[pos++] = p;
    if (2 * p + 1 <= n)
    {
        dfs_write(2 * p);
        dfs_write(2 * p + 1);
    }
}

int dfs(int p, int sz)
{
    if ((1 << (g - 1)) <= p && p < (1 << g))
    {
        int l = timer;
        timer += sz;
        pos = l;
        dfs_write(p);
        sort(id + l, id + l + sz, cmp);
        mark[id[l]] = true;
        return id[l];
    }
    int l = timer;
    int new_sz = ((sz - 1) / 2);
    int s1 = dfs(2 * p, new_sz);
    int s2 = dfs(2 * p + 1, new_sz);
    merge(id + l, id + l + new_sz, id + l + new_sz, id + l + new_sz + new_sz, buf, cmp);
    buf[sz - 1] = p;
    for (int i = 0; i < sz; i++)
        id[i + l] = buf[i];
    timer++;
    if (cmp(s1, s2))
        s1 = s2;
    for (int i = 0; i < sz; i++)
        if (cmp(s1, id[i + l]))
        {
            mark[id[i + l]] = true;
            return id[i + l];
        }
    return 0;
}

void rm(int i)
{
    if (a[2 * i] == 0 && a[2 * i + 1] == 0)
    {
        a[i] = 0;
        mark[i] = false;
        return;
    }
    if (a[2 * i] > a[2 * i + 1])
    {
        a[i] = a[2 * i];
        mark[i] = mark[2 * i];
        rm(2 * i);
    }
    else
    {
        a[i] = a[2 * i + 1];
        mark[i] = mark[2 * i + 1];
        rm(2 * i + 1);
    }
}

void dfs_ans(int p)
{
    while (a[p] != 0 && !mark[p])
    {
        cout << p << " ";
        rm(p);
    }
    if (a[p] == 0)
        return;
    dfs_ans(2 * p);
    dfs_ans(2 * p + 1);
}

void solve()
{
    cin >> h >> g;
    n = (1 << h) - 1;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        mark[i] = false;
    timer = 0;
    dfs(1, n);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        if (mark[i])
            ans += a[i];
    cout << ans << "\n";
    dfs_ans(1);
    cout << "\n";
    for (int i = 0; i <= n; i++)
        a[i] = 0;
}

int32_t main()
{
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

author's code (from top to bottom)

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 1<<20;
int INF = 1000000001;
int a[SIZE], ops[SIZE];
int h, g;
int qq[24], qn;
int pull(int id) {
    int tmp = a[id];
    a[id] = 0;
    qn = 0;
    qq[qn++] = id;
    while(id * 2 < (1 << h) && a[id] < max(a[id<<1], a[(id<<1)|1])) {
        if(a[id<<1] > a[(id << 1) | 1]) {
            swap(a[id<<1], a[id]);
            id <<= 1;
        }
        else {
            swap(a[(id<<1)|1], a[id]);
            id = (id << 1) | 1;
        }
        qq[qn++] = id;
    }
    if(id < (1 << g)) {
        for(int i = qn - 1; i > 0; i--) {
            a[qq[i]] = a[qq[i - 1]];
        }
        a[qq[0]] = tmp;
        return 0;
    }
    return tmp;
}
void solve() {
    scanf("%d%d", &h, &g);
    long long an = 0;
    for(int i = 1; i < (1 << h); i++) {
        scanf("%d", &a[i]);
        an += a[i];
    }
    int need = 0;
    for(int i = 1; i < (1 << g); i++) {
        while(1) {
            int v = pull(i);
            if(v) {
                an -= v;
                ops[need++] = i;
            }
            else break;
        }
    }
    printf("%lld\n", an);
    for(int i = 0; i < need; i++) printf("%d%c", ops[i], " \n"[i == need - 1]);
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

Tutorial is loading...

author's code

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 2e5+10;
char s[SIZE];
int cnt[SIZE];
int cc[26];
int all_cnt;
int ma;
void update_ma() {
    while(ma > 0 && !cnt[ma]) ma--;
}
void dec1(int id) {
    cnt[cc[id]]--;
    cc[id]--;
    cnt[cc[id]]++;
}
pair<int, int> stk[SIZE];
int sn;
int m;
int now;
int last_len;
void add(int i, bool flag) {
    if(flag) {
        dec1(stk[sn - 1].second);
        dec1(stk[i].second);
        all_cnt -= 2;
        printf("%d %d\n",now + 1, now + stk[i].first);
        update_ma();
        sn--;
        now -= stk[sn].first;
        if(i + 1 < m) {
            stk[i + 1].first += stk[sn].first;
        }
        else{
            last_len += stk[sn].first;
        }
    }
    else {
        stk[sn++] = stk[i];
        now += stk[i].first;
    }
}
void solve(){
    scanf("%s", s);
    int n = strlen(s);
    all_cnt = 0;
    int lt = 0;
    m = 0;
    for(int i = 1; i < n; i++) {
        if(s[i] == s[i - 1]) {
            cc[s[i] - 'a']++;
            all_cnt++;
            stk[m++] = make_pair(i - lt, (int)(s[i] - 'a'));
            lt = i;
        }
    }
    last_len = n - lt;
    ma = 0;
    for(int i = 0; i < 26; i++) {
        cnt[cc[i]]++;
        ma = max(ma, cc[i]);
    }
    printf("%d\n", 1 + max(ma, (all_cnt + 1) / 2));
    if(ma * 2 < all_cnt) {
        sn = now = 0;
        for(int i = 0; i < m; i++) {
            add(i, sn && stk[sn - 1].second != stk[i].second && ma * 2 < all_cnt);
        }
        m = sn;
    }
    int main_id = -1;
    for(int i = 0; i < 26; i++) {
        if(cc[i] == ma) main_id = i;
    }
    sn = now = 0;
    for(int i = 0; i < m; i++) {
        add(i, sn && ((stk[sn - 1].second == main_id) ^ (stk[i].second == main_id)));
    }
    for(int i = 0; i < sn; i++) {
        printf("%d %d\n",1 ,stk[i].first);
    }
    printf("%d %d\n", 1, last_len);
    memset(cc, 0, sizeof(cc));
    memset(cnt, 0, sizeof(int) * (ma + 1));
}
int main(){
    int T;
    scanf("%d", &T);
    for(int i = 1; i <= T; i++) solve();
    return 0;
}

Tutorial is loading...

isaf27's solution

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

//defines
typedef long long ll;
typedef long double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define prev _prev
#define y0 _y0
#define kill _kill

//permanent constants
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int alf = 26;
const int dig = 10;
const int two = 2;
const int th = 3;
const ll prost = 239;
const ll btc = 30;
const ld eps = 1e-8;
const ll INF = (ll)(1e18 + 239);
const int BIG = (int)(1e9 + 239);
const int MOD = 1e9 + 7; //

//random
mt19937 rnd(239); //(chrono::high_resolution_clock::now().time_since_epoch().count());

//constants
const int M = (int)(4e5 + 239);
const int N = (int)(2e3 + 239);
const int L = 20;
const int T = (1 << 18) + 239;
const int B = 500;
const int X = 210;

ll up(ll a, ll b)
{
    return (a + b - 1) / b;
}

ll down(ll a, ll b)
{
    return a / b;
}

int m;
ll l[M], n, k;

void solve()
{
    cin >> n >> m >> k;
    ll pr = 0;
    for (int i = 0; i < m; i++)
    {
        ll p;
        cin >> p;
        l[i] = p - pr;
        pr = p;
    }
    l[m++] = n - pr;
    //for (int i = 0; i < m; i++)
    //    cerr << l[i] << " ";
    //cerr << "\n";
    ll sum = k + m;
    ll bl = 1;
    ll br = n + 1;
    while (br - bl > 1)
    {
        ll h = (bl + br) >> 1LL;
        ll cur = 0;
        for (int i = 0; i < m; i++)
            cur += down(l[i], h);
        if (sum <= cur)
            bl = h;
        else
            br = h;
    }
    ll MIN = bl;
    bl = 0;
    br = n + 1;
    while (br - bl > 1)
    {
        ll h = (bl + br) >> 1LL;
        ll cur = 0;
        for (int i = 0; i < m; i++)
            cur += up(l[i], h);
        if (sum >= cur)
            br = h;
        else
            bl = h;
    }
    ll MAX = br;
    vector<pair<ll, ll>> ban;
    for (int i = 0; i < m; i++)
    {
        if (up(l[i], MAX) <= down(l[i], MIN))
            continue;
        ll bl = 0;
        ll br = MIN;
        while (br - bl > 1)
        {
            ll h = (bl + br) >> 1LL;
            if (down(l[i], h) == down(l[i], MIN))
                br = h;
            else
                bl = h;
        }
        ll first = MIN - br;
        bl = MAX;
        br = INF;
        while (br - bl > 1)
        {
            ll h = (bl + br) >> 1LL;
            if (up(l[i], MAX) == up(l[i], h))
                bl = h;
            else
                br = h;
        }
        ll second = bl - MAX;
        ban.push_back(make_pair(first, second));
    }
    ll add = MAX - MIN;
    if (ban.empty())
    {
        cout << add << "\n";
        return;
    }
    sort(ban.begin(), ban.end());
    vector<pair<ll, ll>> a;
    for (int i = 0; i < (int)ban.size(); i++)
    {
        while (!a.empty() && a.back().second <= ban[i].second)
            a.pop_back();
        a.push_back(ban[i]);
    }
    ll ans = INF;
    ans = min(a[0].second + 1, ans);
    ans = min(a.back().first + 1, ans);
    for (int i = 0; i + 1 < (int)a.size(); i++)
        ans = min(ans, a[i].first + a[i + 1].second + 2);
    cout << ans + add << "\n";
}

int32_t main()
{
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

author's solution

/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
LL a[SIZE],num[SIZE];
bool done[SIZE],be_added[SIZE];
int n;
LL K;
LL get_upper_bound(int i){
    LL v=a[i]/num[i];
    if(v*num[i]!=a[i])v++;
    return v;
}
LL get_next_upper_bound(int i){
    LL v=a[i]/(num[i]-1);
    if(v*(num[i]-1)!=a[i])v++;
    return v;
}
LL go(){
    if(K==n){
        return a[n-1]-a[0];
    }
    LL ll=1,rr=a[n-1];
    while(ll<rr){
        LL mm=(ll+rr)/2;
        LL need=0;
        REP(i,n){
            if(a[i]>mm)need+=a[i]/mm;
            else need++;
        }
        if(need>=K)ll=mm+1;
        else rr=mm;
    }
    LL low=ll;
    VPLL pp;
    LL need=0;
    REP(i,n){
        if(a[i]>=low){
            num[i]=a[i]/low;
            pp.PB({a[i]/(num[i]+1),i});
        }
        else {
            num[i]=1;
        }
        need+=num[i];
    }
    {
        bool fail=0;
        REP(i,n){
            if(get_upper_bound(i)>=low){
                fail=1;
                break;
            }
        }
        if(!fail) return low-1-min(low-1,a[0]);
    }
    REP(i,n){
        if(a[i]>=low&&a[i]/(num[i]+1)==low-1){
            LL v=a[i]/(low-1);
            LL mi=min(v-num[i],K-need);
            num[i]+=mi;
            need+=mi;
            if(need==K)break;
        }
    }
    priority_queue<PLL,VPLL,greater<PLL>>added;
    priority_queue<PLL>top;
    LL mi=a[0];
    REP(i,n){
        if(num[i]>1){
            added.push(MP(get_next_upper_bound(i),i));
        }
        top.push(MP(get_upper_bound(i),i));
        mi=min(mi,a[i]/num[i]);
    }
    LL an=top.top().F-mi;
    REP(i,n)be_added[i]=done[i]=0;
    LL ma=low-1;
    while(!top.empty()&&!added.empty()){
        int id=top.top().S;
        if(be_added[id])break;
        done[id]=1;
        top.pop();
        num[id]++;
        mi=min(mi,a[id]/num[id]);
        auto tmp=added.top();
        added.pop();
        if(done[tmp.S])break;
        be_added[tmp.S]=1;
        num[tmp.S]--;
        if(num[tmp.S]>1)added.push({get_next_upper_bound(tmp.S),tmp.S});
        ma=max(ma,tmp.F);
        an=min(an,(top.empty()?ma:max(ma,top.top().F))-mi);
    }
    return an;
}
void solve(){
    LL L;
    //R(n,K,L);
    R(L,n,K);
    K+=n+1;
    LL lt=0;
    REP(i,n){
        LL x;
        R(x);
        a[i]=x-lt;
        lt=x;
    }
    a[n++]=L-lt;
    sort(a,a+n);
    W(go());
}
int main(){
    CASET{
        solve();
    }
    return 0;
}

import java.io.BufferedWriter; import java.io.IOException; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.Scanner; public class C { public static void main(String[] args) throws IOException { Scanner std = new Scanner(System.in); int n = std.nextInt(); int m = std.nextInt(); if (m==1) { if (n == m) { System.out.println(1); } else { System.out.println(-1); } return; } BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out)); int tmpN = n; int[] arr = new int[m]; for (int i = 0; i < m; i++) { arr[i] = std.nextInt(); } int[] postSum = new int[m]; postSum[m-1] = arr[m-1]; for (int i = m-2; i>=0; i--) { postSum[i] = arr[i] + postSum[i+1]; } int lastBlockStart = n - arr[0] + 1; int lastBlockEnd = n; log.write(lastBlockStart + " "); //inclusive... for (int i = 1; i < m - 1; i++) { int greedyStart = (lastBlockEnd - 1) - arr[i] + 1; //place at this index if possible int greedyStart2 = postSum[i + 1] + 1; //must place at this index in worse case... int currBlockStart = Math.min(greedyStart, greedyStart2); int currBlockEnd = currBlockStart + arr[i] - 1; //ends here... if (currBlockEnd < lastBlockEnd && currBlockEnd + 1 >= lastBlockStart) { lastBlockEnd = currBlockEnd; lastBlockStart = currBlockStart; log.write(currBlockStart + " "); } else { System.out.println(-1); return; } } int currBlockStart = 1; //starts here int currBlockEnd = currBlockStart + arr[m - 1] - 1; //ends here if (currBlockEnd < lastBlockEnd && currBlockEnd + 1 >= lastBlockStart) { log.write("1"); } else { System.out.println(-1); return; } log.flush(); } }

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

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

stefdasca

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

← Rev. 2 →

+19

Check out the video editorials

Also, you should add the codes under spoiler dreamoon_love_AA

→ Ответить

dreamoon_love_AA

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

Thanks to you very much!

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

durmanko

+23

I had different approach for Div2B, which is probably more intuitive.

Lets calculate two values:

$$$rpref[i]$$$ — the number of different elemtens in ith prefix.

$$$rsuf[i]$$$ — the number of different elements in ith suffix.

So lets fix l1. Our task is to check that sequences from [1 to l1] and from [l1 + 1 to n] are permutations. How to check this?

Sequence from [1 to K] is permutation if and only if sum(1..k) = k * (k + 1) / 2 and rpref[k] = k. We can do same procedure for suffixes.

My submission: https://mirror.codeforces.com/contest/1330/submission/75366634.

luG_0

I thought the same maybe I missed something X0 here

__SON-GOKU__

same here i got tle using same approch can someone check where my problem is -- help would be much appriciated https://mirror.codeforces.com/contest/1330/submission/75452454

__SON-GOKU__, I rewrited your code and it got AC.

You had a few problems.

1) MAX should be at least 2e5.

2) Look at these lines:

Spoiler

To create vector<||> distinct(MAX) is spent $$$O(MAX)$$$ time which means that on each test-case you were doing $$$O(MAX)$$$ iterations which naturally causes TL.

3) #define int long long

Submit: https://mirror.codeforces.com/contest/1330/submission/75483684.

← Rev. 3 →

luG_0, I found mistake in your code. In second check you should rewrite check(i+1, n,a) -> check(i, n,a), because your function checks from [a;b). I submitted your code and it got AC.

P.S. Sorry for my poor english

Submit: https://mirror.codeforces.com/contest/1330/submission/75476653

Byte_S

hey my logic was same as yours but i was unable to find how to correct it :( https://mirror.codeforces.com/contest/1330/submission/75427713 please correct my code . thanks in advance

Just write #define int long long.

Submit: https://mirror.codeforces.com/contest/1330/submission/75488123

manish_98

Hey u have declared pre and suf array as integer but the sum might exceed max value of integer.Declare it as long long

will_hunting

I used the same approach but solution is failing on test 3 can you please look at the solution https://mirror.codeforces.com/contest/1330/submission/75404652

You have the same mistake as many other participants — Overflow.

$$$sum[i+1]=((i+1)*(i+2))/2;$$$, but $$$i$$$ is Integer in your code. I replaced int i with ll i (or you can add (ll) before your formula). To avoid this sad mistakes i write #define int long long.

Submit: https://mirror.codeforces.com/contest/1330/submission/75497341

Nikhil-2500

← Rev. 7 →

https://mirror.codeforces.com/contest/1330/submission/75501441 gives wrong answer on test 2. everything is working properly except for input number 74 output is repeated 2 times. please help to correct it.

Check this test-case:

Answer is 3 2.

its coming 3 2 but printing two times. i don't know why.?

try to debug by yourself

EduardoBrito

My idea is similar to the one you use:

I do not calculate to:

rpref[i] — the number of different elements in i-th prefix. rsuf[i] — the number of different elements in i-th suffix.

Because it is also not difficult to see that for a solution to exist no number can be repeated more than twice, so what I do is check that this is true, and then I say that: Sequence from [1 to k] is permutation if and only if sum(1..k) = k * (k + 1) / 2 and max element in the sequence (1...k) = k. We can do same procedure for suffixes.

My submission with Prefix Sums: 75496699 My submission with Wavelet Tree: 75442213

Xia21

How to count different elements in fast way? I thought the same but time limit

supermatthew

There is a standard way to do this: Keep a variable called numDistinct; Also use an array or map count[] where you increment count[x] whenever you see x. Then after some increment of count[y], check whether count[y]=1. If so, then this is the first time seeing it, so increment numDistinct.

The same thing can be done when removing elements. Then you would decrement count[y], and afterward check if it became 0; if so, then decrement numDistinct.

svaderia

Hi, I had thought of the same approach, but my code is failing on TC8, My submission

Submit: https://mirror.codeforces.com/contest/1330/submission/75589871

Please, read what I wrote above.

sevlll777

Nice contest, D1B is beautiful!

Thank you~

CP_Sucks

div2B detailed https://competitiveprogrammingdiscuss.blogspot.com/2020/04/codeforces-round-631-div-2-problem-b.html

div2C detailed https://competitiveprogrammingdiscuss.blogspot.com/2020/04/codeforces-round-631-div-2.html

Mooncrater

4 года назад, # ^ |

Thank you for the explanations! I could not understand Div2C.

Regarding your solution for Div2C, the inner while loop was not required

for(int i = m;i >= 1; --i){
    	// cout << ans[i - 1] << ' ' << a[i - 1] << '\n';
    	while((ans[i - 1] + a[i - 1] - 1) < pos_needed) ++ans[i - 1];
    	pos_needed = ans[i - 1] - 1;	
    }

Instead of jumping one step ahead until you find a roadblock, you can simply take the starting point of the next block (whose value had already been calculated), and decrease one. Say it's last = ans[i+1]-1. So if this last value is greater than the end point of the current segment, then we can simply shift the current segment to the last point. If last is less than our endpoint, then we just update last=ans[i]-1, and move on.

Due to this, a tad bit faster solution can be found.

Amazing contest.

spookywooky

Somebody explain Div2D in smaller steps?

I understand that we need to choose a[i] in a way that we add at least one bit to b[i-1], and we can remove all lower bits. How does this lead to closed formular for fixed a[0], or sum of "some" a[]s?

highbias

Suppose x is some element of our sequence (say at index u). Suppose the i-th bit of x is set . Now if for every other element of the sequence, the i-th bit is 0, the prefix xor array(considering i-th bit only) will be 0 till (u — 1) and 1 after. If there exist some other element (say at index v) with i-th bit set, then the prefix xor array will be 0 till u — 1, 1 from u to v — 1 and 0 after v. This violates the strictly increasing property of prefix xor array. Hence there should be a unique element with a particular bit set. Now since a(i) > a(i — 1) and a(i) and a(i — 1) do not share any common bit, MSB(a(i)) > MSB(a(i — 1)).

abhi1260

i can not understand div2 C problem correctly. can anyone help me in this plzz. the editorial is quite fast.

SnipErrr

li in i-th operation means in this operation, you can color li numbers of cells, you can start with any position as long as there are no less than li cells after this position and cells will have the color from the latest operation. So the task is to find the starting position for every operation so that you can color all cells and every colors are used at least once.

thank you for your help. now i understand how to solve it. thank u.

AgentCode

The question states that each color must appear at least once.How many colors are there?

Prajwal_

there are m colors = number of operations

You can see the tutorial one more time. I add some detail about this problem.

trawiser

I have some issue in understanding problem Div2-C

In test case 2 2 1 2

n = 2 m = 2

output should be 2 1

Why is it "-1"?

In your solution, the first color will be covered by the second color. In the end, there is only one color.

leetcode07

I loved the contest. Thank you dreamoon_love_AA

+11

slick69

Can anyone tell what was wrong with this submission? https://mirror.codeforces.com/contest/1330/submission/75383926

asc123

for input like 1 2 1 2 3 4 ans is 2 4 from both ways by your code and each ans should be unique

huayucaiji

Thanks for the wonderful tutorial,Ienjoy this competition very much ^_^

tianxiawoyou

I liked the contest very much, but I wish the pretests can be better next time.

Thank you for the round,and thanks to Denis aramis Shitov.

REFLAME_ASH

I thick that Div.1B is much more difficult than Div.1C.

ltc.groverkss

Tbh I think it depends on how good you are in counting problems. I found divB easier because I'm not that good in implementing even though I had the algo for div1C

allitnicS

Could anyone explain why my 2C is wrong? Thanks! Link: https://mirror.codeforces.com/contest/1330/submission/75413150

LOVE_YJZ

What a great contest!

Gats

Why "For each i, posi=max(i,n−suffix_sum[i]+1)"?

Same question (about 2C/1A). Seems like magic — can anyone explain the intuition?

kinoud

One observation is that for any valid solution we can adjust it so that if i<j holds then pos[i]<pos[j] also holds. Thus we can do it greedily. First, we make pos[i]=n-suffix[i]+1 for every i. After doing this, we may find pos[1] < 1. Then we need increase pos[1] to 1 and then increase pos[2] to 2 if pos[2]<2 then increase pos[3] to 3... Iterate this until we find pos[x]>=x.

Thanks for your answer

Herio

Nice Contest！Good problems.

I'm glad that you can think so. :)

clairvoyant

Weak pretests for Div2A unfortunately :(

Anshika_85

In 1330B — Dreamoon Likes Permutations , according to author solution if we give test case like size of array is 5 and array elements — {1,2,3,4,5}. Then ans is 2 0 5 5 0 But it is said the two permutations are of non-zero length. Isn't this a contradiction? Answer shoud be 0. Please correct me where I am wrong.

Please check the constraint of array element. all values are between $$$1$$$ to $$$n-1$$$

grandesonnerie

Could someone please explain how we arrived at this formula for Div 2C? For each $$$i, pos_i=max(i,n−suffixsum[i]+1)$$$.

EDIT: Formatting

walleeva

See this may help with example 1330C solution with example

vector94

Problem B(Div2) also solvable by using the prefix sum. Here's my submission: 75458331

SLIMSHADYNICK

Problem B can be easily solved using rolling hash!

inszva

Div2-D/Div1-B, I dont't know how to solve it, but i just print the answer for the first 16 number using a program I. And I found regular pattern in it (table I). i-th row in table I is the number of every possible xor-sum of the case n = i.

Observation I: $$$f(x)$$$ represents the number of the case n=x, then $$$f(x) = f(x-1)*2$$$ if x is qual to lowbit(x) where lowbit(x) means x&-x. The lowbit of 0b100100 is 0b100.

Observation II: $$$g(x)=highbit(x)$$$, highbit means the highest-bit in the number. The highbit of 0b10100 is 0b1000 and the highbit of 0b11101 is 0b10000. Then $$$f(x) = f(x-1) + f(g(x)-1)$$$ if x is not equal to lowbit(x). So $$$f(x) = f(g(x)) + (x - g(x))f(g(x)-1)$$$ if x is not eual to lowbit(x).

Then I write the solution by the observation. Solution in contest

Thanks for the fortune make me become candidate master.

Program I

signed main() {
    map<int, int> cnt;
    cnt[0] = 1;
    for (int i = 1; i <= 16; i++) {
        map<int, int> cnt2;
        for (auto &p : cnt) {
            cnt2[p.fi] += p.se;
            if ((p.fi ^ i) > p.fi) cnt2[p.fi^i] += p.se;
        }
        for (auto& p: cnt2) {
            cout << p.se << " ";
        }
        cout << endl;
        cnt = cnt2;
    }
    return 0;
}

Table I

1 1 
1 1 1 1 
1 1 2 2 
1 1 2 2 1 1 2 2 
1 1 2 2 2 2 4 4 
1 1 2 2 4 4 5 5 
1 1 2 2 6 6 6 6 
1 1 2 2 6 6 6 6 1 1 2 2 6 6 6 6 
1 1 2 2 6 6 6 6 2 2 4 4 12 12 12 12 
1 1 2 2 6 6 6 6 4 4 5 5 18 18 18 18 
1 1 2 2 6 6 6 6 6 6 6 6 24 24 24 24 
1 1 2 2 6 6 6 6 12 12 12 12 25 25 26 26 
1 1 2 2 6 6 6 6 18 18 18 18 26 26 28 28 
1 1 2 2 6 6 6 6 24 24 24 24 28 28 29 29 
1 1 2 2 6 6 6 6 30 30 30 30 30 30 30 30 
1 1 2 2 6 6 6 6 30 30 30 30 30 30 30 30 1 1 2 2 6 6 6 6 30 30 30 30 30 30 30 30

Lex_An

Can someone please tell me what is wrong with my submission for Div.2B? Similar idea with editorial but simpler implementation with 2 sorted vectors?

My Submission: https://mirror.codeforces.com/contest/1330/submission/75460697

ghoshsai5000

Problem D reminded me of Bookshelves. The reason it reminded me of it is because both problems require us to divide the given problem into 30 sub problems (based on the number of bits) and then solve that sub-problem with a DP. When I saw Bookshelves, I was very surprised at the idea. But introspecting about it was the reason I was able to solve this D.

Here are my solutions, in case anybody wants to refer them

sanskar111100

https://mirror.codeforces.com/contest/1330/submission/75403704 Getting wrong answer on B, can someone help?

you can check the 11-st test cases in test 2.

What you get wrong is in the following input:

1
6
2 2 2 2 1 1

sorry gave the wrong link, https://mirror.codeforces.com/contest/1330/submission/75432926

lucifer_1502

Your code fails when l1=l2. Then there is only one unique partition but you printed 2.

dmkz

← Rev. 5 →

For Div1B sequence can be found on OEIS. This is the differences between answers for $$$d$$$ and $$$d+1$$$. Source code for python available on OEIS too in bottom of the page. I copy-pasted this code to my program and got accepted during contest. Idea to search on OEIS came to me on second hour, because I believed to author when read the statement that it can't be found on OEIS.

I think what you mean is the sequence of "distinct" differences between answers for $$$d$$$ and $$$d+1$$$. You are right. I didn't found it when I test it during preparing the contest. It shows that I still need to train myself about the ability of searching in OEIS. (>__<)

In Div2 D, I think there is a typo in the example of editorial. For example, when n = 6 , it should be d=6 . 'n' is the size of a matrix.

Thank you. I fix it now.

ace_loves_xq

Love how you explained the constructive algorithm in 1329A so thoroughly! I didn't find a solution in 2 hours, just as you say, the conditions are way too 'open'. Your explanation gives me new insight on how to approach problems like this.

a_journey

dreamoon_love_AA can you please explain it more for coloring problem.

There exists some i such that li+i−1>n. In this condition, at least one of the first i−1 colors will disapear after i-th operation.

how to prove it.

If there exists some $$$i$$$ such that $$$l_i+i-1 > n \Leftrightarrow i > n-l_i+1$$$, the $$$i-th$$$ operation must be done at position $$$p_i < i$$$, that is because $$$p_i \le n-l_i+1 < i$$$. In this case, it will overlap other colors and make them disappear. Hope that help!

utsavparakhiya

i m not satisfied with the tutorial.

What if the test case is 6 5 1 4 3 4 2

As per tutorial it gives -1.But still the solution is possible as 1 2 4 2 2 which is possible.

why's that, the 2nd colour and the 4th colour have the same length and the same p[i] (as you said), then the 4th colour will surely overlap the 2nd one. (or did you have a typo i think?)

try to colour as i have mentioned in the answer. There will be one colour of each m which is the requirement in question.

bitshar

This means that n — li < i — 1. Now, whenever you colour li blocks, exactly n — li blocks remain uncoloured. If this number is less than i — 1, it means that less than i — 1 blocks remain uncoloured after this operation. But in the previous i — 1 operation, you have put i — 1 colour and even if each of them occupies just 1 block, it will disappear after this operation.

vinhnhibinh

In Div2 problem B (1330B), i don't understand what "p+len1" mean, can anyone help me? (line 16)

Jon.Snow

p+len1 means reference to "array p at index len1" so a[0] will point to p[len1]

In Div2-C, how do we know that after applying "sort" constraint, our problem won't become unsolvable?

No need to sort SEE HERE

In my opinion, the output of your solution is also "sorted".

In a sense yes. But great problem though ,feels good to solve this one even after contest

You won't know before you try it. That's just like We don't know whether we can solve a problem before we think out a solution. When solving problems, just like do DFS on the thought until you arrive at the correct solutions. apply "sort" constraint is just one possible try on this problem. You can also try many other things such as all $$$p_i$$$ are equal or $$$p_i$$$ is from larger to smaller.

PVsNPSolver

Nice contest . This is how contests should be — 5 problems and 2 hrs. max . Nice , compact and standard problem statements and conducted very well . Although I believe pretests should have been stronger . This is my first comment ever and I wrote it to appreciate your commendable work .

onthefloor

+43

Was scrolling through the comments and didn't seem to find someone giving a proof on the correctness of Div 1B/Div 2D (that is, the sequence is valid if and only if $$$h(a_i)<h(a_{i+1})$$$ always holds.

If $$$h(a_i)<h(a_{i+1})$$$ always holds, then $$$a_i<a_{i+1}$$$ for for each $$$i$$$ so the first condition is true. To show that this would imply $$$b_i<b_{i+1}$$$, for each $$$i$$$, $$$h(a_k)<h(a_{i+1})$$$ for all $$$k\le i$$$. It then follows that $$$h(b_k)<h(a_{i+1})$$$ for all $$$k\le i$$$ (by the definition of XOR), and therefore $$$h(b_{i+1})=h(a_{i+1})>h(b_k)$$$ for all $$$k\le i$$$: the first equality is because $$$b_{i+1}=a_{i+1} \otimes b_{i}$$$. It then follows that $$$b_i$$$ is also increasing.

Now we show that $$$h(a_i)<h(a_{i+1})$$$ is essential. Suppose otherwise. Given that $$$a_i$$$ is increasing, there exists $$$k$$$ satisfying $$$h(a_k)=h(a_{k+1})$$$. Choose such a minimum $$$k$$$ (i.e. $$$h(a_i)<h(a_{i+1})$$$ for all $$$i<k$$$); adapting the proof above we see that $$$h(b_k)=h(a_k)=h(a_{k+1})$$$, which means that the $$$j$$$-th digit of $$$b_k$$$ and $$$a_{k+1}$$$ in their binary expansion matches for all $$$j\ge h(b_k)$$$. It follows that $$$b_{k+1}=a_{k+1} \otimes b_k$$$ must have the $$$j$$$-th digit as 0 for all $$$j\ge h(b_k)$$$, which follows that $$$h(b_{k+1})<h(b_k)$$$ and therefore $$$b_{k+1}<b_k$$$, contradiction.

Whizzo_Mo1kai

Why do in the final answer , we are subtracting the value obtained by -1, like I understand how we got 24 in the editorial solution but why do we subtract the value obtained by multiplication by 1 to get 23 ? Plz help.

The empty sequence is counted once in the analysis, but it's not allowed. Hence the $$$-1$$$.

Tru3R00T

1329B - Dreamoon Likes Sequences Can someone please explain how does knowing v=0,1,2 ... solve the problem for all lengths n>=1 ?? Thanks.

MinhazIbnMizan

dreamoon_love_AA May I know when will the construction of Div. 1 C and E be over? I am eagerly waiting for the editorial of Div. 1 C or may I get some hint for Div. 1 C?

I hope I can complete it this weekend. I cannot make sure what time I can complete it just like I don't know what time I can become LGM again.

P.S. In fact, I'm writting it now. But my writing speed is very slow.

Now Div.1 C is complete.

Thank you very much!

jaineric

My code for div 2B was O(n^2). It gave TLE on test case 3. But according to the constraints it should have worked. Please help me out if I am missing something. https://mirror.codeforces.com/contest/1330/submission/75401692

Why do you think it can work with the constraints? $$$O(n^2)$$$ shouldn't work.

n=200000 n^2=4*10^10 t=10^4 In 1 second we can do 10^8 operations Constraint is 2 seconds. Hence we can do 10^16 operations. t*n^2=4*10^14. So I thought it should work. I think I am wrong somewhere. Please correct me.

Yuki726

+10

You can do 2*10^8 operations in 2s not 10^16

Oh thanks! I get it now. What a stupid mistake.

time_14_07

Anyone explain properly in simple language Div 2C.

Try this may be helpful Solution

Can you also provide a better explanation link for Div 2D.

Sorry But i did not solve that one yet

In div1.c bottom to top approach, while constructing the solution, it is said if the current value at the iterated node is not in final tree call f(). But how to prove its possible to do the operation at that node without the leaf going below height g?

I had written it. Please see the tutorial carefully.

I didn't understand this part, "Then We iterate node from smallest index to the larger one. We always can determine the weight value of the iterated node, because the weight value only can be the maximum value in its subtree". Didn't we already determine value for each node while finding minimum sum?

When we have chosen the weight values set $$$S$$$ remaining in the final tree, according to the trait of max heap, the value of node $$$1$$$ must be the largest one from $$$S$$$. And the value of node $$$2$$$ must be the maximum value in the subtree of node 2 who belongs to $$$S$$$ except the final value of node $$$1$$$. And so on, we can make sure all values in the final tree will be the same with the lower bound calculated by the algorithm.

Swistakk

+78

The more I hear/read about poeple's solutions to Div1C, the more I appreciate my strikingly simple solution. All authors solutions seem to me overly complicated. I call positions from $$$1$$$ to $$$2^g-1$$$ free initially (positions that are at least $$$2^g$$$ are not considered free). I sort all elements in this heap and consider them in increasing order. Whenever I consider some value, I traverse path from its initial node to root. If there is no free element on it, I skip it. If there is one, I check whether both of its sons are not free, and if it the case then I put it there and call it taken instead of free (if exactly one of sons is free then I skip it). And that's it, very short code here: https://ideone.com/1XiSlu

+12

Wow! I appreciate your solution a lot!

happy15

+22

I tried to understand the correctness of your simple solution, but couldn't.

Could you please kindly provide some proof of it? or at least any hint?

aaaaajack

+16

Lemma: A height-$$$g$$$ heap is a valid final heap if and only if for every position $$$r$$$, the element $$$a_r$$$ on it is originally in the subheap rooted at $$$r$$$. Proof: =>: observe that an element can only move to the position of its ancestor <=: observe that if you fix the elements left in the final heap, the shape of the final heap is unique. (largest element should be the root, and right and left subheap both have unique shape by induction hypothesis)

We will prove by induction that

If we place an element, it is in the correct position.
If we skip an element, it is not in the optimal solution.

Proof for 1. Suppose we can $$$a_r$$$ on $$$r$$$ but in the optimal solution there's $$$b_r$$$ on $$$r$$$. If $$$b_r>a_r$$$, we can replace $$$b_r$$$ with $$$a_r$$$ in the optimal solution. This is still valid by our lemma, and has a better value (contradiction). If $$$b_r<a_r$$$, that means we skip $$$b_r$$$ before. (contradiction)

Proof for 2. Suppose we skip $$$a_r$$$ but it's actually on $$$r$$$ in the optimal solution. Now consider all elements under $$$r$$$ in the optimal solution. They are $$$<a_r$$$ so we should have placed them in the correct position. That means all nodes under $$$r$$$ are full at this point so we will not skip $$$a_r$$$ by our rule. (contradiction)

jarvis307

Thanks for the great and easy solution.

I had one doubt and would be grateful if you could take 5 minutes to clear it out.

How did you decide that the nodes not considered from the sorted array will be the one that we have to choose while doing f operation?

TIA

arobindo

div2D min(2(v+1)−1,d)−2v+2.why added 2 here.anyone help please

$$$\min(2(v+1)−1,d)−2v+2$$$ mean the number of different condition that you can choose at most one number from $$$2v$$$ to $$$\min(2(v+1)−1,d)$$$. Let $$$x = 2v$$$, $$$y = \min(2(v+1)−1,d)$$$. Firstly, there are $$$y-x+1$$$ numbers from $$$x$$$ to $$$y$$$. So if you choose exactly one number, there are $$$y-x+1$$$ choices. Secondly, you must add an additional one for the case don't choose any number from the range. That's why.

UPD: fixed the bug in the fomula

Phill.

Thanks for explaining this point, but I think that y = min(2(v+1)-1,d) without -2v + 2.

on of the 24 combinations is choosing nothing. we should remove it.

Iceberg

Div2D For example, when d = 6, there are 2 choices for v=0, 3 choices for v=1, 4 choices for v=2.

Please someone give me all the choices for every v. Because I get it like that for v = 0 --> 1 choice : 1(1) for v = 1 --> 2 choices : 2,3(10,11) for v = 2 --> 3 choices : 4,5,6(100,101,110)

You miss the choice "don't choose anyone".

pranay.agra

I was wondering if anyone could let me know what the issue with this code for problem C Div 2 is (and possibly a test case to replicate it). Running on C — Dreamoon Likes Coloring gets the wrong answer on test case 6, but the input is too long to replicate and copy. I have also tried similar types of values to this test case, but they all succeed. I do know that my answer outputs "-1" when it should be possible. I appreciate it a lot! (First time posting.)

integer overflow

Works now! Thanks

starboy_jb

Wow dreamoon_love_AA, This editorial includes, How to approach the problems, Not just solution. Kudos to You, Thank You!.

wicher3

Can anyone provide proof of that is stated in Div2(Problem D) editorial about h(ai) must less than h(ai+1).

I had provided the link of the proof written by a good person in the tutorial. Please see the tutorial carefully.

raghav_19

for Div1-C i have an idea to solve it. for each node find the number of node we have to delete in its subtree from left side, since the number of node need to delete from right and left side will be equal to get perfect binary tree after all operation, lets denote it by num[i]. and maintain left[i] and right[i] to store number of nodes we have deleted in left & right subtree of node i till now respectively. now if i call required function from pos 1 then there are 4 possiblity.

if(v[l]>v[r] && left[i]<num[i]) then it will goto left child

if(v[l]>v[r] && left[i]==num[i]) then it has to go to right child in this case i will update the pos from where i am calling function to get perfect binary tree finally. similarly other two condition where v[r]>v[l].

once it get to leaf node, i will break it and call required function from pos that we get from above function. As i am calling required function from top most possible node every time then i should get minimum possible total sum and and i will also get binary tree finally. But i am getting WA and i couldn't find such test case. Here is my submission. Can anyone tell me what is wrong in my solution

Update: thanks dreamoon_love_AA i forgot to update left[i] & right[i] for all ancestor of node from where i was calling required function. If some one want to look, here it is

You get WA on this test:

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

ni__kh__il

https://mirror.codeforces.com/contest/1330/submission/75732591

i Dont't know that is wrong logic in my code can some one help me with div2 B problem will be much appreciated thanks

https://mirror.codeforces.com/blog/entry/75559?#comment-598438

← Rev. 6 →

its done thankyou btw i dont know about OIES

I don't know what's OIES either.

daayan

I do not understand the editorial for Div2C. Can someone explain it better?

There are many tutorials you can search from google or in Codeforces comments(For example, here). Please see them first. I'm busy on weekdays. I will add it in the weekend.

mballen1

I've been trying div2 (B. Dreamoon Likes Permutations) but I'm not really sure why am I getting T.L.E could you please help me to find out ? 78243837 ... I find the maximum inside input array and check the two possible casses (len1 = ma, len2 = n- ma ... len1 = n-ma, len2 = ma)... I use a function that is intended to check if there is a permutation in the subarray bounded by the different lengths in O(n)

You declare "vi calc(MAXN + 1);" too many time.

I guess I need to study more about memory handling. Thanks

I think the thing you must know is declaring a vector with length $$$N$$$ need time which is proportional to $$$N$$$.

gurharpartapdhaliwal

My approach for div 2 B is little diff. i stored elements of the prefix and suffix in 2set and checked if size of set is equal to size of suffix . this will ensure that the elements are unique and also the max element should be equal to the length. though sometimes it gave segmentation fault when i tried to remove elements from the suffix set.

Colossus20

4 года назад, # |

I don't get why can we use $$$p_i = \max(i, n - suffix\text{_}sum[i] + 1)$$$. If you don't describe the most crucial part of the solution what's the point of the editorial?

The editorial for Div2C has so many typos and odd english that it seems like a first draft.

Sorry, I'm the guy rejected by Google and many companies because of bad English. It' quite hard to write a better editorial of this problem in English for me. And I recommend you to find tutorials from the Internet. There are many better editorials in the Internet nowadays. So I won't update this tutorial anymore.

KDVinit

I have a rather "simple to think" solution for Div1 C, This may be a bit long in implementation than the one mentioned by Swistakk, but it is just Greedy and Brute forces, which makes it simple to think in the first place (and so not a 2400 Problem ;).

See my submission — 111844109

Note that this (not as advised by the problem creator dreamoon_love_AA) a top-down approach :)

What basically this does is check if the largest element can be removed from the heap and if it can be removed just remove it (Greedy).

Thus if iterate over the nodes in decreasing value of the node, and if they can be removed from the heap remove them and update the heap as in problem (Brute Force).

To check if it can be removed we will check the sum of height and depth of the node should be greater than "g".

Also while updating the heap we keep an account of the new index of the nodes in a global array "Index".

To me, this seemed easier than most of the solutions I have seen, do tell me if there are some mistakes with the logic :)

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