Does anyone still remember this problem Dreamoon and Ranking Collection?

In the statement of this problem, Dreamoon would like to collect all the places from 1 to 54. Now, after 41 more rounds, Dreamoon did it!

I'm very happy now, so I share my good news to the Codeforces community. ^_^

#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;
}

#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;
}

#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;
}

UPD: onthefloor provides proof for what I mention here.

#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();
    }
}

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

#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;
}

//#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;
}

#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;
}

#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;
}

//#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;
}

/*{{{*/
#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;
}

Hello, everyone! Codeforces Round #631 will be held at 03.04.2020 17:35 (Московское время).

The problems are almost from me(dreamoon_love_AA), except one problem of which the idea is from drazil and developed by me. Also we want to thank 300iq for helping me prepare the round, isaf27, tmt514, rowdark, yp155136, wangyenjen, n_dao107 and woruo27 for testing this round, and MikeMirzayanov for Codeforces and Polygon.

This is my third time organizing a problemset for a Codeforces round (my previous rounds: Codeforces Round #292, Codeforces Round #320).

Good luck and have fun!

UPD: Below is a message for you from MikeMirzayanov:

About two weeks ago, we completed the crowdfunding campaign dedicated to the 10th anniversary of Codeforces. Community help inspires and provides resources for the development and operation of the platform. Thanks! With this round, we want to say thank you to Denis aramis Shitov, for his significant contribution and support. It is valuable, important and very nice when people from the community lend a helping hand and congratulate. Thank you, Denis!

UPD2: Also thanks to Shik for testing the round!

UPD3: Score distribution:

• Div2: 500 1000 1500 1750 2500
• Div1: 500 750 1500 2000 2500

UPD4: link to tutorial

UPD5:

I won't say sorry that the pretests are not strong. Because I don't think the pretests must be strong in every contest.

But I still want to give congratulations to the winners:

div1:

1. Um_nik
2. tourist
3. Petr
4. ecnerwala
5. ffao

div2:

1. 3u_my_light
2. hydd
3. fafafafafafa
4. timmyfeng
5. FrijolitoAzul

Among these winners, I want to especially congratulate Um_nik. I am quite excited when I see him solve all problems.

After Educational Codeforces Round 79, I want to share a problem I create this year.

It's host on 2019 Multi-University Training Contest 5.

Problem link is here.

The statement of problem is following:

Many problems require printing the probability of something. Moreover, it is common that if the answer is $$$\frac{a}{b}$$$, you should output $$$a \times b^{-1} \pmod{p}$$$ ($$$p$$$ is a prime number). In these problems, you cannot know the exact value of the probability. It's so confusing!!! Now, we want to reverse engineer the exact probability from such calculated output value x. We do so by guessing the probability is the one with the minimum $$$b$$$ such that $$$a \times b^{-1} = x \pmod{p}$$$. Now we invite you to solve this problem with us!

What the statement mentioning is quite match the situation in contest of today!

The following is the reference solution (you can use the code to get the correct fraction format output in today contest):

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef long long LL;
typedef pair<LL,LL> PLL;
const int SIZE = 1e6+10;
PLL solveWA(LL x0, LL p){
    PLL r; 
    r.S = p / x0 + 1;
    r.F = r.S * x0 - p;
    PLL x = {x0, 1LL};
    while(r.F >= r.S) {
        if(r.F * 2 < x.F) {
            PLL nxt_r = make_pair((x.F / r.F + 1) * r.F - x.F , (x.F / r.F + 1) * r.S - x.S);
            x = r;
            r = nxt_r;
        }
        else {
            LL dif = x.F - r.F;
            LL tt = x.F / dif;
            // x.F - i * dif < r.S * i - x.S * (i-1)
            // x.F - x.S < (r.S + dif - x.S) * i
            LL need = (x.F - x.S) / (r.S + dif - x.S) + 1;
            if(need <= tt) return {x.F - need * dif, (r.S - x.S) * need + x.S};
            PLL nxt_r = {x.F - tt * dif, (r.S - x.S) * tt + x.S};
            x = r;
            r = nxt_r;
        }
    }
    return r;
}
PLL solveAC(LL x0, LL p){
    PLL r; 
    r.S = p / x0 + 1;
    r.F = r.S * x0 - p;
    PLL x = {x0, 1LL};
    while(r.F >= r.S) {
        if(r.F * 2 < x.F) {
            PLL nxt_r = make_pair((x.F / r.F + 1) * r.F - x.F , (x.F / r.F + 1) * r.S - x.S);
            x = r;
            r = nxt_r;
        }
        else {
            LL dif = x.F - r.F;
            LL tt = x.F / dif;
            // x.F - i * dif < r.S * i - x.S * (i-1)
            // x.F - x.S < (r.S + dif - x.S) * i
            LL need = (x.F - x.S) / (r.S + dif - x.S) + 1;
            if(need <= tt) return {x.F - need * dif, (r.S - x.S) * need + x.S};
            PLL nxt_r = {x.F - tt * dif, (r.S - x.S) * tt + x.S};
            x = {x.F - (tt - 1) * dif, (r.S - x.S) * (tt - 1) + x.S};
            r = nxt_r;
        }
    }
    return r;
}
LL modmul(LL A,LL B,LL mod)
{
    return (A*B-(LL)((long double)A*B/mod)*mod+mod)%mod;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--) {
        LL p, x;
        scanf("%lld%lld", &p, &x);
        PLL ret=solveAC(x,p);
        printf("%lld/%lld\n",ret.F,ret.S);
    }
    return 0;
}

Hi, all.

I found a magic thing that $$$x\ /\ i * j$$$ is not always equal to $$$x * j\ /\ i$$$! For example, when $$$x = 12, i = 9, j = 6$$$, then $$$x\ /\ i * j = 6$$$ but $$$x * j\ /\ i = 8$$$. The fact surprised me.

