Codeforces Round 1106 (Div. 2)

3 месяца назад, скрыть # |

Is it NP-complete?

→ Ответить

All_rounder

3 месяца назад, скрыть # |

As an All_rounder, I carefully decided to start with Problem A. Peak strategy.

→ Ответить

Escapisst

3 месяца назад, скрыть # |

← Rev. 2 →

+13

as a guy who decided to not test this round i hope it was a good decision.

UPD: also, as a friend i won't talk to Friendiks ever after unless I become master today

→ Ответить

3 месяца назад, скрыть # |

Wow such a big difficult gap.

→ Ответить

Helloworld_4207

3 месяца назад, скрыть # |

why was yesterdays contest creators fixated on XOR!!

→ Ответить

The_Flying_Dutch_Man

3 месяца назад, скрыть # ^ |

Same reason as why today the setters were fixated on GCD (number theory), as well as graphs! Overall, it was a great and balanced contest. Problem C is a great problem.

→ Ответить

Ver_Nick

3 месяца назад, скрыть # ^ |

C < B imho

→ Ответить

lushfeast

3 месяца назад, скрыть # ^ |

no what?

→ Ответить

MikhagnusTalsen

3 месяца назад, скрыть # |

I hope this one isn't as hard as yesterday's. ~ fellow newbie

→ Ответить

3 месяца назад, скрыть # |

I hope to solve A to C (and maybe D)

→ Ответить

zap2727

3 месяца назад, скрыть # |

How can I hack during the contest?

→ Ответить

priyansh2006

3 месяца назад, скрыть # |

+17

such a fun contest after a long time honestly

→ Ответить

Astroflexx

3 месяца назад, скрыть # |

← Rev. 2 →

Loved the number theory problems $$$B$$$ and $$$D$$$.

Good problems, thanks for the round.

→ Ответить

Gmaeknight999

3 месяца назад, скрыть # |

Love the themes for the questions!

→ Ответить

Rynical

3 месяца назад, скрыть # |

One of the most beautiful contest I ever gave

Seriously, like the dopamine hit when I got D was like kisses.

This might just be my opinion, cause I love math more than coding.

→ Ответить

_biniyam

3 месяца назад, скрыть # |

Good problems

→ Ответить

wrusb

3 месяца назад, скрыть # |

Love NumberTheoryForces!

→ Ответить

gevak

3 месяца назад, скрыть # |

-8

Why to hell CodeForces website soooo non-responsive??? Submitting a solution often takes several minutes. mirror.codeforces.com is completly dead, m1/m2/m3.codeforeces.com are also dead. Failed to submit E on last minutes :(

→ Ответить

__dopamIne

3 месяца назад, скрыть # |

problem D best(as a math lover). but esay.

→ Ответить

AksLolCoding

3 месяца назад, скрыть # |

+26

Best div2 in a while imo

→ Ответить

Misaka16172

3 месяца назад, скрыть # |

Great contest, reached CM. Lets gooooo

→ Ответить

greateric

3 месяца назад, скрыть # |

How it feels knowing that you can throw this round and suffer no consequences

And then proceed to get ABCDE and think I do amazing and then see perf of 2070 :sob:

→ Ответить

nEwBie_c0der

3 месяца назад, скрыть # |

Me after solving B.

→ Ответить

__dopamIne

3 месяца назад, скрыть # |

problem D best(as a math lover). but esay.

→ Ответить

wuyukai0403

3 месяца назад, скрыть # |

Wow fast system test :)

→ Ответить

3 месяца назад, скрыть # |

In problem C,

"The houses in the village are connected by bidirectional paths"

So, if the graph is 1---2---3 then houses 1 and 3 forms a guild, right? (v=2;h=1)

→ Ответить

0xdaksh.12

3 месяца назад, скрыть # ^ |

{3} is guild, not {1, 3}

→ Ответить

Victor0902

3 месяца назад, скрыть # ^ |

No, the problem specifies "houses in the subtree".

→ Ответить

3 месяца назад, скрыть # ^ |

Carefully check the problem description again, and you'll see that a guild only contains nodes in the subtree of node $$$v$$$, which means the guild is $$$3$$$ instead of $$$1,3$$$.

