pwned orz!

Omg “highschool CPers” CF round!!! Expecting an interesting problemset!!

:penchickpride: pwned orz!!

:pinoypride: penchick pwned orz!!

I waddle for the fish!

pwned orz!!

As a taster, I found the problems very delicious

hi orz ppl @pwned @culver0412

i will definitely join! :penchickcheer:

As a tester, maomao90 is gay

As a setter, I'm surprised Penchick hasn't had jet lag yet.

pwned orz

excited for penchick-pilled round !!!!! (pwned orz)

As a tester, I'll let you in on some facts:

GL&HR!

as a participant, here is an obligatory penchick image that nobody has posted yet

After more than two years of preparation and nearly thirty problems on our shortlist

Couldn’t be more excited to get into this

Excited to participate, pwned orz!

As a tester W round

as someone giving their advice in creating interesting problems, please upvote

As a participant, I love Penchick!

As a participant, I read all the comments and wondered why only one peng' has orange beak and why are the 2 rubik's cubes having 2 different "**shades of green**" ?!

duckforces

Hoping for the best Div.2 Round! Btw, the penguins are cute <3

penguinforces

So excited,hope that the problems are as cute as the announcement and the penchicks.

As a tester, good luck and

Penguiiiiiiiiiins

"Why is there no Div 4? The last one was 1.5 months ago..."

You for being an awesome member of the CF community! The "You" of this sentence is surprising!!!!!!!!

As a tester, after creating six problems for us, Penchick is now resting peacefully.

i will get another positive contribution with this comment

As a participant, I am not a tester.

Hope to comeback CM after this round.

omg NeroZein mentioned

Masters Masters Everywhere.

I think "note the unusual time!" should be bold and large font like

note the unusual time!

pwned orz!

Oh,this Penchicks are so cute!

As a tester, did I come late? I kept asking Penchick for the delicious feast and almost forgot the time for this round.

Finally, a plush toys photo session in round announcement <3 Thanks, guys!

Penchick

I'm back :)

The way right penchick is saying Good Luck

Very cute!

what are penchicks?

So many people registering for this contest! Hope everyone +ve rating!

very good unusual time, very scary interactive problem, like from porcelain

NO way C is a real problem

This is true SpeedForces.

i choked really hard today. C is the worst C i ever met in a div 2 too

i just spent 30 minutes searching for a mistake just to discover that i wrote cerr instead of cout

is D a graph problem?

edit : can you give some hints

plz provide enough test cases

What is the solution for odd in C ?

Thank you very much for the contest.

what was the distribution technique for question 3rd... I thought of pairing in 2 because their difference will be 1 which is a perfect square but for odd N, i paired index 1 10 and 26 as their difference is also perfect sqaure.

Anyone ? whose solution got AC ? Thanks !!

Is this correct for F? I was not able to submit it due to the fucking internet

Did thought about pythagorean triplet, and still choke at problem C.

Double the pain again.

the B problem has an issue with python solution did you ever test it with python? i always get TLE

LETSGOOOO! I solved 4!

Nice contest! C was a cool problem. Thanks for the round pwned ACGN HappyPacMan maomao90 AverageDiv1Enjoyer and all testers!

I submitted E in the last 10s of the contest but unfortunately got WA.

Anybody got an idea why this got WA on pretest 23?

#include<bits/stdc++.h>

#define x first
#define y second
#define pf push_front
#define pb push_back
#define pc putchar
#define rep(i,A,B) for(int i=A;i<(int)(B);i++)
#define r0p(i,A) rep(i,0,A)
#define r1p(i,A) rep(i,1,A+1)
#define FOR() for(int _t=rd<int>();_t;_t--)
#define all(A) A.begin(),A.end()
#define mpl(A,B) A=(A+B)%mod
#define dbg(A) cerr<<#A<<": "<<A<<endl
#define sz(A) (int)(A.size())
#define re(A) cout<<A<<endl,exit(0)

using namespace std;

#define TI template <typename T> inline

TI void chmax(T &A,T B){if(A<B) A=B;}
TI void chmin(T &A,T B){if(A>B) A=B;}
TI T abs(T A){return A<0?-A:A;}
TI void rd(T &A){
	A=0;char C=getchar();bool F=0;
	while(C<'0'||C>'9') F|=(C=='-'),C=getchar();
	while(C>='0'&&C<='9') A=(A<<3)+(A<<1)+(C^48),C=getchar();
	if(F) A=-A;
}
TI void wr(T A) {
    if(A<0) pc('-'),A=-A;
    if(A>9) wr(A/10);
    pc((A%10)^48);
}