Now, given three positive number $$$x$$$, $$$a$$$, $$$b$$$, I wonder how may pair of $$$(i,j)$$$ satisfy $$$x\ /\ i * j = x * j\ /\ i$$$ and $$$1 \le i \le a$$$ and $$$1 \le j \le b$$$?

I hope I can solve about $$$20$$$ tests which satisfy $$$1 \le x,a,b \le 10^9$$$ in 1 second. Can you help me?

PS. This is a problem that I give in some local contest. I feel it's interesting and share it here.

PS2. I think it's a math problem instead of programing problem.

In past years, rng_58 usually post some information about finalist of big event. I appreciate these posts a lot.

This year, I enter top 25 luckily. And I am curious about Codeforces handle of other people.

I try to find out all Codeforces handles of Yandex finalists this year. If there are any mistake, please let me know >__<

In SnackDown 2017 Online Elimination Round yesterday, I cannot get AC from problem Waiting in a Queue during contest.

After many hours of contest, I found a bug of my code:

The correct input format of this problem is:

n

a₁ a₂ ... a_n

b₁ b₂ ... b_n

But I read Input as following:

n

a₁ b₁

a₂ b₂

.
.
.

a_n b_n

I felt shocked after finding this bug. Why can I pass sample with this bug !!??

Then I saw the sample carefully. It shows:

2
3 2
2 2

I don't know how to use English to describe my though....

And I thought, if I get AC by just fixing this bug, I must post this bug on Codeforces!

Now it's the time.

Hi all!

We're hosting the 26th Weekly Training Farm, a weekly training contest to popularize algorithm contests in Taiwan. We prepared both English and Chinese versions of the problems and welcomes everyone on Codeforces to join this round!

This round will start at 2017/3/3 19:30~21:30 (GTC+8) and lasts for 2 hours. There are five problems of estimated difficulties: 500-1000-1500-1750-3000 (compared to a Div.2 Codeforces round).

To participate the contest:

• First join our Codeforces group at http://codeforces.net/group/gRkn7bDfsN
• Then the contest can be found at http://codeforces.net/group/gRkn7bDfsN/contests

The writer of this round is drazil and the testers are dreamoon_love_AA and tmt514. Thanks! Good luck and have fun!

Dear CodeForces,

I added one interesting team contest for preparing ICPC World Final into gym!

Every year National Taiwan University will host selection contest in order to determine which team will go to World Final. This year, I host this contest. Ideas of most problems are came from me. Hope these problems can let everyone feel interesting!

I set the start time of this contest as 13:30 UTC. If you have no time in this time slot, don't be sad. You still can choose any time after that to enjoy the contest.

UPD: Reminder : The contest will start in around 6 hours from now.

Hi all.

This week's farm training contest will be held on 3.7 hours later. This week's writer is drazil and tester is me (dreamoon). This week's contest consists of 6 problems of difficulties (Div. 2 500-1000-1750-2500-2250-2500). We invite all who is interested to our contest. This contest will be held in our group gym. You can find the contest in our codeforces group.

Thanks!

UPD:

Hi all, Weekly Training Farm 21 has ended.

Congradulations to the winner W4yneb0t and the first runners up eddy1021, they are the only two who solved all six problems!!

Thanks to all who participated in the contest. We hope you enjoy the problems.

The editorial will be posted within a couple of days.

We wish to see you in the next week's training farm prepared by zscoder!

Thanks drazil to translate the Chinese editorial to English.

Two of the problems in this week are created by modifying input constraints of recent Atcoder problems. The other three are a series of problems. Thus, in this editorial we won't follow the order of the problems but begin with the problems which are modified from Atcoder problems and put the series problems to the last.

Problem B — Write a Special Judge!

This problem is modified from AGC007 — Shik and Stone, which is originally created by Dreamoon as well. The difference in the Atcoder version is that the input must be a valid path (starting at the top left corner and ending at the bottom right corner). In fact, this modified version is the very first version proposed. But the contest organizers at Atcoder think this (modified) version is not easy enough resulting the constraint to the input. With the constraint we only need to verify whether the number of '#'s is n + m - 1 or not (you can justify why this solution will fail in the modified version).

Although we cannot count the number of '#'s directly in the modified version, this problem still has many ways to solve. Here we demonstrate a straightforward and easy to code one: Travel all cells in the order of left to right, top to bottom. Each time when we meet a '#', check if it is to the right or bottom of the last met '#'. Also don't forget to make sure the first and the last '#' are located at the top left and the bottom right cell respectively.

PS. Tester got accepted two times using incorrect code. Thanks him for making the test cases strong enough!

Here is the judge's code:

#include<cstdio>
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    char s[12];
    int x=0,y=1;
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=m;j++){
            if(s[j]=='#'){
                if((i==x&&j==y+1)||(i==x+1&&j==y)){
                    x=i;y=j;
                }
                else return 0*puts("Wrong Answer");
            }
        }
    }
    if(x!=n||y!=m)puts("Wrong Answer");
    else puts("Accepted");
    return 0;
}

Problem D — Edit Sequence

This problem is modified from ARC063 — An Invisible Hand. The difference is that the input numbers in the modified version are not unique (and also we simply the statement a lot). To be honest I didn't realized that the numbers are unique while participating in ARC063 (so I was shocking that many of the contestants got accepted so fast ... and I find out I ignored that condition after the contest when I look at the solutions of other contestants).

Let f(a) = h. Intuitively, we may list all numbers that contributes to f(a) = h first, then modify some of them to make f(a) smaller. For example, when a = [3, 5, 3, 3, 5, 2, 3, 4, 3, 3, 2, 4, 1, 2, 3]. Now we have h = 2 and the contributing numbers are [3, 5, 3, 3, 5, 2,  , 4,  , , 2, 4, 1, , 3].