→ Ответить

3 месяца назад, скрыть # ^ |

I understand that from the picture but since the graph is bidirectional, we have no sense of direction

So, when we build a subtree with h=1;v=2 how can we include 3 but exclude 1?

→ Ответить

3 месяца назад, скрыть # ^ |

The graph of houses and paths represents a rooted∗ tree†, rooted at vertex $$$1$$$, where the town hall is located.

Check the description again, the tree is rooted at $$$1$$$.

→ Ответить

3 месяца назад, скрыть # ^ |

← Rev. 5 →

Since the graph is bidirectional, it will have atleast 1 loop (assuming $$$n \ge 2$$$)

So, if we define a tree with root 1, it's contradictory (as loops not allowed in tree)

EDIT: nvm, just realised that "bidirectional paths" is part of storyline and has nothing to do with the problem itself...

→ Ответить

MikhagnusTalsen

3 месяца назад, скрыть # ^ |

its a tree !

only the children of a node can form a guild.

ancestors can not.

→ Ответить

__dopamIne

3 месяца назад, скрыть # |

problem D best(as a math lover). but esay.

→ Ответить

3 месяца назад, скрыть # |

I submitted F at 01:58:55, 65 seconds before the contest ended, and it got an AC a minute after the contest ended :)

→ Ответить

Leokud

3 месяца назад, скрыть # |

oh yes Mathforces and Guessforces

→ Ответить

3 месяца назад, скрыть # ^ |

-7