bool stt;

const int N=1e6+5;
int n,f[N],dep[N],ans[N];
vector<int>a[N];
void dfs(int i){
	// dbg(i),dbg(ceil(log2(sz(a[i]))));
	for(auto j:a[i]){
		ans[j]=dep[j]=dep[i]+1;
		dfs(j);
		chmax(ans[i],ans[j]);
	}
	double cnt=0;
	for(auto j:a[i]) cnt+=pow(0.5,ans[i]-ans[j]);
	ans[i]+=max(0.0,ceil(log2(cnt))-1);
}

bool edd;

signed main(){
//	dbg((&edd-&stt)/1024.0/1024.0);
	IO("");
	FOR(){
		rd(n);
		r1p(i,n) a[i].clear(),ans[i]=0;
		rep(i,2,n+1) rd(f[i]),a[f[i]].pb(i);
		dfs(1);
		cout<<ans[1]<<endl;
	}
	exit(0);
}

Why does cpp23, cpp20 and cpp17 give different results for these solutions??

291657006 291656787 291655971

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

typedef long long ll;
// typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>  ordered_set;
//member functions : order_of_key(k){no_of_ele < k} find_by_order(k){kth ele}

const ll M = 1e9 + 7;
const ll N = 1e7 + 1;
const ll lmax = 2e18;
const ll lmin = -2e18;
//  ... &mdash; ... 
// --------------------------------------------------------------
void minPreprocess(vector<ll> arr, ll n, pair<ll, ll> minTable[][20])
{
    for (ll i = 0; i < n; i++)
        minTable[i][0] = {arr[i], i};
    for (ll j = 1; (1 << j) <= n; j++)
    {
        for (ll i = 0; (i + (1 << j) &mdash; 1) < n; i++)
        {
            if (minTable[i][j &mdash; 1].first < minTable[i + (1 << (j &mdash; 1))][j &mdash; 1].first)
                minTable[i][j] = minTable[i][j &mdash; 1];
            else
                minTable[i][j] = minTable[i + (1 << (j &mdash; 1))][j &mdash; 1];
        }
    }
}
pair<ll, ll> minQuery(ll L, ll R, pair<ll, ll> minTable[][20])
{
    ll j = (ll)log2(R &mdash; L + 1);
    if (minTable[L][j].first <= minTable[R &mdash; (1 << j) + 1][j].first)
        return minTable[L][j];
    else
        return minTable[R &mdash; (1 << j) + 1][j];
}