It's not hard to find out that we can split those contributing numbers into non-overlapping segments (such as [3, 5, 3, 3, 5], [2, 4, 2, 4], [1, 3] in the above example) so that in each segment there are only two values and the lower values in each segment are decreasing (from left to right).

After splitting, we now need to further split each segment into two halves (with possibly an empty half). For each segment, if we modify all values in the left half to the larger values of the two and all values in the right half to the smaller value of the two, then the segment becomes valid. Again in the above example, [5, 5, 3, 3, 3][4, 4, 2, 2], [3, 3] is one of the valid example. After all those modifications, f(a) becomes smaller!

So the answer to the problem can be obtained by finding the smallest numbers of values need to be modified in each segment among all possible splits. A DP approach along with some simple counting can be utilized to get the answer in O(N), details are in the code.

At Codeforces, a contestant proposes exploiting the relation between matching and maximum flow to greedily compute the sub-answer for each segmentation. His code is HERE.

Here is the judge's code:

#include <bits/stdc++.h>
using namespace std;
const int INF = 1023456789;
const int SIZE = 200002;
int A[SIZE],left_mi[SIZE],right_ma[SIZE];
int solve(vector<int>& seq){
    int now=0,ret;
    for(int i=0;i<seq.size();i++){
        if(seq[i]!=seq[0])now++;
    }
    ret=now;
    for(int i=0;i<seq.size();i++){
        if(seq[i]==seq[0])now++;
        else now--;
        ret=min(ret,now);
    }
    return ret;
}
int main(){
    int N,h=0;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)scanf("%d",&A[i]);
    left_mi[0]=INF;
    for(int i=1;i<=N;i++){
        left_mi[i]=min(left_mi[i-1],A[i]);
    }
    right_ma[N+1]=-INF;
    for(int i=N;i>0;i--){
        right_ma[i]=max(right_ma[i+1],A[i]);
        h=max(h,right_ma[i]-left_mi[i-1]);
    }
    int low=INF,an=0;
    vector<int>seq;
    for(int i=1;i<=N;i++){
        if(A[i]<low){
            an+=solve(seq);
            seq.clear();
            low=A[i];
        }
        if(A[i]==low+h)seq.push_back(A[i]);
        else if(A[i]==low&&right_ma[i+1]==low+h)seq.push_back(A[i]);
    }
    an+=solve(seq);
    printf("%d\n",an);
    return 0;
}

Problem A — Score Distribution 1

This is the first problem of the series. Let's assume p₁ ≤ p₂ ≤ ... ≤ p_N since the order of scores doesn't matter. The minimum possible total score of x problems is , while the maximum possible total score of x problems is . So the problem asks us to make sure the minimum score of i + 1 problems is always strictly greater than the maximum score of i problems for all i from 1 to N - 1.

Of course, we cannot calculate the summation in O(N) for each i separately. We must use a more efficient algorithm.

Here is the judge's code:

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 200001;
int p[SIZE];
int main(){
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)scanf("%d",&p[i]);
    sort(p+1,p+N+1);
    long long left_part=p[1],right_part=0;
    for(int i=2;i<=N;i++){
        left_part+=p[i];
        right_part+=p[N+2-i];
        if(left_part<=right_part)
            return 0*printf("bad\n%d\n",i-1);
    }
    return 0*puts("good");
}

Problem C — Score Distribution 2

This is the second problem of the series, from now on we assume p₁ ≤ p₂ ≤ ... ≤ p_N.

If you're guessing purely by looking at sample test cases, you may think that the answer is using binary search to find the smallest N consecutive numbers that satisfy the constraints. But sorry, I'm not a kind problem setter >_<. If you use this kind of methods, you may end up with values greater than 10⁹. There are some other ways to get answers in the allowed range!

Here are some notations we will use later:

• , which is the sum of the smallest i + 1 problems minus the sum of the i largest problem.
• i is bad if and only if S_i ≤ 0, in this case the condition is violated.
• All division from now on is integer division.

Before solving this problem. Let's prove an important property of this series: If i is bad, then for all i ≤ j ≤ (N - 1) / 2, j is bad.

Prove: We can observed that Si first decreases then increases (actually non-increases and non-decreases). The minimum value in Si will occur at S_{(N - 1) / 2}. i is bad means S_i ≤ 0, which indicates that all j between i and (N - 1) / 2 is bad since in that range S_j is decreasing (actually non-increasing).

Note that from now on we define S_{(N - 1) / 2} as the discriminant of the related sequence p, denoted as Δ(p).

From the property above, we know that if y > (N - 1) / 2 the answer must be Impossible, and we also know that in all other cases S_y ≤ 0 and S_y−1 > 0.

Now we consider a special sequence p only consists of two values: the first (N + 1) / 2 numbers are v1 and the last N / 2 numbers are v2. Under this assumption we must satisfy v1 × y > v2 × (y - 1) and v1 × (y + 1) ≤ v2 × y to comply with the condition. With some intuition we can see v1 = y, v2 = y + 1 perfectly fits the requirements!

Here is the judge's code:

#include<bits/stdc++.h>
int N,p[200001];
int main(){
    int x,y;
    scanf("%d%d",&x,&y);
    N=x;
    if(y*2+1>N)puts("Impossible");
    else{
        printf("%d\n",N);
        for(int i=1;i<=(N+1)/2;i++)printf("%d ",y);
        for(int i=(N+1)/2+1;i<=N;i++)printf("%d%c",y+1," \n"[i==N]);
    }
    return 0;
}

Problem E — Score Distribution 3

This is the third problem in the series, as usual we assume p₁ ≤ p₂ ≤ ... ≤ p_N and integer division.