and also bitforces(yesterday's round)

→ Ответить

lushfeast

3 месяца назад, скрыть # ^ |

bro what, c was tree dp

→ Ответить

3 месяца назад, скрыть # |

Why did nobody hack?

Is it unhackable?

→ Ответить

Igor_Parfenov

3 месяца назад, скрыть # |

What is the solution to problem E?

→ Ответить

3 месяца назад, скрыть # ^ |

E is just pure DP. Consider $$$dp_{k,i,j}$$$ means the maximum number of the minimum wrong answers in $$$[1,k]$$$ among all F segments $$$[l,k]$$$ where the minimum wrong answers in $$$[1,k]$$$ among all F segments $$$[l,r]$$$ is $$$i$$$ and the actual number of F's in $$$[1,k]$$$ is $$$j$$$.

If the $$$k+1$$$-th cake is F, we have $$$dp_{k,i,j} \to dp_{k+1,\min(i+1,dp_{k,i,j}),j+1}$$$;
If the $$$k+1$$$-th cake is T, we have $$$\min(dp_{k,i,j}+1,j) \to dp_{k+1,\min(i,dp_{k,i,j}+1,j),j}$$$.

Total $$$O(\sum n^3)$$$.

→ Ответить

3 месяца назад, скрыть # ^ |

My code:

/*
dp[k][i][j]:在 1~k 的前缀总共出现 j 个 F 且任意 1~k 之间的 F 线段在 1~k 至少错 i 个时，任意 l~k 的 F 线段至少错的数量
若 k+1 填 F，则 dp[k][i][j] -> dp[k+1][min(i+1,dp[k][i][j])][j+1]
若 k+1 填 T，则 min(dp[k][i][j]+1,j) -> dp[k+1][min(i,dp[k][i][j]+1,j)][j]
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mx(a,b) a=max(a,b)
int t,n,ans,dp[2][509][509];
char c;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n,ans=0;
		for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) dp[0][i][j]=-0x3f3f3f3f;
		dp[0][0][0]=0;
		for(int k=1,u=1,v=0;k<=n;++k,u=!u,v=!v){
			cin>>c;
			for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) dp[u][i][j]=-0x3f3f3f3f;
			if(c!='T') for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) if(dp[v][i][j]>=0) mx(dp[u][min(i+1,dp[v][i][j])][j+1],dp[v][i][j]);
			if(c!='F') for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) if(dp[v][i][j]>=0) mx(dp[u][min(i,min(dp[v][i][j]+1,j))][j],min(dp[v][i][j]+1,j));
		}
		for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) if(dp[n&1][i][j]>=0) ans=max(ans,i);
		cout<<ans<<"\n";
	}
	return 0;
}

→ Ответить

gevak

3 месяца назад, скрыть # ^ |

Image all N's are already replaced.
When 2nd player selects sub-segment, he tries to take max F's and min T's, specifically max(F — T) on sub-segment.
And the answer is {total amount of F's} — {max [amount of F's — amount of T's] among all sub-segments}.

Solution is O(n^3) DP. State is:
i: position which we consider (all to the left (i.e. prefix) is already processed).
f: amount of F's in processed prefix.
d: current balance of F's and T's (maximal cnt(F) — cnt(T) among suffixes of processed prefix).
Value of DP is best (minimal) balance.
Transitions are:
F: (i + 1, f + 1, d + 1)
T: (i + 1, f, max(0, d — 1))
2nd players uses new d to maximize best d (i.e. the DP value).
Final answer is amount of F's — best balance.
https://codeforces.me/contest/2238/submission/380519271

→ Ответить

CoolCatPro

3 месяца назад, скрыть # |

+12

As neither a tester nor a participant, I can say after the round that C was a really good and interesting problem.

→ Ответить

lushfeast

3 месяца назад, скрыть # |

Can someone explain F solution.

→ Ответить

3 месяца назад, скрыть # ^ |

First, you need to notice that you cannot fire two students if one of them is subortinate to the other one, unless you fire both of them in the same day, which is not optimal.

Now, all the students who has never been fired forms a tree.

If a student gets fired in the $$$(n-i)$$$-th day, the number of students hired in his subtree in the $$$n$$$-th day would be $$$2^i-1$$$.

Count the students hired in the last day, and you will find that the sum of $$$2^i-1$$$ among all fired students equals to $$$k-(s-1)$$$, where $$$s$$$ is the number of fired students.

This means, the sum of $$$2^i$$$ is $$$k+1$$$.

Now, you have to minimize $$$s$$$, so you should choose the biggest possible $$$2^i(0 \le i \le n-1)$$$ for each student.

The answer is $$$C(s-1) \times f$$$, where $$$C(x)$$$ is the number of different possible trees with $$$x$$$ nodes, which is the Catalan sequence, and $$$f$$$ is the number of different permutations of all the $$$2^i$$$ you need.

→ Ответить

3 месяца назад, скрыть # ^ |

← Rev. 2 →

Upd 1:Oops, found a mistake in the note inside my code. Fixed.

My code:

/*
第 n-i 轮结束时解雇一个人会导致最终这棵子树大小为 2^i-1
总共解雇 s 个人的话，根附近始终未解雇的有 s-1 人
于是 sum i=1~s(x[i])=k-s+1
其中 x[i]=2 的不超过 n-1 次幂 -1
令 y[i] in 2^0,2^1,...,2^(n-1)
首先找到一种最优策略
如果有两个相同的 2^i，可以变为 2^(i+1)，不优
于是除了 2^(n-1)，每个 2^i 至多取一次
所以一定尽可能用大的来凑
先统计总共要解雇 s 个人，ans=C(s-1)*S
如果有 a[i] 个 2^i(a[0],a[1],...,a[n-2] 都为 0 或 1)
则 S=s!/a[n-1]!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7,R=1e9+5;
int t,n,k;
ll s,ans,o[29],f[400009],g[400009];
inline ll w(ll a,ll b){return !b?1:b==1?a:b&1?w(a*a%mod,b>>1)*a%mod:w(a*a%mod,b>>1);}
inline ll C(int x){return f[2*x]*g[x]%mod*g[x+1]%mod;}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	f[0]=1;
	for(int i=1;i<=400005;++i) f[i]=f[i-1]*i%mod;
	g[400005]=w(f[400005],R);
	for(int i=400005;i;--i) g[i-1]=g[i]*i%mod;
	cin>>t;
	while(t--){
		cin>>n>>k,s=ans=0;
		++k,--n,n=min(n,__lg(k)),memset(o,0,sizeof(o));
		if(k==(1<<n)){cout<<"1\n";continue;}
		for(int i=n;i>=0;--i) o[i]=k>>i,s+=o[i],k&=((1<<i)-1);
		cout<<f[s]*g[o[n]]%mod*C(s-1)%mod<<"\n";
	}
	return 0;
}

→ Ответить