void dfs(ll node, vector<ll> adj[], vector<bool> &vis, vector<ll> &indexes) {
    // cout << node << ' ';
    vis[node] = true;
    indexes.push_back(node);
    for (auto it: adj[node]) {
        if(vis[it])
            continue;
        dfs(it, adj, vis, indexes);
    }
}
// --------------------------------------------------------------
void solve() {
    ll t = 1;
    cin >> t;
    ll count = 0;
    srand(time(0));
    while (t--) {
        count++;
        ll n; cin >> n;
        vector<ll> a(n);
        vector<pair<ll, ll>> prefix_max(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (i != 0) {
                if (prefix_max[i &mdash; 1].first <= a[i])
                    prefix_max[i] = {a[i], i};
                else prefix_max[i] = prefix_max[i &mdash; 1];
            }
            else prefix_max[i] = {a[i], i};
        }
        vector<ll> adj[n];
        pair<ll, ll> minTable[n][20];
        minPreprocess(a, n, minTable);
        vector<bool> vis(n, 0);
        vector<ll> ans(n);
        for (int i = n &mdash; 1; i >= 0; i--) {
            if (vis[i]) {
                continue;
            }
            ll x = a[i], ind = i;
            while(!vis[ind]) {
                vis[ind] = true;
                // go backward first
                ll new_x = prefix_max[ind].first, new_ind = prefix_max[ind].second;
                if(x != new_x) {
                    adj[ind].push_back(new_ind);
                    adj[new_ind].push_back(ind);
                }
                x = new_x;
                ind = new_ind;
                vis[ind] = true;
                // then go forward to find max ans
                auto p = minQuery(ind + 1, n &mdash; 1, minTable);
                pair<ll, ll> z = p;
                ll low = ind + 1, high = n &mdash; 1;
                while(high >= low) {
                    ll mid = low + (high &mdash; low) / 2;
                    auto zz = minQuery(mid, high, minTable);
                    if(zz.first < x) {
                        low = mid + 1;
                        if(z.second < zz.second)
                            z = zz;
                    } else {
                        high = mid &mdash; 1;
                    }
                }
                p = z;
                if (x > p.first) {
                    adj[ind].push_back(p.second);
                    adj[p.second].push_back(ind);
                } else break;
                x = p.first;
                ind = p.second;
            }
        }
        vector<bool> vis1(n, 0);
        for (int i = 0; i < n; i++) {
            if(vis1[i])
                continue;
            vector<ll> indexes;
            // cout << "x: ";
            dfs(i, adj, vis1, indexes);
            // cout << '\n';
            ll max_ele = a[indexes[0]];
            for(auto it: indexes)
                max_ele = max(max_ele, a[it]);
            for(auto it: indexes)
                ans[it] = max_ele;
        }
        for(auto it: ans)
            cout << it << ' ';
        cout << '\n';
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("bunny_hopscotch_input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    solve();
    return 0;
}

nvm, overkilled it, realising it now that it could've been solved in a much more easier manner T_T

I really thought I would end up screwing up this round because I spent way too long on B, but I pulled off C and D quickly enough :D

Did anyone else get Runtime error pretest 61 on E? Sys tests aren't happening and the suspense is killing me T-T

My solution:

[D]

Observation1: note the maximum value as mx, and the number to the right of mx will definitely reach mx.

Observation2: if a[i]>min(mxpos,n), all a[i,...n] can reach mx.

So we can maintain a variable pos and continuously execute the following process:

pos=posmx initially.

• find min i (1<=i<pos) such that a[i]>min(a[pos,...,n])

• update pos:=i, or break if no such i

So we found a suffix that can reach mx. Then recursively solve the sub-problem.

[E]

Consider reverse operation: add nodes from the given tree to make it a perfect binary tree.

DP. Note dp[x] as the minimum depth at which subtree x becomes a perfect binary tree.

Observing the process of adding nodes (from leaves to roots) is actually a classic Huffman tree.

So we can use greed+priority queue to process dp [son[x][i]] to obtain dp[x].

Great problem C, really like it! Thanks for the round :)

Why is there such an important change in E so much later into the contest??? I was already working on the solution according to the problem statement by then, trying to write this complicated re-rooting dp code, and after submitting towards the end of the contest notice this change. How is this fair?? Please make this contest unrated.

D can be solved with dsu. For each point, merge it with the point to the left of this point and with the highest height, and also merge it with the point to the right that is farthest away from it and with a height smaller than it. The answer corresponding to the set is maintained while merging. It can be shown that this merging is optimal.

Is there any reason for the memory limit to be smaller than the size of the stack for max N in python? I had a very inelegant solution to D that failed due to stack not fitting the memory.

C and D were interesting

All problems here are bangers!! E is my favorite, but F is cool as well

comeback CM now (probably)

Good Problems..

How is it that suddenly 2000+ people solved C problem in the last 20-30 mins? Hope the cheaters are found and removed!!

This was a really fun contest, with lots of interesting problems!

Will I get back to 1900 after rollback?

https://codeforces.net/contest/2031/submission/291676661

Can anyone let me know why my solution for B is wrong? I cannot find any edge case for this.

Please let me know why my solution is wrong, thank you very much

So many new accounts on top positions :(. One has to improve if they want to simply keep their rating (otherwise they will be in an equilibrium rating lower than their “true” rating. Maybe this is not a problem if the amount of Smurfs is constant between contests, but I feel like this one has quite a lot)

Making $$$2 \le k \le n$$$ i.e., asking subsequence of length atleast $$$2$$$ will make the problem $$$F$$$ as troll D2C ig ;)

nice round

only flaw is the statement of E is a bit misleading, I assumed the usual definition of isomorphic and got stuck (it seems that in such meaning it can be solved with tree decomposition with matrices, but I'm unable to make it clear)

my rating still did increase tho

sto sto orz orz

Good contest, thanks.

Also the problem F is amazing.

Congrats to programpiggy for finally reaching M!