First we define a subsequence q  =  q₁ = p_k1, q₂ = p_k2, ..., q_m = p_km of p (k₁ < k₂... < k_m) is good if and only if q satisfy the conditions (i.e. Δ(q) > 0).

A key observation is that is that for a p and a related good subsequence q, if we keep all values in q not changed and modify all other numbers in p to the value of p_{k(m + 2) / 2}, then the modified p' will become good because Δ(p') = Δ(q).

Secondly, we can see that if there exists some good q of length m, then there exists some good "continuous" subsequence q' of length m which is also good. One way of constructing such q' is to take consecutive m values in p where the (m + 1) / 2-th number in q' is the (m + 1) / 2-th number in q (because Δ(q') ≤ Δ(q)).

Last key observation: if a continuous subsequence q is good, then any continuous subsequence of q is also good.

Prove: Assume q is of length m. We construct q' by removing the rightmost value in q. If m is even, Δ(q) - q_{m / 2 + 1} + q_m = Δ(q'). If m is odd, Δ(q) - q_{(m + 1) / 2} + q_m = Δ(q'). So we have Δ(q′) ≥ Δ(q), that means a good subsequence is still good if the rightmost value is removed. A similar prove can show that this conclusion holds for removing the leftmost value. In addition, any continuous subsequence of q can be obtained by removing values from left or right in q, q.e.d.

At this point, the problem is identical to find the longest continuous good subsequence. We can iterate all right boundaries and binary search for the left boundary to find the longest good continuous subsequence. Note that to check a continuous subsequence q is good or not only required O(1) time after O(N) preprocessing since we only need to know Δ(q). Also note that if the input is sorted there exists an O(N) solution.

Here is the judge's code:

#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define MP make_pair
#define PB push_back
#define PII pair<int,int>
#define VPII vector<pair<int,int> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int SIZE = 200*1000+1;
VPII pp;
long long sum[SIZE];
int an[SIZE];
int main(){
    int N;
    scanf("%d",&N);
    pp.PB(MP(0,0));
    for(int i=1;i<=N;i++){
        int x;
        scanf("%d",&x);
        pp.PB(MP(x,i));
    }
    sort(pp.begin(),pp.end());
    for(int i=1;i<=N;i++){
        sum[i]=sum[i-1]+pp[i].F;
    }
    int ma=1,anL=1,anR=2;
    for(int i=N;i>ma;i--){
        int ll=1,rr=i-1;
        while(ll<rr){
            int mm=(ll+rr)/2;
            if(sum[(mm+i)/2]-sum[mm-1]>sum[i]-sum[(mm+i+1)/2])rr=mm;
            else ll=mm+1;
        }
        if(ma<i-ll+1){
            ma=i-ll+1;
            anL=ll;
            anR=i+1;
        }
    }
    int v=pp[(anL+anR)/2].first;
    for(int i=1;i<anL;i++)an[pp[i].second]=v;
    for(int i=anL;i<anR;i++)an[pp[i].second]=pp[i].first;
    for(int i=anR;i<=N;i++)an[pp[i].second]=v;
    for(int i=1;i<=N;i++)printf("%d%c",an[i]," \n"[i==N]);
    return 0;
}

Sorry for my bad English >__<

I will host a small contest called "Weekly Training Farm #15" today.

The exact time is 2nd December 12:00 UTC. It's just about 4 hours before Codeforces Round #383.

Weekly Training Farm Contest Series are hosted in Codeforces group tw-icpc-blog

All problem are prepared by me. This time all problems are my original problems.

You can see the last contest Weekly Training Farm #14 to understand the style of problems.

UPD: The contest starts in around 6 hours! You can register contest now.

UPD 2: 15 minutes remaining!

UPD 3: If you can read Chinese(Traditional), you can find editorial Here.

Sorry for my bad English >__<

There is a small contest called "Weekly Training Farm #14" hosted in one hour latter.

Weekly Training Farm Contest Series are hosted in Codeforces group tw-icpc-blog

These problems are mixed by old problems in many judge and some original problem.

You can see the last contest Weekly Training Farm #13 to understand the style of problems.

The Series contest is hosted in order to spread programming contest in Taiwan. But there are only little participants :(

As problem setters, I hope there will be more people can see these problems. So I post the blog to invite everyone. Thanks~

UPD: If you can read Chinese(Traditional), you can find editorial Here.

UPD 2: The English editorial is here.

I intend to create a special contest like ABBYY cup in groups. That is, problems can have many testset and each testset have different scores. How can I achieve it?

Problm 1 : Raising Bacteria

Write down x into its binary form. If the i^th least significant bit is 1 and x contains n bits, we put one bacteria into this box in the morning of (n + 1 - i)^th day. Then at the noon of the n^th day, the box will contain x bacteria. So the answer is the number of ones in the binary form of x.

code of author's friend: this

Problem 2 : Finding Team Member

Sort all possible combinations from high strength to low strength. Then iterator all combinations. If two people in a combination still are not contained in any team. then we make these two people as a team.

author's code: this

Problem 3 : A Problem about Polyline

If point (a,b) is located on the up slope/ down slope of this polyline. Then the polyline will pass the point (a - b,0)/(a + b,0).(we call (a - b) or (a + b) as c afterwards) And we can derive that c / (2 * x) should be a positive integer. Another condition we need to satisfy is that x must be larger than or equal to b. It’s easy to show that when those two conditions are satisfied, then the polyline will pass the point (a,b).

Formally speaking in math : Let c / (2 * x) = y Then we have x = c / (2 * y) ≥ b and we want to find the maximum integer y. After some more math derivation, we can get the answer is . Besides, the only case of no solution is when a < b.

In fact, always dosn't exist or larger than .

author's code:

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int main(){
    LL a,b;
    cin>>a>>b;
    if(a<b)puts("-1");
    else printf("%.12f\n",(a+b)/(2.*((a+b)/(2*b))));
    return 0;
}

Problem 4 : Or Game

We can describe a strategy as multiplying a_i by x t_i times so a_i will become b_i = a_i * x^t_i and sum of all t_i will be equals to k. The fact is there must be a t_i equal to k and all other t_i equals to 0. If not, we can choose the largest number b_j in sequence b, and change the strategy so that t_j = k and all other t_j = 0. The change will make the highest bit 1 of b_j become higher so the or-ed result would be higher.

After knowing the fact, We can iterator all number in sequence a and multiply it by x^k and find the maximum value of our target between them. There are several method to do it in lower time complexity. You can check the sample code we provide.(I believe you can understand it quickly.)

author's code:

#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZE = 2e5+2;
long long a[SIZE],prefix[SIZE],suffix[SIZE];
int main(){
    int n,k,x;
    scanf("%d%d%d", &n, &k, &x);
    long long mul=1;
    while(k--)
        mul *= x;
    for(int i = 1; i <= n; i++)
        scanf("%I64d", &a[i]);
    for(int i = 1; i <= n; i++)
        prefix[i] = prefix[i-1] | a[i];
    for(int i = n; i > 0; i--)
        suffix[i] = suffix[i+1] | a[i];
    long long ans = 0;
    for(int i= 1; i <= n; i++)
        ans = max(ans, prefix[i-1] | (a[i] * mul) | suffix[i+1]);
    printf("%I64d\n",ans);
}

Problem 5 : Weakness and Poorness

Let , we can write down the definition of poorness formally as

. It's easy to see that A is a strictly decreasing function of x, and B is a strictly increasing function of x. Thus the minimum of max(A, B) can be found using binary or ternary search. The time complexity is ,

Now here give people geometry viewpoint of this problem:

let

We plot n + 1 straight line y = i * x + b_i in the plane for i from 0 to n.

We can discover when you are given x. The weakness will be (y coordinator of highest line at x) — (y coordinator of lowest line at x).

So we only need to consider the upper convex hull and the lower convex hull of all lines. And the target x value will be one of the intersection of these convex hull.

Because you can get these line in order of their slope value. we can use stack to get the convex hulls in O(n).

author's code : this (using binary search)

code of author's friend (using stack to handle convexhull with O(n), have more precision)

Problem 6 : LCS again

Followings are solution in short. Considering the LCS dp table lcs[x][y] which denotes the LCS value of first x characters of S and first y characters of T. If we know lcs[n][n] = n - 1, then we only concern values in the table which abs(x - y) ≤ 1 and all value of lcs[x][y] must be min(x, y) or min(x, y) - 1. So each row contains only 8 states(In fact,three states among these states will never be used), we can do dp on it row by row with time complexity O(n).

There is another not dp method. You can refer this comment.

author's code:

#include <bits/stdc++.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 RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#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 PII pair<int,int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e5+10;
// template end here
LL dp[SIZE][8];
char s[SIZE];
int get_bit(int x,int v){return (x>>v)&1;}
int main(){
    DRII(n,m);
    RS(s+1);
    REPP(i,1,n+1)s[i]-='a';
    s[n+1]=-1;
    REP(i,m){
        int state=1;
        if(i==s[1])state|=2;
        if(i==s[1]||i==s[2])state|=4;
        dp[1][state]++;
    }
    REPP(i,2,n+1){
        REP(j,8){
            int d[4]={i-3+get_bit(j,0),i-2+get_bit(j,1),i-2+get_bit(j,2)};
            REP(k,m){
                int d2[4]={};
                REPP(l,1,4){
                    if(s[i-2+l]==k)d2[l]=d[l-1]+1;
                    else d2[l]=max(d2[l-1],d[l]);
                }
                if(d2[1]>=i-2&&min(d2[2],d2[3])>=i-1)dp[i][(d2[1]-(i-2))|((d2[2]-(i-1))<<1)|((d2[3]-(i-1))<<2)]+=dp[i-1][j];
            }
        }
    }
    printf("%lld\n",dp[n][0]+dp[n][1]+dp[n][4]+dp[n][5]);
    return 0;
}

Problem 7 : Walking!

Since there is only one person, it’s not hard to show the difference between the number of left footprints and the number of right footprints is at most one.

For a particular possible time order of a sequence of footprints, if there are k backward steps, we can easily divide all footprints into at most k + 1 subsequences without backward steps. Then you might guess that another direction of the induction is also true.That is, we can combine any k + 1 subsequence without backward steps into a whole sequence contains at most k backward steps. Your guess is correct !

Now we demostrate the process of combining those subsequences.

We only concern the first step and the last step of a divided subsequence. There are four possible combinations, we denote them as LL/LR/RL/RR subsequence separately(the first character is the type of the first step and the second character is the type of the second step).

Suppose the number of four types of subseueqnce(LL/LR/RL/RR) are A, B, C, D separately. We have abs(A - D) ≤ 1.

We can combine all RR, LL subsequeces in turn into one subsequenceswith at most A + D - 1 backward steps(the result may be of any of the four subsquence types). Now we have at most one LL or RR type subsequence.

Then we can combine all RL subsequence into only one RL subsequence with at most A - 1 backward steps easily. And so do LR subsequences. Now we want to combine the final RL and LR subsequences together. We could pick the last footprint among two subsequences, exclude it from the original subsequcne and append it at the tail of another subsequence. The move will not increase the number of backward step and the types of the two subsequences would become RR and LL ! We can easily combine them into one LR or RL subsequence now. If there is still a LL or RR type subsequence reamained. We can easily combine them, too.

So if we can divide all footprints into the least number of subsequences without backward steps. Then we have solved the problem. And this part can be done with greedy method.

Now we provide one possible greedy method:

Firstly, we translate this problem to a maximum matching problem on bipartite graph as following:

Take "RLLRRL" as example:

We split each footprint into two vertices which on is in left part and another is in right part.

If two footprints is next to each other in resulted subsequnces, we will connect the left vertex of the former to right vertex of the latter in the corresponded matching. So the matching described in above left graph is subsequences: "RL-R--" and "--L-RL" and in above right graph is "RL-R-L" and "--L-R-". we can find that the number of subsequences is (number of footprints) — (value of matching).

Due to the graphs produced by this problem is very special, we can solve this bipartite matching as following:

Iterate each vertex in left part from top to bottom and find the uppermost vertex which is able to be matched in right part and connect them.

If we process this algorithm in "RLLRRL", the resulted matching is the above right graph.

Why the greedy method is correct? we can prove it by adjusting any maximum matching to our intended matching step by step. In each step, you can find the uppermost vertex the state of which is different to what we intend and change its state. I guess the mission of adjusting is not too hard for you to think out! Please solve it by yourself >_<

By the way, I believe there are also many other greedy methods will work. If your greedy method is different to author's. Don't feel strange.

author's code: this

Problem 8 : The Mirror Box

If we view the grid intersections alternatively colored by blue and red like this:

Then we know that the two conditions in the description are equivalent to a spanning tree in either entire red intersections or entire blue dots. So we can consider a red spanning tree and blue spanning tree one at a time.

We can use disjoint-sets to merge connected components. Each component should be a tree, otherwise some grid edges will be enclosed inside some mirrors. So for the contracted graph, we would like to know how many spanning trees are there. This can be done by Kirchhoff’s theorem.

Since there are at most 200 broken mirrors, the number of vertices in the contracted graph should be no more than 401. Hence a O(|V|³) determinant calculation algorithm may be applied onto the matrix.

author's code: this

Hello, everyone! Codeforces Round #320 will be held at Sep/16/2015 18:00 MSK. Note that round starts in the unusual time!

The problems are from tmt514, Shik, drazil, and me(dreamoon_love_AA). Also we want to thank Zlobober for helping us preparing the round, AlexFetisov and winger for testing this round , Delinur for translating the statement into Russian, and MikeMirzayanov for Codeforces and Polygon.

This is my second time organizing a problemset for a Codeforces round (my previous round: #292). In my previous round all problems were provided by me. But I think that if problems are provided by more people, then the contest will be more interesting! So I asked my friends to help me this time. Hope everybody can have fun during the round!

Participants in each division will be given six tasks and two and a half hours for solving them (the last four problems in Div. 2 are as same as as the first four problems in Div. 1). Scoring system will be announced later closer to the start of the round.

Bayan is an Iranian software company working on large-scale web applications. It doesn't only develop the search engine, but also it holds an annual open competition Bayan Programming Contest with an on-site round in Tehran. The on-site round of 2015 became an international event with many strong participants.

Bayan has supported Codeforces on our Codeforces 5-year crowdfunding program. Thank you Bayan! This round is in your honor!

UPD 1: Due to technical reasons the round starts at 18:15 Moscow time.

UPD 2: The round will use the dynamic scoring with 250 points step.

UPD 3: Problems are ordered according to their supposed difficulty.

UPD 4: Winners!

Div1:

1) Um_nik

2) Egor

3) Endagorion

