atcoder_official's blog

By atcoder_official, history, 10 months ago, In English

We will hold Toyota Programming Contest 2024#1(AtCoder Beginner Contest 337).

We are looking forward to your participation!

  • Vote: I like it
  • +59
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it -64 Vote: I do not like it

Hopefully no googleable problems this time

»
10 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I can make ABCDE!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yet another TOYOTA Round. Excited.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to make ABCDEF

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to get positive delta!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the problem with my solution for Problem E

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can only ask once and then you need to print the answer

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve $$$E$$$?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hint: Hamming codes

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For each bit $$$i$$$ take $$$S_i$$$ to be set of all indices with the bit equal to $$$1$$$. (assuming zero-indexed)

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler

    Submission

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    It's actually a pretty well-known brain teaser problem afaik: Link1, Link2

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      If it was original I bet lot less submissions would have happent , doesn't matter learnt something new

»
10 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    Oh I think I know my mistake. I haven't take into account that a ball with the same color can belong to different boxes when the maximum capacity of the box has been reached

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Balls in one color can be in different boxes. Think of this:

    7 2 2
    1 1 1 1 1 1 1
    

    You can always fill two boxes with the balls. The answer should be 4.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Delete the 20th line of your code. There shouldn't be a newline as you've printed it in the 18th line of your code.

»
10 months ago, # |
Rev. 5   Vote: I like it -11 Vote: I do not like it

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.

AC Code in C++
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Just do ceil(log2(n)), you won't trigger precision problems at such a small $$$N$$$.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for pointing this out, got WA because of this

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Root the tree arbitrarily and for each node x calculate how many elements are lesser than x and parent[x] in the subtree of x. (I did this using small to large merging with ordered set)

    Now we can do rerooting and keep calculating these values for all the other nodes in another dfs, F(i) will be sum of all the elements smaller than x in the subtree of x, for all nodes x in the subtree.

    Code

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are two types of pair for a node $$$v$$$, one is those the first node is $$$v$$$, and the other is those the first node is not $$$v$$$. We note the number of these two types of pair respectively by $$$ans_2(v)$$$ and $$$ans_3(v)$$$.

    Now we can use DP on tree. Suppose $$$u$$$ is the parent of $$$v$$$, and we already knew its answer $$$dp[u]$$$. Due to that $$$u$$$ and $$$v$$$ are adjacent, any type-3 pairs of $$$u$$$ must be a type-3/type-2 pair of $$$v$$$. Then we only need to consider the type-2 pairs of $$$u$$$. If one of them has a node in the subtree of $$$v$$$, then it can't be any type of pair for $$$v$$$, otherwise it should also be a type-3 pair for $$$u$$$. So we must exclude the nodes in the subtree of $$$v$$$ that are smaller than $$$u$$$. We refer to the number of them by $$$F$$$.

    And are there anything left? Yes. The type-2 pairs of $$$v$$$ might have one element in other subtrees than the one headed by $$$v$$$. These pairs don't match any type for $$$u$$$ and we need to add them into our total number for $$$v$$$. We refer to the number of them by $$$G$$$.

    Finally, we got our equation $$$dp[v]=dp[u]-F[v]+G[v]$$$. But how to compute the $$$F$$$ and $$$G$$$ within the time limit? We use a technique called "sack" (or "dsu on tree") to reduce the time complexity. For more info about it, you can refer to the post that segment_tea mentioned.

    I learned the solution from this submission.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sliding Window and prefix sum!!. Assume it as a 2-D matrix. Now slide a K-length sliding window through each row as well as each column, and greedily calculate the minimum no of '.' required to convert to 'o' to get a continuous K-length subarray of 'o' only. Use prefix sum to calculate the number of '.' and 'o' present in each K-length window.

    Once you compute the minimum for each K-length window, then greedily take the minimum of that. Hope that helps :)

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can consider dp. this is my dp solution.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to maintain the cost in a sliding window, as your window cannot pass through x, you can set its cost as a sufficiently large number ($$$10^6$$$ for example), so when your window contains an x it is automatically out of competition for the smallest cost. An o costs nothing and a . costs $$$1$$$. Then, use prefix sum to calculate the cost for the window.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
10 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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;
}
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used segtree merge, which is $$$O(n\log n)$$$, see https://atcoder.jp/contests/abc337/submissions/49506487
    btw, can you explain what is "sack + lazy segtree" please?

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      Thanks for another kind of solution.

      Ah, ignore that lazy part, I'm just dumb. For the sack part, I'm using it to calculate how many nodes $$$v$$$ are there in the subtree of node $$$u$$$ such that $$$v < u$$$. And then, I am doing some math in range $$$(\text{tin}_u, \text{tout}_u)$$$. After the math, I can use sweepline algorithm to calculate net values.

      Accepted now, https://atcoder.jp/contests/abc337/submissions/49516509

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Do you mind to explain how's your approach and why euler tour + segment tree can solve this problem?

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I'm glad to. Here is the explanation.

        hint
        solution
»
10 months ago, # |
  Vote: I like it +86 Vote: I do not like it

G is same as TTPC2019 M.

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

»
10 months ago, # |
  Vote: I like it +36 Vote: I do not like it

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?)

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you use centroid decomposition for this problem, I could not figure it out ?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please help on to solve the E

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problems similar to E have appeared in brain teasers before. Click this for reference.

»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem E was Educative. Learned something new.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain please.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hii I have a doubt in problem E. It is asked that the minimum number of friends needed to predict the poisonous juice, so why can't I just take a single friend and make him drink N times ( N different juices).

    P.S — Sorry for this lame doubt, I might have misunderstood the question :(

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because we need to know the result on the very next day.Hope this helps.

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So which set of distribution can guarantee me the answer on the very next day, if suppose there are N drinks and there are k friends..?

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So you're telling me that only one query is enough for us to know the infected juice, if have the correct distribution of juices.

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          We will distribute juices among friends in such a way that all the upset friends have exactly 1 juice in common and the friends should be minimum in number.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's what I thought at first,then i just ac two point.But I found that there seemed to be only one juice to be found.That's why I have to pick a lot of friends at a time.

»
10 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use dfs and just print from the starting node which is v[i]==-1 and call dfs(v[i]) and print resulting path .

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can just define the next array to print next peorle

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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;

}

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's easy.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ???