We will hold Toyota Programming Contest 2024#1(AtCoder Beginner Contest 337).
- Contest URL: https://atcoder.jp/contests/abc337
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240120T2100&p1=248
- Duration: 100 minutes
- Writer: leaf1415, MMNMM, ynymxiaolongbao, kyopro_friends, evima
- Tester: cn449, physics0523
- Rated range: ~ 1999
- The point values: 100-200-300-400-425-550-600
We are looking forward to your participation!
Hopefully no googleable problems this time
Me too.
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!
Me too.
So do I.
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??
you can only ask once and then you need to print the answer
How to solve $$$E$$$?
Hint: Hamming codes
For each bit $$$i$$$ take $$$S_i$$$ to be set of all indices with the bit equal to $$$1$$$. (assuming zero-indexed)
For example n= 8, m is 3:
Submission
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
It's actually a pretty well-known brain teaser problem afaik: Link1, Link2
If it was original I bet lot less submissions would have happent , doesn't matter learnt something new
I kept getting WA on F. My idea was like :
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
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
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
Balls in one color can be in different boxes. Think of this:
You can always fill two boxes with the balls. The answer should be 4.
Yup. This is the case. Thanks
How can I do problem E?I got a WA:
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.
Thanks!
I lost 425 points:(
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:
But now the state
00000
is wasted. We can save it by constructing:Here, the state
0000
just means00001
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.
Just do
ceil(log2(n))
, you won't trigger precision problems at such a small $$$N$$$.Thanks for pointing this out, got WA because of this
How to solve G?
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
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.
How to solve D?
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 :)
You can consider dp. this is my dp solution.
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 anx
it is automatically out of competition for the smallest cost. Ano
costs nothing and a.
costs $$$1$$$. Then, use prefix sum to calculate the cost for the window.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.
ABCABC
should return no, but your code returns yes.Oh, I know my mistake. I though it should return yes. tq
Problem B can be solved by sort the original string and check the string obtained by sort whether is equal to the original string.
just check if string is sorted or not. Realised it after 2 WA.
Code: https://atcoder.jp/contests/abc337/submissions/49454288
I don't know STL has such a API called is_sorted before. Thanks!
You can also use the regular expression
/^A*B*C*$/
How to optimize sack + lazy segtree in G ? I thought $$$\mathcal{O}(n \log{n})$$$ would easily pass.
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?
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
Thank you!
Do you mind to explain how's your approach and why euler tour + segment tree can solve this problem?
I'm glad to. Here is the explanation.
Find a way to calculate the contribution to each $$$f(u)$$$.
For each node $$$u$$$ and it's son $$$v$$$, the path $$$x\to u\to w$$$, where $$$x<u$$$ is inside the subtree of $$$v$$$ and $$$w$$$ is outside the subtree of $$$v$$$, contributes to $$$f(w)$$$.
Also, the path $$$x\to u\to w$$$, where $$$x<u$$$ is outside the subtree of $$$u$$$ and $$$w$$$ is inside the subtree of $$$u$$$, contributes to $$$f(w)$$$.
If we have known how many nodes $$$v$$$ are there in the subtree of node $$$u$$$ such that $$$v<u$$$, for each $$$u\in[n]$$$, then it's all about doing updates on a series of subtrees, which becomes a sequence update problem on the Euler tour.
To calculate how many nodes $$$v$$$ are there in the subtree of node $$$u$$$ such that $$$v<u$$$, I can provide you some methods.
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?)
How did you use centroid decomposition for this problem, I could not figure it out ?
please help on to solve the E
Problems similar to E have appeared in brain teasers before. Click this for reference.
Problem E was Educative. Learned something new.
Can you explain please.
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 :(
Because we need to know the result on the very next day.Hope this helps.
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..?
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.
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.
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.
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.
@chokudai
@maroonrk Bless for help!!!
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?
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 .
you can just define the next array to print next peorle
why the below code of problem D is giving some wrong answers?( I got 61 cases passed and 6 cases wrong)
}
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 ???