Div2:

1) EmaxxMaster

2) gongy

3) Irisviel_von_Einzber

UPD5: link of Editorial

In recent one year, I don't know why but there are many people sending messages to me for asking similar problems. So I decide to create this blog.

In the beginning, I must say, you may feel disappointed after reading this blog. Because I don't have any special tips. My study method has wasted me many many time.

There are some basic points I think you have known.

1. Practice, practice, and practice. I take so many time to think and solve problems. I think I do it 5 hours a day on average.

2. Make friends with many awesome people. I know many awesome people. For example, arosusti, kelvin, peter50216(peter50216), seanwu, Shik, takaramono, tmt514, ... If I have some problems that I can't solve in few weeks, I can almost get solution from my friends.

Then I say what I do for training myself.

When I do problems. There are two possible order for choosing problem.

1. Start from most people solved one.
2. Solve consecutive Numbers of problems and try to solve all of them.

I don't know which one is best. But I often change the strategy. And when I feel I can't solve problems anymore from a judge. I will find a new judge and continue to do the same thing.

In fact, I think the order of doing problems is not important for me. When I read and solve 90% problems from a judge. Will you think the order of solving be important? I really don't know how to choose order is best for me. So I do almost the problems.

List some judges I use.(In fact, There are many Taiwanese judges I solved not listing in following because they don't open for all people.)

1. Codeforces. I think Codeforces is the best judge recently. It's easy to use and contain editorial for most problems.

2. Topcoder. Topcoder have many awesome problems. Even I sometimes think problems of 250 pt are also beautiful. It contain Editorial for most problems, too. (You can find problems here.|You can find editorial here.)

3. sgu I think sgu is the hardest judge. It contain many problems with unusual skill.

4. Timus There are many hard contest in the judge. I think it's good for group training.

5. ProjectEuler There are many good math problems in this website. After you solve a problem, you also can see how other people solve it in forum.

I think the feel between practice and competition is quite different. So sometimes I will random choose some problems from a judge to form a problemset and set time limit for training myself. But now Codeforces have function of virtual contest. We can simply do the same thing in Codeforces.

I don't choose problems by their topic. On the contrary, I study topic when I occur a problem that I cannot solve it. Then I will ask my friends whether the problem is related to some topic or google it.

I usually read AC code of other people even I can solve it. Sometimes we can found a totally different solutions, better time complexity solutions, or short solutions.

I don't study from specific websites or resources, either. I will google each thing from google respectively.

That's all what I do for studying algorithm.

Thanks to johnathan79717 fo polish my words.

515-A Drazil and Date

If Drazil chooses the shortest path from (0,0) to (a,b), it takes |a| + |b| steps.

So we know that all numbers less than |a| + |b| are impossible to be the number of steps that Drazil took.

Now consider when the number of steps is not less than |a| + |b|.

When Drazil arrives at (a, b), he can take two more steps such as (a, b) -> (a, b + 1) -> (a, b) to remain at the same position.

So we know that for all s such that s ≥ |a| + |b| and (s - (|a| + |b|))%2 = 0, there exists a way for Drazil to get to (a, b) in exactly s steps.

The last part we should prove is that it's impossible for Drazil to arrive at (a,b) in exactly s steps when (s - (|a| + |b|))%2 = 1.

We can color all positions (x, y) where (x + y)%2 = 0 as white and color other points as black.

After each step, the color of the position you're at always changes.

So we know that it's impossible for Drazil to get to (a, b) in odd/even steps if the color of (a, b) is white/black.

Conclusion: If s ≥ |a| + |b| and (s - (|a| + |b|))%2 = 0 print "Yes", Otherwise print "No".

Time Complexity: O(1).

author's code

515-B Drazil and His Happy Friends

You may notice that Drazil invites his friends periodically, and the period of invitation patterns is at most n * m (because there are only n * m possible pairs of boys and girls).

So if no one changes from unhappy to happy in consecutive n * m days, there won't be any changes anymore since then.

We can simulate the process of having dinner until there are no status changes in consecutive n * m days.

Because there are only n+m people, it's easy to prove the simulation requires O((n + m) * n * m) days.

But in fact, the simulation takes only O(n * m) days.(More accurately, the bound is (min(n, m) + 1) * (max(n, m) - 1) )

What happens? You can do some experiments by yourself. =) (you can suppose that only one person is happy in the beginning.)

