Hopefully no googleable problems this time

Well done! The score of problem E is only 425 pts.

Hopefully, through this competition, my name will change from brown to green.

I hope I can make ABCDE!

Yet another TOYOTA Round. Excited.

Hope to make ABCDEF

Hoping to get positive delta!

How to solve E?

What's the problem with my solution for Problem E

what's wrong ? is it the approach or the interaction??

How to solve $$$E$$$?

Sigh, solved E after the contest, just missed by 33 seconds.

E was discussed long ago on a Chinese Q&A platform (which is completely unrelated to CP and more like Quora) as a brainteaser.

https://www.zhihu.com/question/487696887

I kept getting WA on F. My idea was like :

1. For each $$$L$$$, find the farthest $$$R$$$ such that number of unique element between range $$$(L, R)$$$ doesn't exceed $$$M$$$. This can be done with two pointers

2. After that, for each interval $$$(L, R)$$$, get the sum of number of balls that can be put in the box. This can be done by using data structures that supports range sum query (such as fenwick). To count this, I will find the index of the first occurrence of a ball within the range, and then when I move $$$L$$$ forward, I update the occurrence of the next ball with $$$\text{min}(cnt_{ball}, K)$$$

I get WA on 8 test cases. Can anyone help me to spot the flaw in my idea / implementation?

Submission : 49504325

How can I do problem E?I got a WA:

#include<bits/stdc++.h>
using namespace std;
vector<int>v[10];
int main(){
	int n,m,ans=0;
	string x;
	scanf("%d",&n);
	m=ceil(log2(n));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(i&(1<<(j-1)))
				v[j].push_back(i);
	printf("%d\n",m);
	for(int i=1;i<=m;i++){
		printf("%d ",v[i].size());
		for(int j=0;j<v[i].size();j++)
			printf("%d ",v[i][j]);
		printf("\n");
	}
	printf("\n");
	fflush(stdout);
	cin>>x;
	for(int i=0;i<m;i++)
		if(x[i]=='1')
			ans+=(1<<i);
	if(ans==0)
		printf("%d\n",n);
	else
		printf("%d\n",ans);
	fflush(stdout);
	return 0;
}

There's a little bit difficult about problem E is that if $$$N$$$ is a power of $$$2$$$, we can only use $$$\log_2 N$$$ friends, instead of $$$\lfloor \log_2 N \rfloor + 1$$$.

A easy way to think this problem is to seperate with binary bits. But there may be some waste when processing $$$N = 2^x$$$.

Suppose $$$N=16$$$, we can construct:

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

But now the state 00000 is wasted. We can save it by constructing:

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

Here, the state 0000 just means 00001 in the previous version of construction.

It doesn't work when $$$N$$$ isn't a power of $$$2$$$, because we cannot determine what does the full-0 state mean then.

#include <bits/stdc++.h>
using namespace std;

int n, len, ans;
string s;

int main() {
    cin >> n;
    len = ceil(log2(n));
    cout << len << endl;
    for (int i = 0; i < len; i++) {
        vector<int> p;
        for (int j = 1; j <= n; j++)
            if (j >> i & 1)
                p.push_back(j);
        cout << p.size() << " ";
        for (int j : p) cout << j << " ";
        cout << endl;
    }
    cin >> s;
    for (int i = 0; i < len; i++)
        if (s[i] == '1')
            ans |= (1 << i);
    if (ans == 0) ans = n; /* Pay attention to this */
    cout << ans << endl;
    return 0;
}

How to solve G?

How to solve D?

Solved till E, Got to be patient and not jump on the first approach that comes to my mind, For E As at first I was making N(N+1)/2 kind of combinations, and after 4 Wa's I realised it was just 2^x combinations.

B, Does anyone know what's wrong with this? 4 WAs.

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define pb push_back
typedef long long ll;

