Hello, We invite you to the contest "Replay of ICT Division presents – 7th DRMC International Tech Carnival 2024 Programming Contest [Onsite]" on May 23, at 14:00 (UTC)(Tomorrow)
Contest link: https://toph.co/c/kldhdrk-r
Setter & tester: Dhruba10414,Nafis.Shahriar, arnab_baishnab, ashraful9194 & me.
See you on the Leaderboard. GLHF.
Reminder: only 1 hour left to start
A
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int N, K, L;
int dp[205][205][2050];
int add(int x, int y) {
x += y;
while(x >= MOD) x -= MOD;
if(x < 0) x += MOD;
return x;
}
int mul(int x, int y) {
return (1LL * x * y) % MOD;
}
int dist[1000], color[1000];
int brute(int pos) {
if(pos == N) {
memset(dist, -1, sizeof(dist));
for(int i = 0; i < N; i++) {
if(dist[color[i]] == -1 or abs(dist[color[i]] - i) <= L) {
dist[color[i]] = i;
}
else {
return 0;
}
}
return 1;
}
int ret = 0;
for(int i = 0; i < K; i++) {
color[pos] = i;
ret = add(ret, brute(pos + 1));
}
return ret;
}
int solve(int pos, int colorsLeft, int lastLColors) {
lastLColors = lastLColors & ((1 << (L + 1)) - 1);
// cout << pos << ' ' << colorsLeft << ' ' << lastLColors << endl;
if(pos == N) return 1;
int &ret = dp[pos][colorsLeft][lastLColors];
if(ret != -1) return ret;
ret = 0;
if(colorsLeft) ret = add(ret, mul(colorsLeft, solve(pos + 1, colorsLeft - 1, (lastLColors | 1) << 1)));
for(int i = 1; i <= L; i++) {
if(lastLColors & (1 << i)) {
ret = add(ret, solve(pos + 1, colorsLeft, ((lastLColors ^ (1 << i)) | 1) << 1));
}
}
return ret;
}
void testCase() {
cin >> N >> L >> K;
// L = min(L, N - 1);
for(int i = 0; i <= N; i++) {
for(int j = 0; j <= K; j++) {
for(int l = 0; l <= (1 << L + 1); l++) {
dp[i][j][l] = -1;
}
}
}
int result = solve(0, K, 0);
cout << result << endl;
// memset(dist, -1, sizeof(dist));
// memset(color, -1, sizeof(color));
// cout << brute(0) << endl;
}
void file(){
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
}
int main() {
// file();
int t, cs = 0;
cin >> t;
while(t--) {
cout << "Case #" << ++cs << ": ";
testCase();
}
}
B - Using Tree-rooting technique
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define dhoom3 ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
const int N= 5e5+5;
vector<ll> adj[N];
ll n,k;
ll g_node[N][2],g_dist[N][2];
ll r_node[N][2],r_dist[N][2];
string s;
void dfs(ll u,ll par=-1){
for(auto it: adj[u]){
if(it==par) continue;
dfs(it,u);
if(g_dist[it][0]+1<g_dist[u][0]){
//
g_node[u][1]=g_node[u][0],g_dist[u][1]= g_dist[u][0];
g_dist[u][0]= g_dist[it][0]+1;
g_node[u][0]= g_node[it][0];
//
if(g_dist[it][1]+1<g_dist[u][1]){
g_dist[u][1]= g_dist[it][1]+1;
g_node[u][1]= g_node[it][1];
}
}
else if(g_dist[it][0]+1<g_dist[u][1]){
//
g_dist[u][1]= g_dist[it][0]+1;
g_node[u][1]= g_node[it][0];
}
if(r_dist[it][0]+1<r_dist[u][0]){
//
r_node[u][1]=r_node[u][0],r_dist[u][1]= r_dist[u][0];
r_dist[u][0]= r_dist[it][0]+1;
r_node[u][0]= r_node[it][0];
//
if(r_dist[it][1]+1<r_dist[u][1]){
r_dist[u][1]= r_dist[it][1]+1;
r_node[u][1]= r_node[it][1];
}
}
else if(r_dist[it][0]+1<r_dist[u][1]){
//
r_dist[u][1]= r_dist[it][0]+1;
r_node[u][1]= r_node[it][0];
}
}
if(s[u]=='G'){
g_node[u][1]=g_node[u][0],g_dist[u][1]= g_dist[u][0];
g_node[u][0]=u,g_dist[u][0]=0;
}
else{
//if(u==4) cout<<"f"<<endl;
r_node[u][1]=r_node[u][0],r_dist[u][1]= r_dist[u][0];
r_node[u][0]=u,r_dist[u][0]=0;
}
}
void solve(ll u,ll par=-1){
for(auto it: adj[u]){
if(it==par) continue;
vector<pair<ll,ll>> vp;
vp.pb({g_dist[u][0]+1,g_node[u][0]});
vp.pb({g_dist[u][1]+1,g_node[u][1]});
vp.pb({g_dist[it][0],g_node[it][0]});
vp.pb({g_dist[it][1],g_node[it][1]});
sort(all(vp));
ll ps=0, last=-1;
for(ll i=0;i<4;i++){
if(vp[i].second!=last) {last=g_node[it][ps]= vp[i].second, g_dist[it][ps]= vp[i].first; ++ps;}
if(ps==2) break;
}
vp.clear();
vp.pb({r_dist[u][0]+1,r_node[u][0]});
vp.pb({r_dist[u][1]+1,r_node[u][1]});
vp.pb({r_dist[it][0],r_node[it][0]});
vp.pb({r_dist[it][1],r_node[it][1]});
sort(all(vp));
ps=0, last=-1;
for(ll i=0;i<4;i++){
if(vp[i].second!=last) {last=r_node[it][ps]= vp[i].second, r_dist[it][ps]= vp[i].first; ++ps;}
if(ps==2) break;
}
solve(it,u);
}
}
int main(){
dhoom3;
int Test=1;
while(Test--){
//
for(ll i=1;i<=N;i++){
g_dist[i][0]=g_dist[i][1]= 1e9;
r_dist[i][0]=r_dist[i][1]= 1e9;
}
cin>>n>>k;
for(ll i=2;i<=n;i++){
ll x; cin>>x;
adj[x].pb(i); adj[i].pb(x);
}
cin>>s;
s="#"+s;
if(n==1){
cout<<-1<<endl;
continue;
}
ll rc=0,gc=0;
for(ll i=1;i<=n;i++){
rc+= s[i]=='R';
gc+= (s[i]=='G');
}
ll mn= min(rc,gc);
if(mn<=1){
cout<<mn<<endl;
return 0;
}
dfs(1);
solve(1);
ll res=0;
for(ll i=1;i<=n;i++){
if(s[i]=='G' && g_dist[i][1]>k) ++res;
if(s[i]=='R' && r_dist[i][1]>k) ++res;
// cout<<i<<endl;
// cout<<r_node[i][0]<<' '<<r_dist[i][0]<<endl;
// cout<<r_node[i][1]<<' '<<r_dist[i][1]<<endl;
}
cout<<res<<endl;
}
return 0;
}
/*
7 2
1 1 2 2 3 3
GGRRGRG
ans: 1
7 2
1 1 2 2 3 3
GGGGGGG
ans: 0
7 2
1 1 2 2 3 3
GGGRGGG
ans: 1
7 80
1 1 3 4 1 6
GGGGRGG
ans: 1
7 80
1 1 3 4 1 6
RRRRGRR
*/
B - Centroid decomposition
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define dhoom3 ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
const int N= 5e5+5;
const int MX = 5e5+5;
set<int> adj[N];
vector<int> nTree[N];
int par[N],sub[N];
int ans[N],scr[N];
int node1[N],node2[N];
vector <pair <int, int> > graph[MX];
ll wei[MX];
const int L = 17;
int anc[MX][L];
int depth[MX];
int parent[MX];
int n,k;
string s;
int LCA(int a, int b) {
if (depth[a] < depth[b]) {
int c = b;
b = a;
a = c;
}
int dist = depth[a] - depth[b];
while (dist > 0) {
for(ll i=0;i<L;i++) {
if (dist & 1 << i) {
a = anc[a][i];
dist -= 1 << i;
}
}
}
if (a == b) return a;
for(ll j=(L)-1;j>=0;j--) {
if (anc[a][j] != -1 && anc[a][j] != anc[b][j]) {
a = anc[a][j]; b = anc[b][j];
}
}
return parent[a];
}
void parDFS(int v, int p, int d) {
parent[v] = p; depth[v] = d;
for(ll i=0;i<(int)(graph[v]).size();i++) {
int nxt = graph[v][i].first;
if (nxt == p) continue;
wei[nxt] = wei[v] + graph[v][i].second;
parDFS(nxt, v, d+1);
}
}
void preprocess() {
parDFS(1, -1, 0);
for(ll i=0;i<N;i++) for(ll j=0;j<L;j++) anc[i][j] = -1;
for(ll i=0;i<N;i++) anc[i][0] = parent[i];
for(ll j=1;j<L;j++) {
for(ll i=0;i<N;i++) {
if (anc[i][j-1] != -1) {
anc[i][j] = anc[anc[i][j-1]][j-1];
}
}
}
}
int find_subTreeSize(int node,int p){
sub[node]=1;
for(int child: adj[node]){
if(child!=p){
sub[node] += find_subTreeSize(child,node);
}
}
return sub[node];
}
int find_centroid(int node,int p,int n){
for(int child: adj[node]){
if(child!=p && sub[child]>n/2){
return find_centroid(child,node,n);
}
}
return node;
}
int decompose(int node,int p){
int SubTreeSize = find_subTreeSize(node,p);
int centroid = find_centroid(node,p,SubTreeSize);
//cout<<"Root: "<<node<<" SubTreeSize: "<<SubTreeSize<<" Centroid: "<<centroid<<endl;
if(p==-1) p=centroid;
par[centroid]=p;
for(int child: adj[centroid]){
adj[child].erase(centroid);
int val= decompose(child,centroid);
nTree[centroid].pb(val);
}
return centroid;
}
int dist(int a,int b){
return wei[a]+wei[b]-2*wei[LCA(a,b)];
}
///
void update(int node,int p){
while(1){
int dd= dist(p,node);
if(ans[p]==1e9) ans[p]= dd, node1[p]= node;
else{
if(ans[p]>=dd) {
scr[p]= ans[p], ans[p]= dd;
node2[p]= node1[p];
node1[p]= node;
}
else{
if(dd<scr[p]){
scr[p]= dd;
node2[p]= node;
}
}
}
if(par[p]==p) break;
p=par[p];
}
}
ll nn=-1;
pair<int,int> query1(int node){
int p=node,answer=1e9, tar=-1;
while(1){
int cur= ans[p]+dist(node,p);
//answer=min(answer,cur);
if(cur<answer){
answer= cur;
tar= node1[p];
}
if(p==par[p]) break;
p=par[p];
}
return {answer,tar};
}
pair<int,int> query2(int node){
int p=node,answer=1e9, tar=-1;
while(1){
int cur= ans[p]+dist(node,p);
int cur2= scr[p]+dist(node,p);
if(node1[p]!=nn && cur<answer){
answer= cur;
tar= node1[p];
}
else if(node2[p]!=nn && cur2<answer){
answer= cur2;
tar= node2[p];
}
if(p==par[p]) break;
p=par[p];
}
return {answer,tar};
}
int main(){
dhoom3;
int Test=1;
//cin>>Test;
while(Test--){
cin>>n>>k;
for(ll i=2;i<=n;i++){
ll x; cin>>x;
adj[x].insert(i); adj[i].insert(x);
graph[x].pb({i, 1});
graph[i].pb({x, 1});
}
cin>>s;
if(n==1){
cout<<-1<<endl;
return 0;
}
ll rc=0,gc=0;
for(ll i=0;i<n;i++){
rc+= s[i]=='R';
gc+= (s[i]=='G');
}
ll mn= min(rc,gc);
if(mn<=1){
cout<<mn<<endl;
return 0;
}
wei[1]=0;
preprocess();
decompose(1,-1);
ll res=0;
//Red
for(ll i=1;i<=n;i++) ans[i]=scr[i]=1e9;
for(ll i=1;i<=n;i++){
if(s[i-1]=='R') update(i,i);
}
for(ll i=1;i<=n;i++){
pair<int,int> pp = query1(i);
//cout<<pp.first<<' '<<pp.second<<endl;
nn= pp.second;
//cout<<nn<<endl;
pp = query2(i);
//cout<<pp.first<<' '<<pp.second<<endl<<endl;
if(s[i-1]=='R' && pp.first>k) ++res;
}
//cout<<res<<endl;
//Green
for(ll i=1;i<=n;i++) ans[i]=scr[i]=1e9;
for(ll i=1;i<=n;i++){
if(s[i-1]=='G') update(i,i);
}
for(ll i=1;i<=n;i++){
pair<int,int> pp = query1(i);
//cout<<pp.first<<' '<<pp.second<<endl;
nn= pp.second;
//cout<<nn<<endl;
pp = query2(i);
//cout<<pp.first<<' '<<pp.second<<endl<<endl;
if(s[i-1]=='G' && pp.first>k) ++res;
}
cout<<res<<endl;
}
return 0;
}
/*
7 2
1 1 2 2 3 3
GGRRGRG
ans: 1
7 2
1 1 2 2 3 3
GGGGGGG
ans: 0
7 2
1 1 2 2 3 3
GGGRGGG
ans: 1
*/
D
#include "bits/stdc++.h"
#define fastIO std::ios::sync_with_stdio(0);std::cin.tie(0)
#define ll long long int
#define flush fflush(stdout)
#define bl printf("\n")
// #define int ll
using pii = std::pair<int,int>;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int mxN = 500005, inf = 1000000005;
signed main() {
// fastIO;
int testCases=1;
// scanf("%lld",&testCases);
// std::cin >> testCases;
for (int T = 1; T <= testCases; T++) {
int N;
scanf("%d", &N);
int out[N + 1] = {0};
std::vector<int> g[N + 1];
for (int i = 1, x; i <= N; i++) {
scanf("%d", &x);
out[i] = x;
for (int j = 0, y; j < x; j++) {
scanf("%d", &y);
g[y].push_back(i);
}
}
std::queue<int> q;
for (int i = 1; i <= N; i++) {
if (out[i] == 0) {
q.push(i);
}
}
int ans = 0;
while ((int)q.size()) {
int nw = q.front();
q.pop();
ans++;
for (auto fore : g[nw]) {
out[fore]--;
if (out[fore] == 0) {
q.push(fore);
}
}
}
printf("%d\n", ans);
}
return 0;
}
/*
*/
C
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
const ll N= 1e5+5, mod= 1e9+7;
int main(){
FastIO;
ll T=1, cs=0; cin>>T;
while(T--){
ll n,k; cin>>n>>k;
string s; cin>>s;
bool vis[30];
ll ans= 1e18;
for(ll i=0;i<26;i++){
ll sum=0;
bool ckk=1;
for(ll j=0;j<n;j++){
ll cur= s[j]-'a';
ll opr=0;
bool chk=0;
memset(vis,0,sizeof(vis));
while(!vis[cur]){
vis[cur]=1;
if(cur==i) { chk=1; break; }
opr++;
cur= (cur+k)%26;
}
if(!chk) ckk=0;
else sum+= opr;
}
if(ckk){
ans=min(ans,sum);
//cout<<i<<' '<<sum<<endl;
}
}
if(ans==1e18) cout<<-1<<endl;
else cout<<ans<<endl;
}
return 0;
}
/*
3
5 3
acfdr
5 26
acfdr
5 7
acfdr
ans:
22
-1
31
Explanation:
1: matched with 'c' in 22 opreation
2: no way to match
3: matched with 'b' in 31 opreations
*/
E
//for double/floating number don't use cout, please use printf.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define pii 3.141592653589793
#define pb push_back
const int N = 3e5+1;
const int M=100000;
const ll mxn =1e18;
const long long mod = 1e9+7;
#define FAST ios::sync_with_stdio(false);cin.tie(NULL);
#define FF fflush(stdout);
#define lcm(a,b) (a*b)/__gcd(a,b)
#define F first
#define S second
#define mp make_pair
#define nl '\n'
#define vi vector<int>
#define forr(i,n,a) for(int i=0;i<n;i+=a)
set<int>::iterator it,itt;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<ll,ll>, null_type,less<pair<ll,ll> >, rb_tree_tag,tree_order_statistics_node_update>
typedef tree<int, null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> ordered_setl;
typedef tree<int, null_type,greater<int >, rb_tree_tag,tree_order_statistics_node_update> ordered_set2;
#define infinity 1<<30 //2^30
void solve()
{
ll m,n,c,i,a[26]={0},b[26]={0},j;
string x,y;
cin>>m>>n>>c;
cin>>x>>y;
for(i=0;i<m;i++)a[(x[i]-'a') ]++;
for(i=0;i<n;i++)b[(y[i]-'a')]++;
ll ans=0;
for(i=0;i<26;i++)
{
if((a[i] && b[i]==0) || (b[i]&& a[i]==0))
{
cout<<"impossible\n";
return;
}
if(a[i] && b[i])
{
int w=min(a[i],b[i])-1+c;
int p=2*c;
int q=max(a[i],b[i])-min(a[i],b[i]);
ans+=min(w,min(p,q));
}
}
cout<<ans<<endl;
}
int main()
{
FAST
int tc=1,cs=0;
cin>>tc;
while(tc--)
{
//cout<<"Case #"<<(++cs)<<": ";
solve();
}
}
F
/**Failing is always better than never trying*/
/**Winners never quit and quitters never win.*/
#include <bits/stdc++.h>
using namespace std;
// Define your policy based data structure here
#define int long long
#define pb push_back
#define pii pair<int,int>
#define endl '\n'
const int N=5e5+5;
int pref[N][35],n,q,k,a[N];
int ans[N];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// #ifndef ONLINE_JUDGE
// freopen("inp.txt","r",stdin);
// freopen("out.txt","w",stdout);
// #endif
// fstream cin("out.txt",ios::in);///i have to create the input file
// fstream cout("ans.txt",ios::out);///auto create output file
cin>>n>>q;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=0; i<30; i++)
{
for(int j=1; j<=n; j++)
{
pref[j][i]=0;
int x=(a[j]>>i)&1;
if(!x) continue;
pref[j][i]=pref[j-1][i]+1;
}
}
for(int i=1; i<=n; i++)
{
vector<pii>v;
for(int j=0; j<30; j++)
{
if(!pref[i][j]) continue;
v.pb(make_pair(pref[i][j],(1LL<<j)));
}
sort(v.rbegin(),v.rend());
int sz=v.size();
int now=0;
for(int j=0; j<sz; j++)
{
int len=v[j].first;
int val=v[j].second;
now|=val;
ans[len]=max(ans[len],now);
}
}
int mx=0;
for(int i=n; i>=1; i--)
{
mx=max(mx,ans[i]);
ans[i]=mx;
}
while(q--)
{
cin>>k;
cout<<ans[k]<<endl;
}
}
///Debug tips : Look for corner logic that is not handled.
Editorial?
I will add sample solution, soon. We will try for an editorial. But can't give guarantee.
upd1: sample soln added.