In fact, this problem can be solved in O(n + m).

Let g be the greatest common divisor of n and m. If the i-th person is happy, then all people with number x satisfying will become happy some day because of this person.

So for each 0 ≤ i ≤ g - 1, we only need to check if there exists at least one person whose number mod g is i and is happy.

If it exists for all i, the answer is 'Yes', otherwise the answer is 'No'.

author's code

515-C Drazil and Factorial

Conclusion first:

First, we transform each digit of the original number as follows:

0, 1 -> empty

2 -> 2

3 -> 3

4 -> 322

5 -> 5

6 -> 53

7 -> 7

8 -> 7222

9 -> 7332

Then, sort all digits in decreasing order as a new number, then it will be the answer.

Proof:

We can observe that our answer won't contain digits 4,6,8,9, because we can always transform digits 4,6,8,9 to more digits as in the conclusion, and it makes the number larger.

Then, how can we make sure that the result is the largest after this transformation?

We can prove the following lemma:

For any positive integer x, if it can be written as the form (2!)^c₂ * (3!)^c₃ * (5!)^c₅ * (7!)^c₇, there will be only one unique way.

Suppose that there exists two ways to write down x in this form, we can assume that the two ways are (2!)^a₂ * (3!)^a₃ * (5!)^a₅ * (7!)^a₇ and (2!)^b₂ * (3!)^b₃ * (5!)^b₅ * (7!)^b₇.