using namespace std;


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
    string ss,s; cin >> ss;
    int ok = 1;
    for(int i = 0; i < ss.size(); i++) {
        if(i == 0) {
            s+=ss[i];
            continue;
        }
        if(ss[i] != ss[i-1]) s+=ss[i];
    }
    for(int i = 0; i < s.size(); i+=3) {
        if(s[i] != 'A') ok = 0;
    }
    for(int i = 1; i < s.size(); i+=3) {
        if(s[i] != 'B') ok = 0;
    }
    for(int i = 2; i < s.size(); i+=3) {
        if(s[i] != 'C') ok = 0;
    }
    if(ok) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

How to optimize sack + lazy segtree in G ? I thought $$$\mathcal{O}(n \log{n})$$$ would easily pass.

G is same as TTPC2019 M.

Found it after contest and the exactly same code got AC.

Is it intended that $$$O(n \space log^2n)$$$ centroid decomposition solutions receive TLE on problem G? (I was able to get AC using pragmas and some constant optimizations, but why requiring so to solve the problem?)

please help on to solve the E

Problem E was Educative. Learned something new.

may I know the reason , why you guys are not providing English editorials? I know I can translate the Japanese version , but still it will be convenient to have English editorials as we had earlier.

Can someone tell me D,i got TLE and WA too,i am not able to think of some faster approach

How to solve C?

why the below code of problem D is giving some wrong answers?( I got 61 cases passed and 6 cases wrong)

Your code here...
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mod = 998244353;
void solve() {
    int h,w,k,i,j,ans,t;
    cin>>h>>w>>k;
    vector<string> s(h);
    for(i=0;i<h;++i) cin>>s[i];
    vector<vector<pair<int,int>>> dp1(h,vector<pair<int,int>>(w,{0,w})),dp2(h,vector<pair<int,int>>(w,{0,h}));
    i=h-1;
    for(j=0;j<w;++j){
        if(s[i][j]=='x') dp2[i][j]={0,i};
        else{
            if(s[i][j]=='.') dp2[i][j].first=1;
            else dp2[i][j]={0,h};
        }
    }
    for(i=h-2;i>=0;--i){
        for(j=0;j<w;++j){
            if(s[i][j]=='x') dp2[i][j]={0,i};
            else{
                dp2[i][j]=dp2[i+1][j];
                if(s[i][j]=='.') dp2[i][j].first++;
            }
        }
    }
    j=w-1;
    for(i=0;i<h;++i){
        if(s[i][j]=='x') dp1[i][j]={0,j};
        else{
            if(s[i][j]=='.') dp1[i][j].first=1;
            else dp1[i][j]={0,h};
        }
    }
    for(j=w-2;j>=0;--j){
        for(i=0;i<h;++i){
            if(s[i][j]=='x') dp1[i][j]={0,j};
            else{
                dp1[i][j]=dp1[i][j+1];
                if(s[i][j]=='.') dp1[i][j].first++;
            }
        }
    }
    ans=INT_MAX;
    for(i=0;i<h;++i){
        for(j=0;j<=w-k;++j){
            if(dp1[i][j].second>j+k-1){
                t=dp1[i][j].first-dp1[i][j+k-1].first;
                if(s[i][j+k-1]=='.') ++t;
                ans=min(ans,t);
            }
        }
    }
    for(i=0;i<=h-k;++i){
        for(j=0;j<w;++j){
            if(dp2[i][j].second>i+k-1){
                t=dp2[i][j].first-dp2[i+k-1][j].first;
                if(s[i+k-1][j]=='.') ++t;
                ans=min(ans,t);
            }
        }
    }
    if(ans==INT_MAX) ans=-1;
    cout<<ans<<endl;
}
signed main() {
    int tc=1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

}
return 0;

}

can we solve $$$G$$$ with centroid decomposition with eular tour ? (I tried but second sample failed :/)

PS: after seeing some peeps I got an ac with similar approach submission

It's easy.

Hi can any explain this problem in E n=5 s="101" I am getting ans 6 but how it is possible and Atcoder giving AC solution

if(s=="111") ans=8 i don't know why this is correct because bottle number 5 only

output n=5 why this distribution is not wrong , if s="111" every friend is ill but in distribution no any such bottle is common in all 3 2 2 4 2 3 4 1 5 8

Please give some insight ???