atcoder_official's blog

Toyota Programming Contest 2024#1（AtCoder Beginner Contest 337） Announcement
By atcoder_official, history, 2 years 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

Comments Comments (54)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it -64 Vote: I do not like it

Hopefully no googleable problems this time

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hope I can make ABCDE!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Yet another TOYOTA Round. Excited.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope to make ABCDEF

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hoping to get positive delta!

→ Reply
»
2 years ago, hide # |
 
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??

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve $$$E$$$?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
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

→ Reply
»
2 years ago, hide # |
 
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

→ Reply
»
2 years ago, hide # |
 
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;
}
→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve G?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
    ← 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

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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.

    → Reply
»
2 years ago, hide # |
 
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.

→ Reply
»
2 years ago, hide # |
← 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;
}
→ Reply
»
2 years ago, hide # |
 
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.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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?

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
      ← 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 \lt 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

      → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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?

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        I'm glad to. Here is the explanation.

        hint
        solution
        → Reply
»
2 years ago, hide # |
 
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.

→ Reply
»
2 years ago, hide # |
 
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?)

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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 ?

    → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

please help on to solve the E

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Problem E was Educative. Learned something new.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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 :(

    → Reply
»
2 years ago, hide # |
 
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.

→ Reply
»
2 years ago, hide # |
 
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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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 .

    → Reply
»
2 years ago, hide # |
← 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

→ Reply