We find the largest i such that a_i ≠ b_i, Then we know there exists at least one prime number whose factor is different in the two ways.

But according to the Fundamental Theorem of Arithmetic, there is only one prime factorization of each integer. So we get a contradiction.

After getting the result, we don't need to worry about other numbers being larger than ours.

Time Complexity: O(n).

author's code

515-D Drazil and Tiles

Again we give conclusion first:

First, view each cell as a vertex and connect two adjacent cells by an edge.

Then, build a queue and push all vertices of degree 1 in it.

Finally, in each iteration, we pop a vertex from the queue until the queue is empty. If the vertex is used, go to the next iteration. Otherwise, we put a tile on the vertex and its adjacent vertex, and erase these two vertices from the graph. If it yields a new vertex with degree 1, push it into the queue.

When the queue is empty, if there are still some cells not covered by any tiles, the answer will be "Not unique."

It's easy to understand that if we can put tiles on all cells by the above steps, the result is correct. But how about the remaining cases?

We will prove that when the degrees of all vertices are at least two, the solution is never unique.

Suppose there is at least one solution.

According to this solution, we can color those edges covered by tiles as black and color other edges as white.

We can always find a cycle without any adjacent edges having the same colors. (I'll leave it as an exercise. You should notice that the graph is a bipartite graph first.)

Then we can move the tiles from black edges to white edges.

So if there is at least one solution, there are in fact at least two solutions.

Time Complexity: O(nm)

author's code

515-E Drazil and Park

There are many methods for this problem. I'll only explain the one that I used.

Let's split a circle at some point (for example between 1 and n) and draw a picture twice (i. e. 1 2 3 ... n 1 2 3 ... n), thus changing the problem from a circle to a line.

Remember that if two trees Drazil chooses are x and y, the energy he consumes is d_x + d_x + 1 + ... + d_y - 1 + 2 * (h_x + h_y).

Now rewrite this formula to (d₁ + d₂ + ... + d_y - 1 + 2 * h_y) + (2 * h_x - (d₁ + d₂ + ... + d_x - 1))

Denote (d₁ + d₂ + ... + d_k - 1 + 2 * h_k) as R_k and denote (2 * h_k - (d₁ + d₂ + ... + d_k - 1)) as L_k

When a query about range [a, b] comes (The range [a, b] is where Drazil can choose, but not the range where the children are playing), it's equivalent to querying the maximum value of L_u + R_v, where u and v are in [a, b] and u < v.

Another important thing is that L_u + R_v always bigger than L_v + R_u when u < v.

So we can almost solve the problem just by finding the maximum value of L_u and R_v by RMQ separately and sum them up.

However, there is a special case: u = v, but we can handle it by making RMQ find the two maximum values.

Time Complexity: O(n + m).

author's code (implement with )

More information about RMQ: editorial from Topcoder

516-D Drazil and Morning Exercise

We can use dfs twice to get the farthest distance from each node to any leaves (detail omitted here), and denote the longest distance from the i-th node to any leaves as d_i.

Then we choose a node with minimum value of d_i as the root. We will find that for any node x, d_x isn't greater than d_y for any node y in the subtree of node x.

Next, we solve the problem when there's only one query of L. In all valid groups of nodes, where node x is the nearest to the root, obviously we can choose all nodes with d_i ≤ d_x + L into the group. Now we want to enumerate all nodes as the nearest node to the root. We denote the group of nodes generated from node i as G_i.

We can do it in using dfs only once. (if the length of every edge is 1, we can do it in O(n))

Imagine that G_i will almost be as same as the union of all G_j where node j is a child of node i, but some nodes which are too far from node i are kicked out. Each node will be kicked out from the groups we considered at most once in the whole process. Now we want to know when it happens. We solve it as follows: When we do dfs, we reserve a stack to record which nodes we have visited and still need to come back to. Yes, it's just like the implementation of recursive functions. Then we can just use binary search to find the node in the stack that when we go back to it, the current node will be kicked out (the closest node with |d_x - d_i| ≥ L).

So the time complexity of the above algorithm is

Now we provide another algorithm with O(qnα(n) + nlog(n)) by union find. (Thanks Shik for providing this method.)

First, sort all nodes by d_i.

Then for each query, consider each node one by one from larger d_i's to smaller d_i's.

At the beginning, set each node as a group of its own. We also need to record how many nodes each group contains.

When handling a node x, union all groups of itself and its children. At the same time, for each node j with d_j > d_x + L, we minus 1 from the record of how many nodes j's group has.

By doing these, we can get the number of nodes j in x's subtree with d_j <  = d_x + L. That's exactly what we want to know in the last algorithm.

author's code (implement with O(qnα(n) + nlog(n))))

516-E Drazil and His Happy Friends

Simplifying this question, suppose that n and m are coprime. If n and m are not coprime and the gcd of n and m is g, then we can divide all people into g groups by the values of their id mod g and find the maximum answer between them. Obviously, If there is at least one group of friends which are all unhappy in the beginning, the answer is -1.

Now we determine the last one becoming happy, for boys and girls separately.

In fact, there's an easy way to explain this problem — finding the shortest path! View all friends as points, and add another point as the source. For all friends, we will view the distance from the source as the time becoming happy. And define two types of edges.

(1)

There is a fact: If a girl x become happy in time t, then the girl (x + n)%m will become happy in time t + n. So we can build a directed edge from point x to (x + n)%m with length n. Similar for boys.

(2)

If the i-th boy/girlfriend is happy originally, we can connect it to the source with an edge of length i. At the same time, we also connect the source to i%n-th boy(i%m for girl) with an edge of length i. You can imagine that the same gender of friends form a cycle. (eg. the (i * m)%n-th boy is connected to the ((i + 1) * m)%n)-th boy for i from 0 to n - 1)

With these two types of edges, we can find that if a friend is unhappy originally, he/she will become happy at the time value which is the length of the shortest path from the source.

The only question is that there are too many points and edges!

We can solve this problem by considering only some "important" points.

1. Points connected by the second type of edges.
2. Points connected to important points in 1., by the first type of edges.

And we can combine some consecutive edges of the first type to a new edge. The group of edges is the maximal edges that contain deleted points.(These deleted points always form a line).

Finally we find the maximum value of the shortest path from the source to these friends which is unhappy originally in the reduced graph.

Time complexity:

author's code

Hello, everyone! Codeforces Round #292 will be held at Feb/17/2015 19:30 MSK. We're looking forward to your participation!

The problems are from dreamoon_love_AA, and thanks Shik for some discussion. Also we want to thank Zlobober for helping me prepare the round, AlexFetisov and winger for testing this round , Delinur for translating the statement into Russian, and MikeMirzayanov for Codeforces and Polygon.

This is first time I provide all problems for a Codeforces round. I hope you'll find it interesting! Please read all problem statements and discover what the main character drazil do in those problems for he's really cute =)

Finally, I would like to ask sorry_dreamoon to participate this round. I believe everyone have the same curiosity as me about your behavior in Dreamoon's round =) May I have the honor of inviting you?

Update1 : Because problems of this round are hard to determine their difficulty, We will use Dynamic score for this round. Then the order of problems is from easy to hard by sense of me and testers.

Update2 : Due to technical reasons we have to move round on five minutes.

Update3 : Congratulation to our winners:

Div 1:

1. Haghani

2. sorry_dreamoon

3. Endagorion

4. jcvb

5. xyz111

Also, special congrats on rng_58, who solved problem E in Div.1, which anyone else could not solve.

Div 2:

1. EarthQuito

2. I.Smirn0ff

3. zclimber

4. Chipe1

5. tylerbrazill

Between them, EarthQuito is the only person who solve all problems!

Update4 : link to editorial

The feature is: The colour of submission status of summary represent what kind of language the person use.

I'm very depressed to know it so lately...

dreamoon4 is so cute! I love him very much >///<.

Firstly, we denote the multiplicative inverse of x mod p as inv(x,p).

1. use dp method to calculation x! mod p for x=1 ~ n (1<=n<p, p is some prime)
2. calculate inv(n!,p) utilize Extended Euclidean algorithm.
3. use dp again to calculate inv(x!,p) for x=n-1 ~ 1 with the fact inv(x!,p) * x = inv((x-1)!, p)
4. now, if we want to now inv(x,p) for some x in [1,n], we only need to calculate (x-1)! * inv(x!,p)